Clustering gerarchico

Da Wikipedia, l'enciclopedia libera.

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[modifica | modifica wikitesto]

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[modifica | modifica wikitesto]

Exquisite-kfind.png Per approfondire, vedi 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, \sqrt{2} or 1 se si utilizzando rispettivamente le norme 1, 2 o infinito.

Metriche comuni sono le seguenti:[1]

Criteri di collegamento[modifica | modifica wikitesto]

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[modifica | modifica wikitesto]

  1. ^ (EN) The DISTANCE Procedure: Proximity Measures in SAS/STAT 9.2 Users Guide, SAS Institute. URL consultato il 26 aprile 2009.
  2. ^ (EN) The CLUSTER Procedure: Clustering Methods in SAS/STAT 9.2 Users Guide, SAS Institute. URL consultato il 26 aprile 2009.

Bibliografia[modifica | modifica wikitesto]

  • (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[modifica | modifica wikitesto]

Bibliografia[modifica | modifica wikitesto]

  • Roberto Todeschini, Introduzione alla chemiometria, 1ª ed., Napoli, EdiSES, 2003, ISBN 88-7959-146-0.

Collegamenti esterni[modifica | modifica wikitesto]