ANALISI DEI GRUPPI
seconda parte
Argomenti della lezione
 Distanze
 Metodi gerarchici:
legame singolo e legame
completo
Per i dati di tipo
quantitativo si
ricorre alle distanze
Una distanza possiede le
seguenti proprietà:
identità
dii = 0
simmetria
dij = dji
non negatività
dij ≥ = 0
disuguaglianza triangolare
dil + dlj ≤ = dij
Distanza di Minkowski
p
rd
ij
=

k=1
r
xik - xjk
1/r
Per r = 2
si ha la distanza euclidea
p
2d
ij
=

k=1
2
xik - xjk
1/r
Distanza di Mahalanobis
p
dij =
p

k=1 h=1
1/2
shk (xik - xjk) (xih - xjh)
in cui
shk indica il generico elemento
della matrice inversa delle varianzecovarianze tra le p variabili
Matrice delle dissomiglianze
D =
0
d21
…
dn1
d12 … d1n
0 … d2n
… … …
dn2 … 0
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
I passaggi di un
algoritmo aggregativo
gerarchico applicato ad
un insieme di n unità
sono i seguenti:
1 Si inizia con n gruppi contenenti
ciascuno una sola unità e una
matrice di distanze simmetrica nxn
2 Si individua nella matrice delle
distanze la coppia più vicina
(più simile), ad esempio quella
formata dai gruppi U e V
3 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
4
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.
Metodi di aggregazione
gerarchica:

legame semplice

legame completo

legame medio

di Ward
Distanza tra gruppi
(dissimilarità) per (a)
legame singolo,
(b) legame completo,
e (c) legame medio
Cluster distance
3
1
4
2
d24
5
(a)
3
1
4
2
d15
5
(b)
3
1
4
2
(c)
5
d13+ d14 + d15 + d23 + d24 + d25
6
Legame 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:
d(UV)W = min [ dUW , dVW]
Esempio
Passo 1
individui
A
A
0
B
9
0
C
3
7
0
D
6
5
9
0
E
11
10
2
8
B
C
D
E
0
I due individui più vicini
sono l'individuo C
e l'individuo E
min
ij
(dij) = dCE = 2
Passo 2
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),B = min [ d
CB,
d
EB]
= min [7,10] =7
d(CE),D = min [ d
CD,
d
ED]
= min [9,8] =8
Si ottiene quindi la nuova
matrice delle dissomiglianze
(CE)
A
B
(CE)
0
A
3
0
B
7
9
0
D
8
6
5
D
0
Passo 3
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] = 7
d
(ACE)D
= min [d(CE)D, d
AD]
= min[8,6] =6
La nuova matrice delle
dissomiglianze è la seguente:
(ACE)
(ACE)
B
D
0
B
7
0
D
6
5
0
Passo 4
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
La matrice finale è la
seguente:
(ACE)
(ACE)
0
(BD)
6
(BD)
0
Passo 5
La fusione finale
avviene quindi ad una
distanza pari 6
I risultati di una procedura di cluster
gerarchica possono essere
rappresentati dal dendrogramma
o diagramma ad albero
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
Dendrogramma della procedura di
aggregazione con il legame singolo
Distanza
6
4
2
0
1
3 5 2
Individui
4
Legame
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
d(UV)W = max [dUW, dVW]
Esempio
Passo 1
individui
A
A
0
B
9
0
C
3
7
0
D
6
5
9
0
E
11
10
2
8
B
C
D
E
0
I due individui più vicini
sono l'individuo C
e l'individuo E
min
ij
(dij) = dCE = 2
Passo 2
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),B = max [ d
CB,
d
EB]
= max [7,10] =10
d(CE),D = max [ d
CD,
d
ED]
= max [9,8] =9
La nuova matrice delle
distanze è la seguente:
(CE)
A
B
(CE)
0
A
11
0
B
10
9
0
D
9
6
5
D
0
Passo 3
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
=
e la matrice delle distanze è
la seguente:
(ACE)
(BD)
(ACE)
0
(BD)
10
0
A
11
9
A
0
Passo 4
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
Dendrogramma della
procedura di
aggregazione con
il legame completo
12
Distanze
10
8
6
4
2
0
1
2
4
3
Individui
5