Home

Federica EU

1/13

Massimo Aria » 11.Cluster Analysis Gerarchica

Metodi divisivi e agglomerativi

I metodi gerarchici di analisi dei gruppi possono essere divisivi o agglomerativi.

Il punto di partenza di un metodo gerarchico divisivo è rappresentato da una partizione formata da un unico gruppo comprendente l’intero insieme delle n unità statistiche considerate. Attraverso passi successivi, veene formata una gerarchia di partizioni ottenute dividendo il gruppo iniziale in gruppi via via più omogenei internamente.

Al contrario i metodi gerarchici agglomerativi partono da una partizione iniziale formata da n gruppi (o grappoli), ognuno formato da una sola unità, per giungere, attraverso successive fusioni dei grappoli meno distanti tra di loro, ad una situazione in cui si ha un solo grappolo che contiene tutte le n unità.

Nelle applicazioni pratiche, i metodi agglomerativi sono quelli maggiormente utilizzati in quanto consentono di costruire la gerarchia di partizioni con un costo computazionale notevolmente ridotto rispetto a quello che caratterizza i metodi divisivi.

Dendrogramma

Il risultato finale di un metodo gerarchico non è, quindi, una singola partizione delle n unità, ma una serie di partizioni nidificate che possono essere rappresentate graficamente attraverso un “dendrogramma” o “diagramma ad albero” nel quale sull’asse delle ordinate viene riportato il livello di distanza ultrametrica, mentre sull’asse delle ascisse vengono riportate le singole unità.

Ogni ramo del diagramma (linea verticale) corrisponde ad un grappolo (gruppo o cluster). La linea di congiunzione (orizzontale) di due o più rami individua il livello di distanza al quale i grappoli si fondono.

Dendrogramma.

Metodi per il calcolo delle distanze tra gruppi

I metodi gerarchici si distinguono per il modo in cui, dopo la l-esima fusione, vengono calcolate le distanze tra il nuovo grappolo ed i rimanenti.

Tra i numerosi metodi proposti in letteratura si ricordano:

metodo del legame singolo;
metodo del legame completo;
metodo del legame medio;
metodo del centroide;
metodo di Ward.

Metodo del legame singolo

Nel Metodo del legame singolo (Single-Linkage), detto anche del “vicino più prossimo” (Nearest Neighbor), la distanza tra i gruppi è posta pari alla più piccola delle distanze calcolabili a due a due tra tutti gli elementi dei due gruppi.
Se C e D sono due gruppi, la loro distanza, secondo questo metodo, è definita come la più piccola (il minimo) tra tutte le $n_1 \times n_2$ distanze che si possono calcolare tra ciascuna unità i di C e ciascuna unità j di D:
$d(C,D)=min(d_{ij})<br />$
Per ogni i appartenente a C e j appartenente a D.

L’adozione di questo algoritmo per la composizione dei gruppi evidenzia in maniera netta e decisamente più accentuata rispetto agli altri algoritmi tutte le similitudini e somiglianze tra gli elementi: privilegia l’omogeneità tra gli elementi del gruppo a scapito della differenziazione netta tra gruppi.
Il dendrogramma costruito su questa matrice ha i rami molto più corti ed è più compatto: questo proprio perché vengono valorizzate le somiglianze.

Metodo del legame singolo.

Metodo del legame completo

Nel Metodo del legame completo (Complete-Linkage), detto anche del “vicino più lontano” (Furthest Neighbor), si considera la maggiore delle distanze calcolate a due a due tra tutti gli elementi dei due gruppi. Si avrà quindi:
$d(C,D)=max(d_{ij})$
Per ogni i appartenente a C e j appartenente a D.
Si uniscono i due gruppi che presentano la più piccola distanza così definita.

Questo algoritmo di aggregazione evidenzia in maniera netta le differenze tra elementi: privilegia la differenza tra i gruppi piuttosto che l’omogeneità degli elementi di ogni gruppo.
Il dendrogramma costruito su questa matrice ha i rami molto più lunghi, i gruppi (e soprattutto i rami) si formano a distanze maggiori. In uno stesso range di valori, rispetto al legame singolo, gli elementi sono molto meno compatti e più diluiti.

Metodo del legame completo.

Metodo del legame medio

Nel Metodo del legame medio (Average-Linkage), si considera, come distanza tra due gruppi, la media di tutte le distanze calcolate a due a due tra tutti gli elementi dei due gruppi. Si avrà quindi:
$d\left( {C,D} \right) = \frac{1}{{n_1 n_2 }}\sum\limits_{i = 1}^{n_1 } {\sum\limits_{j = 2}^{n_2 } {d_{ij} } }<br />$
Per ogni i appartenente a C e j appartenente a D.
Si uniscono i due gruppi che presentano la più piccola distanza così definita.

L’adozione di questo algoritmo per la composizione dei gruppi semplifica notevolmente la composizione dell’albero costruito con l’algoritmo completo.
Essendo basato sulla media delle distanze, i risultati sono più attendibili e i gruppi risultano più omogenei e ben differenziati tra di loro.

Metodo del legame medio.

