Omtrent het begrip cluster is er geen eenduidige consistente definitie beschikbaar

Clusteranalyse - E. Omey - AJ 2006-2007

1

Clusteranalyse E. Omey 1. Inleiding In verschillende sociale, politieke en ecnomische systemen zoals onderwijs en overheid en bedrijfswereld kunnen we structuren en soms hiërarchishe structuren herkennen: streek, school, klas of centrale, regionale en lokale overheid. Deze structuren vormen natuurlijke groepen of clusters in bijvoorbeeld het opzetten van geclusterde steekproeven. Clusteranalyse is de naam voor een grote waaier van procedures die gebruikt worden om een populatie in te delen in klassen. Elementen van de populatie die dezelfde of gelijk(w)aardige“ informatie uitdrukken worden samengevoegd tot groepen van individuen of objecten. Clusteranalyse is een multivariate procedure waarbij men vertrekt van een (grote) dataset en waarbij men de dataset wil reorganiseren tot relatief homogene groepen. Deze groepen zijn vooraf niet gekend en ook het aantal groepen is vooraf niet bekend. Wij willen dat elementen die tot één cluster behoren min of meer één homogene groep vertegenwoordigen. Elementen uit verschillende clusters vertonen géén homogeen beeld: zoveel mogelijk gelijkenissen binnen één groep zoveel mogelijk verschil tussen de groepen. “Cluster analysis techniques are concerned with discovering whether or not a set of multivariate data consist of distinct groups or clusters of individuals and, if so, to determine both the number of such groups and their characteristics” (Everitt, 1987). Omtrent het begrip “cluster” is er geen eenduidige consistente definitie beschikbaar. Toepassingen van clusteranalyse zijn te vinden in marktsegementering (individuen met gelijke behoeftepatroenen groeperen) en marktafbakening (producten of merken die tot eenzelfde markt behoren groeperen). Ook in de banksector en de verzekeringswereld probeert men van de klanten na te gaan tot welke risicogroep/risicoprofiel zij behoren. Op de aandelenmarkt kan men ook proberen aandelen met dezelfde kenmerken te groeperen. In biologie probeert men de dierenwereld zodanig te organiseren en typeren zodat dieren op een adequate manier van elkaar kunnen onderscheiden worden. Toepassing van clusteranalyse zijn er ook in de biomedische wereld


2

9 8 7 6 5 4 3 2 1 0 0

2

4

6

8

10

12

150000

100000

50000

0 0

-50000

-100000

100000

200000

300000

400000

500000

600000

700000

800000


3

10 9 8 7 6 5 4 3 2 1 0 1

2

3

4

5

6

0,025 0,02 0,015 0,01 0,005 0 0 -0,005 -0,01 -0,015

100

200

300

400

500

600

700


4

12 10 8 6 4 2 0 0

5

10

15

20

25

0

5

10

15

20

25

-2

12 10 8 6 4 2 0 -2

120 100 80 60 40 20 0 -20200 -40 -60 -80 -100

250

300

350

400


2. Basisstappen in een clusteringproces In principe wordt elke clusteranalyse gekarakteriseerd door meerdere basisstappen.

2.1. Bepaling van het onderzoeksprobleem Hier bepalen we welke entiteiten (respondenten, observaties,... ) of welke populatie we willen onderzoeken. Deze stap bepaalt in grote mate de manier waarop we onze data zullen verzamelen.

2.2. Selectie van de data of attributen De variabelen kunnen zowel binair zijn (nominaal of ordinaal) of niet binair, d.w.z. van het intervalniveau of het ratio-niveau. Heel dikwijls zal men data van verschillende grootte-orde vooraf standardiseren. Het is interessant om te beschikken over data van dezelfde “dimensie”. Wanneer bijvoorbeeld X = de leeftijd en Y = het inkomen, dan is het aangewezen om vooraf te standardiseren. Dit doen of niet doen kan grote invloed hebben op de volgende stap. Opmerking - Bij nominale variabelen gebruikt men dummy-variabelen. - bij ordinale variabelen gebruitk men dikwijls de volgende werkwijze om de variabele om te zetten naar meerdere dummy’s. Stel dat we een ordinale variabele hebben met 5 categorieën: A < B < C < D < E In dit geval gebruikt men 5 dummy-variabelen. Een object met waarde B krijgt dan de code 1 1 0 0 0 Een object met waarde E krijgt de code 1 1 1 1 1

2.3. Selectie van een afstandsmaat Wanneer we willen nagaan of twee objecten al dan niet “dicht” bij elkaar liggen, dan zullen we moeten beschikken over een afstandsmaat of een afstandsindex. Een afstandsmaat (in de n-dimensionale ruimte) is een functie die voldoet aan vier voorwaarden: (a) symmetrie: d(x, y) = d(y, x) (b) positief: d(x, y) ≥ 0 (c) d(x, y) = 0 enkel en alleen als x = y (d) driehoeksongelijkheid: d(x, y) ≤ d(x, z) + d(z, y) In sommige gevallen wordt voorwaarde (c) afgezwakt en werkt men soms met zgn. pseudo-metrieken.

5


6

Voorbeeld Van drie objecten noteerden we 9 kenmerken en na standardiseren (behalve x(7) en x(9)) vonden we:

1 2

y -1,75 -1,78

x(1) 1,59 2,25

x(2) -1,65 -1,39

x(3) -0,26 -1,65

x(4) 3,27 -0,31

x(5) -0,66 -0,66

