Cluster Analysis: metodi di classificazione

Effettuata la scelta dei coefficienti di diversità da utilizzare, si determina l'algoritmo di classificazione e l'eventuale criterio di aggregazione/suddivisione.

Tra i metodi di classificazione più comuni troviamo:

  1. metodi gerarchici aggregativi;
  2. metodi gerarchici divisivi;
  3. metodi non gerarchici

In questo articolo, noi ci occuperemo esclusivamente dei metodi gerarchici aggregativi visto che sono quelli più comuni.

 

Metodi gerarchici aggregativi

Supponiamo che l'insieme degli oggetti da classificare sia dotato di una misura di dissimilarità, per facilità consideriamo una distanza. I passi da svolgere sono i seguenti:

  1. costruire una prima matrice delle distanze partendo dalla matrice dei dati $X$;
  2. aggregare le due unità più vicine (cioè aventi distanza minima) in un cluster;
  3. applicare uno degli algoritmi aggregativi per far entrare un'unità nel cluster trovato al punto precedente o per fondere due unità in un cluster diverso;

Si continua così, finchè non si sia formato un unico cluster contenente tutte le unità.

Metodo del legame singolo (o del vicino più vicino)

Il metodo del legame singolo si basa su un criterio di distanza minima. Dopo aver trovato gli elementi A e B che hanno distanza minima tra loro e averli fusi in uno stesso cluster (come al punto 2), si procede aggiungendo ad esso l'unità C che presenta distanza minima dal cluster, ovvero quello per cui vale:

$$d_{(A,B)C}=min(d_{AC},d_{BC})$$

 

Ad esempio, supponiamo di avere per 5 unità statistiche la seguente matrice di distanze:

$$D^{(1)}=\begin{matrix} \ & A & B & C & D & E\\ A & 0 & 2,449 & 7,810 & 17,292 & 20,125\\ B & 2,449 & 0 & 7,280 & 16,763 & 19,875\\ C & 7,810 & 7,280 & 0 &11,045 & 14,900\\ D & 17,292 & 16,763 & 11,045 & 0 & 4,690\\ E & 20,125 & 19,875 & 14,900 & 4,690 & 0\end{matrix}$$

Nel primo passo vengono fuse le unità A e B, essendo le più vicine (con $d_{AB}=2,449$).

Nel secondo passo si calcolano le distanza tra questo cluster (AB) e le altre unità.

$$\begin{array}{l} d_{(AB),C}=min(d_{AC},d_{BC})=7,280\\ d_{(AB),D}=min(d_{AD},d_{BD})=16,763\\ d_{(AB),E}=min(d_{AE},d_{BE})=19,875\end{array}$$

Si ottiene così una nuova matrice delle distanze:

$$D^{(2)}=\begin{matrix} \ & AB & C & D & E\\ AB & 0 & 7,280 & 16,763 & 19,875\\ C & 7,280 & 0 & 11,045 & 14,900\\ D & 16,763 & 11,045 & 0 & 4,690\\ E & 19,875 & 14,900 & 4,690 & 0\end{matrix}$$

Il minor elemento di $D^{(2)}$ è $4,690$ e rappresenta la distanza tra D ed E. Quindi, le unità D ed E vanno a formare il cluster (DE).

Come prima calcoliamo le distanze tra questo cluster e le altre unità o cluster:

$$\begin{array}{l} d_{(DE),(AB)}=min(d_{D,A}, d_{D,B},d_{E,A},d_{E,B})=16,763\\ d_{(DE),C}=min(d_{DC},d_{EC})=11,045\end{array}$$

Ottenendo una nuova matrice delle distanze:

$$D^{(3)}=\begin{matrix} \ & AB & C & DE\\ AB & 0 & 7,280 & 16,763 \\ C & 7,280 & 0 & 11,045 \\ DE & 16,763 & 11,045 & 0\end{matrix}$$

Al passo successivo l'unità C viene aggregata nel cluster AB (essendo minima la distanza tra i due) e nell'ultimo passo i due cluster (ABC) e (DE) vengono fusi in un unico gruppo. (Vedi dendogramma)

Metodo del legame completo (o del vicino più lontano)

Tale metodo si basa su un criterio di distanza massima. Dopo aver trovato gli elementi A e B che hanno distanza minima tra loro e averli fusi in uno stesso cluster, si procede aggiungendo ad esso l'unità C che presenta distanza massima dal cluster, ovvero quello per cui vale:

$$d_{(AB),C}=max(d_{A,C},d_{B,C})$$

mentre, la distanza tra il cluster (AB) ed il cluster (CD) viene definita come:

$$d_{(AB),(CD)}=max(d_{A,C},d_{A,D},d_{B,C},d_{B,D})$$

Metodo del legame medio

Nel metodo del legame medio la distanza tra cluster è definita come media aritmetica delle distanze tra tutte le possibili coppie di elementi appartenenti l'uno ad un cluster, l'altro ad un altro.

Dati due cluster $C_1$ e $C_2$, contenenti rispettivamente $n_1$ ed $n_2$ unità, indicando con l'indice $i$ il generico elemento del cluster $C_1$ e con l'indice $j$ il generico elemento del cluster $C_2$, e con $d_{i,j}$ la loro distanza, la distanza tra $C_1$ e $C_2$ sarà:

