ANALISI DEI
GRUPPI III
Argomenti della lezione
 Algoritmi gerarchici: legame
medio e metodo di Ward
 Algoritmi non gerarchici
 Determinazione del numero
dei gruppi e valutazione dei
risultati
Legame medio
La procedura del legame medio
considera la distanza tra due
individui come la media
aritmetica delle distanze tra
tutte le coppie in cui ogni
elemento della coppia
appartiene a un gruppo diverso
Le distanze tra il gruppo (UV)
e il gruppo W
sono determinate da:
∑∑
d(UV)W =
i
dik
k
N(UV)NW
dove
dik è la distanza tra l'unità i
appartenente al cluster (UV) e l'unità k
appartenente al cluster W
N(UV) e NW sono rispettivamente il
numero degli elementi appartenenti a
ciascun gruppo
Metodo di
Ward
Secondo questo metodo si riuniscono,
ad ogni tappa del processo, i due gruppi
dalla cui fusione deriva il minimo
incremento della devianza entro. Date n
unità statistiche, suddivise in G gruppi
di numerosità variabile Ng
(g = 1,2,…G) rispetto a p caratteri
osservati la devianza totale è pari a:
Dev(totale)
G
ng
=
p
= ∑ ∑ ∑ ( xikg - xk )2
g=1
i=1
k=1
La devianza totale è
scomponibile in devianza
entro (within) e devianza tra
(between)
La devianza entro è
data da
Dev(entro)
G
ng
=
p
= ∑ ∑ ∑ ( xikg - xk )2
g=1
i=1
k=1
e la devianza tra da
Dev(tra) =
G
p
= ∑ ∑ ( xikg - xk )2
g=1
k=1
dove
1
xk =
n
G
ng
∑ ∑
g=1
xikg
i=1
è il valore medio della variabile
nell'intero collettivo e
xkg
1
=
ng
ng
∑
xikg
i=1
è il valor medio della stessa
variabile nel g-mo gruppo
Metodi non
gerarchici
I metodi non gerarchici
(o di partizionamento iterativo)
mirano a classificare direttamente
le n unità in un numero G di gruppi
generando una sola partizione. Una
volta che sia stato fissato a priori
il numero G, le procedure non
gerarchiche si articolano nelle fasi
seguenti:
A determinazione di una partizione
iniziale degli n individui in G gruppi
(o determinazione dei seed points che
costituiscono i nuclei dei gruppi)
B spostamento successivo delle unità
tra i G gruppi, in modo da ottenere
la partizione che meglio risponde
ai concetti di omogeneità interna
ai gruppi e di eterogeneità tra gli
stessi
Algoritmo di
McQueen
(o delle k-medie)
A
si ripartiscono le unità
in G gruppi iniziali o si
determinano G centroidi
iniziali
B
si esamina la lista delle unità
assegnandole rispettivamente
al cluster il cui centroide è il più
vicino (usualmente si impiega
la distanza euclidea). Si ricalcola
il centroide sia per il gruppo che
riceve la nuova unità che per
il gruppo che la cede
C
si ripete il passo b) fino a
quando non si verificano più
cambiamenti di assegnazione
ai gruppi
Se si utilizza la distanza euclidea
la procedura di McQueen minimizza
implicitamente la devianza entro i
gruppi relativamente alle p variabili
ESEMPIO
Sia dato un insieme di
quattro unità (A,B,C,D)
sulle quali sono state
misurate le variabili x1 e x2
Caratteri
Unità
x1
x2
A
5
3
B
-1
1
C
1
-2
D
-3
-2
L’obiettivo è di dividere l’insieme in
due gruppi connotati dalla massima
omogeneità
Dividiamo arbitrariamente il
collettivo in due gruppi (AB) e (CD)
Le coordinate dei centroidi sono
rispettivamente
Caratteri
Gruppi
x1
x2
(AB)
2
2
(CD)
-1
-2
Calcoliamo la distanza euclidea
del punto A da ciascun centroide:
d2(A, (AB) = 10
d2(A, (CD) = 61
Poiche il punto A è piu vicino al
centroide del gruppo (AB) rispetto
all’altro gruppo non viene effettuata
la riassegnazione
Continuiamo calcolando le
distanze per il punto B
d2(A, (AB) = 10
d2(A, (CD) = 9
Poiché il punto B è più vicino
al gruppo (CD) che al gruppo (AB)
si procede alla sua riassegnazione
dando origine al gruppo (BCD)
Le nuove coordinate dei
centroidi sono le seguenti:
Caratteri
Gruppi
x1
x2
A
5
3
-1
-1
(BCD)
Di nuovo ciascuna unità
è controllata per la
riassegnazione. Le distanze
di ciascuna unità dai
centroidi dei gruppi sono
le seguenti
Unità
Gruppi
A
B
C
D
A
0
40
41
89
(BCD)
52
4
5
5
Non è necessaria alcuna
riassegnazione e il processo
termina
E’ buona norma di comportamento
replicare l’applicazione dell’algoritmo
utilizzato con diverse partizioni
iniziali e scegliere la migliore
secondo la regola di ottimizzazione
adottata
E’ opportuno rappresentare in forma
tabellare le coordinate dei centroidi
dei gruppi e le varianze interne a
ciascun gruppo
Individuazione
del numero dei gruppi
A
Rappresentazioni grafiche
per valutare il numero
ottimale di gruppi
Distanza tra i due gruppi
che si uniscono per
le soluzioni da dieci a uno
gruppi con l’algoritmo
gerarchico di Ward
Numero dei gruppi
10
9
8
7
6
5
4
3
2
1
300 400 500 600 700 800
Distanza tra i gruppi
900
B
dg =
Analisi degli incrementi
della distanza tra gruppi
g-1d
–
g
d (con g = 2,…, n-1)
Il numero g per cui è massima
la differenza dg identifica il numero
ottimo di gruppi, in quanto questi sono
ottimamente separati
C
Rapporto tra la devianza
tra i gruppi e la devianza
totale
Tale valore è tendenzialmente
decrescente al decrescere dei gruppi.
Si considera l’aggregazione che mostra
l’aggregazione relativa più
consistente. La procedura va arrestata
al passo che precede tale
aggregazione