Analiză Cluster

Gruparea cazurilor sau

a variabilelor

Când utilizăm această metoda?

Avem un set de date şi vrem să ştim cum anume se grupează cazurile sau variabilele de ex. vrem sa ştim cum anume se grupează

oraşele Romaniei în funcţie de cateva variabile demografice (mortalitate infantilă, natalitate, speranţa de viată la naştere)

de ex. vrem să ştim ce variabile demografice au valori asemănătoare pentru cazurile cu care lucăm

Specificul acestei metode

Dorim să detectăm clasele “NATURALE” în care itemii sau variabilele se plasează nu să creem noi o ordine în structura datelor

Clasele nu sunt date din punct de vedere statistic, precum se întâmplă în alte metode (de ex. analiza discriminantă), ci trebuie descoperite

Tipuri de analiză cluster

Metode non-ierarhice cea mai cunoscută metoda de acest fel este k-

means (metoda celor k-medii): se porneşte de la k valori (de obicei aleatoare) şi în functie de ele se construiesc clusterele

Metode ierarhice aglomerative: se porneşte de la n clase (câte

cazuri avem) şi se ajunge la o clasă care le cuprinde pe toate celălate anterioare ei

divizive: se porneşte de la o clasă şi se ajunge la n clase (câte cazuri avem) cuprinse în clasa de pornire

Algoritm ierarhic aglomerativ

1. Calcularea distanţelorîntre itemi

2. Selectarea perechii de itemi care este cea mai apropiată şi unirea lor într-o clasă

3. Recalcularea distantelor faţă de celelte clase, itemi

4 (2 din nou). Selectarea perechii de itemi care este cea mai apropiată şi unirea lor într-o clasă

Algoritm ierarhic aglomerativ

1. Calcularea distanţelor între itemi2. Selectarea perechii de itemi care

este cea mai apropiată şi unirea acelei perechii într-o clasă

3. Recalcularea distantelor faţă de celelte clase, itemi

4. Se reia punctul (2.) până când se obţine o singură clasă (cluster)

Calcularea distantelor partea I

Calcularea distanţelor între itemi se poate face în mai multe moduri: Euclidienă ( (xi-yi)2)1/2

Distanţa Euclidiană

X

Y

X1 Y2

X1

Y2

Distanţa Manhatan

X

Y

X1 Y2

X1

Y2

Manhatan lxi-yil

Chebyshev maxi lxi-yil

Minkovsky ( lxi-yilp)1/p

Putere ( lxi-yilp)1/r

Calcularea distantelor partea II

Când calculăm distanţe între variabile folosim în general: Corelaţia Pearson Corelaţia între vectori

Nota: aceste distanţe se pot folosi si pentru gruparea cazurilor

Putem reprezenta cazurile ca puncte în spaţiul trasat de variabile ca şi coordonate

variabila 1

vari

abil

a 2

Sau putem reprezenta variabi-lele ca vectori în spaţiul trasat de cazuri ca şi coordonate

cazul 1ca

zul 2

var 1

var

2

Calcularea distantelor un exemplu partea III

Cs. La cine ai apela dacă ai avea nevoiede…?

Nu

e cazul, le

rezolv singu

r

Nu

am la cin

eap

ela

Ru

de

Prieten

i

Colegi d

e camer

ă,vecini

Colegi d

e şcoală

Profesori

Altele

a. Intervenţii la Decanat sau Rectorat 33.49 7.36 6.95 8.85 1.55 6.09 41.52 2.87

b. Informaţii legate de bibliografie/ sursesuplimentare

8.10 .63 2.07 13.90 7.76 40.09 64.44 3.16

c. Lămurirea unor neclarităţi legate dedomeniile studiate

4.82 .29 1.72 10.62 6.67 37.09 71.29 1.49

d. Intervenţii la secretariat/ serviciusocial

51.58 8.79 3.04 9.02 1.90 7.69 15.79 7.29

e. Ajutor în contestarea unei note 41.82 7.01 1.55 3.04 .75 6.55 39.69 2.93

Calcularea distantelor Matricea de disimilaritate partea IV

Matricea de disimilaritate este matricea distanţelor între cazuri (variabile). Este o matrice simetrică

Pentru ex.de mai sus, distanţa euclidiană între cazul 1 şi 2 este calculată astfel:

a. Intervenţii la Decanat sau Rectorat 33.49 7.36 6.95 8.85 1.55 6.09 41.52

b. Informaţii legate de bibliografie/ sursesuplimentare

8.10 .63 2.07 13.90 7.76 40.09 64.44(ai - bi)2

Distanta2 (1,2) = 644.6521 + 45.2929 + 23.8144 +

25.5025 + 38.5641 + 1156 +

