analisi dei gruppi seconda parte. argomenti della lezione distanze metodi gerarchici: legame singolo...
TRANSCRIPT
![Page 1: ANALISI DEI GRUPPI seconda parte. Argomenti della lezione Distanze Metodi gerarchici: legame singolo e legame completo](https://reader036.vdocumenti.com/reader036/viewer/2022062319/5542eb50497959361e8bf3b8/html5/thumbnails/1.jpg)
ANALISI DEI GRUPPI seconda parte
ANALISI DEI GRUPPI seconda parte
![Page 2: ANALISI DEI GRUPPI seconda parte. Argomenti della lezione Distanze Metodi gerarchici: legame singolo e legame completo](https://reader036.vdocumenti.com/reader036/viewer/2022062319/5542eb50497959361e8bf3b8/html5/thumbnails/2.jpg)
Argomenti della lezioneArgomenti della lezione
Distanze Distanze
Metodi gerarchici: legame singolo e legame completo
Metodi gerarchici: legame singolo e legame completo
![Page 3: ANALISI DEI GRUPPI seconda parte. Argomenti della lezione Distanze Metodi gerarchici: legame singolo e legame completo](https://reader036.vdocumenti.com/reader036/viewer/2022062319/5542eb50497959361e8bf3b8/html5/thumbnails/3.jpg)
Per i dati di tipo quantitativo si
ricorre alle distanze
Per i dati di tipo quantitativo si
ricorre alle distanze
![Page 4: ANALISI DEI GRUPPI seconda parte. Argomenti della lezione Distanze Metodi gerarchici: legame singolo e legame completo](https://reader036.vdocumenti.com/reader036/viewer/2022062319/5542eb50497959361e8bf3b8/html5/thumbnails/4.jpg)
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
![Page 5: ANALISI DEI GRUPPI seconda parte. Argomenti della lezione Distanze Metodi gerarchici: legame singolo e legame completo](https://reader036.vdocumenti.com/reader036/viewer/2022062319/5542eb50497959361e8bf3b8/html5/thumbnails/5.jpg)
Distanza di MinkowskiDistanza di Minkowski
pp
k=1k=1
rdijrdij xik - xjkxik - xjk
rr 1/r1/r
![Page 6: ANALISI DEI GRUPPI seconda parte. Argomenti della lezione Distanze Metodi gerarchici: legame singolo e legame completo](https://reader036.vdocumenti.com/reader036/viewer/2022062319/5542eb50497959361e8bf3b8/html5/thumbnails/6.jpg)
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
![Page 7: ANALISI DEI GRUPPI seconda parte. Argomenti della lezione Distanze Metodi gerarchici: legame singolo e legame completo](https://reader036.vdocumenti.com/reader036/viewer/2022062319/5542eb50497959361e8bf3b8/html5/thumbnails/7.jpg)
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
![Page 8: ANALISI DEI GRUPPI seconda parte. Argomenti della lezione Distanze Metodi gerarchici: legame singolo e legame completo](https://reader036.vdocumenti.com/reader036/viewer/2022062319/5542eb50497959361e8bf3b8/html5/thumbnails/8.jpg)
Matrice delle dissomiglianzeMatrice delle dissomiglianze
DD
00
00
00
d21d21
dn1dn1 dn2dn2
d2nd2n
d1nd1nd12d12
……
……
………………
……
……
![Page 9: ANALISI DEI GRUPPI seconda parte. Argomenti della lezione Distanze Metodi gerarchici: legame singolo e legame completo](https://reader036.vdocumenti.com/reader036/viewer/2022062319/5542eb50497959361e8bf3b8/html5/thumbnails/9.jpg)
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
![Page 10: ANALISI DEI GRUPPI seconda parte. Argomenti della lezione Distanze Metodi gerarchici: legame singolo e legame completo](https://reader036.vdocumenti.com/reader036/viewer/2022062319/5542eb50497959361e8bf3b8/html5/thumbnails/10.jpg)
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:
![Page 11: ANALISI DEI GRUPPI seconda parte. Argomenti della lezione Distanze Metodi gerarchici: legame singolo e legame completo](https://reader036.vdocumenti.com/reader036/viewer/2022062319/5542eb50497959361e8bf3b8/html5/thumbnails/11.jpg)
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
![Page 12: ANALISI DEI GRUPPI seconda parte. Argomenti della lezione Distanze Metodi gerarchici: legame singolo e legame completo](https://reader036.vdocumenti.com/reader036/viewer/2022062319/5542eb50497959361e8bf3b8/html5/thumbnails/12.jpg)
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
![Page 13: ANALISI DEI GRUPPI seconda parte. Argomenti della lezione Distanze Metodi gerarchici: legame singolo e legame completo](https://reader036.vdocumenti.com/reader036/viewer/2022062319/5542eb50497959361e8bf3b8/html5/thumbnails/13.jpg)
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
![Page 14: ANALISI DEI GRUPPI seconda parte. Argomenti della lezione Distanze Metodi gerarchici: legame singolo e legame completo](https://reader036.vdocumenti.com/reader036/viewer/2022062319/5542eb50497959361e8bf3b8/html5/thumbnails/14.jpg)
Metodi di aggregazione gerarchica:
Metodi di aggregazione gerarchica:
legame semplice legame semplice
legame completo legame completo
legame medio legame medio
di Ward di Ward
![Page 15: ANALISI DEI GRUPPI seconda parte. Argomenti della lezione Distanze Metodi gerarchici: legame singolo e legame completo](https://reader036.vdocumenti.com/reader036/viewer/2022062319/5542eb50497959361e8bf3b8/html5/thumbnails/15.jpg)
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
![Page 16: ANALISI DEI GRUPPI seconda parte. Argomenti della lezione Distanze Metodi gerarchici: legame singolo e legame completo](https://reader036.vdocumenti.com/reader036/viewer/2022062319/5542eb50497959361e8bf3b8/html5/thumbnails/16.jpg)
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)
![Page 17: ANALISI DEI GRUPPI seconda parte. Argomenti della lezione Distanze Metodi gerarchici: legame singolo e legame completo](https://reader036.vdocumenti.com/reader036/viewer/2022062319/5542eb50497959361e8bf3b8/html5/thumbnails/17.jpg)
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]
![Page 18: ANALISI DEI GRUPPI seconda parte. Argomenti della lezione Distanze Metodi gerarchici: legame singolo e legame completo](https://reader036.vdocumenti.com/reader036/viewer/2022062319/5542eb50497959361e8bf3b8/html5/thumbnails/18.jpg)
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
![Page 19: ANALISI DEI GRUPPI seconda parte. Argomenti della lezione Distanze Metodi gerarchici: legame singolo e legame completo](https://reader036.vdocumenti.com/reader036/viewer/2022062319/5542eb50497959361e8bf3b8/html5/thumbnails/19.jpg)
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
![Page 20: ANALISI DEI GRUPPI seconda parte. Argomenti della lezione Distanze Metodi gerarchici: legame singolo e legame completo](https://reader036.vdocumenti.com/reader036/viewer/2022062319/5542eb50497959361e8bf3b8/html5/thumbnails/20.jpg)
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
![Page 21: ANALISI DEI GRUPPI seconda parte. Argomenti della lezione Distanze Metodi gerarchici: legame singolo e legame completo](https://reader036.vdocumenti.com/reader036/viewer/2022062319/5542eb50497959361e8bf3b8/html5/thumbnails/21.jpg)
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
![Page 22: ANALISI DEI GRUPPI seconda parte. Argomenti della lezione Distanze Metodi gerarchici: legame singolo e legame completo](https://reader036.vdocumenti.com/reader036/viewer/2022062319/5542eb50497959361e8bf3b8/html5/thumbnails/22.jpg)
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
![Page 23: ANALISI DEI GRUPPI seconda parte. Argomenti della lezione Distanze Metodi gerarchici: legame singolo e legame completo](https://reader036.vdocumenti.com/reader036/viewer/2022062319/5542eb50497959361e8bf3b8/html5/thumbnails/23.jpg)
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
![Page 24: ANALISI DEI GRUPPI seconda parte. Argomenti della lezione Distanze Metodi gerarchici: legame singolo e legame completo](https://reader036.vdocumenti.com/reader036/viewer/2022062319/5542eb50497959361e8bf3b8/html5/thumbnails/24.jpg)
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
![Page 25: ANALISI DEI GRUPPI seconda parte. Argomenti della lezione Distanze Metodi gerarchici: legame singolo e legame completo](https://reader036.vdocumenti.com/reader036/viewer/2022062319/5542eb50497959361e8bf3b8/html5/thumbnails/25.jpg)
(BD)(BD)
(ACE)(ACE) 00
(ACE)(ACE) (BD)(BD)
66 00
La matrice finale è la seguente:
La matrice finale è la seguente:
![Page 26: ANALISI DEI GRUPPI seconda parte. Argomenti della lezione Distanze Metodi gerarchici: legame singolo e legame completo](https://reader036.vdocumenti.com/reader036/viewer/2022062319/5542eb50497959361e8bf3b8/html5/thumbnails/26.jpg)
La fusione finale avviene quindi ad una
distanza pari 6
La fusione finale avviene quindi ad una
distanza pari 6
Passo 5Passo 5
![Page 27: ANALISI DEI GRUPPI seconda parte. Argomenti della lezione Distanze Metodi gerarchici: legame singolo e legame completo](https://reader036.vdocumenti.com/reader036/viewer/2022062319/5542eb50497959361e8bf3b8/html5/thumbnails/27.jpg)
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
![Page 28: ANALISI DEI GRUPPI seconda parte. Argomenti della lezione Distanze Metodi gerarchici: legame singolo e legame completo](https://reader036.vdocumenti.com/reader036/viewer/2022062319/5542eb50497959361e8bf3b8/html5/thumbnails/28.jpg)
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
![Page 29: ANALISI DEI GRUPPI seconda parte. Argomenti della lezione Distanze Metodi gerarchici: legame singolo e legame completo](https://reader036.vdocumenti.com/reader036/viewer/2022062319/5542eb50497959361e8bf3b8/html5/thumbnails/29.jpg)
Legame completoLegame
completo
![Page 30: ANALISI DEI GRUPPI seconda parte. Argomenti della lezione Distanze Metodi gerarchici: legame singolo e legame completo](https://reader036.vdocumenti.com/reader036/viewer/2022062319/5542eb50497959361e8bf3b8/html5/thumbnails/30.jpg)
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]
![Page 31: ANALISI DEI GRUPPI seconda parte. Argomenti della lezione Distanze Metodi gerarchici: legame singolo e legame completo](https://reader036.vdocumenti.com/reader036/viewer/2022062319/5542eb50497959361e8bf3b8/html5/thumbnails/31.jpg)
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
![Page 32: ANALISI DEI GRUPPI seconda parte. Argomenti della lezione Distanze Metodi gerarchici: legame singolo e legame completo](https://reader036.vdocumenti.com/reader036/viewer/2022062319/5542eb50497959361e8bf3b8/html5/thumbnails/32.jpg)
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
![Page 33: ANALISI DEI GRUPPI seconda parte. Argomenti della lezione Distanze Metodi gerarchici: legame singolo e legame completo](https://reader036.vdocumenti.com/reader036/viewer/2022062319/5542eb50497959361e8bf3b8/html5/thumbnails/33.jpg)
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
![Page 34: ANALISI DEI GRUPPI seconda parte. Argomenti della lezione Distanze Metodi gerarchici: legame singolo e legame completo](https://reader036.vdocumenti.com/reader036/viewer/2022062319/5542eb50497959361e8bf3b8/html5/thumbnails/34.jpg)
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
![Page 35: ANALISI DEI GRUPPI seconda parte. Argomenti della lezione Distanze Metodi gerarchici: legame singolo e legame completo](https://reader036.vdocumenti.com/reader036/viewer/2022062319/5542eb50497959361e8bf3b8/html5/thumbnails/35.jpg)
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
![Page 36: ANALISI DEI GRUPPI seconda parte. Argomenti della lezione Distanze Metodi gerarchici: legame singolo e legame completo](https://reader036.vdocumenti.com/reader036/viewer/2022062319/5542eb50497959361e8bf3b8/html5/thumbnails/36.jpg)
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
![Page 37: ANALISI DEI GRUPPI seconda parte. Argomenti della lezione Distanze Metodi gerarchici: legame singolo e legame completo](https://reader036.vdocumenti.com/reader036/viewer/2022062319/5542eb50497959361e8bf3b8/html5/thumbnails/37.jpg)
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
![Page 38: ANALISI DEI GRUPPI seconda parte. Argomenti della lezione Distanze Metodi gerarchici: legame singolo e legame completo](https://reader036.vdocumenti.com/reader036/viewer/2022062319/5542eb50497959361e8bf3b8/html5/thumbnails/38.jpg)
Dendrogramma della procedura di
aggregazione con il legame completo
Dendrogramma della procedura di
aggregazione con il legame completo
![Page 39: ANALISI DEI GRUPPI seconda parte. Argomenti della lezione Distanze Metodi gerarchici: legame singolo e legame completo](https://reader036.vdocumenti.com/reader036/viewer/2022062319/5542eb50497959361e8bf3b8/html5/thumbnails/39.jpg)
11IndividuiIndividui
Dis
tan
ze
00
22
44
66
88
1010
1212
22 44 33 55