Clusteranalyse

John Val/ Informatica/ Informatie/ Kunstmatige Intelligentie /cluster analyse

Editor: John Val

Inleiding Begrippen ⯆
Afstandsmaten Afstandsmatrix Clusterafstand
Methoden ⯆
k-means methode andere methoden
Vragen ⯆
vragen k-means vragen andere methoden

Figuur 1: Het classificeren
van objecten

Inleiding

Clusteranalyse 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 unsupervised learning (=ongestuurd leren)

Het doel van clusteranalyse 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. Is de clusteranalyse uitgevoerd dan kan de collectie van deelverzamelingen worden gebruikt om een nieuwe meting te classificeren. Bij classificatie liggen de eigenschappen van een groep dus al vast, dit dus in tegenstelling tot de clusteranalyse. 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 hier en hier te vinden.

Toepassingen

Identificatie van nepnieuws

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.

In een artikel 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.

Biologie
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.
Marketing
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.

Begrippen

We gaan straks $K$-means-clustering als algoritme presenteren. Daartoe moeten er eerst wat begrippen worden geïntroduceerd die in dit algoritme worden gebruikt. Deze begrippen spelen ook in andere clustermethoden een rol.

Afstandsmaten

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 ).

Afstand tussen datapunten (objecten):


Figuur 2: De stelling van Pythagoras


Figuur 3: Stukje Manhattan,
Je kunt alleen over de weg.

Hebben we datapunten dan kunnen we wiskundig de afstand tussen punten uitrekenen. De stelling van Pythagoras (Figuur 2) zal je vast bekend voorkomen als een 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 schuine zijde de afstand tussen de punten. Deze afstand noemt men de Euclidische astand. In drie dimensies en hoger wordt op een zelfde manier de afstand tussen twee punten berekend.

De definitie van de Euclidische afstand 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:
$$\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}$$

Naast de Euclidische afstand is er een andere maat die vaak gebruikt wordt, de Manhattan of City-block afstand. 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.

De definitie van de Manhattan of City-block afstand 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:
$$\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}$$

Voorbeeld A
Geef de afstand tussen de volgende objecten in een 5 dimensionale ruimte:
Object $A$ 10 12 15 13 9
Object $B$ 18 23 13 15 17

De Manhattan of City-block afstand is: $d(A,B)= |10−18|+|12−23|+|15−13|+|13−15|+|9−17|=31$

De Euclidische afstand is: $d(A,B)=\sqrt{(10−18)^{2}+(12−23)^{2}+(15−13)^{2}+(13−15)^{2}+(9−17)^{2}} =16,16$

Afstandsmatrix

Een matrix van afstanden is een matrix waarvan de elementen de afstanden tussen de punten aangeven.

Twee dimensionale Euclidische afstand $d(A,B)=\sqrt{(a_{1}-b_{1})^{2}+ (a_{2}-b_{2})^{2}}$

Voorbeeld B

Gegeven een dataset met vier objecten.
Geef de afstandsmatrix.
xy
A21
B42
C61
D72
Gebruiken we de gewone Euclidische afstand dan
ziet de afstandsmatrix er als volgt uit:
ABCD
A02.2445.1
B2.2402.243
C42.2401.41
D5.131.410

Afstand tussen clusters

Als je de afstand tussen elk paar van objecten weet, wat is dan de afstand tussen twee clusters $C_{1}$ en $C_{2}$?
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 Single Linkage.

Single Linkage: $d(C_{1},C_{2})=\min\{d(A,B)|A \in C_{1}\,\,en\,\, B \in C_{2} \}$

Voorbeeld C

Gegeven een dataset met zes punten.
xy
$A_{1}$13
$A_{2}$14
$A_{3}$22
$B_{1}$51
$B_{2}$52
$B_{3}$72
De clusters zijn $C_{1}=\{A_{1},A_{2},A_{3}\}$ en $C_{2}=\{B_{1},B_{2},B_{3}\}$
Geef de minimale afstand tussen $C_{1}$ en $C_{2}$
De afstandsmatrix is:
$B_{1}$$B_{2}$$B_{3}$
$A_{1}$4.474.126.03
$A_{2}$54.476.32
$A_{3}$3.1635
$d(C_{1},C_{2})=\min\{d(A,B)|A \in C_{1}\,\,en\,\, B \in C_{2} \}$
$d(A_{3},B_{2})=\sqrt{(5-2)^{2}+(2-2)^2}=3$ is de kleinste afstand en is dus de afstand tussen $C_{1}$ en $C_{2}$.

Centrum cluster

Het centrum $M(m_{1},m_{2}, \dots, m_{n})$ van een cluster wordt bepaald als het gemiddelde van de coördinaten van de punten in de cluster. Wiskundig gezien is het het zwaartepunt van de veelhoek die door de punten wordt gevormd.

Centrum $M$ van een cluster:
$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)$.

Voorbeeld D

Gegeven een cluster $C$ die de volgende objecten bevat:
xy
$A_{1}$00
$A_{2}$78
$A_{3}$48
$A_{4}$30
Bereken het centrum van de cluster $C$.
$C=\{A_{1},A_{2},A_{3},A_{4}\}$
$M= \left( \frac{0 + 7 + 4 +3 }{4},\frac{0+8+8+0}{4}\right)=( 3\frac{1 }{2},4)$

Cluster methoden


Figuur 4: Animatie van het $K$-means algoritme

Figuur 5: Het algoritme

Zoals eerder vermeld zijn er verschillende methoden die binnen kunstmatige intelligentie gebruikt worden om tot clusters te komen. We beginnen hier met de $K$-means-clustering 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.

$K$-means-clustering

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 je wilt hebben. 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.

Om de optimale clustering te vinden ga je als volgt te werk:

Start: Kies de centra van de clusters de eerste keer willekeurig en bepaal het maximaal aantal stappen dat je toestaat.

  1. 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.
  2. 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.
  3. 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:
    $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)$.
    $n$ is dan het aantal elementen in één cluster.
  4. 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.
Leuk zo'n verhaal maar voorbeelden maken het inzichtelijker.

Voorbeeld E

Gegeven een cluster $C$ die de volgende objecten bevat:
xy
$A_{1}$22
$A_{2}$42
$A_{3}$61
$A_{4}$82
We bepalen vooraf dat we twee clusters willen, dus $k=2$.
Bepaal met het $K$-means algoritme een geschikte clustering.
Als afstandsmaat gebruik je de normale (Euclidische) afstand.
Start:
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 hiernaast.
Iteratie 1:
  1. Bepaal de afstanden van de datapunten tot de centra en plaats de datapunten in het juiste cluster.
    De afstandsmatrix wordt:
    $M_{1}$$M_{2}$toewijzing
    $A_{1}$2.834$C_{1}$
    $A_{2}$22$C_{1}$
    $A_{3}$3.611$C_{2}$
    $A_{4}$4.472$C_{2}$
  2. De nieuwe clusters zijn:
    $C_{1}$$\{A_{1},A_{2}\}$
    $C_{2}$$\{A_{3},A_{4}\}$
    We moeten door naar stap 3
  3. Bereken de nieuwe centra:
    $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)$
Iteratie 2:
  1. Bepaal de afstanden van de datapunten tot de centra en plaats de datapunten in het juiste cluster.
    De afstandsmatrix wordt:
    $M_{1}'$$M_{2}'$toewijzing
    $A_{1}$15.02$C_{1}$
    $A_{2}$13.04$C_{1}$
    $A_{3}$3.161.12$C_{2}$
    $A_{4}$51.12$C_{2}$
  2. 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:
    $C_{1}$$\{A_{1},A_{2}\}$
    $C_{2}$$\{A_{3},A_{4}\}$
Start

Iteratie 1

Voorbeeld F

