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:

Partitioning (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...).
Gerarchico, in cui viene creata una visione gerarchica dei cluster, visualizzando in un trellis i passi di accorpamento/divisione dei gruppi.
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.

Partitioning

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 oppure il cluster da dividere. Le misure normalmente utilizzate sono le seguenti, alcune delle quali però utilizzabili solamente per il caso agglomerativo:

Single-link proximity
Average-link proximity
Complete-link proximity
Distanza tra centroidi

Density-based

Algoritmi

Algoritmi di clustering molto usati sono: