Analiza de cluster

Algoritmii de clusterizare sau clasificare nesupervizată sunt utilizați pentru a determina grupările naturale
ale datelor sau pentru a furniza o împărțire convenabilă a datelor în grupuri.
Spre deosebire de clasificarea supervizată (analiza discriminantă), în clasificarea nesupervizată nu există o
informație prealabilă despre grupele în care se va face clasificarea. Analiza de cluster este o metodă exploratorie.
Numărul grupelor este subordonat scopului analizei.
Datele supuse analizei sunt valori ale relațiilor dintre indivizii și variabilele aflate în studiu, luate câte două -
distanțe sau disimilarități. Înregistrarea acestor valori ia forma matricelor de distanță. Așadar, valorile supuse analizei
reprezintă deja rezultatul unor calcule care au ca rezultat măsuri de disimilaritate dintre obiecte (instanțe sau variabile).
Grupele formate prin clasificare conțin indivizi asemănători intre ei, cu disimilarități mici. Privită din această
perspectivă, a formării de grupe omogene, analiza de cluster este o metodă de sinteză informațională, așa cum este și
analiza în componente principale, doar că se referă în principal la instanțe și nu la variabile. O grupă omogenă poate
fi reprezentată în diverse analize printr-un singur individ: centrul grupei.
Există mai multe motive pentru care o grupare a datelor este necesară:
- Identificarea trăsăturilor fundamentale ale datelor. Se studiază relațiile semnificative existente între date.
- Obținerea unor reprezentări avantajoase în efectuarea analizelor
- Stocare și regăsire rapidă a informației. În acest sens este preocupantă îmbunătățirea vitezei de acces prin
furnizarea unor strategii de rutare pentru informația stocată. Eficiența grupării se măsoară prin eficiența timpului de
regăsire a unei părți dorite din ansamblul datelor.

Descrierea algoritmilor de clasificare

Algoritmii de clusterizare se împart în următoarele grupe:

- algoritmi ierarhici;
- algoritmi de partiționare (KMeans)
- algoritmi aglomerativi (K-nn)
- algoritmi de tip grid (OCluster)

Algoritmi ierarhici

Fie Ω = {w1, w2, ..., wn} mulțimea obiectelor (indivizi/instanțe sau variabile) aflate în analiză. O ierarhie,
notată cu H, este un ansamblu ordonat de mulțimi, formate din elemente ale mulțimii Ω, agregate la un anumit nivel,
si care are proprietățile:
1.   H, adică submulțimea agregată la nivelul cel mai de sus conține toți indivizii;
2. pentru orice wi, i=1,n (n este numărul de obiecte), există {wi}H care formează submulțimile de bază, terminale;
3. pentru orice h, h’H există implicația: hh’    h h’ sau h’h.
Outputul grafic al algoritmilor ierarhici este graficul dendrogramă. Una dintre axele graficului este axa distanțelor.
Cealaltă axă este axa obiectelor. Graficul evidențiază distanțele de agregare din ierarhie.
Exemplu. În figura următoare este construită o ierarhie după distanța euclidiană pentru 5 puncte din plan și graficul
aferent

w2 w1

w4
w3
w5

w1 w2 w4 w3 w5
Figura 1. Exemplu de ierarhie

Iată pașii prin care se construiește o ierarhie:

Intrări: un set de n(n-1)/2 distanțe și un set de n mulțimi hi = {wi}, i = 1,n, aflate la nivelul cel mai de jos de
agregare
Pasul 1: se selectează mulțimile care vor fi agregate: hi și hk
 Pasul 2: se adună obiectele mulțimilor hi și hk și se înlocuiesc cu un nouă mulțime h' = hi  hk actualizându-
se și distanțele între noua mulțime h' și celelalte mulțimi
Pasul 3: Atâta timp cât rămân cel puțin două mulțimi, se revine la pasul 1.
O ierarhie se construiește în n-1 etape/iterații. La fiecare iterație are loc o joncțiune, două mulțimi dispar în
locul lor apărând una nouă formată prin reuniune. Se poate spune că după fiecare joncțiune se obține o nouă repartizare
a obiectelor în mulțimi. O astfel de repartizare este numită partiție.
Prima partiție corespunde nivelului cel mai de jos de repartizare: P 1 = {{w1},{w2}, ..., {wn}}. Următoarele
partiții vor avea n-1, n-2, ..., 1 elemente. Ultima partiție este P n = {{w1,w2, ...,wn}}.
Partițiile pot fi evidențiate in graficul dendrogramă prin secționări paralele cu axa distanțelor. Numărul de
mulțimi dintr-o partiție este egal cu numărul de brațe intersectate de secțiune. In imaginile de mai jos sunt evidențiate
diverse partiții obținute prin secționare.

Un cluster este definit printr-o mulțime de obiecte din partiție sau din ierarhie. Un cluster format dintr-un
singur obiect este numit cluster singleton.

Figura 2. Partiții cu 2,3 și 4 clustere

Un algoritm general de clusterizare ierarhică poate fi scris în pseudocod astfel:

Procedure Ierarhie(D;H)
array D(n,n),P(n)
List[] H
for i=1,n
P[i] = {i}
call add(H,{i})
endfor
for i=1,n-1
call Select(D,P;k,j)
P[k] = P[k] + P[j]
P[j] = {}
call add(H,P[k])
call Actualizare(D,k,j)
call Afisare(P)
endfor
return
end

Unde:
D - este matricea de distanțe
P - este un vector de liste de mulțimi (clusteri), utilizat pentru memorarea unei partiții. În listă sunt memorate valorile
index ale obiectelor/instanțelor din mulțime (indexul in tabelul de observații).
H - este o listă de mulțimi (clusteri) și reprezintă ierarhia. În final H va avea 2n-1 elemente (n clusteri de start, n-1
clusteri obținuți în cele n-1 joncțiuni ale algoritmului).
Procedurile Select și Actualizare individualizează fiecare implementare. Procedura Select implementează principiul
de grupare iar procedura Actualizare recalculează distanțele după joncțiune. Procedura Add adaugă un cluster la
ierarhie.
Toate metodele de grupare ierarhică urmează acest algoritm. Diferențele sunt date de modul în care se aleg clusterii
care joncționează la un moment dat și de modul în care sunt actualizate distanțele după joncționare.
Metode de grupare ierarhică
1. Gruparea prin legătură simplă. Selecția clusterilor se face prin distanța minimă. Actualizarea distanțelor după
joncționare se face după relația:
d 2 (hs  hr , hi )  Minimd 2

(hs , hi ), d 2 (hs , hi ) ,

unde hs și hr sunt clusterii selectați pentru joncționare, iar hi este unul dintre clusterii rămași.
Exemplu.
Sunt prezentate în continuare agregările şi construirea dendogramei pornind de la un tabel de distanțe pentru
5 indivizi.
1 2 3 4 5 1 24 3 5
1 0 4 9 5 8 1 0 4 9 8
2 4 0 6 3 6 24 4 0 6 5
3 9 6 0 6 3 3 9 6 0 3
4 5 3 6 0 5 5 8 5 3 0
5 8 6 3 5 0
Distanțele inițiale Distanțele dintre 2-4 și restul
1 24 35 124 35
1 0 4 8 124 0 5
24 4 0 5 35 5 0
35 8 5 0
Distanțele dintre 3-5 și restul Distanțele dintre 1-2-4 și 3-5

Graficul dendrogramă Distanțe

5
4
3
2
1
0
1 2 4 3 5
Dendrograma

2. Gruparea prin legătură completă. Selecția clusterilor se face prin distanța minimă. Actualizarea distanțelor după
 
joncționare se face după relația: d 2 (hs  hr , hi )  Maxim d 2 (hs , hi ), d 2 (hs , hi ) .

3. Gruparea prin legătură medie. Selecția clusterilor se face prin distanța minimă. Actualizarea distanțelor după
joncționare se face după relația:
 d 2 (hs , hi )  d 2 (hs , hi )
 Medie neponderat ă
 2
d 2 (hs  hr , hi )  
 ns  d (hs , hi )  nr  d (hr , hi )
2 2
Medie ponderată
 n s  nr
unde:
nr - numărul de indivizi din hr
ns - numărul de indivizi din hs.

4. Metoda centroidă. Selecția clusterilor se face prin distanța minimă. Actualizarea distanțelor după joncționare se
face după relația:
 d 2 ( g s , g i )  d 2 ( g r , hi )
 Medie neponderat ă
 2
d 2 (hs  hr , hi )  
 n s  d ( g s , g i )  nr  d ( g r , g i )
2 2
Medie ponderată

 n s  nr
unde gs și gr sunt centrii clusterilor hs și hr.

5. Metoda varianței minime sau Ward. Se bazează pe descompunerea varianței totale în varianță intra-clase și varianță
inter-clase.
Fie q numărul grupelor (clusterilor) existente la un moment dat. Varianțele totală, intra-clase și inter-clase sunt definite
astfel:

 x 
n m
1 2
T= ij xj - varianța totală,
n i 1 j 1
 q

 x 
m


