Clustering

Da Wikipedia, l'enciclopedia libera.

Il Clustering o analisi dei gruppi (dal termine inglese cluster analysis introdotto da Robert Tryon nel 1939) è un insieme di tecniche di analisi multivariata dei dati volte alla selezione e raggruppamento di elementi omogenei in un insieme di dati. Le tecniche di clustering si basano su misure relative alla somiglianza tra gli elementi. In molti approcci questa similarità, o meglio, dissimilarità, è concepita in termini di distanza in uno spazio multidimensionale. La bontà delle analisi ottenute dagli algoritmi di clustering dipende molto dalla scelta della metrica, e quindi da come è calcolata la distanza. Gli algoritmi di clustering raggruppano gli elementi sulla base della loro distanza reciproca, e quindi l'appartenenza o meno ad un insieme dipende da quanto l'elemento preso in esame è distante dall'insieme stesso.

Le tecniche di clustering si possono basare principalmente su due "filosofie":

  • Dal basso verso l'alto (metodi aggregativi o Bottom-Up):
Questa filosofia prevede che inizialmente tutti gli elementi siano considerati cluster a sé, e poi l'algoritmo provvede ad unire i cluster più vicini. L'algoritmo continua ad unire elementi al cluster fino ad ottenere un numero prefissato di cluster, oppure fino a che la distanza minima tra i cluster non supera un certo valore, o ancora in relazione ad un determinato criterio statistico prefissato.
  • Dall'alto verso il basso (metodi divisivi o Top-Down):
All'inizio tutti gli elementi sono un unico cluster, e poi l'algoritmo inizia a dividere il cluster in tanti cluster di dimensioni inferiori. Il criterio che guida la divisione è naturalmente quello di ottenere gruppi sempre più omogenei. L'algoritmo procede fino a che non viene soddisfatta una regola di arresto generalmente legata al raggiungimento di un numero prefissato di cluster.

Tecniche di Clustering[modifica | modifica wikitesto]

Esistono varie classificazioni delle tecniche di clustering comunemente utilizzate. Una prima categorizzazione dipende dalla possibilità che un elemento possa o meno essere assegnato a più clusters:

  • Clustering esclusivo: ogni elemento può essere assegnato ad uno e ad un solo gruppo. I clusters risultanti, quindi, non possono avere elementi in comune. Questo approccio è detto anche Hard Clustering.
  • Clustering non-esclusivo, in cui un elemento può appartenere a più cluster con gradi di appartenenza diversi. Questo approccio è noto anche con il nome di Soft Clustering o Fuzzy Clustering (dal termine usato per indicare la logica fuzzy).

Un'altra suddivisione delle tecniche di clustering tiene conto del tipo di algoritmo utilizzato per dividere lo spazio:

  • Clustering partizionale (detto anche non gerarchico, o k-clustering), in cui per definire l'appartenenza ad un gruppo viene utilizzata una distanza da un punto rappresentativo del cluster (centroide, medioide ecc...), avendo prefissato il numero di gruppi della partizione risultato. Si tratta di derivazioni del più noto algoritmo di clustering, quello detto delle K-means, introdotto da MacQueen nel 1967.
  • Clustering gerarchico, in cui viene costruita una gerarchia di partizioni caratterizzate da un numero (de)crescente di gruppi, visualizzabile mediante una rappresentazione ad albero (dendrogramma), in cui sono rappresentati i passi di accorpamento/divisione dei gruppi.

Queste due suddivisioni sono del tutto trasversali, e molti algoritmi nati come "esclusivi" sono stati in seguito adattati nel caso "non-esclusivo" e viceversa.

Clustering partizionale[modifica | modifica wikitesto]

Gli algoritmi di clustering di questa famiglia creano una partizione delle osservazioni minimizzando una certa funzione di costo:
\sum_{j=1}^k E( C_j )
dove k è il numero dei clusters, C_j è il j-esimo cluster e E:C \rightarrow R^{+} è la funzione di costo associata al singolo cluster. L'algoritmo più famoso appartenente a questa famiglia è il k-means, proposto da MacQueen nel 1967. Un altro algoritmo abbastanza conosciuto appartenente a questa classe è il 'Partitioning Around Medioid (PAM)'.

Clustering gerarchico[modifica | modifica wikitesto]

Le tecniche di clustering gerarchico non producono un partizionamento flat dei punti, ma una rappresentazione gerarchica ad albero. Hierarchical1.jpg

Questi algoritmi sono a loro volta suddivisi in due classi:

  • Agglomerativo- Questi algoritmi assumono che inizialmente ogni cluster (foglia) contenga un singolo punto; ad ogni passo, poi, vengono fusi i cluster più "vicini" fino ad ottenere un singolo grande cluster. Questi algoritmi necessitano di misure per valutare la similarità tra clusters, per scegliere la coppia di cluster da fondere ad ogni passo.
  • Divisivo - Questi algoritmi, invece, partono considerando lo spazio organizzato in un singolo grande cluster contenente tutti i punti, e via via lo dividono in due. Ad ogni passo viene selezionato un cluster in base ad una misura, ed esso viene suddiviso in due cluster più piccoli. Normalmente viene fissato un numero minimo di punti sotto il quale il cluster non viene ulteriormente suddiviso (nel caso estremo questo valore è 1). Questi tipi di algoritmi necessitano di definire una funzione per scegliere il cluster da suddividere.