Gegeven een cluster $C$ die de volgende objecten bevat:
xy
$A_{1}$01
$A_{2}$31
$A_{3}$32
$A_{4}$03
$A_{5}$41
We bepalen vooraf dat we twee clusters willen, dus $k=2$.
Bepaal een juiste clustering.
Als afstandsmaat gebruik je de normale (Euclidische) afstand.
Start:
Kies twee willekeurig centra. $M_{1}=(2,2)$ en $M_{2}=(3,0)$
Iteratie 1:
  1. De afstandsmatrix wordt:
    $M_{1}$$M_{2}$toewijzing
    $A_{1}$2.243.16$C_{1}$
    $A_{2}$1.411$C_{2}$
    $A_{3}$12$C_{1}$
    $A_{4}$2.244.24$C_{1}$
    $A_{5}$2.241.41$C_{2}$
  2. De nieuwe clusters zijn:
    $C_{1}$$\{A_{1},A_{3},A_{4}\}$
    $C_{2}$$\{A_{2},A_{5}\}$
  3. 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)$
Iteratie 2:
  1. De afstandsmatrix wordt:
    $M_{1}'$$M_{2}'$toewijzing
    $A_{1}$1.413.5$C_{1}$
    $A_{2}$2.240.5$C_{2}$
    $A_{3}$21.12$C_{2}$
    $A_{4}$1.414.03$C_{1}$
    $A_{5}$3.160.5$C_{2}$
  2. De nieuwe clusters zijn:
    $C_{1}$$\{A_{1},A_{4}\}$
    $C_{2}$$\{A_{2},A_{3},A_{5}\}$
  3. 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)$
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:
$C_{1}$$\{A_{1},A_{4}\}$
$C_{2}$$\{A_{2},A_{3},A_{5}\}$
Start

Iteratie 1

Iteratie 2