x(6) 0,84 0,84

3

0,21

-0,59

0,23

-1,65

-0,31

0,39

-0,94

x(7) 1 1

x(8) 1,68 1,17

1

-1,22

x(9) 1 0 0

Grafisch krijgen we het volgend beeld: obs 1 en obs 2 4,00 3,00 2,00 1,00 0,00 -1,00

1

2

3

4

5

6

7

8

9

10

7

8

9

10

-2,00 -3,00

obs 2 en obs 3 2,50 2,00 1,50 1,00 0,50 0,00 -0,50 -1,00 -1,50 -2,00

1

2

3

4

5

6


7

Om de afstand tussen observaties te meten zijn er verschillende mogelijkheden. We gebruiken de volgende notaties: x(i, k) = resultaat van variabele k voor individu of object i 1 x(k ) = ∑ x(i, k ) = (rekenkundig) gemiddelde van m.b.t. variabele k n i Wanneer we een deel A van de observaties bekijken, dan stellen we 1 x A (k ) = ∑ x(i, k ) = gemiddelde van de objecten in A m.b.t. variabele k n( A) x ( i )∈A

2.3.1. Euclidische afstand Een populaire afstandsmaat is de afstand in vogelvlucht of de Euclidische afstand. De afstand tussen twee individuen i en j wordt als volgt gemeten k

d ²(i, j ) = ∑ ( x(i, r ) − x( j , r ))² r =1

2.3.2 Manhattan- of taxi-afstand Nu wordt de afstand tussen twee individuen i en j als volgt gemeten k

d T (i, j ) = ∑ x(i, r ) − x( j , r ) r =1

2.3.3. De Max-afstand (Chebychev) Hier wordt de afstand tussen twee individuen i en j als volgt gemeten d M (i, j ) = max r x(i, r ) − x( j, r )

2.3.4. Correlatiecoëfficiënt Alhoewel correlatiecoëfficiënten geen echte afstandsmaten zijn, wordt deze coëfficiënt toch dikwijls gebruikt als maatstaf voor gelijkheid. Bemerk dat de correlatiecoëfficiënt en de Euclidische afstand als volgt gerelateerd zijn: d²(x, y) = 2(1 – r(x, y)) Voorbeeld (vervolg) Voor het minivoorbeeld berekenen we verschillende afstanden:

1 vs 2 1 vs 3 2 vs 3

eucl² 16,43879 40,53035 24,64161

taxi 7,426668 17,71304 11,66814

max 3,572173 3,572173 2,840399

r 0,665863 -0,24991 -0,08433


2.3.5. Kwalitatieve variabelen Wanneer we vertrekken van alleen kwalitatieve variabelen (nominaal of ordinaal) dan kunnen we deze variabelen omzetten in binaire 0 – 1 variabelen en associatiemaatstaven gebruiken. Stel dat we alleen 0 – 1 variabelen hebben en de “afstand” willen berekenen tussen twee objecten i en j. We kunnen de volgende tabel opstellen:

individu 2 totaal

1 0

individu 1 a c a+c

1 0 b d b+d

totaal a+b c+d a+b+c+d

Hier is a = het aantal keer dat individu 1 en 2 allebei het kenmerk hebben b = het aantal keer dat individu 1 wèl en individu 2 het kenmerk nièt heeft enzovoort Als de individuen “dicht” bijeen liggen dan verwachten we dat a + d “groot” is in vergelijking met c en b. De simple matching coëfficiënt is gelijk aan

a+d a+b+c+d Wanneer men alleen geïnteresseerd is in de uitkomsten “1”, dan kan de Jaccard coëfficiënt gebruikt worden: a J= a+b+c S=

8


9

2.3.6. Voorbeeld 2 We werken nog een tweede voorbeeld uit met de volgende gegevens: data 1 2 3 4 5 6

x(1) 6 2 5 9 8 8

x(2) 3 3 4 1 2 0

x(3) 4 5 6 1 0 1

x(4) 5 4 3 8 9 8

Voor de eerste en de tweede waarneming vinden we voor de Euclidische afstand: d²(1ste, 2de) = 4² + 0² + 1² + 1² = 18 = (4,24)² Voor de max-afstand vinden we: dmax(1ste, 2de) = max(4, 0, 1, 1) = 4 De andere waarden staan in de volgende tabellen: Euclidische afstand 1 2 3 4 5 6

1 0 4,24 3,16 5,57 6,08 5,57

2

3

4

5

6

0 3,46 9,22 9,33 8,77

0 8,66 9,22 8,66

0 2 1,41

0 1,41

0

2

3

4

5

6

0 3 7 6 6

0 5 6 5

0 1 1

0 2

0

Max Afstand 1 2 3 4 5 6

1 0 4 2 3 4 3


2.4. Afstand tussen clusters? In de vorige paragraaf bekeken we verschillende manieren om de “afstand” te meten tussen observaties. Hoe kunnen we nu een afstand berekenen tussen verzamelingen van punten? Er zijn verschillende mogelijkheden.