Una rappresentazione grafica del processo di clustering è fornita dal Dendrogramma.

Misure utilizzate nel clustering gerarchico[modifica | modifica wikitesto]

In entrambe i tipi di clustering gerarchico sono necessarie funzioni per selezionare la coppia di cluster da fondere ("agglomerativo"), oppure il cluster da dividere ("divisivo").

Nel primo caso, sono necessarie funzioni che misurino la similarità (o, indistintamente, la distanza) tra due cluster, in modo da fondere quelli più simili. Le funzioni utilizzate nel caso agglomerativo sono:

  • Single-link proximity
Calcola la distanza tra i due cluster come la distanza minima tra elementi appartenenti a cluster diversi:  D(C_i,C_j)=\min_{x \in C_i, y \in C_j} d(x,y)

Singlelink.jpg

  • Average-link proximity
Questa funzione calcola la distanza tra i due cluster come la media delle distanze tra i singoli elementi:  D(C_i,C_j)= \frac{1}{|C_i| |C_j|} \sum_{x \in C_i,y \in C_j} d(x,y)
  • Complete-link proximity
Questa funzione calcola la distanza tra i due cluster come la distanza massima tra elementi appartenenti ai due clusters:  D(C_i,C_j)=\max_{x \in C_i, y \in C_j} d(x,y)
  • Distanza tra centroidi
La distanza tra i due clusters coincide con la distanza calcolata tra i centroidi (o medioidi):
 D(C_i,C_j)=d(\hat{c_i},\hat{c_j}).

Nei 4 casi precedenti,  d(x,y) indica una qualsiasi funzione distanza su uno spazio metrico.

Nel clustering divisivo, invece, è necessario individuare il cluster da suddividere in due sottogruppi. Per questa ragione sono necessarie funzioni che misurino la compattezza del cluster, la densità o la sparsità dei punti assegnati ad un cluster. Le funzioni normalmente utilizzate nel caso divisivo sono:

  • Average internal similarity
Questa funzione valuta la similarità media tra i documenti interni ad un cluster: più sono tra loro dissimili (valori bassi di similarità), più il cluster è da suddividere in sottogruppi:
 D(C_i)= \frac{1}{|C_i| (|C_i| - 1)} \sum_{x,y \in C_i, x \neq y} d(x,y)
  • Maximum internal distance
Questa funzione valuta la distanza massima tra due punti interni ad un cluster. Tale valore è noto anche come 'diametro del cluster': più tale valore è basso, più il cluster è compatto:
D(C_i)=\max_{x,y \in C_i} d(x,y)

Clustering density-based[modifica | modifica wikitesto]

Nel Clustering density-based, il raggruppamento avviene analizzando l'intorno di ogni punto dello spazio. In particolare, viene considerata la densità di punti in un intorno di raggio fissato.

Un esempio è il metodo di clustering Dbscan.

Algoritmi[modifica | modifica wikitesto]

Algoritmi di clustering molto usati sono:

QT clustering[modifica | modifica wikitesto]

Il QT (Quality Threshold) Clustering (Heyer et al., 1999) è un metodo alternativo di partizionare i dati, inventato per il clustering dei geni. Richiede più potenza di calcolo rispetto al K-Means, ma non richiede di specificare il numero di cluster a priori, e restituisce sempre lo stesso risultato quando si ripete diverse volte.

L'algoritmo è:

  • L'utente sceglie un diametro massimo per i clusters;
  • Costruzione di un cluster candidato per ogni punto, includendo il punto più vicino, il prossimo più vicino, e così via, fino a che il diametro del cluster non supera la soglia;
  • Salvataggio del cluster candidato con la maggior parte dei punti come primo vero cluster, e rimozione di tutti i punti nel cluster da ulteriori considerazioni;
  • Ricorsione col ridotto insieme di cluster.

La distanza tra un punto ed un gruppo di punti è calcolata usando il concatenamento completo, cioè come la massima distanza dal punto di ciascun membro del gruppo (vedi il "Clustering gerarchico agglomerativo" sulla distanza tra i cluster nella sezione clustering gerarchico).

Bibliografia[modifica | modifica wikitesto]

  • Roberto Todeschini, Introduzione alla chemiometria, 1ª ed., Napoli, EdiSES, 2003, ISBN 88-7959-146-0.
  • G.Susinno, M.A.Miceli, Ultrametricity in Fund of Funds Diversification, Physica A 344 (1-2) (2004) 95-99

Voci correlate[modifica | modifica wikitesto]

Altri progetti[modifica | modifica wikitesto]

Collegamenti esterni[modifica | modifica wikitesto]

matematica Portale Matematica: accedi alle voci di Wikipedia che trattano di matematica