Vragen

  1. Gegeven is een dataset met 6 datapunten.
    $x_{1}$$x_{2}$$x_{3}$$x_{4}$
    $A_{1}$6345
    $A_{2}$2354
    $A_{3}$5463
    $A_{4}$9118
    $A_{5}$8209
    $A_{6}$8018
    Als afstandsmaat gebruiken we de normale (Euclidische) afstand.
    1. Bereken de Euclidische afstand van $A_{1}$ en $A_{2}$ Antwoord $d(A_{1},A_{2})=\sqrt{(6-2)^{2}+(3-3)^{2}+(4-5)^{2}+(5-4)^{2}}=\sqrt{18}=3\sqrt{2}$
    We clusteren deze gegevens in twee clusters: $C_{1}=\{A_{1},A_{2},A_{3}\}$ en $C_{2}=\{A_{4},A_{5},A_{6}\}$
      Vul de volgende afstandsmatrix in: Antwoord
      $A_{4}$$A_{5}$$A_{6}$
      $A_{1}$5.576.085.57
      $A_{2}$9.229.338.77
      $A_{3}$8.669.228.66
    $A_{4}$$A_{5}$$A_{6}$
    $A_{1}$
    $A_{2}$
    $A_{3}$
    1. Geef de afstand tussen de clusters $C_{1}$ en $C_{2}$. Antwoord De afstand tussen $C_{1}$ en $C_{2}$ is de kleinste afstand in de tabel dus: $d(C_{1},C_{2})=5.57$
    2. Bereken de centra van clusters $C_{1}$ en $C_{2}$ Antwoord
      $C_{1}$: centrum $M_{1}=(4.33,3.33,5,4)$
      $C_{2}$: centrum $M_{2}=(8.33,1,0.67,8.33)$
  2. Gegeven de volgende vier objecten:
    $x_{1}$$x_{2}$
    $O_{1}$22
    $O_{2}$86
    $O_{3}$68
    $O_{4}$24
    Als afstandsmaat gebruiken we de normale (Euclidische) afstand.
    We willen deze gegevens clusteren in twee clusters ($K$=2), met behulp van het $K$-means algoritme.
    Initialiseer het algoritme met: objecten 1 en 3 in één cluster $C_{1}$ en objecten 2 en 4 in de andere cluster $C_{2}$.
    Noteer $C_{1}=\{O_{1},O_{3}\}$ en $C_{2}=\{O_{2},O_{4}\}$
    1. Bereken het centrum $M_{1}$ van $C_{1}$ en het centrum $M_{2}$ van $C_{2}$ Antwoord
      $C_{1}$: centrum $M_{1}=(4,5)$
      $C_{2}$: centrum $M_{2}=(5,5)$
    2. Vul de volgende afstandsmatrix in en bereken daarmee de afstand tussen clusters $C_{1}$ en $C_{2}$
      $O_{2}$$O_{4}$
      $O_{1}$
      $O_{3}$
      Antwoord
      $O_{2}$$O_{4}$
      $O_{1}$7.212
      $O_{3}$2.835.7
      Dus de afstand $d(C_{1},C_{2})=2$
    3. Bereken de afstanden tot de centra $M_{1}$ en $M_{2}$ en vul de volgende tabel in:
      $M_{1}$$M_{2}$toewijzing
      $O_{1}$
      $O_{2}$
      $O_{3}$
      $O_{4}$
      Antwoord
      $M_{1}$$M_{2}$toewijzing
      $O_{1}$3.64.2$C_{1}$
      $O_{2}$3.63.2$C_{2}$
      $O_{3}$4.13.2$C_{2}$
      $O_{4}$2.23.2$C_{1}$
    4. Wat zijn uiteindelijk de clusters van het $K$-means algoritme. Antwoord
      $C_{1}=\{O_{1},O_{4}\}$ en $C_{2}=\{O_{2},O_{3}\}$ $C_{1}$: centrum $M_{1}'=\{2,3\}$
      $C_{2}$: centrum $M_{2}'=\{7,7\}$
      $M_{1}'$$M_{2}'$toewijzing
      $O_{1}$17.1$C_{1}$
      $O_{2}$6.71.4$C_{2}$
      $O_{3}$6.41.4$C_{2}$
      $O_{4}$15.8$C_{1}$
      Er is geen verandering in de clustering.
      Dus:$C_{1}=\{O_{1},O_{4}\}$ en $C_{2}=\{O_{2},O_{3}\}$
  3. Gegeven de volgende zes datapunten:
    $x_{1}$$x_{2}$
    $D_{1}$63
    $D_{2}$23
    $D_{3}$54
    $D_{4}$91
    $D_{5}$82
    $D_{6}$80
    Als afstandsmaat gebruiken we de normale (Euclidische) afstand.
    We willen deze gegevens clusteren in drie clusters ($K$=3), met behulp van het $K$-means algoritme.
    Initialiseer het algoritme met $C_{1}=\{D_{1},D_{2}\}$ , $C_{2}=\{D_{3},D_{4}\}$ en $C_{3}=\{D_{5},D_{6}\}$
    1. Bereken het centrum $M_{1}$ van $C_{1}$, het centrum $M_{2}$ van $C_{2}$ en het centrum $M_{3}$ van $C_{3}$ Antwoord
      $C_{1}$: centrum $M_{1}=(4,3)$
      $C_{2}$: centrum $M_{2}=(7,2.5)$
      $C_{3}$: centrum $M_{3}=(8,1)$
    2. Bereken de afstanden van de datapunten tot de centra $M_{1}$ en $M_{2}$ en vul de volgende tabel in en voer zonodig een herclustering uit:
      $M_{1}$$M_{2}$$M_{3}$toewijzing
      $D_{1}$
      $D_{2}$
      $D_{3}$
      $D_{4}$
      $D_{5}$
      $D_{6}$
      Antwoord
      $M_{1}$$M_{2}$$M_{3}$toewijzing
      $D_{1}$21.12.83$C_{2}$
      $D_{2}$25.06.3$C_{1}$
      $D_{3}$1.42.54.2$C_{1}$
      $D_{4}$5.42.51$C_{3}$
      $D_{5}$4.11.11$C_{3}$
      $D_{6}$52.71$C_{3}$
      Er is de herclustering $C_{1}=\{D_{2},D_{3}\}$ , $C_{2}=\{D_{1}\}$ en $C_{3}=\{D_{4},D_{5},D_{6}\}$
    3. Wat zijn de nieuwe centra en zijn we nu klaar?. Antwoord
      $C_{1}=\{D_{2},D_{3}\}$ , $C_{2}=\{D_{1}\}$ en $C_{3}=\{D_{4},D_{5},D_{6}\}$
      $C_{1}$: centrum $M_{1}'=(3.5,3.5)$
      $C_{2}$: centrum $M_{2}'=(6,3)$ $C_{3}$: centrum $M_{3}'=(8.3,1)$
      $M_{1}'$$M_{2}'$$M_{3}'$toewijzing
      $D_{1}$2.503$C_{2}$
      $D_{2}$1.646.6$C_{1}$
      $D_{3}$1.61.44.5$C_{2}$
      $D_{4}$63.60.7$C_{3}$
      $D_{5}$4.772.271.1$C_{3}$
      $D_{6}$5.73.61.1$C_{3}$
      Er is weer verandering in de clustering.
      Dus:$C_{1}=\{D_{2}\}$ , $C_{2}=\{D_{1},D_{3}\}$ en $C_{3}=\{D_{4},D_{5},D_{6}\}$
      Er is dus minstens nog een iteratie nodig.
  4. Gegeven de volgende vier objecten:
    $x_{1}$$x_{2}$
    $A_{1}$00
    $A_{2}$78
    $A_{3}$48
    $A_{4}$30
    Als afstandsmaat gebruiken we de normale (Euclidische) afstand.
    Cluster de gegevens volledig in twee clusters ($K$=2), met behulp van het $K$-means algoritme.
    Initialiseer het algoritme met de willekeurige centrum $M_{1}=(0,6)$ en $M_{2}=(7,2)$. Vul je resultaten in onderstaande tabel in.
    ClustersCentra
    Start$M_{1}=(0,6)$
    $M_{2}=(7,2)$
    Iteratie 1$C_{1}=$
    $C_{2}=$    		$M_{1}=$
    $M_{2}=$
    Iteratie 2$C_{1}=$
    $C_{2}=$    		$M_{1}=$
    $M_{2}=$
    ...
    Antwoord Iteratie 1:
    $M_{1}$$M_{2}$toewijzing
    $A_{1}$6.007.28$C_{1}$
    $A_{2}$7.286.00$C_{2}$
    $A_{3}$4.476.71$C_{1}$
    $A_{4}$6.714.47$C_{2}$
    ClustersCentra
    Start$M_{1}=(0,6)$
    $M_{2}=(7,2)$
    Iteratie 1$C_{1}=\{A_{1},A_{3}\}$
    $C_{2}=\{A_{2},A_{4}\}$    		$M_{1}=(2,4)$
    $M_{2}=(5,4)$
    Iteratie 2:
    $M_{1}$$M_{2}$toewijzing
    $A_{1}$4.476.40$C_{1}$
    $A_{2}$6.404.47$C_{2}$
    $A_{3}$4.474.12$C_{2}$
    $A_{4}$4.124.47$C_{1}$
    ClustersCentra
    Start$M_{1}=(0,6)$
    $M_{2}=(7,2)$
    Iteratie 1$C_{1}=\{A_{1},A_{3}\}$
    $C_{2}=\{A_{2},A_{4}\}$    		$M_{1}=(2,4)$
    $M_{2}=(5,4)$
    Iteratie 2$C_{1}=\{A_{1},A_{4}\}$
    $C_{2}=\{A_{2},A_{3}\}$    		$M_{1}=(1.5,0)$
    $M_{2}=(5.5,8)$
    Iteratie 3:
    $M_{1}$$M_{2}$toewijzing
    $A_{1}$1.509.71$C_{1}$
    $A_{2}$9.711.50$C_{2}$
    $A_{3}$8.381.50$C_{2}$
    $A_{4}$1.508.38$C_{1}$
    Geen verandering clustering dus klaar.
  5. Een reisagentschap wil zijn klanten opdelen in twee clusters ($K$=2), op basis van leeftijd en duur van geboekte vakanties. De informatie van het reisagentschap is gegeven in de onderstaande tabel. De leeftijd van klanten uitgedrukt in aantal jaren, de duur van de vakantie in het aantal dagen.
    LeeftijdDuur vakantie
    $TO_{1}$193
    $TO_{2}$258
    $TO_{3}$4314
    $TO_{4}$6114
    $TO_{5}$307
    $TO_{6}$2210
    Als afstandsmaat gebruiken we de normale (Euclidische) afstand.
    Cluster de gegevens volledig in twee clusters ($K$=2), met behulp van het $K$-means algoritme.
    Initialiseer het algoritme met de cetra $M_{1}=TO_{1}$ en $M_{2}=TO_{2}$. Vul je resultaten in onderstaande tabel in.
    ClustersCentra
    Start$M_{1}=(19,3)$
    $M_{2}=(25,8)$
    Iteratie 1$C_{1}=$
    $C_{2}=$    		$M_{1}=$
    $M_{2}=$
    Iteratie 2$C_{1}=$
    $C_{2}=$    		$M_{1}=$
    $M_{2}=$
    ...
    Antwoord Iteratie 1:
    $TO_{1}$0.007.81 $C_{1}$
    $TO_{2}$7.810.00 $C_{2}$
    $TO_{3}$26.4018.97 $C_{2}$
    $TO_{4}$43.4236.50 $C_{2}$
    $TO_{5}$11.705.10 $C_{2}$
    $TO_{6}$7.623.61 $C_{2}$
    ClustersCentra
    Start$M_{1}=(19,3)$
    $M_{2}=(25,8)$
    Iteratie 1$C_{1}=\{TO_{1}\}$
    $C_{2}=\{TO_{2},TO_{3},TO_{4},TO_{5},TO_{6}\}$    		$M_{1}=(19,3)$
    $M_{2}=(36.2,10.6)$
    Iteratie 2:
    $M_{1}$$M_{2}$toewijzing
    $TO_{1}$0.0018.80 $C_{1}$
    $TO_{2}$7.8111.50 $C_{1}$
    $TO_{3}$26.407.60 $C_{2}$
    $TO_{4}$43.4225.03 $C_{2}$
    $TO_{5}$11.707.17 $C_{2}$
    $TO_{6}$7.6214.21 $C_{1}$
    ClustersCentra
    Start$M_{1}=(0,6)$
    $M_{2}=(7,2)$
    Iteratie 1$C_{1}=\{TO_{1}\}$
    $C_{2}=\{TO_{2},TO_{3},TO_{4},TO_{5},TO_{6}\}$    		$M_{1}=(19,3)$
    $M_{2}=(36.2,10.6)$
    Iteratie 2$C_{1}=\{TO_{1},TO_{2},TO_{6}\}$
    $C_{2}=\{TO_{3},TO_{4},TO_{5}\}$    		$M_{1}=(22,7)$
    $M_{2}=(44.7,11.7)$
    Iteratie 3:
    $M_{1}$$M_{2}$toewijzing
    $TO_{1}$5.0027.09 $C_{1}$
    $TO_{2}$3.1620.01 $C_{1}$
    $TO_{3}$22.142.87 $C_{2}$
    $TO_{4}$39.6216.50 $C_{2}$
    $TO_{5}$8.0015.39 $C_{1}$
    $TO_{6}$3.0022.73 $C_{1}$
    ClustersCentra
    Start$M_{1}=(0,6)$
    $M_{2}=(7,2)$
    Iteratie 1$C_{1}=\{TO_{1}\}$
    $C_{2}=\{TO_{2},TO_{3},TO_{4},TO_{5},TO_{6}\}$    		$M_{1}=(19,3)$
    $M_{2}=(36.2,10.6)$
    Iteratie 2$C_{1}=\{TO_{1},TO_{2},TO_{6}\}$
    $C_{2}=\{TO_{3},TO_{4},TO_{5}\}$    		$M_{1}=(22,7)$
    $M_{2}=(44.7,11.7)$
    Iteratie 3$C_{1}=\{TO_{1},TO_{2},TO_{5},TO_{6}\}$
    $C_{2}=\{TO_{3},TO_{4}\}$    		$M_{1}=(24,7)$
    $M_{2}=(52,14)$
    Iteratie 4:
    $M_{1}$$M_{2}$toewijzing
    $TO_{1}$6.4034.79 $C_{1}$
    $TO_{2}$1.4127.66 $C_{1}$
    $TO_{3}$20.259.00 $C_{2}$
    $TO_{4}$37.669.00 $C_{2}$
    $TO_{5}$6.0023.09 $C_{1}$
    $TO_{6}$3.6130.27 $C_{1}$
    Geen verandering in clusters dus klaar.
  6. Hieronder staan gegevens van 4 (fictieve) studenten van een data mining cursus. We noteren respectievelijk het aantal bijgewoonde lessen, het aantal dagen examenvoorbereiding, en of ze al dan niet voor het examen kwamen opdagen: $D=\{S_{1}(0.0,0,1),S_{2}(7.8 ,2,1),S_{3}(4.8,2,1),S_{4}(3.0,0,1)\}$
    We willen deze objecten clusteren, wat we kunnen doen door middel van de $K$-means methode. Kies $K=2$, en als initiële willekeurige cluster centra: $M_{1}=(0.6,1,0)$ en $M_{2}=(7.2,1,0)$. Pas de $K$-means methode toe op $D$ tot een maximum van 3 stappen. Noteer voor elke iteratie welke clusters gevormd worden en wat de centra zijn.
    Convergeert de methode? Zo ja, leg uit.
    Vul de resultaten in de onderstaande tabel in:
    ClustersCentra
    Start$M_{1}=(0.6,1,0)$
    $M_{2}=(7.2,1,0)$
    Iteratie 1$C_{1}=$
    $C_{2}=$    		$M_{1}=$
    $M_{2}=$
    Iteratie 2$C_{1}=$
    $C_{2}=$    		$M_{1}=$
    $M_{2}=$
    ...
    Antwoord Iteratie 1 :
    $M_{1}$$M_{2}$toewijzing
    $S_{1}$1.547.34$C_{1}$
    $S_{2}$7.341.54$C_{2}$
    $S_{3}$4.432.79$C_{2}$
    $S_{4}$2.794.43$C_{1}$
    ClustersCentra
    Start$M_{1}=(0.6,1,0)$
    $M_{2}=(7.2,1,0)$
    Iteratie 1$C_{1}=\{S_{1},S{4}\}$
    $C_{2}=\{S_{2},S{3}\}$    		$M_{1}=(1.5,0,1)$
    $M_{2}=((6.3,2,1)$
    Iteratie 2:
    $M_{1}$$M_{2}$toewijzing
    $S_{1}$1.506.61$C_{1}$
    $S_{2}$6.611.50$C_{2}$
    $S_{3}$3.861.50$C_{2}$
    $S_{4}$1.503.86$C_{1}$
    Geen verandering in clusters dus klaar.

Andere cluster methoden

Als het $K$-means algoritme zo eenvoudig en snel is, waarom zijn er dan, zoals eerder genoemd, andere clusteralgoritmen? Het antwoord hierop is dat er dataverzamelingen zijn die niet passen bij het $K$-means algoritme. Bekijk maar eens het volgende plaatje:


Figuur 6: Verschillende verdelingen datapunten (bron) en algoritmen.

De eerste kolom hoort bij een $K$-means variant. Alleen de verdeling in de vijfde rij past daar echt goed bij. Welk algoritme denk jij dat bij de verschillende rijen het beste past? Er zijn een aantal algoritmen die bij meerdere verdelingen goed scoren, maar die hebben weer andere minpunten. Het is dus van belang om te controleren of je de juiste versie kiest. Heb je meer dan twee assen dan wordt een visuele inspectie zoals in de figuur al een stuk lastiger.

De clusteralgoritmen kunnen worden onderverdeeld in partitiemethoden en hiërarchische methoden. In de partitiemethoden staat clustering met een centrum centraal. Het $K$-means valt in deze groep. In de hiërarchische methoden zijn naaste buren belangrijker. Deze buren vormen dan een stamboom vergelijkbaar met een indeling in het dierenrijk. Iedere splitsing vormt op dat niveau een cluster. In figuur 6 is Agglomerative Clustering daarvan een voorbeeld.

Voor een eerste kennismaking met clustering is het voldoende te weten dat er verschillende methoden zijn en dat deze allen iteratief werken en op afstandsmaten zijn gebaseerd. Wil je je in deze cursus meer verdiepen in clustering dan zijn de verdiepingsopdrachten hieronder een startpunt.

Vragen en opdrachten andere methoden

  1. Wat is het verschil tussen hiërarchische methoden en partitiemethoden? Antwoord In hiërarchische wordt een stamboom gevormd op basis van nabijheid tot omliggende punten, bij partitiemethoden worden puntenverzamelingen gevormd op basis van afstand tot centra van de die puntenverzamelingen.
    2. Opdracht: Ga naar de site     educlust. Er worden hier verschillende clustermethoden aangeboden en verschillende datasets vergelijkbaar met figuur 6. Van iedere methode wordt het algoritme getoond.
    1. Kies methode "k-means" en kies de dataset "Three circles sparse" en zet k op 3. Druk op de het zwarte knopje. Hoeveel iteraties zijn er gemaakt om tot het resultaat te komen? Ben je tevreden over het resultaat?
    2. Kies weer de methode "k-means" en kies de dataset "Three equal circles" en zet k op 3. Druk op de het zwarte knopje. Hoeveel iteraties zijn er gemaakt om tot het resultaat te komen? Ben je tevreden over het resultaat?
    3. Kies de hiërarchische methode "Single linkage" en kies de dataset "Three circles sparse". Druk op de het zwarte knopje. Aan het eind van het proces hebben alle punten een gelijke kleur. Onder de figuur vind je een dendogram (boomstructuur). Als je in het dendogram met je muis over de bolletjes bij de splitsingen gaat zie je punten oplichten die onder de betreffende splitsing vallen.
      Hoeveel stappen zijn er gemaakt om tot het resultaat te komen? Ben je tevreden over het resultaat?
    4. Kies weer de hiërarchische methode "Single linkage" en kies de dataset "Three equal circles". Druk op de het zwarte knopje en heb veel geduld. Hoeveel stappen zijn er gemaakt om tot het resultaat te komen? Ben je tevreden over het resultaat?
    5. Wat leer je uit de bovenstaande opdrachten?
  2. Verdiepende opdracht:In de vorige opdracht heb je met een klein experiment twee methoden vergeleken. Ga naar de site towards datascience. Daar staat informatie over verschillende clustermethoden waaronder K$-means clustering en Agglomerative Hierarchical Clustering (=Single linkage). Zoek in de tekst de voordelen en de problemen bij de ze twee methoden. Ook op de site Analytixslab worden voor en nadelen van deze methoden beschouwd (Agglomerative Hierarchical Clustering heet hier AGNES). Wordt hier de zelfde informatie gegeven?
  3. Verdiepende opdracht: Ga weer naar de site educlust. Maak je eigen keuze van methoden die je wilt vergelijken. Zoek vervolgens uit hoe de methoden precies werken en wat de voor en nadelen van de methoden zijn. Verwerk je onderzoek in een verslag (website / tekstdocument / poster)