2.4.1. Nearest neighbour Bij deze wijze is de afstand tussen twee verzamelingen gelijk aan de kleinste afstand tussen de observaties van A en van B: d ( A, B ) = min( d ( x (i ), y ( j ) : x (i ) ∈ A, y ( j ) ∈ B )

of

d ( A ∪ B, C ) = min( d ( A, C ), d ( B, C ))

Grafisch:

2.4.2. Furthest neighbour method Hier bekijkt men de grootste afstand tussen punten van A en van B: d ( A, B ) = max( d ( x (i ), y ( j ) : x (i ) ∈ A, y ( j ) ∈ B )

of

d ( A ∪ B, C ) = min( d ( A, C ), d ( B, C ))

Grafisch:

2.4.3. Average linkage In de vorige werkwijzen bepaalt één afstand hoe groot de afstand is tussen 2 verzamelingen. Bij deze werkwijze berekent men een gemiddelde afstand: 1 d ( A, B ) = ∑ x (i )∈A ∑ y ( j )∈B d ( x(i), y( j )) n( A)n( B)

2.4.4. Afstand tussen middelpunten Bij deze werkwijze selecteert men uit beide verzamelingen A en B een “representatief” punt m(A) en m(B) en stelt men d(A, B) = d(m(A), m(B)) Hierbij rijst onmiddellijk de vraag naar de keuze van m(A).

10


11

2.4.5. Ward’s afstand De variatie binnenin een verzameling A van observaties (n observatiesen k variabelen) is gelijk aan k

V ( A) = ∑

∑ ( x(i, j ) − m( j ))²

j =1 x ( i )∈ A

1 ∑ x(i, j ) . n( A) x ( i )∈A Als indicator voor de afstand tussen A en B neemt Ward de volgende definitie:

waarbij m( j ) =

d ( A, B ) = V ( A ∪ B ) − V ( A) − V ( B )

Opmerking Er zijn nog andere manieren om te komen tot (pseudo-)afstanden. Een van de werkwijzen werkt als volgt (k-th nearest-neighbour method): - specifieer k; - stel r(k, x) = de afstand van x tot de kde dichtste observatie; - we bekijken nu de cirkel/sfeer met middelpunt x en met straal r(k, x); - we schatten de dichtheidsfunctie van x als f(x) = # observaties in de sfeer met straal r(k, x) gedeeld door het volume van de cirkel; - we berekenen nu D*(x(i), x(j)) = 0,5*(1/f(x(i)) + 1/f(x(j)) als d(x(i), x(j)) < max(r(k, x(i)), r(k, x(j)) = ∝ anders In weer andere werkwijzen kiest men r vast en stelt men f(x) = # observaties in de cirkel met middelpunt x en met straal r gedeeld door het volume van deze sfeer. Dan berekent met D*(x(i), x(j)) = 0,5*(1/f(x(i)) + 1/f(x(j)) als d(x(i), x(j)) < r = ∝ anders Voor een overzicht van andere (ingewikkelde) methoden,zie het overzicht op www.mainserver.state.mn.us/sas/stat/chap23/sect12.htm


12

2.4.6. Voorbeeld (vervolg voorbeeld 2.3.6) We gebruiken de Euclidische afstand, cf tabel Euclidische afstand 1 0 4,24 3,16 5,57 6,08 5,57

1 2 3 4 5 6

2

3

4

5

6

0 3,46 9,22 9,33 8,77

0 8,66 9,22 8,66

0 2 1,41

0 1,41

0

en berekenen de “afsatnd” tussen sommige groepen. We gebruiken hiervoor de average linkage. - de afstand tussen (1) en (5,6) is d((1), (5,6)) = (d(1, 5) + d(1, 6))/2 = (6,08 + 5,57)/2 = 5,83 - de afstand tussen (3) en (4,5,6) is d((3), (4,5,6)) = (8,66 + 9,22 + 8,66)/3 = 8,85 - de afstand tussen (1,3) en (4,5,6) is d((1,3), (4,5,6)) = (5,57 + 6,08 + 5,57 + 8,66 + 9,22 + 8,66)/6 = 7,29 enzovoort.

2.4.7. Voorbeeld 2 Gegevens

1 2 3 4 5 6 7 8 9 10

x(1) 0,91 0,77 0,45 0,76 0,81 0,24 0,10 -0,35 0,01 -0,75

x(2) -0,66 -0,48 -0,59 -0,99 -0,19 -0,77 -0,04 -0,08 -0,23 0,83

x(3) 0,77 0,50 0,23 0,77 1,31 -0,31 0,50 -0,58 0,23 -2,19

x(4) -0,72 -0,72 -0,26 1,12 1,12 1,12 1,12 -0,26 -0,72 -0,26

x(5) -0,31 -0,31 -0,31 -0,31 -0,31 -0,31 -0,31 -0,31 -0,31 -0,31

x(6) -0,66 -0,66 -0,66 1,43 -0,66 -0,66 1,43 -0,66 1,43 -0,66

We wensen een afstand te berekenen tussen de groepen A = (1,2,3,4,5) en B = (6,7,8,9,10). We vertrekken van de Euclidische afstand tussen de onderlinge objecten:


d²(euclides) 1 2 3 4 5 6 7 8 9 10

1 0,00 0,13 0,73 7,88 3,93 5,03 8,87 3,96 5,65 13,99

2 0,13 0,00 0,40 8,09 4,14 4,42 8,40 2,79 5,07 11,51

3 0,73 0,40 0,00 6,82 3,37 2,28 6,76 1,54 4,89 9,33

4 7,88 8,09 6,82 0,00 5,29 5,84 1,41 10,14 4,85 20,66

5 3,93 4,14 3,37 5,29 0,00 3,27 5,53 6,81 9,56 17,65

min (i, B) max(i, B)

3,96 13,99

2,79 11,51

1,54 9,33

1,41 20,66

3,27 17,65

gemiddelde

13

6 5,03 4,42 2,28 5,84 3,27 0,00 5,56 2,81 8,40 9,02

7 8,87 8,40 6,76 1,41 5,53 5,56 0,00 7,63 3,52 15,01

8 3,96 2,79 1,54 10,14 6,81 2,81 7,63 0,00 5,36 3,60

9 5,65 5,07 4,89 4,85 9,56 8,40 3,52 5,36 0,00 12,13

10 13,99 11,51 9,33 20,66 17,65 9,02 15,01 3,60 12,13 0,00

7,21

We berekenen nu op verschillende manieren de afstand tussen groep A = {1,2,3,4,5} en B = {6,7,8,9,10}


14

1) nearest neighbour

d(A, B) =

1,412

2) Furthest neighbour