Metodo del centroide

Nel Metodo del centroide si considera, come distanza tra due gruppi, la distanza tra i rispettivi centroidi (o baricentri).
Per centroide si intende il vettore formato dai valori medi delle p variabili X considerate nella analisi dei gruppi.
Esso può essere considerato come il punto medio della nuvola dei punti che forma un determinato gruppo.

Se $\overline X_C$ e $\overline X_D$
sono i centroidi, allora avremo:

$d\left( {C,D} \right) = d\left( {\overline X_C , \overline X_D } \right)$

Metodo del centroide.

Metodo di Ward

Il Metodo di Ward segue un approccio differente da quelli già trattati sino ad ora.

Infatti, nei metodi del legame semplice, completo, ecc. una volta chiarita la modalità con cui si definisce la distanza tra due gruppi (i due punti più vicini, più lontani, ecc.) , il criterio agglomerativo è comunque sempre lo stesso:
“si uniscono i due gruppi che presentano minore distanza tra loro”.

Secondo il metodo di Ward, ad ogni passo della costruzione agglomerativa del dendrogramma, si uniscono i gruppi dalla cui “fusione” deriva il minimo incremento possibile della devianza “entro”.
Questo criterio trae quindi origine da un concetto ben noto in statistica: la scomposizione della devianza in Devianza tra i gruppi e Devianza entro i gruppi:

Dev(Totale)=Dev(tra)+Dev(entro)

$\sum\limits_{s = 1}^p {\sum\limits_{i = 1}^n {\left( {x_{is} - \overline x _s } \right)^2 } } = \sum\limits_{s = 1}^p {\sum\limits_{i = 1}^g {\left( {\overline x _{sk} - \overline x _s } \right)^2 \cdot n_k } } + \sum\limits_{k = 1}^g {\sum\limits_{s = 1}^p {\sum\limits_{i = 1}^n {\left( {x_{is} - \overline x _{sk} } \right)^2 } } }$

Nel passare da k+1 a k gruppi (aggregazione) Dev (entro) aumenta, mentre ovviamente Dev(tra) diminuisce. Ad ogni passo del metodo di Ward si aggregano tra loro quei gruppi per cui vi è il minor incremento della devianza entro i gruppi o, alternativamente, il maggior decremento della devianza tra i gruppi.

I passi dell’algoritmo agglomerativo

Un algoritmo di cluster analysis di tipo agglomerativo può essere descritto mediante le seguenti fasi:

a.
Calcolo della matrice delle distanze tra tutti i punti

b.
Analisi della matrice delle distanze e fusione delle sue unità aventi la distanza più piccola

c.
Calcolo della nuova matrice delle distanze (utilizzando il metodo del legame prescelto)

d.
Si ritorna al punto b ripetendo il processo fino a comprendere tutti gli elementi in un’unica classe

I passi dell’algoritmo : un esempio numerico

Scelta del numero dei gruppi

Una volta terminato il processo iterativo che per successive agglomerazioni porta alla costruzione del dendrogramma, è necessario scegliere il livello di taglio della gerarchia per la identificazione della partizione finale e del numero di gruppi che la comporranno.

Nel caso di una cluster gerarchica la scelta del numero di cluster può essere effettuata utilizzando in primo luogo la distanza di fusione.
La distanza di fusione è una distanza metrica opportunamente riscalata, attraverso uno dei metodi di aggregazione illustrati in precedenza (semplice, completo, ecc.), per godere della condizione di Krassner.
Se ne deduce quindi che la distanza metrica utilizzata, nel contesto della cluster gerarchica diventa una distanza ultrametrica che consente di misurare le distanze tra le diverse partizioni nidificate ottenute dall’analisi.

Scelta del numero dei gruppi (segue)

Un criterio possibile per la scelta del taglio, e quindi della partizione da “conservare” è il seguente:

se nel passaggio da g gruppi a g+1 si registra un forte incremento della distanza di fusione si deve “tagliare” a g gruppi.

Sempre utilizzando la distanza di fusione si possono utilizzare gli scree plot, grafici in cui viene posto in ordinata il numero di gruppi ed in ascissa la distanza di fusione.

Il taglio va effettuato nel tratto in cui la curvo riduce notevolmente la sua pendenza diventando quasi-piatta.

Scree Plot.

Taglio del dendrogramma.

Alcune osservazioni

L’applicazione di metodi gerarchici, come tutte le tecniche statistiche, reca con sé limiti e vantaggi.

I metodi gerarchici presuppongono indirettamente una regola classificatoria sottostante più o meno rispettata dalle unità, nella quale esse rientrano progressivamente. Ovviamente, se nel nostro contesto una tale regola non può essere ipotizzata, l’adozione di metodi gerarchici è abbastanza limitata in quanto può generare tipologie errate.

I vantaggi sono invece legati alla possibilità di studiare e comprendere il processo agglomerativo che porta le diverse unità ad aggregarsi in gruppi man mano che si risale la gerarchia. Ciò può essere di notevole interesse per stabilire la forza del legame che lega le diverse unità e con quale priorità compongono la partizione finale.