Clustering

Il Clustering o analisi dei cluster o analisi di raggruppamento è una tecnica di analisi multivariata dei dati volta alla selezione e raggruppamento di elementi omogenei in un insieme di dati. Tutte le tecniche di clustering si basano sul concetto di distanza tra due elementi. Infatti la bontà delle analisi ottenute dagli algoritmi di clustering dipende essenzialmente da quanto è significativa la metrica e quindi da come è stata definita la distanza. La distanza è un concetto fondamentale dato che gli algoritmi di clustering raggruppano gli elementi a seconda della distanza e quindi l'appartenenza o meno ad un insieme dipende da quanto l'elemento preso in esame è distante dall'insieme. Le tecniche di clustering si possono basare principalmente su due filosofie.

Dal basso verso l'alto

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.

Dall'alto verso il basso

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 è sempre quello di cercare di ottenere elementi omogenei. L'algoritmo procede fino a che non ha raggiunto un numero prefissato di cluster. Questo approccio è anche detto gerarchico.

La tecniche di clustering vengono utlizzate generalmente quando si hanno tanti dati eterogenei e si è alla ricerca di elementi anomali. Per esempio le compagnie telefoniche utilizzano le tecniche di clustering per cercare di individuare in anticipo gli utenti che diventeranno morosi. Normalmente questi utenti hanno un comportamento nettamente diverso rispetto alla maggioranza degli utenti telefonici e le tecniche di clustering riescono sovente ad individuarli o comunque definiscono un cluster dove vengono concentrati tutti gli utenti che hanno un'elevata probabilità di diventare utenti morosi.

Tecniche di Clustering

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

Clustering esclusivo, in cui ogni elemento può essere assegnato ad esattamente 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.

Un'altra suddivisione delle tecniche di clustering tiene conto della tipologia dell'algoritmo utilizzato per dividere lo spazio:

Clustering Partitivo (detto anche k-clustering), in cui per definire l'appartenenza ad un gruppo viene utilizzata una distanze ed un punto rappresentativo del cluster (centroide, medioide ecc...).
Clustering Gerarchico, in cui viene creata una visione gerarchica dei cluster, visualizzando in un trellis i passi di accorpamento/divisione dei gruppi.
Clustering density-based , in cui 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.

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 partitivo

Gli algoritmi di clustering di questa famiglia creano la suddivisione dello spazio minimizzando una certa funzione di costo:
$\sum _{j=1}^{k}E(C_{j})$
dove $k$ è il numero dei clusters, $C_{j}$ è il $j-th$ 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

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

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 passso.
Divisivo - Questi algoritmi, invece, partono considerando lo spazio organizzato in un singolo grande cluster contenente tutti i punti e via via 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 diviso (nel caso estremo questo valore è 1). Questi tipi di algoritmi necessitano di definire una funzione per scegliere il cluster da suddividere.

Misure utilizzate nel clustering gerarchico

In entrambe le tipologie 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)

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}|(1-|C_{i}|)}}\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

Dbscan

Algoritmi

Algoritmi di clustering molto usati sono:

QT clustering

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 cosi via, fino a che il diametro del cluster non supera la soglia.
Salvataggio del cluster candidato con la maggior parte dei punti come il 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 e un gruppo di punti è calcolata usando il concatenamento completo, cioè come la massima distanza dal punto di ciascun membro del gruppo (vedi la sezione "Clustering agglomerativo gerarchico" sulla distanza tra i cluster).