d(A, B) =

20,658

3) Average linkage

d(A,B) =

7,208

4) middelpunten we werken met rekenkundig gemiddelden

m(A) m(B)

0,74 -0,15

-0,58 -0,06

0,72 -0,47

d(m(A), m(B)) =

0,11 0,20

-0,31 -0,31

-0,24 0,18

2,65

5) Ward groep A

1 2 3 4 5

0,91 0,77 0,45 0,76 0,81 0,15

-0,66 -0,48 -0,59 -0,99 -0,19 0,42

0,77 0,50 0,23 0,77 1,31 0,80

-0,72 -0,72 -0,26 1,12 1,12 4,47

-0,31 -0,31 -0,31 -0,31 -0,31 0,00

-0,66 -0,66 -0,66 1,43 -0,66 4,35

som 10,19

6 7 8 9 10 variatie

0,24 0,10 -0,35 0,01 -0,75 0,80

-0,77 -0,04 -0,08 -0,23 0,83 1,66

-0,31 0,50 -0,58 0,23 -2,19 5,55

1,12 1,12 -0,26 -0,72 -0,26 3,72

-0,31 -0,31 -0,31 -0,31 -0,31 0,00

-0,66 1,43 -0,66 1,43 -0,66 6,53

som 18,26

1 2 3 4 5 6 7 8 9 10 variatie

0,91 0,77 0,45 0,76 0,81 0,24 0,10 -0,35 0,01 -0,75 3,05

-0,66 -0,48 -0,59 -0,99 -0,19 -0,77 -0,04 -0,08 -0,23 0,83 2,61

0,77 0,50 0,23 0,77 1,31 -0,31 0,50 -0,58 0,23 -2,19 9,55

-0,72 -0,72 -0,26 1,12 1,12 1,12 1,12 -0,26 -0,72 -0,26 7,30

-0,31 -0,31 -0,31 -0,31 -0,31 -0,31 -0,31 -0,31 -0,31 -0,31 0,00

-0,66 -0,66 -0,66 1,43 -0,66 -0,66 1,43 -0,66 1,43 -0,66 10,15

som 32,67

variatie groep B

A en B

Ward afstand

4,22


15

2.5. Keuze van een clusteralgoritme Er zijn verschillende clusteralgoritmes beschikbaar. Er wordt een onderscheid gemaakt tussen hiërarchische methodes en partitiemethodes.

2.5.1. Hiërarchische methodes Bij de hiërarchische methode worden de dataniet in één fase in groepen verdeeld. Het gaatom een opeenvolging van fusies of divisies. Bij agglomeratieve (samenvoegende) technieken vertrekt men van n clusters (elk datapunten vormt een individuele cluster) en men smelt clusters samen tot men één cluster heeft waarin alle objecten zitten. Deze familie van technieken is veruit het populairst. Bij divisieve (splitsende) technieken werkt men in de omgekeerde richting: hier vertrekt men van één grote groep omuiteindelijk te komen tot n individuele clusters (met daarin telkens één observatie.

2.5.2. Partitiemethodes Deze methodes zijn ontworpen om de entiteiten te verdelen in k clusters waarbij men dus vooraf beslist hoeveel clusters men wil bereiken. In principe verloopt dezze procedure als volgt: 1) bepaal k 2) kies uit alle observaties k observaties O(1), O(2), ..., O(k); 3) Bepaal voor alle observaties de afstanden d(P, O(i)) en verdeel de observaties in k clusters C(1), C(2), ..., C(k) (P behoort tot C(i) als d(P, C(i)) < d(P, C(j))); 4) bepaal voor elke cluster C(i) een centrale waarde M(i); 5) herhaal opnieuw stappen 3 en 4 tot de clusters niet meer veranderen of tot een bepaald stopcriterium is bereikt. Bij deze partitiemethodes zijn er enkele belangrijke beslissingen die moeten genomen worden of vragen die moeten beantwoordt worden. - keuze van de beginpositie? - keuze van een centrale waarde? - wanneer stoppen? Deze vragen komen later aan bod.


16

