-
Notifications
You must be signed in to change notification settings - Fork 1
/
techniek_cluster_analyse.html
1701 lines (1645 loc) · 63 KB
/
techniek_cluster_analyse.html
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
897
898
899
900
901
902
903
904
905
906
907
908
909
910
911
912
913
914
915
916
917
918
919
920
921
922
923
924
925
926
927
928
929
930
931
932
933
934
935
936
937
938
939
940
941
942
943
944
945
946
947
948
949
950
951
952
953
954
955
956
957
958
959
960
961
962
963
964
965
966
967
968
969
970
971
972
973
974
975
976
977
978
979
980
981
982
983
984
985
986
987
988
989
990
991
992
993
994
995
996
997
998
999
1000
<!DOCTYPE html>
<html>
<head>
<meta http-equiv="Content-Type" content="text/html; charset=UTF-8" />
<link href="css/normalize.css" rel="stylesheet">
<link href="css/ai.css" rel="stylesheet" type="text/css" />
<link href="css/menus.css" rel="stylesheet" type="text/css" />
<link href="css/treeview.css" rel="stylesheet" type="text/css" />
<title>Kunstmatige Intelligentie</title>
<script src="utils.js"></script>
<script src="treeview.js"></script>
<script type="text/javascript" src="https://cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.1/MathJax.js?config=TeX-AMS-MML_HTMLorMML"></script>
<script type="text/x-mathjax-config">
MathJax.Hub.Config({
tex2jax: { inlineMath: [['$','$'],['\\(','\\)']] }
});
</script>
<script src="ai.js" language="JavaScript" type="text/javascript"></script>
<script>
function run(id)
{
var k =Number(document.getElementById('K').value);
var O = eval(document.getElementById('O').value);
var M = eval(document.getElementById('M').value);
var res="";
var foutje = false;
var obj = document.getElementById(id);
if( O == undefined ){
res+="Geen objecten gegeven<br/>";
foutje = true;
}
if( M == undefined || M==null ) M=null;
else if( M.length!=k )
{
res+="Aantal centra moet gelijk zijn aan het aantal gewenste clusters"+k+"<br/>";
foutje = true;
}
if( !foutje )
{
res="Oplossing:"+kMeansSteps(O,k,C=null,M,4);
}
obj.innerHTML=res;
MathJax.Hub.Queue(["Typeset",MathJax.Hub,obj]);
}
</script>
</head>
<body id="technieken" onload="initTreeview()" >
<a name="Inleiding" style="counter-reset: subsection 3;"></a>
<header class="paragraaf titel">Clusteranalyse</header>
<section>
<h4 class="pad" id="path_lead"><a href="index.htm" target="_parent">Kunstmatige Intelligentie</a>/<a href="inleiding_technieken.html" target="_parent">Technieken</a>/Clusteranalyse</h4>
<div style="height: 100px;">
<div style="float:right;">
<a rel="license" href="https://creativecommons.org/licenses/by-nc-sa/4.0/">
<img alt="Creative Commons License" style="border-width:0" src="https://i.creativecommons.org/l/by-nc-sa/4.0/88x31.png" /></a>
<br />This work is licensed under a
<br />
<a rel="license" href="https://creativecommons.org/licenses/by-nc-sa/4.0/">Creative Commons Attribution-NonCommercial-ShareAlike
4.0
<br />International License</a>.
</div>
<a name="Inleiding"></a> bron:<a href="../Informatie/Big Data studenten OCE/Lesmodule Big Data.pdf">Lesmodule Big Data</a>
</div>
</section>
<article>
<div class="navbar">
<div class="centreer">
<a href="#Inleiding">Inleiding</a>
<a href="#Toepassingen">Toepassingen</a>
<span class="dropdown">
<div class="dropbtn" onclick="window.location='#begrippen'">Begrippen ▼</div>
<div class="dropdown-content">
<a class="submenuitem" href="#afstand">Afstandsmaten</a>
<a class="submenuitem" href="#matrix">Afstandsmatrix</a>
<a class="submenuitem" href="#clusterafstand">Clusterafstand</a>
</div>
</span>
<span class="dropdown">
<div class="dropbtn" onclick="window.location='#methoden'">Methoden ▼</div>
<div class="dropdown-content">
<a class="submenuitem" href="#methode">k-means methode</a>
<a class="submenuitem" href="#andere">andere methoden</a>
</div>
</span>
<span class="dropdown">
<div class="dropbtn">Vragen ▼</div>
<div class="dropdown-content">
<a class="submenuitem" href="#vragen">vragen k-means</a>
<a class="submenuitem" href="#vragen2">vragen andere methoden</a>
</div>
</span>
</div>
</div>
<button class="doel" onclick="toon('leerdoelen')">Leerdoelen</button>
<div class="popup" id="leerdoelen" onclick="verberg(this);">
<h3>Leerdoelen</h3>
Na dit hoofdstuk:
<ul>
<li>weet je het doel en de taak van clusteranalyse bij datamining.
</li>
<li>kun je een paar toepassingen van clustering noemen.
</li>
<li>kun je de begrippen datapunt, object, cluster, centrum, centroide, Euclidische afstand, Manhattan afstand en centrum uitleggen.
</li>
<li>kun je de afstand tussen zowel twee objecten als twee clusters met behulp van afstandsmaten zoals Euclidische afstand en Manhattan afstand berekenen.
</li>
<li>kun je het centrum of de centroide van een cluster bepalen.
</li>
<li>ben je in staat de $K$-means methode op passende problemen toepassen
</li>
<li>weet je dat er ook nog andere clustermethoden zijn.
</li>
<li>ben je je bewust van de problemen die bij clustering op kunnen treden
</li>
</ul>
</div>
<h2 class='paragraaf'><a name="Inleiding">Inleiding</h2>
<div class="theorie example">Voorbeeld
<div style="padding-left:25px;">
<p>Stel er komt een aantal buitenlandse studenten binnen op de hogeschool waar jij als studiecoördinator werkt en jij moet er voor zorgen dat deze studenten worden bijgeschoold in Engels voordat zij mogen beginnen met de rest van de opleiding.
</p>
<p>Er zijn twee docenten beschikbaar en je wilt de studenten indelen in twee groepen (een groep noemen we in het vervolg een <strong>cluster</strong>), groep A en groep B. Bij de indeling wil je clusters maken van studenten van gelijk niveau. De grootte van de clusters is onbelangrijk.
</p>
<p>Je wilt indelen op de twee eigenschappen lezen en verstaan van Engels. Je laat daarom alle studenten een test maken waaruit een score van 1 tot 10 komt. Daarbij geef je alleen gehele punten als cijfer.
</p>
<p>Om inzicht te krijgen hoe je de clusters kunt indelen zet je de studenten in een schema waarbij de horizontale as het cijfer voor lezen aangeeft en de verticale as het cijfer voor verstaan. In het onderstaande schema zijn de resultaten van de vijf studenten s1 t/m s5 weergegeven.
</p>
<div class="midden theorie">
<img src="images/vbCluster1.png" style="width: 600px;"/>
</div>
<div class="caret doel">Welke clusters zou jij maken?</div>
<div class="nested">
<div class="midden theorie">
<img src="images/vbCluster2.png" style="width: 600px;"/><br/>
De meest logische indeling is om s1 en s4 in groep A te stoppen en s2,s3 en s5 in groep B.
</div>
</div>
<p>
</p>
</div>
</div>
<p>In het voorbeeld was het niet zo moeilijk om te bepalen welke clusters je het best kon maken. Maar wat nu als er veel meer studenten zijn en/of veel meer eigenschappen zijn waar je rekening mee wilt houden?
</p>
<p><strong>Clusteranalyse</strong> is het classificeren of het groeperen in 'clusters' of 'klassen' van objecten op grond van hun kenmerken zonder vooraf de clusters vast te leggen. De gebruikte algoritmen bepalen wel de weg om tot clusters te komen, maar de gegevens bepalen welke clusters het worden. Deze algoritmen zijn, net als de algoritmen uit de associatie analyse, vormen van <strong>unsupervised learning</strong> (= ongestuurd leren). Het belangrijkste AI-kenmerk is ook hier: <strong>de invoer die het programma krijgt, is niet volledig te bepalen en is complex.
</strong>
</p>
<div class ='hammer treeview' style="clear: both;">Vraag
<div style="padding-left:25px;">
<ol>
<li>Wat zijn in het voorbeeld de objecten en de kenmerken?
<div class="caret doel">antwoord</div>
<ul class="nested">
<li>De objecten zijn de studenten, de kenmerken de resultaten voor lezen en verstaan.
</li>
</ul>
</li>
</ol>
</div>
</div>
<div class="theorie rechts">
<img src="images/classObj.png"/><br/>
<caption>Figuur 1: Het classificeren<br/>van objecten</caption><br/>
</div>
<p>
Het doel van clusteranalyse (<strong>trainingsfase</strong>) is het vormen van deelverzamelingen (clusters of groepen) die elk hun eigen gedeelde kenmerken bevatten. De clusters en liefst ook het aantal clusters zijn vooraf niet bekend. Het streven is zoveel mogelijk gelijkenis binnen een groep en zoveel mogelijk verschil tussen de groepen te krijgen.
</p>
<p>
Is de clusteranalyse uitgevoerd dan kan de collectie (=<strong>verzameling</strong> ) van deelverzamelingen worden gebruikt om een nieuw object te classificeren. Bij classificatie achteraf van een nieuw object liggen de eigenschappen van een groep dus al vast. Dit dus in tegenstelling tot de trainingsfase.
</p>
<div class ='hammer treeview' style="overflow: hidden;">Vraag
<div style="padding-left:25px;">
<ol start="2">
<li>Er meldt zich weer een nieuwe buitenlandse student bij de hogeschool, een week na de start van de bijscholing. Deze student haalt een 4 voor lezen en een 3 voor verstaan. In welke groep wordt deze student geplaatst?
<div class="caret doel">antwoord</div>
<ul class="nested">
<li>Deze leerling past het best in groep A.
</li>
</ul>
</li>
</ol>
</div>
</div>
<p>
Voor we één algoritme ($K$-means-clustering) meer in detail uitwerken en jullie laten kennismaken met alternatieven geven we eerst een aantal voorbeelden van terreinen waarin clusteranalyse wordt toegepast. Meer voorbeelden zijn onder andere <a href="https://datafloq.com/read/7-innovative-uses-of-clustering-algorithms/6224" target="uitleg">hier</a> en <a href="https://www.analytixlabs.co.in/blog/types-of-clustering-algorithms/#sub4" target="uitleg">hier</a> te vinden.
</p>
<a id="Toepassingen"></a><br/>
<h2>Toepassingen</h2>
<p>
<dl>
<dt>Identificatie van nepnieuws</dt>
<dd><p>Nepnieuws is geen nieuw fenomeen, maar het treedt meer en meer op de voorgrond vooral binnen sociale media. Zelfs president Trump schaamde zich niet om zijn campagne met nepnieuws te voeren of ander onwelgevallige berichten tot nepnieuws te bombarderen.
</p>
<p>In een <a href="http://snap.stanford.edu/mis2/files/MIS2_paper_2.pdf" target="uitleg">
artikel</a> gepubliceerd door twee informaticastudenten (Seyedmehdi Hosseinimotlagh en Evangelos E. Papalexakis, University of California, Riverside) wordt een clusteralgoritme gebruikt om nepnieuws te identificeren. Het algoritme krijgt (nep)nieuwsartikelen aangeboden. Uit deze artikelen worden de belangrijkste en meest sensatierijke woorden gevist. Op deze woorden wordt dan geclusterd. Omdat sensatie beluste woorden de aandacht van mensen trekt komen deze woorden vaker voor in nepnieuwsartikelen. De clusters bevatten dus combinaties van dit soort woorden waarmee nieuwe berichten geclassificeerd kunnen worden op mate van nepnieuws.
</dd>
<dt>Biologie
</dt>
<dd>In de biologie zijn er meerdere gebieden waar clusteranalyse wordt toegepast. Denk bijvoorbeeld aan de classificatie van verschillende organismen. Elk organisme hoort bij een soort. Soorten kunnen op hun beurt weer worden onderverdeeld in lagere taxa, zoals ondersoort en variëteit. Soorten zelf worden samengevoegd in geslachten en deze weer in families en in taxa van nog hogere rang. Een ander voorbeeld van het gebruiken clustertechnieken in de biologie is het maken van groepen met genen die een bepaalde erfelijke ziekte kunnen bevatten. Door het gebruik van clustermethoden kunnen groepen met samenwerkende genen gevonden worden. Als deze groepen bekend zijn, kan deze kennis helpen om meer gericht onderzoek te doen naar medicijnen die een erfelijke ziekte gekoppeld aan de groep genen kan voorkomen of genezen.
</dd>
<dt>Marketing
</dt>
<dd>
Personalisatie en bepaling van doelgroepen in marketing is big business. Dit wordt bereikt door naar specifieke kenmerken van een persoon te kijken en campagnes met hen te delen die succesvol zijn geweest met andere vergelijkbare mensen. Doet een bedrijf dat niet of verkeerd dan loopt het bedrijf de kans niets te verkopen of nog erger het vertrouwen van klanten te verliezen. Clusteranalyse helpt de doelgroepen te bepalen.
</dd>
</dl>
</p>
<a id="begrippen"></a><br/>
<h2>Begrippen</h2>
<p>We gaan straks $K$-means-clustering als algoritme presenteren. Het voorbeeld van de studenten aan het begin van het hoofdstuk past hierin. Daartoe moeten er eerst wat begrippen worden geïntroduceerd die in dit algoritme worden gebruikt. Deze begrippen spelen ook in andere clustermethoden een rol.
</p>
<a id="afstand"></a><br/>
<h3>Afstandsmaten</h3>
<p>
In clustering speelt afstand tussen gegevens een grote rol. Een computer heeft daar meestal getallen voor nodig. Vaak moet er eerst een bewerking van gegevens plaatsvinden om deze om te zetten in getallen. Combinatie van verschillende eigenschappen leveren dan datapunten op in een assenstelsel (iedere eigenschap zijn eigen as, b.v. leeftijd, sociale klasse, salaris ).
</p>
<div class ='hammer treeview' style="overflow: hidden;">Vraag
<div style="padding-left:25px;">
<ol start="3">
<li>Welke assen zijn er in het hogeschool voorbeeld?
<div class="caret doel">antwoord</div>
<ul class="nested">
<li>Er is een as voor verstaan en een as voor lezen.
</li>
</ul>
</li>
</ol>
</div>
</div>
<h4>Afstand tussen datapunten (objecten):</h4>
<div class="theorie example">Vervolg voorbeeld
<div style="padding-left:25px;">
De weergave voor studenten in een schema is niet handig om afstanden te meten. Het is beter deze te plaatsen in een assenstelsel zoals je dat in de wiskunde doet.
<div class="theorie midden">
<img src="images/clust_analyse.svg" style="width: 300px;"/><br/>
</div>
</div>
</div>
<br/>
<div class="theorie rechts clearfix">
<img src="images/Pythagoras.png" width="200"/><br/>
<caption>Figuur 2: De stelling van Pythagoras</caption><br/><br/>
<img src="images/Manhattan.png" width="200"/><br/>
<caption>Figuur 3: Stukje Manhattan,<br/>Je kunt alleen over de weg.</caption><br/>
</div>
<p>Hebben we datapunten zoals hierboven dan kunnen we wiskundig de afstand tussen punten uitrekenen. Je hebt waarschijnlijk de vorige vraag beantwoord met de stelling van Pythagoras. De stelling van Pythagoras (Figuur 2) is de manier om de afstand van de schuine zijde in een tweedimensionale rechthoekige driehoek te berekenen. In een assenstelsel vormen de verplaatsingen langs de assen de rechthoekzijden en de lengte van schuine zijde de kortste afstand tussen de punten. Deze afstand noemt men ook wel de <strong>Euclidische</strong> afstand. In drie dimensies en hoger wordt op een zelfde manier de afstand tussen twee punten berekend.
</p>
<div class="theorie important" style="overflow: hidden"><strong>Definitie: Euclidische afstand</strong>
<div style="padding-left:25px;">
De <i>Euclidische afstand</i>
tussen twee punten $A=(a_{1},a_{2},\dots , a_{n-1}, a_{n})$ en
$B=(b_{1},b_{2},\dots , b_{n-1}, b_{n})$ is:<br/>
$$\begin{array}{rcl}d(A,B)& = &\sqrt{\sum_{i=1}^{n}(a_{i}-b_{i})^{2} }\\
& = &\sqrt{(a_{1}-b_{1})^{2}+ (a_{2}-b_{2})^{2}+ \dots + (a_{n}-b_{n})^{2}}\end{array}$$
Twee dimensionale Euclidische afstand: $d(A,B)=\sqrt{(a_{1}-b_{1})^{2}+ (a_{2}-b_{2})^{2}}$
</div>
</div>
<p>
Naast de Euclidische afstand is er een andere maat die vaak gebruikt wordt,
de <strong>Manhattan of City-block afstand</strong>. In figuur 3 zie je een stukje van de kaart van Manhattan. Je kunt alleen van hoek naar hoek
komen als je door de straten gaat. In een rooster dus alleen evenwijdig aan de assen.
</p>
<div class="theorie important" style="overflow: hidden"><strong>Definitie: Manhattan of City-block afstand</strong>
<div style="padding-left:25px;">
De <i> Manhattan of City-block afstand</i>
tussen twee punten $A=(a_{1},a_{2},\dots , a_{n-1}, a_{n})$ en
$B=(b_{1},b_{2},\dots , b_{n-1}, b_{n})$ is:<br/>
$$\begin{array}{rcl}d(A,B)& = &\sum_{i=1}^{n} |a_{i}-b_{i}|\\
& = &|a_{1}-b_{1}|+ |a_{2}-b_{2}|+ \dots + |a_{n}-b_{n}|\end{array}$$
Hierin is $|x|$ de absolute waarde van $x$, $|2|=2$ maar ook $|-2|=2$
</div>
</div>
<p>
<div class="theorie example" style="overflow: hidden">
Voorbeeld A
<div style="padding-left:25px;">
Bereken de Manhattan afstand en de Euclidische afstand tussen de volgende objecten in een 5 dimensionale ruimte:
<table>
<tr>
<td>Object $A$</td>
<td>
10</td>
<td>
12</td>
<td>
15</td>
<td>
13</td>
<td>
9</td>
</tr>
<tr>
<td>
Object $B$</td>
<td>
18</td>
<td>
23</td>
<td>
13</td>
<td>
15</td>
<td>
17</td>
</tr>
</table>
<hr/>
<p>Om de Manhattan of City-block afstand te bereken moeten we evenwijdig aan de assen lopen langs de eerste as gaan we van 10 naar 18 ofwel afstand 8, dan van 12 naar 23 ofwel 11, etc. Een afstand moet altijd positief zijn, 10-18 en 18-10 moeten beide antwoord 8 geven. Dat doe je door de absolute waarde te nemen van het verschil<br/>
$ |10-18|=|18-10|=8$.<br/>
Min wordt plus en plus blijft plus.
<p>De Manhattan of City-block afstand van object $A$ tot object $B$ is dan:<br/>
$d(A,B)= |10−18|+|12−23|+|15−13|+|13−15|+|9−17|=31$</p>
</p>
<hr/>
<p>De Euclidische bereken door al de afstanden langs de assen te kwadrateren, deze kwadraten op te tellen en vervolgens de wortel te trekken van het totaal:<br/>$d(A,B)=\sqrt{(10−18)^{2}+(12−23)^{2}+(15−13)^{2}+(13−15)^{2}+(9−17)^{2}} =16,16$
</p>
</div>
</div>
<p class="pagebreak"></p>
<a id="matrix"></a><br/>
<h3>Afstandsmatrix</h3>
<p>
Een matrix van afstanden is een matrix waarvan de elementen de afstanden tussen de punten aangeven.</p>
<div class="theorie treeview example" style="overflow: hidden">
Voorbeeld B
<div style="padding-left:27px;">
Gegeven een dataset met vier objecten.
<table>
<tr>
<td></td><th>x</th><th>y</th>
</tr>
<tr>
<th>A</th><td>2</td><td>1</td>
</tr>
<tr>
<th>B</th><td>4</td><td>2</td>
</tr>
<tr>
<th>C</th><td>6</td><td>1</td>
</tr>
<tr>
<th>D</th><td>7</td><td>2</td>
</tr>
</table>
Laat zien dat de afstand van A naar D $5.10$ is.
<br/>Geef de gehele afstandsmatrix.
<div class="caret doel">uitwerking</div>
<div class="nested">
$d(A,B)=\sqrt{(7-2)^{2}+(2-1)^{2}}=\sqrt{26}=5.10$
<hr/>
Gebruiken we de gewone Euclidische afstand dan<br/>
ziet de afstandsmatrix er als volgt uit:
<table>
<tr>
<td></td><th>A</th><th>B</th><th>C</th><th>D</th>
</tr>
<tr>
<th>A</th><td>0</td><td>2.24</td><td>4</td><td>5.1</td>
</tr>
<tr>
<th>B</th><td>2.24</td><td>0</td><td>2.24</td><td>3</td>
</tr>
<tr>
<th>C</th><td>4</td><td>2.24</td><td>0</td><td>1.41</td>
</tr>
<tr>
<th>D</th><td>5.1</td><td>3</td><td>1.41</td><td>0</td>
</tr>
</table>
</div>
</div>
</div>
<a id="clusterafstand"></a><br/>
<h3>Afstand tussen clusters</h3>
<p>Als je de afstand tussen elk paar van objecten weet, wat is dan de
afstand tussen twee clusters $C_{1}$ en $C_{2}$?<br>
We nemen hier de kleinste afstand tussen twee objecten waarvan er één
in $C_{1}$ aanwezig is en de andere in $C_{2}$. Deze afstand noemt men
<strong>Single Linkage</strong>.
</p>
<div class="theorie important" style="overflow: hidden">
<strong>Definitie: Single Linkage</strong>
<div style="padding-left:25px;">
Single Linkage: $d(C_{1},C_{2})=\min\{d(A,B)|A \in C_{1}\,\,en\,\, B \in C_{2} \}$
</div>
</div>
<br/>
<div class="theorie treeview example" style="overflow: hidden">
Voorbeeld C
<div style="padding-left:27px;">
Gegeven een dataset met zes punten.
<table>
<tr>
<td></td><th>x</th><th>y</th>
</tr>
<tr>
<th>$A_{1}$</th><td>1</td><td>3</td>
</tr>
<tr>
<th>$A_{2}$</th><td>1</td><td>4</td>
</tr>
<tr>
<th>$A_{3}$</th><td>2</td><td>2</td>
</tr>
<tr>
<th>$B_{1}$</th><td>5</td><td>1</td>
</tr>
<tr>
<th>$B_{2}$</th><td>5</td><td>2</td>
</tr>
<tr>
<th>$B_{3}$</th><td>7</td><td>2</td>
</tr>
</table>
De clusters zijn $C_{1}=\{A_{1},A_{2},A_{3}\}$ en $C_{2}=\{B_{1},B_{2},B_{3}\}$<br/>
Geef de kleinste afstand tussen $C_{1}$ en $C_{2}$
<div class="caret doel">uitwerking</div>
<div class="nested">
De afstandsmatrix tussen de objecten in $C_{1}$ en $C_{2}$ is:
<table>
<tr>
<td></td><th>$B_{1}$</th><th style="background-color: green">$B_{2}$</th><th>$B_{3}$</th>
</tr>
<tr>
<th>$A_{1}$</th><td>4.47</td><td>4.12</td><td>6.03</td>
</tr>
<tr>
<th>$A_{2}$</th><td>5</td><td>4.47</td><td>6.32</td>
</tr>
<tr>
<th style="background-color: green">$A_{3}$</th><td>3.16</td><td style="background-color: green">3</td><td>5</td>
</tr>
</table>
Geef de kleinste afstand tussen $C_{1}$ en $C_{2}$ is
de kleinste afstand in de matrix:<br/>
$d(C_{1},C_{2})=\min\{d(A,B)|A \in C_{1}\,\,en\,\, B \in C_{2} \}$<br/>
$d(A_{3},B_{2})=\sqrt{(5-2)^{2}+(2-2)^2}=3$.
</div>
</div>
</div>
<a id="centrum"></a><br/>
<h3>Centrum cluster</h3>
<p>Als we straks na de training clusters hebben gevormd en willen bepalen in welk cluster een nieuw object moet worden geplaatst is het heel efficiënt om een cluster op een bepaalde manier samen te vatten. Het centrum $M(m_{1},m_{2}, \dots, m_{n})$ van een cluster is een samenvatting die we straks gaan gebruiken. Het centrum is een punt $M$ met coördinaten. Het centrum wordt bepaald als het gemiddelde van de coördinaten van de punten in de cluster. Wiskundig gezien is het het zwaartepunt van de veelhoek ( een lichaam in hogere dimensie) die door de punten wordt gevormd.
</p>
<div class="theorie example" style="overflow: hidden">
<strong>Definitie: Cluster centrum</strong>
<div style="padding-left:25px;">Centrum $M$ van een cluster:<br/>
$M(m_{1},m_{2}, \dots, m_{n})= \left( \frac{\sum^{1}_{n} a_{1i}}{n},\frac{\sum^{1}_{n} a_{2i}}{n}, \dots, \frac{\sum^{1}_{n} a_{ni}}{n}\right)$.
</div>
</div>
<br/>
<div class="theorie treeview example" style="overflow: hidden">
Voorbeeld D
<div style="padding-left:27px;">
Gegeven een cluster $C$ die de volgende objecten bevat:
<table>
<tr>
<td></td><th>x</th><th>y</th>
</tr>
<tr>
<th>$A_{1}$</th><td>0</td><td>0</td>
</tr>
<tr>
<th>$A_{2}$</th><td>7</td><td>8</td>
</tr>
<tr>
<th>$A_{3}$</th><td>4</td><td>8</td>
</tr>
<tr>
<th>$A_{4}$</th><td>3</td><td>0</td>
</tr>
</table>
Bereken het centrum van de cluster $C=\{A_{1},A_{2},A_{3},A_{4}\}$.
<div class="caret doel">uitwerking</div>
<div class="nested">
Het centrum komt uit de volgende berekening:
$$M(m_{1},m_{2})= \left( \frac{\sum_{i=1}^{4} x_{i}}{4},\frac{\sum_{i=1}^{4} y_{i}}{4}\right)$$
Dat ziet er lastig uit maar $m_{1}$ is niets anders dan het gemiddelde van de $x$-coördinaten en $m_{2}$ is niets anders dan het gemiddelde van de $y$-coördinaten:
$$M= \left( \frac{0 + 7 + 4 +3 }{4},\frac{0+8+8+0}{4}\right)=( 3\frac{1 }{2},4)$$
</div>
</div>
</div>
<p class="pagebreak"></p>
<a id="methoden"></a><br/>
<h2>Cluster methoden</h2>
<div class="links theorie" style="width: 250px;">
<img src="images/k_means_vid.gif" style="width: 250px;"><br/>
<caption>Figuur 4: Animatie van het $K$-means algoritme</caption>
</div>
<div class="rechts theorie">
<img src="images/K_Means.svg"/><br/>
<caption>Figuur 5: Het algoritme</caption>
</div>
<p>Zoals eerder vermeld zijn er verschillende methoden die binnen kunstmatige intelligentie
gebruikt worden om tot clusters te komen.
We beginnen hier met de <b>$K$-means-clustering</b> de meest eenvoudige
methode. Het onderliggende algoritme geeft inzicht in hoe
dergelijke methoden van de data leren om later input te kunnen
classificeren. Ook is gekozen voor deze methode omdat je met pen en papier
eenvoudig het algoritme na kan spelen.
</p>
<h3>$K$-means-clustering</h3>
<p>
Het oudste en meest bekende clusteralgoritme is de $K$-means methode. Later zijn er veel varianten ontwikkeld die gebaseerd zijn op deze methode. $K$-means is een eenvoudige en relatief snelle iteratieve manier van clusteren. Vooraf wordt bepaald hoeveel clusters ( b.v. 3) je wilt hebben. De clustering (training) op basis van de gegevens levert dan de clusters samengevat door de bijbehorende centra. In de figuur 4 hiernaast zie je een animatie van een clustering waarin de data stap voor stap in drie groepen wordt verdeeld. De kruisjes die je ziet bewegen zijn de centra van de clusters. In figuur 5 staat de flowchart van het algoritme dat we hieronder in meer detail beschouwen.
</p>
<p>
Om de optimale clustering te vinden ga je als volgt te werk:
</p>
<p>
<ol>
<li style="background-color: #ccffff">Start: Kies de centra van de clusters de eerste keer willekeurig en bepaal
het maximaal aantal stappen dat je toestaat.
</li>
<li style="background-color: #33cccc">Daarna bepaal je van elk datapunt de afstand tot ieder centrum, en wijs je ieder datapunt toe aan de cluster waarvan het centrum het dichtstbij is.</li>
<ul>
<li style="background-color: #e8eef7">Als er punten zijn die in de vorige stap van cluster zijn veranderd en je nog niet voorbij het vooraf
gekozen maximum aantal iteraties bent gekomen dan ga je naar stap 3. Anders ben je klaar.
</li>
</ul>
<li style="background-color: #ff99cc">Alle datapunten zitten weer in een cluster. Er zijn datapunten
die nu in een nadere cluster zitten. De centra zijn dan niet voor
alle clusters meer hetzelfde en moeten dus opnieuw worden berekend.Hiervoor gebruik je voor ieder
cluster apart de volgende formule:<br/>
$M(m_{1},m_{2}, \dots, m_{n})= \left( \frac{\sum^{1}_{n} a_{1i}}{n},\frac{\sum^{1}_{n} a_{2i}}{n}, \dots, \frac{\sum^{1}_{n} a_{ni}}{n}\right)$.<br/>
$n$ is dan het aantal elementen in één cluster.
<hr/>
Met die nieuwe centra veranderen ook weer de afstanden van de datapunten
tot die centra en moet je dus het hele proces vanaf stap 1 weer herhalen, ofwel start de volgende iteratie.
</li>
</ol>
Leuk zo'n verhaal maar voorbeelden maken het inzichtelijker.
</p>
<p class="pagebreak"></p>
<div class="theorie treeview example" style="overflow: hidden">
Voorbeeld E
<div style="padding-left:27px;">
Gegeven een cluster $C$ die de volgende objecten bevat:
<table>
<tr>
<td></td><th>x</th><th>y</th>
</tr>
<tr>
<th>$A_{1}$</th><td>2</td><td>2</td>
</tr>
<tr>
<th>$A_{2}$</th><td>4</td><td>2</td>
</tr>
<tr>
<th>$A_{3}$</th><td>6</td><td>1</td>
</tr>
<tr>
<th>$A_{4}$</th><td>8</td><td>2</td>
</tr>
</table>
We bepalen vooraf dat we twee clusters willen, dus $k=2$.<br/>Bepaal met het $K$-means algoritme een geschikte clustering.<br/>Als afstandsmaat gebruik je de normale (Euclidische) afstand.
<div class="caret doel">uitwerking</div>
<div class="nested">
<div class="rechts" style="display: inline-block; vertical-align: top;width: 30%;">
Start<br/>
<img src="images/VoorbeeldE1.png" width="300"/><br/>
Iteratie 1<br/>
<img src="images/VoorbeeldE2.png" width="300"/><br/>
</div>
<dl>
<dt>Start:</dt>
<dd>Kies twee willekeurig centra. $M_{1}=(4,4)$ en $M_{2}=(6,2)$
voor respectievelijk de clusters $C_{1}$ en $C_{2}$.
Dit geeft de figuur Start hiernaast.
</dd>
<dt>Iteratie 1:</dt>
<dd>
<ol>
<li>Bepaal de afstanden van de datapunten tot de centra en
plaats de datapunten in het juiste cluster.<br/>
De afstandsmatrix wordt:
<div style="color: seagreen">
<div class="caret doel">Klap dit uit voor een heel handige tip!</div>
<div class="nested">
Als je op een ruitjesblaadje de situatie hiernaast natekent, dan kun je de afstanden ook meten met een liniaal in plaats van iedere keer Pythagoras te moeten doen. Dat scheelt heel veel tijd. Het hoeft in deze voorbeelden en de opgaven er na echt niet heel precies.
</div>
</div>
</li>
<table>
<tr>
<td></td><th>$M_{1}$</th><th>$M_{2}$</th><th>toewijzing</th>
</tr>
<tr>
<th>$A_{1}$</th><td>2.83</td><td>4</td><td>$C_{1}$</td>
</tr>
<tr>
<th>$A_{2}$</th><td>2</td><td>2</td><td>$C_{1}$</td>
</tr>
<tr>
<th>$A_{3}$</th><td>3.61</td><td>1</td><td>$C_{2}$</td>
</tr>
<tr><tr>
<th>$A_{4}$</th><td>4.47</td><td>2</td><td>$C_{2}$</td>
</tr>
<tr>
</table>
</li>
<li>De nieuwe clusters zijn:
<table>
<tr>
<th>$C_{1}$</th><th>$\{A_{1},A_{2}\}$</th>
</tr>
<tr>
<th>$C_{2}$</th><th>$\{A_{3},A_{4}\}$</th>
</tr>
</table>
We moeten door naar stap 3
</li>
<li>
Bereken de nieuwe centra:<br/>
$M_{1}'=(\frac{4+2}{2},\frac{2+2}{2})=(3,2)$ en
$M_{2}'=(\frac{6+8}{2},\frac{1+2}{2})=(7,1.5)$ (zie figuur Iteratie 1)
</li>
</ol>
</dd>
<dt>Iteratie 2:</dt>
<dd>
<ol>
<li>Bepaal de afstanden van de datapunten tot de centra en
plaats de datapunten in het juiste cluster.<br/>De afstandsmatrix wordt:
<table>
<tr>
<td></td><th>$M_{1}'$</th><th>$M_{2}'$</th><th>toewijzing</th>
</tr>
<tr>
<th>$A_{1}$</th><td>1</td><td>5.02</td><td>$C_{1}$</td>
</tr>
<tr>
<th>$A_{2}$</th><td>1</td><td>3.04</td><td>$C_{1}$</td>
</tr>
<tr>
<th>$A_{3}$</th><td>3.16</td><td>1.12</td><td>$C_{2}$</td>
</tr>
<tr>
<th>$A_{4}$</th><td>5</td><td>1.12</td><td>$C_{2}$</td>
</tr>
</table>
</li>
<li>Alle datapunten zitten in de dezelfde cluster uit de vorige
iteratie. De clusters zijn niet veranderd er zijn dus ook geen nieuwe centra. We kunnen stoppen. Het doel is bereikt. De geschikte clustering is:
<table>
<tr>
<th>$C_{1}$</th><th>$\{A_{1},A_{2}\}$</th>
</tr>
<tr>
<th>$C_{2}$</th><th>$\{A_{3},A_{4}\}$</th>
</tr>
</table>
</li>
</ol>
</dd>
</dl>
</div>
</div>
</div>
<p class="pagebreak"></p>
<div class="theorie treeview example" style="overflow: hidden">
Voorbeeld F
<div style="padding-left:27px;">
Gegeven een cluster $C$ die de volgende objecten bevat:
<table>
<tr>
<td></td><th>x</th><th>y</th>
</tr>
<tr>
<th>$A_{1}$</th><td>0</td><td>1</td>
</tr>
<tr>
<th>$A_{2}$</th><td>3</td><td>1</td>
</tr>
<tr>
<th>$A_{3}$</th><td>3</td><td>2</td>
</tr>
<tr>
<th>$A_{4}$</th><td>0</td><td>3</td>
</tr>
<tr>
<th>$A_{5}$</th><td>4</td><td>1</td>
</tr>
</table>
We bepalen vooraf dat we twee clusters willen, dus $k=2$.<br/>Bepaal een juiste clustering.<br/>Als afstandsmaat gebruik je de normale (Euclidische) afstand.
<div class="caret doel">uitwerking</div>
<div class="nested">
<div class="rechts" style="display: inline-block; vertical-align: top;width: 30%;">
Start<br/>
<img src="images/VoorbeeldF1.png" width="200"/><br/>
Iteratie 1<br/>
<img src="images/VoorbeeldF2.png" width="200"/><br/>
Iteratie 2<br/>
<img src="images/VoorbeeldF3.png" width="200"/><br/>
</div>
<dl>
<dt>Start:</dt>
<dd>Kies twee willekeurig centra. $M_{1}=(2,2)$ en $M_{2}=(3,0)$</dd>
<dt>Iteratie 1:</dt>
<dd>
<ol>
<li>De afstandsmatrix wordt:
<table>
<tr>
<td></td><th>$M_{1}$</th><th>$M_{2}$</th><th>toewijzing</th>
</tr>
<tr>
<th>$A_{1}$</th><td>2.24</td><td>3.16</td><td>$C_{1}$</td>
</tr>
<tr>
<th>$A_{2}$</th><td>1.41</td><td>1</td><td>$C_{2}$</td>
</tr>
<tr>
<th>$A_{3}$</th><td>1</td><td>2</td><td>$C_{1}$</td>
</tr>
<tr>
<th>$A_{4}$</th><td>2.24</td><td>4.24</td><td>$C_{1}$</td>
</tr>
<tr>
<th>$A_{5}$</th><td>2.24</td><td>1.41</td><td>$C_{2}$</td>
</tr>
</table>
</li>
<li>De nieuwe clusters zijn:
<table>
<tr>
<th>$C_{1}$</th><th>$\{A_{1},A_{3},A_{4}\}$</th>
</tr>
<tr>
<th>$C_{2}$</th><th>$\{A_{2},A_{5}\}$</th>
</tr>
</table>
</li>
<li>De nieuwe centra zijn:
$M_{1}'=(\frac{0+3+0}{3},\frac{1+2+3}{3})=(1,2)$ en
$M_{2}'=(\frac{3+4}{2},\frac{1+1}{2})=(3.5,1)$
</li>
</ol>
</dd>
<dt>Iteratie 2:</dt>
<dd>
<ol>
<li>De afstandsmatrix wordt:
<table>
<tr>
<td></td><th>$M_{1}'$</th><th>$M_{2}'$</th><th>toewijzing</th>
</tr>
<tr>
<th>$A_{1}$</th><td>1.41</td><td>3.5</td><td>$C_{1}$</td>
</tr>
<tr>
<th>$A_{2}$</th><td>2.24</td><td>0.5</td><td>$C_{2}$</td>
</tr>
<tr>
<th>$A_{3}$</th><td>2</td><td>1.12</td><td>$C_{2}$</td>
</tr>
<tr>
<th>$A_{4}$</th><td>1.41</td><td>4.03</td><td>$C_{1}$</td>
</tr>
<tr>
<th>$A_{5}$</th><td>3.16</td><td>0.5</td><td>$C_{2}$</td>
</tr>
</table>
</li>
<li>De nieuwe clusters zijn:
<table>
<tr>
<th>$C_{1}$</th><th>$\{A_{1},A_{4}\}$</th>
</tr>
<tr>
<th>$C_{2}$</th><th>$\{A_{2},A_{3},A_{5}\}$</th>
</tr>
</table>
</li>
<li>De nieuwe centra zijn:
$M_{1}''=(\frac{0+0}{2},\frac{1+3}{2})=(0,2)$ en
$M_{2}''=(\frac{3+3+4}{3},\frac{1+2+1}{3})=(3.33,1.33)$
</li>
</ol>
</dd>
</dl>
In het plaatje van iteratie 2 hiernaast zie je dat de
derde iteratie niet tot een verandering van clusters gaat leiden. Dus de juiste clustering is:
<table>
<tr>
<th>$C_{1}$</th><th>$\{A_{1},A_{4}\}$</th>
</tr>
<tr>
<th>$C_{2}$</th><th>$\{A_{2},A_{3},A_{5}\}$</th>
</tr>
</table>
</div>
</div>
</div>
<p class="pagebreak"></p>
<a id="vragen"></a><br/>
<h2>Vragen</h2>
<div class ='hammer treeview' style="clear: both;">Bereken je eigen probleem
<div style="padding-left:25px;">
<div class="caret doel">Start</div>
<div class="nested">
<h1>K-means</h1>
<table class="nnapp">
<tr>
<td>Geef aantal clusters
</td>
<td><input type="number" id="K" value="2">
</td>
</tr>
<tr>
<td>Geef objecten lijst in javascript format
</td>
<td>
<textarea name="message" rows="10" cols="80" id="O">
[ [0.0,0,1] , [7.8 ,2,1] , [4.8,2,1] , [3.0,0,1] ]
</textarea>
</td>
</tr>
<tr>
<td>Geef lijst begin centra
</td>
<td>
<textarea name="message" rows="10" cols="80" id="M">
[[0.6,1,0],[7.2,1,0]]
</textarea>
</td>
</tr>
</table>
<button onclick="run('hier')">Voer uit</button>
<p id="hier"></p>
</div>
</div>
</div>
<div id="vragen5.2" class ='hammer treeview' style="clear: both;">Vragen $K$-means
<div style="padding-left:25px;">
<ol start="4">
<li>Gegeven is een dataset met 6 datapunten.
<table>
<tr>
<td></td><th>$x_{1}$</th><th>$x_{2}$</th><th>$x_{3}$</th><th>$x_{4}$</th>
</tr>
<tr>
<th>$A_{1}$</th><td>6</td><td>3</td><td>4</td><td>5</td>
</tr>
<tr>
<th>$A_{2}$</th><td>2</td><td>3</td><td>5</td><td>4</td>
</tr>
<tr>
<th>$A_{3}$</th><td>5</td><td>4</td><td>6</td><td>3</td>
</tr>
<tr>
<th>$A_{4}$</th><td>9</td><td>1</td><td>1</td><td>8</td>
</tr>
<tr>
<th>$A_{5}$</th><td>8</td><td>2</td><td>0</td><td>9</td>
</tr>
<tr>
<th>$A_{6}$</th><td>8</td><td>0</td><td>1</td><td>8</td>
</tr>
</table>
Als afstandsmaat gebruiken we de normale (Euclidische) afstand.
<ol style="list-style-type: lower-alpha;">
<li>Bereken de Euclidische afstand van $A_{1}$ en $A_{2}$
<div class="caret doel">antwoord</div>
<ul class="nested">
<li>$d(A_{1},A_{2})=\sqrt{(6-2)^{2}+(3-3)^{2}+(4-5)^{2}+(5-4)^{2}}=\sqrt{18}=3\sqrt{2}$
</li>
</ul>
</li>
</ol>
We clusteren deze gegevens in twee clusters:
$C_{1}=\{A_{1},A_{2},A_{3}\}$ en $C_{2}=\{A_{4},A_{5},A_{6}\}$<br/>
<ol style="list-style-type: lower-alpha;" start="2">
<li>Vul de volgende afstandsmatrix in:
<table>
<tr>
<td></td><th>$A_{4}$</th><th>$A_{5}$</th><th>$A_{6}$</th>
</tr>
<tr>
<th>$A_{1}$</th><td></td><td></td><td></td>
</tr>
<tr>
<th>$A_{2}$</th><td></td><td></td><td></td>
</tr>
<tr>
<th>$A_{3}$</th><td></td><td></td><td></td>
</tr>
</table>
<div class="caret doel">antwoord</div>
<ul class="nested">
<table>
<tr>
<td></td><th>$A_{4}$</th><th>$A_{5}$</th><th>$A_{6}$</th>
</tr>
<tr>
<th>$A_{1}$</th><td>5.57</td><td>6.08</td><td>5.57</td>
</tr>
<tr>
<th>$A_{2}$</th><td>9.22</td><td>9.33</td><td>8.77</td>
</tr>
<tr>
<th>$A_{3}$</th><td>8.66</td><td>9.22</td><td>8.66</td>
</tr>
</table>
</li>
</ul>
</li>
<li>
Geef de afstand tussen de clusters $C_{1}$ en $C_{2}$.
<div class="caret doel">antwoord</div>
<ul class="nested">
<li>De afstand tussen $C_{1}$ en $C_{2}$ is de kleinste afstand in de tabel dus: $d(C_{1},C_{2})=5.57$
</li>
</ul>
</li>
<li>Bereken de centra van clusters $C_{1}$ en $C_{2}$
<div class="caret doel">antwoord</div>
<ul class="nested">
<li>$C_{1}$: centrum $M_{1}=(4.33,3.33,5,4)$ <br/>
$C_{2}$: centrum $M_{2}=(8.33,1,0.67,8.33)$
</li>
</ul>
</li>
</ol>
</li>
<li>Gegeven de volgende vier objecten:
<table>
<tr>
<td></td><th>$x_{1}$</th><th>$x_{2}$</th>
</tr>
<tr>
<th>$O_{1}$</th><td>2</td><td>2</td>
</tr>
<tr>
<th>$O_{2}$</th><td>8</td><td>6</td>
</tr>
<tr>
<th>$O_{3}$</th><td>6</td><td>8</td>
</tr>
<tr>
<th>$O_{4}$</th><td>2</td><td>4</td>
</tr>
</table>
Als afstandsmaat gebruiken we de normale (Euclidische) afstand.<br/>
We willen deze gegevens clusteren in twee clusters ($K$=2), met behulp van het $K$-means algoritme.<br/>
Initialiseer het algoritme met: objecten 1 en 3 in één cluster $C_{1}$ en objecten 2 en 4 in de andere cluster $C_{2}$.<br/>
Noteer $C_{1}=\{O_{1},O_{3}\}$ en $C_{2}=\{O_{2},O_{4}\}$
<ol style="list-style-type: lower-alpha;">
<li>Bereken het centrum $M_{1}$ van $C_{1}$ en het centrum $M_{2}$ van $C_{2}$
<div class="caret doel">antwoord</div>
<ul class="nested">
<li>$C_{1}$: centrum $M_{1}=(4,5)$ <br/>
$C_{2}$: centrum $M_{2}=(5,5)$
</li>
</ul>
</li>
<li>Vul de volgende afstandsmatrix in en bereken daarmee
de afstand tussen clusters $C_{1}$ en $C_{2}$
<table>
<tr>
<td></td><th>$O_{2}$</th><th>$O_{4}$</th>
</tr>
<tr>
<th>$O_{1}$</th><td></td><td></td>
</tr>
<tr>
<th>$O_{3}$</th><td></td><td></td>
</tr>