nk 1
W=  ij  g kj 2 - varianța intra-clase,
k 1
n nk ihk j 1

  g  - varianța inter-clase,
q m
nk 2
B= kj  x j
k 1
n j 1

unde X este tabelul de observații cu termenul general xij, x j este media generală pentru variabila Xj, gkj este media
variabilei Xj pentru grupa k.

Varianța totală este constantă indiferent cum se împart instanțele pe clusteri. Varianțele intra-clasă și inter-
clasă sunt însă dependente de modul în care se împart instanțele pe clusteri. O împărțire este cu atât mai bună cu cât
clusterii sunt mai omogeni, adică varianța intra-clasa va fi mai mică iar varianța inter-clasă va fi mai mare.
La nivelul cel mai de jos, când fiecare din cele n instanțe constituie câte un cluster, varianța intra-clasă este
nulă în timp ce varianța inter-clasă este maximă. Dacă se agregă doi clusteri, varianța intra-clasă crește (clusterul
format fiind mai puțin omogen) iar varianța inter-clasă scade. Când toate instanțele sunt grupate într-un singur cluster,
varianța intra-clasă crește la valoarea maximă în timp ce varianța inter-clasă scade la 0.
Presupunem că la un moment dat sunt agregate doi clusteri hr și hs. Noul cluster pe care îl notăm cu hrs conține
nr+ns instanțe.
Presupunem datele centrate și modelul simplificat la o singură variabilă.
𝑛 𝑛 𝑛 +𝑛
Varianțele inter-clase datorate clusterilor hr, hs și hrs sunt: Br = 𝑟 𝑔𝑟2 , Bs = 𝑠 𝑔𝑠2 , Brs = 𝑟 𝑠 𝑔𝑟𝑠
2
,
𝑛 𝑛 𝑛
2 𝑛𝑟 𝑔𝑟+ 𝑛𝑠 𝑔𝑠
unde 𝑔𝑟𝑠 = .
𝑛𝑟 +𝑛𝑠
Diferența de varianță inter-clase va fi:
𝑛𝑟+𝑛𝑠 (𝑛𝑟𝑔𝑟 +𝑛𝑠 𝑔𝑠 )2 𝑛 𝑛
Brs - Br - Bs = ∙ (𝑛𝑟+𝑛𝑠 )2
− 𝑟 𝑔𝑟2 − 𝑠 𝑔𝑠2 =
𝑛 𝑛 𝑛
𝑛𝑟2 𝑔𝑟2 +𝑛𝑠2 𝑔𝑠2 +2𝑛𝑟 𝑛𝑠 𝑔𝑟 𝑔𝑠 −𝑛𝑟2 𝑔𝑟2 −𝑛𝑟𝑛𝑠 𝑔𝑟2 −𝑛𝑟 𝑛𝑠 𝑔𝑠2 −𝑛𝑠2 𝑔𝑠2 𝑛𝑟 𝑛𝑠 ∙(𝑔𝑟 −𝑔𝑠 )2 𝑛𝑟 𝑛𝑠
=− =− ∙ 𝑑 2 (𝑔𝑟 , 𝑔𝑠 ),
𝑛(𝑛𝑟 +𝑛𝑠 ) 𝑛(𝑛𝑟 +𝑛𝑠 ) 𝑛(𝑛𝑟 +𝑛𝑠 )
unde 𝑑 2 (𝑔𝑟 , 𝑔𝑠 ) = (𝑔𝑟 − 𝑔𝑠 )2 este distanța dintre centrii clusterilor hr și hs.
Diferența este negativă deoarece varianța inter-clase scade. Varianța intra-clasă crește, iar creșterea va fi egală cu
pierderea de varianță inter-clase. Deci  rs , creșterea de varianță intra-clasă obținută prin juncțiuniea clusterilor hr și
hs va fi  rs = 𝑛(𝑛 +𝑛 ) ∙ 𝑑2 (𝑔𝑟 , 𝑔𝑠 ).
𝑛𝑟 𝑛𝑠
𝑟 𝑠

După criteriul Ward se agregă la o etapă oarecare acele două clustere hr și hs astfel încât  rs să fie
minimă.

Alegerea numărului optim de clusteri

Criterii de alegere a numărului de clusteri:

- Natura problemei. În funcție de scopul urmărit în analiză, numărul de grupe poate fi mai mare sau mai mic.
Decizia aparține specialistului din domeniul în care este efectuată analiza.
- Variația distanței de agregare. Se alege partiția care corespunde diferenței maxime de distanță.
În figura de mai jos este aplicat criteriul variației distanței de agregare.

Figura 3. Împărțire în patru și în doi clusteri după criteriul variației distanței