3. Hiërarchische methoden 3.1. Samenvoegende hiërarchische werkwijze De basisprocedure verloopt als volgt. (1) we vertrekken van een n x n matrix met daarin alle afstanden d(i, j) opgenomen zijn. Bij n observaties moeten we n(n – 1)/2 afstanden berekenen. (2) Bij de centrale samenvoegende methode vormt elke observatie één cluster. In de eerste stap vertrekken we dus van n clusters (C(1,1), C(1,2), ..., C(1,n)) (3) In de volgende stap berekenen we d(C(1,i), C(1,j)) en de twee obervaties i* en j* die het dichtst bij elkaar liggen voegen we samen: C(2, i) = C(1, i) als i verschilt van i* en van j* C(2, i) = C(1,i*) ∪ C(1, j*) als i = i* of i = j* (4) Vervolgens berekenen we opnieuw d(C(2, i), C(2, j)) en de twee clusters C(2, i*) en C(2, j*) die het dichtst bij elkaar liggen worden samengevoegd. Na m stappen vinden we C(m, i) = C(m – 1, i) als i verschilt van i* of van j* C(m, i) = C(m – 1, i*) ∪ C(m – 1, j*) als i = i* of als j = j* (5) Na een beperkt aantal stappen komt men uiiteindelijk tot één cluster waarin alle observaties zitten. De grote vraag die men zich moet stellen is met welke afstandsmaten men zal werken!


17

3.2. Voorbeelden 3.2.1. Voorbeeld (vervolg 2.3.6) We vertrekken van de Euclidische afstanden en gebruiken average linkage. Euclidische afstand 1 0 4,24 3,16 5,57 6,08 5,57

1 2 3 4 5 6

2

3

4

5

6

0 3,46 9,22 9,33 8,77

0 8,66 9,22 8,66

0 2 1,41

0 1,41

0

* de kleinste afstand is 1,41 en we kiezen ervoor om 5 en 6 samen te nemen. We berekenen nu de nieuwe afstanden: voorbeeld: de afstand tussen (1) en (5,6) is d((1), (5,6)) = (d(1, 5) + d(1, 6))/2 = (6,08 + 5,57)/2 = 5,83 De andere afstanden staan in de volgende tabel:

1 2 3 4 (5,6)

1 0,00 4,24 3,16 5,57 5,83

2

3

4

(5,6)

0,00 3,46 9,22 9,05

0,00 8,66 8,94

0,00 1,71

0,00

* De kleinste afstand is nu 1,71 en we nemen 4, 5 en 6 samen De afstand tussen (3) en (4,5,6) is d((3), (4,5,6)) = (8,66 + 9,22 + 8,66)/3 = 8,85. Voor de andere afstanden vinden we:

1 2 3 (4,5,6)

1 0,00 4,24 3,16 5,74

2

3

(4,5,6)

0,00 3,46 9,11

0,00 8,85

0,00

* De kleinste afstand is 3,16 en nu nemen we 1 en 3 samen. De afstand tussen (1,3) en (4,5,6) is d((1,3), (4,5,6)) = (5,57 + 6,08 + 5,57 + 8,66 + 9,22 + 8,66)/6 = 7,29 De andere afstanden zijn:

2 (1,3) (4,5,6)

2 0 3,85 9,22

(1,3)

(4,5,6)

0 7,29

0


18

* De kleinste afstand is 3,85 en nu nemen we 1, 2 en 3 samen. We vinden d((1,2,3), (4,5,6)) = 7,90 * Uiteindelijk worden deze twee groepen samengevoegd en zitten alle waarnemingen in één cluster. Deze gang van zaken kunnen we handig voorstellen in een dendogram. (zie bord)

3.2.2. Voorbeeld 2. We werken een voorbeeld uit waarbij we werken met de Euclidische afstand en met d(A, B) = d(m(A), m(B)), cf. 2.4.4 1) We vertrekken van de matrix met afstanden: d²(euclides) 1 2 3 4 5 6 7 8 9 10

1 0 0,13 0,73 7,88 3,93 5,03 8,87 3,96 5,65 14

2

3

4

5

6

7

8

9

10

0 0,4 8,09 4,14 4,42 8,4 2,79 5,07 11,5

0 6,8 3,4 2,3 6,8 1,5 4,9 9,3

0 5,29 5,84 1,41 10,1 4,85 20,7

0 3,27 5,53 6,81 9,56 17,6

0 5,6 2,8 8,4 9

0 7,63 3,52 15

0 5,36 3,6

0 12,1

0

2) de kleinste afstand is d(1, 2) = 0,13 We voegen nu objecten 1 en 2 samen en herrekenen de afstanden (door bij 1 en 2 rekenkundige gemiddelden te nemen) De nieuwe dataset is:

(1,2) 3 4 5 6 7 8 9 10

x(1) 0,84 0,45 0,76 0,81 0,24 0,10 -0,35 0,01 -0,75

met nieuwe afstanden

x(2) -0,57 -0,59 -0,99 -0,19 -0,77 -0,04 -0,08 -0,23 0,83

x(3) 0,63 0,23 0,77 1,31 -0,31 0,50 -0,58 0,23 -2,19

x(4) -0,72 -0,26 1,12 1,12 1,12 1,12 -0,26 -0,72 -0,26

x(5) -0,31 -0,31 -0,31 -0,31 -0,31 -0,31 -0,31 -0,31 -0,31

x(6) -0,66 -0,66 1,43 -0,66 -0,66 1,43 -0,66 1,43 -0,66

Clusteranalyse - E. Omey - AJ 2006-2007 d² (1,2) 3 4 5 6 7 8 9 10

(1,2) 0,00 0,53 7,95 4,00 4,69 8,60 3,34 5,33 12,72

3 0,53 0,00 6,82 3,37 2,28 6,76 1,54 4,89 9,33

4 7,95 6,82 0,00 5,29 5,84 1,41 10,14 4,85 20,66

5 4,00 3,37 5,29 0,00 3,27 5,53 6,81 9,56 17,65

6 4,69 2,28 5,84 3,27 0,00 5,56 2,81 8,40 9,02

