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