525.3264 + 0.0841 = 2459.237

Distanta (1,2) = 49.59069

49.593 52.709 32.076 11.686

49.593 9.036 73.820 55.522

52.709 9.036 79.146 58.654

32.076 73.820 79.146 27.003

11.686 55.522 58.654 27.003

Case1

2

3

4

5

1 2 3 4 5

Euclidean Distance

Proximity Matrix

This is a dissimilarity matrix

Calcularea distanţelor faţă de un cluster partea I

După unirea a doi itemi apropiaţi şi formarea unui cluster nou se pune problema recalculării distanţelor dintre noul cluster şi ceilalţi clusteri (itemi). În acest sens avem mai multe metode:

12

3 1 2

Nearest neighbor sau Single linkage:

d31

d12

12

3 1 2

Furtest neighbor sau Complete linkage:

Calcularea distanţelor faţă de un cluster partea II

1

3

21

2

Average linkage between groups

(d11+ d12+ d21+ d22+ d31+ d32)/6

13

2 12m1 m2

Centroid

dm1m2,

unde m1, m2 sunt mediile clusterilor

Average linkage whithin groups

(d11+ d12+ d21+ d22+ d31+ d32 + d`12+ d`13+ d`32 +d``12)/10

1

3

21

2

Calcularea distanţelor faţă de un cluster partea III

Ward’s Method urmăreşte minimizarea PIERDERII DE INFORMAŢIE:

suma pătratelor abaterilor fiecărui item din cluster de la media, eroarea sumei pătratelor

ESPtotal = ESP1 + ESP2 + … + ESPk, 1...k clusteri

la fiecare pas este luat în considerare fiecare pereche care ar putea fi unită într+un cluster, iar perechea care conduce la cele mai mici pierderi de informaţie este unificată

Gruparea cazurilor: dendograma

Grafic 1. Exporturile ţărilor CEFTA în CU (dendogramă) 1996-1998Distanţe rescalate de unire a clusterilor

0 5 10 15 20 25 ++++++

România Slovenia Slovacia Cehia Ungaria Polonia

Sursă: calculele autorului pe baza informaţilor disponibile la www.cfta.org.Date: valoarea în mii de dolari a exportaturilor fiecărei ţări CEFTA în CU.Metoda: analiză ierarhică cluster, metoda Ward, distanţe euclidiene pătrate.Interpretare: distanţele la care se unesc două ţări sau grupuri de ţări indică similitudinea lor.Soft utilizat: SPSS Inc, 2000.

Un exemplu

1 2 3 4 51 02 9 03 3 7 04 6 5 9 05 11 10 2 8 0

Pornim de la o matrice de similaritate. Cea mai mică distanţă este între perechea 3 şi 5

(35) 1 2 4(35) 01 3 02 7 9 04 8 6 5 0

Recalcularea distanţei între noul cluster format şi ceilalţi itemi se face prin metoda single linkage d(35)1= min (d31, d51) = min (3, 11) = 3

d(35)2= min (d32, d52) = min (7, 10) = 7

d(35)4= min (d34, d54) = min (9, 8) = 8

Cea mai mică distanţă este între perechea (35) şi 1

(351) 2 4(351) 02 7 04 6 5 0

Distanţa între clusterul (351) şi ceilalţi itemi d(351)2= min (d (35)2, d 12) = min (7, 9) = 7

d(351)4= min (d (35)4, d 14) = min (8, 6) = 6

Cea mai mică distanţă este între perechea 2 şi 4

Un exemplu continuare

Distanţa între clusterul (351) şi clusterul (24) d(351)(24)= min (d (351)2, d (351)4 ) = min (7, 6) = 6

(351) (24)(351) 0(24) 6 0

1

2

3

4

5

6

0 1 3 5 2 4

Dendograma arată programul de aglomerare a clusterilor: valoarea la care s-au unit clasele

Câţi clusteri să păstrăm?

Nu există un criteriu statistic puternic, precum ar fi testele de semnificaţie, care sa ne indice cu o anumită probabilitate care este structura datelor. Totuşi pentru a decide câţi clusteri să pastrăm putem sa folosim următoarele strategii: raţiuni teoretice utilizarea şi a metodelor non-ierarhice analize de varianţă graficul aglomrarilor

123456

0 1 2 3

Distanţa la care s-au unit clusterele

Algoritm non-ierarhic

1. Partiţionarea itemilor în k clase iniţiale

2. Unifică itemul cu clusterul a cărui centroid (medie) este cel mai aproape

3. Recalculează centroidul atât pentru clusterul care a înglobat itemul cât si pentru clusterul care l-a pierdut

4. Reia pasul 2 şi 3 până nu mai au loc modificări