19 7 8,60 6,76 1,41 5,53 5,56 0,00 7,63 3,52 15,01

8 3,34 1,54 10,14 6,81 2,81 7,63 0,00 5,36 3,60

9 5,33 4,89 4,85 9,56 8,40 3,52 5,36 0,00 12,13

10 12,72 9,33 20,66 17,65 9,02 15,01 3,60 12,13 0,00

De kleinste afstand is deze tussen 3 en (1, 2) die in de volgende stap samen gevoegd worden. 2) De nieuwe dataset is:

(1,2,3) 4 5 6 7 8 9 10

x(1) 0,71 0,76 0,81 0,24 0,10 -0,35 0,01 -0,75

x(2) -0,58 -0,99 -0,19 -0,77 -0,04 -0,08 -0,23 0,83

x(3) 0,50 0,77 1,31 -0,31 0,50 -0,58 0,23 -2,19

x(4) -0,57 1,12 1,12 1,12 1,12 -0,26 -0,72 -0,26

x(5) -0,31 -0,31 -0,31 -0,31 -0,31 -0,31 -0,31 -0,31

x(6) -0,66 1,43 -0,66 -0,66 1,43 -0,66 1,43 -0,66

met nieuwe afstanden d² (1,2,3) 4 5 6 7 8 9 10

(1,2,3) 0,00 7,46 3,67 3,77 7,87 2,62 5,07 11,47

4 7,46 0,00 5,29 5,84 1,41 10,14 4,85 20,66

5 3,67 5,29 0,00 3,27 5,53 6,81 9,56 17,65

6 3,77 5,84 3,27 0,00 5,56 2,81 8,40 9,02

7 7,87 1,41 5,53 5,56 0,00 7,63 3,52 15,01

8 2,62 10,14 6,81 2,81 7,63 0,00 5,36 3,60

9 5,07 4,85 9,56 8,40 3,52 5,36 0,00 12,13

10 11,47 20,66 17,65 9,02 15,01 3,60 12,13 0,00

De kleinste afstand is d(4, 7) = 1,41 en er wordt een nieuwe cluster (4, 7) gevormd.


20

3) We ‘rekenen’ verder: dataset:

(1,2,3) (4,7) 5 6 8 9 10

x(1) 0,71 0,43 0,81 0,24 -0,35 0,01 -0,75

x(2) -0,58 -0,52 -0,19 -0,77 -0,08 -0,23 0,83

x(3) 0,50 0,63 1,31 -0,31 -0,58 0,23 -2,19

x(4) -0,57 1,12 1,12 1,12 -0,26 -0,72 -0,26

x(5) -0,31 -0,31 -0,31 -0,31 -0,31 -0,31 -0,31

x(6) -0,66 1,43 -0,66 -0,66 -0,66 1,43 -0,66

afstanden: d² (1,2,3) (4,7) 5 6 8 9 10

(1,2,3) 0,00 7,31 3,67 3,77 2,62 5,07 11,47

(4,7) 7,31 0,00 5,05 5,34 8,53 3,83 17,48

5 3,67 5,05 0,00 3,27 6,81 9,56 17,65

6 3,77 5,34 3,27 0,00 2,81 8,40 9,02

8 2,62 8,53 6,81 2,81 0,00 5,36 3,60

9 5,07 3,83 9,56 8,40 5,36 0,00 12,13

10 11,47 17,48 17,65 9,02 3,60 12,13 0,00

We merken dat “8” bij de groep (1,2,3) komt. 4)

(1,2,3,8) (4,7) 5 6 9 10

d² (1,2,3,8) (4,7) 5 6 9 10

x(1) 0,45 0,43 0,81 0,24 0,01 -0,75

x(2) -0,45 -0,52 -0,19 -0,77 -0,23 0,83

(1,2,3,8) 0,00 7,12 3,97 3,04 4,65 9,01

(4,7) 7,12 0,00 5,05 5,34 3,83 17,48

x(3) 0,23 0,63 1,31 -0,31 0,23 -2,19

5 3,97 5,05 0,00 3,27 9,56 17,65

x(4) -0,49 1,12 1,12 1,12 -0,72 -0,26

6 3,04 5,34 3,27 0,00 8,40 9,02

x(5) -0,31 -0,31 -0,31 -0,31 -0,31 -0,31

x(6) -0,66 1,43 -0,66 -0,66 1,43 -0,66

9 4,65 3,83 9,56 8,40 0,00 12,13

10 9,01 17,48 17,65 9,02 12,13 0,00

Waarneming 6 wordt bij de grote groep (1,2,3,8) geplaatst en we vinden nu:


21

5)

(1,2,3,8,6) (4,7) 5 9 10

x(1) 0,40 0,43 0,81 0,01 -0,75

x(2) -0,52 -0,52 -0,19 -0,23 0,83

d² (1,2,3,8,6) (4,7) 5 9 10

(1,2,3,8,6) 0,00 6,28 3,34 4,91 8,53

(4,7) 6,28 0,00 5,05 3,83 17,48

x(3) 0,12 0,63 1,31 0,23 -2,19 5 3,34 5,05 0,00 9,56 17,65

x(4) -0,17 1,12 1,12 -0,72 -0,26

9 4,91 3,83 9,56 0,00 12,13

x(5) -0,31 -0,31 -0,31 -0,31 -0,31

10 8,53 17,48 17,65 12,13 0,00

en vervolgens 6)

(1,2,3,8,6,5)

(4,7) 9 10

x(1) 0,47 0,43 0,01 -0,75

