Post on 01-May-2015
ANALISI DEI GRUPPI seconda parte
ANALISI DEI GRUPPI seconda parte
Argomenti della lezioneArgomenti della lezione
Distanze Distanze
Metodi gerarchici: legame singolo e legame completo
Metodi gerarchici: legame singolo e legame completo
Per i dati di tipo quantitativo si
ricorre alle distanze
Per i dati di tipo quantitativo si
ricorre alle distanze
Una distanza possiede le seguenti proprietà:
Una distanza possiede le seguenti proprietà:
identità dii = 0identità dii = 0
simmetria dij = djisimmetria dij = dji
non negatività dij ≥ = 0non negatività dij ≥ = 0
disuguaglianza triangolare dil + dlj ≤ = dij
disuguaglianza triangolare dil + dlj ≤ = dij
Distanza di MinkowskiDistanza di Minkowski
pp
k=1k=1
rdijrdij xik - xjkxik - xjk
rr 1/r1/r
Per r = 2 si ha la distanza euclidea
Per r = 2 si ha la distanza euclidea
pp
k=1k=1
2dij2dij xik - xjkxik - xjk
22 1/r1/r
Distanza di MahalanobisDistanza di Mahalanobis
in cuiin cui
shk indica il generico elemento della matrice inversa delle varianze-
covarianze tra le p variabili
shk indica il generico elemento della matrice inversa delle varianze-
covarianze tra le p variabili
pp
k=1k=1
dijdij (xik - xjk) (xih - xjh)(xik - xjk) (xih - xjh)
1/21/2
pp
h=1h=1
shk shk
Matrice delle dissomiglianzeMatrice delle dissomiglianze
DD
00
00
00
d21d21
dn1dn1 dn2dn2
d2nd2n
d1nd1nd12d12
……
……
………………
……
……
Algoritmi gerarchici Algoritmi gerarchici
Gli algoritmi gerarchici procedono sia per mezzo di una serie di
aggregazioni successive o una serie di successive divisioni. Gli
algoritmi aggregativi iniziano con tutte
le unità distinte, così vi sono tanti gruppi quanti sono gli oggetti da
classificare
Gli algoritmi gerarchici procedono sia per mezzo di una serie di
aggregazioni successive o una serie di successive divisioni. Gli
algoritmi aggregativi iniziano con tutte
le unità distinte, così vi sono tanti gruppi quanti sono gli oggetti da
classificare
I passaggi di un algoritmo aggregativo gerarchico applicato ad un insieme di n unità
sono i seguenti:
I passaggi di un algoritmo aggregativo gerarchico applicato ad un insieme di n unità
sono i seguenti:
Si individua nella matrice delle distanze la coppia più vicina (più simile), ad esempio quella formata dai gruppi U e V
Si individua nella matrice delle distanze la coppia più vicina (più simile), ad esempio quella formata dai gruppi U e V
Si inizia con n gruppi contenenti ciascuno una sola unità e una matrice di distanze simmetrica nxn
Si inizia con n gruppi contenenti ciascuno una sola unità e una matrice di distanze simmetrica nxn
22
11
Si raggruppano U e V in un unico gruppo etichettato come (UV). Si aggiorna la matrice delle distanze cancellando le righe e le colonne corrispondenti ai clusters U e V e aggiungendo una riga e una colonna che riporta le distanze tra il gruppo (UV) e i restanti clusters
Si raggruppano U e V in un unico gruppo etichettato come (UV). Si aggiorna la matrice delle distanze cancellando le righe e le colonne corrispondenti ai clusters U e V e aggiungendo una riga e una colonna che riporta le distanze tra il gruppo (UV) e i restanti clusters
33
Si ripetono i passi 2 e 3 per un totale di n-1 volte. Tutti gli oggetti sono raggruppati
in un unico gruppo al termine della procedura.
Si ripetono i passi 2 e 3 per un totale di n-1 volte. Tutti gli oggetti sono raggruppati
in un unico gruppo al termine della procedura.
44
Metodi di aggregazione gerarchica:
Metodi di aggregazione gerarchica:
legame semplice legame semplice
legame completo legame completo
legame medio legame medio
di Ward di Ward
Distanza tra gruppi (dissimilarità) per (a)
legame singolo, (b) legame completo,
e (c) legame medio
Distanza tra gruppi (dissimilarità) per (a)
legame singolo, (b) legame completo,
e (c) legame medio
Cluster distanceCluster distance
d13+ d14 + d15 + d23 + d24 + d25d13+ d14 + d15 + d23 + d24 + d25
66
(c)(c)
11
22
33
4455
d15d15
(b)(b)
11
22
33
4455
d24d24
11
22
33
4455
(a)(a)
Legame sempliceLegame semplice
Le distanze tra i gruppi sono formate considerando la più
piccola delle distanze istituibili a due a due tra tutti gli elementi dei
due gruppi:
Le distanze tra i gruppi sono formate considerando la più
piccola delle distanze istituibili a due a due tra tutti gli elementi dei
due gruppi:
d(UV)W = min [ dUW , dVW]d(UV)W = min [ dUW , dVW]
EsempioEsempio
individuiindividui
AA
BB
CC
DD
EE
00
99
33
66
1111
AA
00
77
55
1010
BB
00
99
22
CC
00
88
DD
00
EE
Passo 1Passo 1
I due individui più vicini sono l'individuo C
e l'individuo E
I due individui più vicini sono l'individuo C
e l'individuo E
min ij (dij) = dCE = 2min ij (dij) = dCE = 2
Passo 2Passo 2
Le distanze tra il gruppo (CE) e i rimanenti oggetti sono calcolate
con il metodo del legame singolo:
Le distanze tra il gruppo (CE) e i rimanenti oggetti sono calcolate
con il metodo del legame singolo:
d(CE),A = min [ d CA, d EA] = min [3,11] =3 d(CE),A = min [ d CA, d EA] = min [3,11] =3
d(CE),B = min [ d CB, d EB] = min [7,10] =7 d(CE),B = min [ d CB, d EB] = min [7,10] =7
d(CE),D = min [ d CD, d ED] = min [9,8] =8 d(CE),D = min [ d CD, d ED] = min [9,8] =8
AA
BB
DD
(CE)(CE) 00
77
88
(CE)(CE)
99
66
AA
55
BB DD
33 00
00
00
Si ottiene quindi la nuova matrice delle dissomiglianze
Si ottiene quindi la nuova matrice delle dissomiglianze
La distanza minima è ora quella d(CE)A = 3
e quindi uniamo il gruppo A al gruppo CE. Procediamo successivamente a calcolare
le nuove distanze:
La distanza minima è ora quella d(CE)A = 3
e quindi uniamo il gruppo A al gruppo CE. Procediamo successivamente a calcolare
le nuove distanze:
d (ACE)B = min [d(CE)B, d AB] = min[7,9] = 7d (ACE)B = min [d(CE)B, d AB] = min[7,9] = 7
d (ACE)D = min [d(CE)D, d AD] = min[8,6] =6d (ACE)D = min [d(CE)D, d AD] = min[8,6] =6
Passo 3Passo 3
La nuova matrice delle dissomiglianze è la seguente:
La nuova matrice delle dissomiglianze è la seguente:
BB
DD
(ACE)(ACE) 00
66
(ACE)(ACE)
55
BB DD
77 00
00
Ora la distanza minore tra i cluster è dBD =5, e a questo punto
otteniamo due gruppi, (ACE) e (BD). La loro distanza secondo la
regola del legame singolo è
Ora la distanza minore tra i cluster è dBD =5, e a questo punto
otteniamo due gruppi, (ACE) e (BD). La loro distanza secondo la
regola del legame singolo è
d(ACE)(BD) = min [d(ACE)B, d(ACE),D] =
= min [7,6] = 6
d(ACE)(BD) = min [d(ACE)B, d(ACE),D] =
= min [7,6] = 6
Passo 4Passo 4
(BD)(BD)
(ACE)(ACE) 00
(ACE)(ACE) (BD)(BD)
66 00
La matrice finale è la seguente:
La matrice finale è la seguente:
La fusione finale avviene quindi ad una
distanza pari 6
La fusione finale avviene quindi ad una
distanza pari 6
Passo 5Passo 5
I rami dell'albero rappresentano i cluster. I rami si uniscono in nodi le cui posizioni lungo l'asse delle distanze (o delle dissomiglianze) indicano il livello in cui avviene
la fusione
I rami dell'albero rappresentano i cluster. I rami si uniscono in nodi le cui posizioni lungo l'asse delle distanze (o delle dissomiglianze) indicano il livello in cui avviene
la fusione
I risultati di una procedura di cluster gerarchica possono essere
rappresentati dal dendrogramma o diagramma ad albero
I risultati di una procedura di cluster gerarchica possono essere
rappresentati dal dendrogramma o diagramma ad albero
Dis
tan
za
0
2
4
6
1 3 5 2 4Individui
Dendrogramma della procedura di aggregazione con il legame singoloDendrogramma della procedura di aggregazione con il legame singolo
Legame completoLegame
completo
Ad ogni passo la distanza (similarità) tra i gruppi è stabilita considerando i due
elementi più lontani (dissimili) nei due gruppi. In questo modo la procedura
del legame completo assicura che tutti gli elementi all'interno di un gruppo siano
comprese ad una distanza massima (o somiglianza minima) l'uno dall'altro
Ad ogni passo la distanza (similarità) tra i gruppi è stabilita considerando i due
elementi più lontani (dissimili) nei due gruppi. In questo modo la procedura
del legame completo assicura che tutti gli elementi all'interno di un gruppo siano
comprese ad una distanza massima (o somiglianza minima) l'uno dall'altro
d(UV)W = max [dUW, dVW]d(UV)W = max [dUW, dVW]
EsempioEsempio
individuiindividui
AA
BB
CC
DD
EE
00
99
33
66
1111
AA
00
77
55
1010
BB
00
99
22
CC
00
88
DD
00
EE
Passo 1Passo 1
I due individui più vicini sono l'individuo C
e l'individuo E
I due individui più vicini sono l'individuo C
e l'individuo E
min ij (dij) = dCE = 2min ij (dij) = dCE = 2
Calcoliamo le distanze tra il gruppo (CE) e i restanti con il metodo del
legame completo
Calcoliamo le distanze tra il gruppo (CE) e i restanti con il metodo del
legame completo
d(CE),A = max [ d CA, d EA] = max [3,11] =11 d(CE),A = max [ d CA, d EA] = max [3,11] =11
d(CE),B = max [ d CB, d EB] = max [7,10] =10 d(CE),B = max [ d CB, d EB] = max [7,10] =10
d(CE),D = max [ d CD, d ED] = max [9,8] =9 d(CE),D = max [ d CD, d ED] = max [9,8] =9
Passo 2Passo 2
La nuova matrice delle distanze è la seguente:La nuova matrice delle distanze è la seguente:
AA
BB
DD
(CE)(CE) 00
1010
99
(CE)(CE)
99
66
AA
55
BB DD
1111 00
00
00
La fusione successiva avviene tra i gruppi B e D. Le nuove distanze
da calcolare sono le seguenti:
La fusione successiva avviene tra i gruppi B e D. Le nuove distanze
da calcolare sono le seguenti:
d(BD)(CE) = max [d B(CE), d D(CE)] =
= max =[10,9] =10
d(BD)(CE) = max [d B(CE), d D(CE)] =
= max =[10,9] =10
Passo 3Passo 3
e la matrice delle distanze è la seguente:
e la matrice delle distanze è la seguente:
(BD)(BD)
AA
(ACE)(ACE) 00
1111
(ACE)(ACE)
99
(BD)(BD) AA
1010 00
00
La fusione seguente produce il gruppo (ABD). Nel passo finale
i gruppi (CE) e (ABD) sono raggruppati nella fusione finale.
La fusione seguente produce il gruppo (ABD). Nel passo finale
i gruppi (CE) e (ABD) sono raggruppati nella fusione finale.Il dendrogramma che rappresenta la procedura di aggregazione
è il seguente
Il dendrogramma che rappresenta la procedura di aggregazione
è il seguente
Passo 4Passo 4
Dendrogramma della procedura di
aggregazione con il legame completo
Dendrogramma della procedura di
aggregazione con il legame completo
11IndividuiIndividui
Dis
tan
ze
00
22
44
66
88
1010
1212
22 44 33 55