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

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, ${\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	$\max \,\{\,d(a,b):a\in A,\,b\in B\,\}.$
Minimum o single-linkage	$\min \,\{\,d(a,b):a\in A,\,b\in B\,\}.$
Average linkage	${\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.

Note

^ (EN) The DISTANCE Procedure: Proximity Measures ^{[collegamento interrotto]}, su SAS/STAT 9.2 Users Guide, SAS Institute. URL consultato il 26 aprile 2009.
^ (EN) The CLUSTER Procedure: Clustering Methods, su SAS/STAT 9.2 Users Guide, SAS Institute. URL consultato il 26 aprile 2009 (archiviato dall'url originale il 7 luglio 2008).

Bibliografia

(EN) Trevor Hastie, Robert Tibshirani e Jerome Friedman, 14.3.12 Hierarchical clustering, in The Elements of Statistical Learning, New York, Springer, 2001, pp. 272–280, ISBN 0-387-95284-5.

Voci correlate

Altri progetti

Wikimedia Commons contiene immagini o altri file sul clustering gerarchico

Collegamenti esterni

(IT) Articolo Il Clustering dell'Unirc (PDF), su unirc.it. URL consultato il 21 febbraio 2023.

Controllo di autorità	LCCN (EN) sh2013002984 · J9U (EN, HE) 987007574954205171

Portale Informatica

Portale Statistica

[1] (EN) The DISTANCE Procedure: Proximity Measures ^{[collegamento interrotto]}, su SAS/STAT 9.2 Users Guide, SAS Institute. URL consultato il 26 aprile 2009.

[2] (EN) The CLUSTER Procedure: Clustering Methods, su SAS/STAT 9.2 Users Guide, SAS Institute. URL consultato il 26 aprile 2009 (archiviato dall'url originale il 7 luglio 2008).

[1]

[2]