x(2) -0,46 -0,52 -0,23 0,83

d²

x(3) 0,32 0,63 0,23 -2,19 (4,7)

0,00 5,61 5,22 9,58

(1,2,3,8,6,5)

(4,7) 9 10

5,61 0,00 3,83 17,48

x(4) 0,04 1,12 -0,72 -0,26

x(5) -0,31 -0,31 -0,31 -0,31

9

10

5,22 3,83 0,00 12,13

9,58 17,48 12,13 0,00

x(6) -0,66 1,43 1,43 -0,66

Nu komt ‘9’ bij de groep (4, 7) en we vinden: 7)

(1,2,3,8,6,5)

(4,7,9) 10

x(1)

x(2)

x(3)

x(4)

x(5)

x(6)

0,47 0,29 -0,75

-0,46 -0,42 0,83

0,32 0,5 -2,19

0,04 0,51 -0,26

-0,31 -0,31 -0,31

-0,66 1,43 -0,66

0,00 4,63 9,58

(4,7,9) 4,63 0,00 14,85

10 9,58 14,85 0,00

d² (1,2,3,8,6,5)

(4,7,9) 10

x(6) -0,66 1,43 -0,66 1,43 -0,66

Clusteranalyse - E. Omey - AJ 2006-2007 Nu komen de groepen (1,2, ..., 5) en (4,7,9) bijeen en tenslotte komt 10 bij de ganse groep. Men kan deze opeenvolging van samenvoegen van clusters schematisch weergeven in een dendogram (hier volgt een slechte tekening):

22


23

3.2.3. Voorbeeld 2 (Ward’s methode)

1 2 3 4 5 6

x(1) 0,45 0,76 0,81 0,24 0,10 -0,35

x(2) 0,77 0,50 0,23 0,77 1,31 -0,31

a) Variatie individueel = 0

b) Variatie bij twee objecten 1 2 2 0,0871 0,0000 3 0,1487 0,0372 4 0,2087 0,2295 5 0,4120 0,5128 6 0,8206 0,9546 2 en 3 samen c) toename van

(2,3) 4 5 6

1

variaties (2,3)

0,1842 0,2087 0,412 0,8206

0 0,3076 0,9082 1,1644

d) toename van (2,3) (4,5) 6

1 0,1470 0,1013 0,8206

e) toename van (2,3) (1,4,5) 0,7363 6 2,107

0,0000 0,3056 0,5743 1,0656

0,0000 0,1552 1,0286

0,0000 1,4058 var (2,3)=

0,0372

5 4 en 5 samen

0 0,1552 1,0286

0 1,4058

(4,5)

6

0 1,3957

TV = 0,0372 + 0,1552 TV = 0,1924

var (2,3) = var (1,4,5)=

0,0372 0,2565

0

TV = 0,1013 + 0,1552+ 0,0372

variatie (1,4,5) 0 1,2944

variatie 6 0

5

4

(2,3) en (1,4,5) samen f) toename van (1,2,..,5) 6 1,4317

4

totale variatie = TV

variatie (2,3) 0 0,8331 1,2016

1 en (4,5) samen

3

6

0,2937

var(2,3,1,4,5)

1,03

0 TV =

1,03 var(1,2,..,6)

alles samen TV =

2,4617

2,4617


24

4. Partitiemethodes Zoals reeds vroeger vermeld zijn deze methodes ontworpen om de entiteiten te verdelen in k clusters waarbij men dus vooraf beslist hoeveel clusters men wil bereiken. In principe verloopt dezze procedure als volgt: 1) bepaal k 2) kies uit alle observaties k observaties O(1), O(2), ..., O(k); 3) Bepaal voor alle observaties de afstanden d(P, O(i)) en verdeel de observaties in k clusters C(1), C(2), ..., C(k) (P behoort tot C(i) als d(P, C(i)) < d(P, C(j))); 4) bepaal voor elke cluster C(i) een centrale waarde M(i); 5) herhaal opnieuw stappen 3 en 4 tot de clusters niet meer veranderen of tot een bepaald stopcriterium is bereikt. Bij deze partitiemethodes zijn er enkele belangrijke beslissingen die moeten genomen worden of vragen die moeten beantwoordt worden: - keuze van afstandsfunctie? - keuze van de beginpositie? - keuze van een centrale waarde? - wanneer stoppen?

4.1. Beginpositie Bij aanvang van de partitiemethode moet men vertrekken van een startpositie van k observaties en/of k clusters. Startpunten. Mogelijkheden om startpunten te kiezen zijn: - kies de eerste k observaties; - nummer de observaties en kies er lukraak k uit; - bij het kiezen van startpunten streeft men er naar dat deze punten de ganse daaset overspannen. Men wil dat er vele punten dicht bij de startpunten zijn en dat de startpunten ver van elkaar verwijderd zijn. Een keer men k startpunten heeft gekozen kan men de andere observaties samen voegen bij een van de startpunten: bepaal voor alle observaties de afstanden d(P, O(i)) en verdeel de observaties in k clusters C(1), C(2), ..., C(k) (P behoort tot C(i) als d(P, C(i)) < d(P, C(j))). Startclusters In de plaats van te werken met startpunten kan men met één van de hierarchische methodes onmiddellijk beginnen met k clusters C(1), C(2), ..., C(k).


25

4.2. Clusters aanpassen Om observaties toe te wijzen aan één van de k clusters kan men op verschillende manieren te werk gaan. Men maakt een onderscheid tussen twee veelgebruikte werkwijzen: - k-means methode; - hill-climbing methode.

