Clustering gerarchico

In statistica e apprendimento automatico, il clustering gerarchico è un approccio di clustering che mira a costruire una gerarchia di cluster. Le strategie per il clustering gerarchico sono tipicamente di due tipi:

• Agglomerativo: si tratta di un approccio "bottom up" (dal basso verso l'alto) in cui si parte dall'inserimento di ciascun elemento in un cluster differente e si procede quindi all'accorpamento graduale di cluster a due a due.
• Divisivo: si tratta di un approccio "top down" (dall'alto verso il basso) in cui tutti gli elementi si trovano inizialmente in un singolo cluster che viene via via suddiviso ricorsivamente in sotto-cluster.

Il risultato di un clustering gerarchico è rappresentato in un dendrogramma.

Dissimilarità tra cluster

Per decidere quali cluster devono essere combinati (approccio agglomerativo) o quale cluster deve essere suddiviso (approccio divisivo) è necessario definire una misura di dissimilarità tra cluster. Nella maggior parte dei metodi di clustering gerarchico si fa uso di metriche specifiche che quantificano la distanza tra coppie di elementi e di un criterio di collegamento che specifica la dissimilarità di due insiemi di elementi (cluster) come funzione della distanza a coppie tra elementi nei due insiemi.

Metriche

Lo stesso argomento in dettaglio: Metrica (matematica).

La scelta di una metrica appropriata influenza la forma dei cluster, poiché alcuni elementi possono essere più "vicini" utilizzando una distanza e più "lontani" utilizzandone un'altra. Per esempio, in uno spazio a 2 dimensioni, la distanza tra il punto (1, 1) e l'origine (0, 0) è 2, ${\displaystyle {\sqrt {2}}}$ or 1 se si utilizzando rispettivamente le norme 1, 2 o infinito.

Metriche comuni sono le seguenti:^[1]

• La distanza euclidea (chiamata anche norma 2)
• La distanza di Manhattan (chiamata anche norma 1)
• La norma uniforme
• La distanza di Mahalanobis, che corregge i dati per scale differenti e le correlazioni nelle variabili
• L'angolo tra i due vettori.
• La distanza di Hamming, che misura il minimo numero di sostituzioni richieste per cambiare un membro nell'altro.

Criteri di collegamento

Il criterio di collegamento (linkage criterion) specifica la distanza tra insiemi di elementi come funzione di distanze tra gli elementi negli insiemi.

Dati due insiemi di elementi A e B alcuni criteri comunemente utilizzati sono:^[2]

Nome del criterio	Formula
Complete linkage	${\displaystyle \max \,\{\,d(a,b):a\in A,\,b\in B\,\}.}$
Minimum o single-linkage	${\displaystyle \min \,\{\,d(a,b):a\in A,\,b\in B\,\}.}$
Average linkage	${\displaystyle {\frac {1}{|A||B|}}\sum _{a\in A}\sum _{b\in B}d(a,b).}$

dove d è la metrica prescelta per determinare la similarità tra coppie di elementi.

Vi è anche il criterio di Ward, che valuta il cambiamento di varianza intra-cluster quando questi si uniscono e seleziona la coppia che dà luogo a un cluster avente la minima varianza al suo interno. Questo criterio punta a creare cluster compatti e omogenei, con una dispersione simile.^[3]