$$d_{C_1,C_2}=\frac{1}{n_1}\frac{1}{n_2}\left(\sum_i\sum_jd_{i,j}\right)$$

Per esempio, riprendendo la matrice $D^{(1)}$

$$D^{(1)}=\begin{matrix} \ & A & B & C & D & E\\ A & 0 & 2,449 & 7,810 & 17,292 & 20,125\\ B & 2,449 & 0 & 7,280 & 16,763 & 19,875\\ C & 7,810 & 7,280 & 0 &11,045 & 14,900\\ D & 17,292 & 16,763 & 11,045 & 0 & 4,690\\ E & 20,125 & 19,875 & 14,900 & 4,690 & 0\end{matrix}$$

nel primo passo vengono fuse le unità A e B essendo le più vicine. Per il metodo del legame medio, bisogna calcolare le distanze tra il cluster (AB) e le altre unità in questo modo:

$$\begin{array}{l} d_{(AB),C}=\frac{1}{2}\cdot 1\cdot (d_{AC}+d_{BC})=7,545\\ d_{(AB),D}=\frac{1}{2}\cdot 1\cdot(d_{AD}+d_{BD})=17.0275\\ d_{(AB),E}=\frac{1}{2}\cdot 1\cdot(d_{AE}+d_{BE})=20\end{array}$$

La nuova matrice delle distanze sarà:

$$D^{(2)}=\begin{matrix} \ & AB & C & D & E\\ AB & 0 & 7,545 & 17.0275 & 20\\ C & 7,545 & 0 & 11,045 & 14,900\\ D & 17.0275 & 11,045 & 0 & 4,690\\ E & 20 & 14,900 & 4,690 & 0\end{matrix}$$

Al passo successivo vengono aggregate in un unico cluster le unità D ed E. Le nuove distanze sono:

$$\begin{array}{l} d_{(AB),(DE)} &=\frac{1}{2}\cdot\frac{1}{2} (d_{A,D}+d_{A,E}+d_{B,D}+d_{B,E})=18,5138\\ d_{C,(DE)}&=1\cdot\frac{1}{2}(d_{C,D}+d_{C,E})=12,9725\end{array}$$

La nuova matrice delle distanze è:

$$D^{(3)}=\begin{matrix} \ & AB & C & DE\\ AB & 0 & 7,545 & 18,5138\\ C & 7,545 & 0 & 12,9725\\ DE & 18,5138 & 12,9725 & 0\end{matrix}$$

Infine C viene aggregata al cluster (AB), ottenendo la stessa gerarchia ottenuta con il metodo del legame semplice (sono però cambiate le distanze e quindi le altezze dei rami del dendogramma).

Metodo del centroide

Il metodo del centroide si applica solo a variabili quantitative e lavora non tanto sulla matrice delle distanze quanto sui singoli vettori di osservazioni. Per ogni gruppo si calcola il baricentro, ossia l'elemento che presenta le modalità medie del gruppo. La distanza tra un'unità e un gruppo o tra due gruppo è calcolata come distanza tra baricentri.

Supponiamo di avere 5 unità statistiche e due variabili $x_1$ e $x_2$ che assumono le seguenti modalità:

$$\begin{matrix} \ & x_1 & x_2 \\ A & 1 & 1\\ B & 1 & 2\\ C & 6 & 3\\ D & 8 & 2\\ E & 8 & 0\end{matrix}$$

Calcoliamo la matrice dei quadrati delle distanze euclidee:

$$D^{(1)}=\begin{matrix} \ & A & B & C & D & E \\ A & 0 & 1 & 29 & 50 & 50\\ B & & 0 & 26 & 49 & 53\\ C & & & 0 & 5 & 13\\ D & & & & 0 & 4\\ E & & & & & 0\end{matrix}$$

Infatti, per esempio $d_{A,E}^2=(1-8)^2+(1-0)^2=50$.

Vengono raggruppate in un unico cluster le unità A e B dato che hanno la minore distanza. Il baricentro del cluster (AB) ha coordinate $(1;1,5)$ e quindi le modalità sono:

$$\begin{matrix} \ & x_1 & x_2 \\ AB & 1 & 1,5\\ C & 6 & 3\\ D & 8 & 2\\ E & 8 & 0\end{matrix}$$

la cui matrice delle distanze sarà:

$$D^{(2)}=\begin{matrix} \ & AB & C & D & E \\ AB & 0 & 27,25 & 49,25 & 51,25\\ C & & 0 & 5 & 13\\ D & & & 0 & 4\\ E & & & & 0\end{matrix}$$

Si procede, poi, con l'aggregazione delle unità D es E, il cui baricentro è dato da $(8;1)$. Si ha così:

$$\begin{matrix} \ & x_1 & x_2 \\ AB & 1 & 1,5\\ C & 6 & 3\\ DE & 8 & 1\end{matrix}$$

E quindi:

$$D^{(3)}=\begin{matrix} \ & AB & C & DE \\ AB & 0 & 27,25 & 49,25\\ C & & 0 & 8\\ DE & & & 0\end{matrix}$$

Nell'ultimo passo l'unità C verrà aggregata al cluster (AB).

Questo sito usa i cookies per fornirti una migliore esperienza di navigazione. Prendi visione della privacy policy e clicca su "Accetta" per proseguire.