4.2.1. k-means methode De bedoeling van deze werkwijze is tweeërlei: men wil tegelijkertijd de variatie binnen elke cluster minimaliseren en de variatie tussen clusters maximaliseren. De volgende procedure kan in principe gevolgd worden. - we vertrekken van k clusters - in elke cluster berekenen we een centrale waarde M(i) - in elke cluster berekenen we de variatie - met de M(i) berekenen (benaderen) de variatie tussen de clusters - verplaats nu een punt van één cluster naar een andere cluster of wissel twee punten van plaats en vernieuw de berekeningen. In de plaats van de variatie kan men ook met andere maatstaven werken en de “afstand” tussen clusters maximaliseren. Voorbeeld We vertrekken van de volgende data en willen bijvoorbeeld komen tot k = 2 clusters.

1 2 3 4 5 6 7 8 9 10

x(1) 0,91 0,77 0,45 0,76 0,81 0,24 0,10 -0,35 0,01 -0,75

x(2) -0,66 -0,48 -0,59 -0,99 -0,19 -0,77 -0,04 -0,08 -0,23 0,83

x(3) 0,77 0,50 0,23 0,77 1,31 -0,31 0,50 -0,58 0,23 -2,19

x(4) -0,72 -0,72 -0,26 1,12 1,12 1,12 1,12 -0,26 -0,72 -0,26

x(5) -0,31 -0,31 -0,31 -0,31 -0,31 -0,31 -0,31 -0,31 -0,31 -0,31

x(6) -0,66 -0,66 -0,66 1,43 -0,66 -0,66 1,43 -0,66 1,43 -0,66

- We starten (zomaar) met C(1) = (1,2,3,4,5) en C(2) = (6,7,8,9,10) We vinden voor deze keuze


26

cluster 1 gemiddelde variatie

0,74 0,12

-0,58 0,34

0,72 0,64

0,11 3,57

-0,31 0,00

-0,24 3,48

TV in C(1) 8,15

-0,15 0,639049

-0,06 1,32767

-0,47 4,441351

0,20 2,977431

-0,31 0

0,18 5,222025

TV in C(2) 14,60753

cluster 2 gemidd variatie

Voor de 2 clusters samen vinden we TV = 8,15 + 14,61 = 22,76 Tussen de clusters is de variatie gelijk aan 1,328. - verbetering? We wisselen 1 en 6 en gebruiken C(1) = (6,2,3,4,5) en C(2) = (1,7,8,9,10). We vinden nu TV(C(1)) = 8,78 TV(C(2)) = 15,94 totaal = 24,72 Tussen de clusters is de variatie gelijk aan: 0,93 Î geen verbetering! - verbetering? Ik gebruik C(1) = (1,2,3,5,8,10) en C(2) = (4,6,7,9). We vinden nu TV(C(1)) = 14 TV(C(2)) = 7,4 totaal = 21,4 Tussen de clusters is de variatie gelijk aan: 1,67 Î verbetering! Enzovoort.

4.2.2. Hill-climbing Bij deze werkwijze worden entiteiten toegewezen aan een cluster in functie van een statistisch criterium dat moet geöptimaliseerd worden. Vertrekkend van een theoretishc model kan men voor elk punt de kans berekenen dat het punt tot een cluster behoort. Vervolgens zoekt men die verdeling waardoor de kansen maximaal zijn (cf. maximum likelihoodmethode). Men vertrekt bijvoorbeeld van een dataset en men veronderstelt dat er twee clusters zijnd die elk afkomstig zijn uit een normale verdeling. Vervolgens probeert men vanuit de dataset de twee groepen te reconstueren.


27

Bibliografie Alsem, K.J. en Hoekstra, J.C. (1998). Een typologie van marketingstrategiën in Nederland. Maandblad voor Accountancy en Bedrijfseconomie, Juni 1998, 290 – 310. Brook R.J, Arnold, G.C., Hassard, T.H and Pringle, R.M. (Editors) (1986). The fascination of statistics. Marcel Dekker Inc. Everitt, B.S. (1980). Cluster Analysis (2nd ed). Heinemann Educational Books, London. Everitt, B.S. & Rabe-Hesketh, S. (1997). The analysis of proximity data. Arnold, London. Everitt, B.S., S. Landau & M. Leese (2001). Cluster Analysis (4th ed). Arnold, London. Hair, J.F., Anderson, R.E., Tatham, R.L. & Black, W.C. (1995). Multivariate data analysis with readings. Prentice Hall International. Jedi, K. et al. (1998). Clustering at the movies. Marketing Letters 9(4), 393 – 405. Kaufman, L. and Rousseeuw, P.J. (1990). Finding groups in data: an introduction to cluster analysis. John Wiley, New York. Paykel, E.S. and Rassaby E. (1978). Classification of suicide attempters by cluster analysis. Brit. J. Psychology 133, 45 – 52. Van Kenhove, P. (1996). Clusteranalyse en factoriële correspondentieanalyse in marktsegmentatieonderzoek: een praktische illustratie. Econ. en Soc. Tijdschrift 1996/2, 281-309. Speeckaert E. (1996). Clusteranalyse. Eindwerk EHSAL. http://www.statsoft.com/textbook http://www2.chass.ncsu.edu/garson/pa765/cluster.htm

Omtrent het begrip cluster is er geen eenduidige consistente definitie beschikbaar

Recommend Documents