Che cos’è il Clustering?

Il Clustering o analisi dei cluster[1] è un insieme di tecniche di analisi multivariata dei dati volte 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.

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…). Gli algoritmi di clustering di questa famiglia creano la suddivisione dello spazio minimizzando una certa funzione di costo:

dove k è il numero dei clusters, C_j è il j − th cluster e è la funzione di costo associata al singolo cluster. L’algoritmo più famoso appartenente a questa famiglia è il k-means[2], proposto da MacQueen nel 1967. Un altro algoritmo abbastanza conosciuto appartenente a questa classe è il Partitioning Around Medioid (PAM).

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

–      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. Il più noto di questi tipi di algoritmi è il Dbscan. Il dbscan è un metodo di clustering basato sulla densità, esso connette regioni di punti con densità dei medesimi sufficientemente alta. Per ogni oggetto saranno trovati i vicini che ricadono in un raggio dato come parametro in ingresso, se il numero di tali vicini è superiore a un fattore di soglia (anch’esso fornito in input all’algoritmo) allora tali punti faranno parte del medesimo cluster di quello dell’oggetto che si sta osservando (in questo caso il nostro punto sarà denominato core point). Al termine dell’algoritmo avremo dei punti appartenenti a cluster e punti lasciati liberi, questi ultimi saranno rumore. Un oggetto q è direttamente rintracciabile in base alla densità rispetto ad un punto p se q è un vicino di p (con lo stesso raggio dato in input) con il rispetto del minimo numero di vicini per quanto riguarda p. Se c’è una catena di oggetti da attraversare (con i consueti vincoli) per raggiungere un punto q da uno p allora q sarà detto semplicemente rintracciabile. Ultimo caso è quello in cui due oggetti “p” e “q” sono detti connessi, per essere definiti in tal modo deve esistere un terzo punto o per il quale “p” e “q” sono entrambi rintracciabili.

Queste due suddivisioni sono del tutto trasversali e molti algoritmi nati come “esclusivi” sono stati in seguito adattati nel caso “non-esclusivo” e viceversa. Gli algoritmi di clustering maggiormente usati sono:

–      K-Means

–      C-Means

–      QT Clustering

L’algoritmo K-Means è un algoritmo di clustering che permette di suddividere gruppi di oggetti in K partizioni sulla base dei loro attributi. È una variante dell’Algoritmo di aspettazione-massimizzazione il cui obiettivo è determinare i K gruppi di dati generati da distribuzioni gaussiane. Si assume che gli attributi degli oggetti possano essere rappresentati come vettori, e che quindi formino uno spazio vettoriale. L’obiettivo che l’algoritmo si prepone è di minimizzare la varianza totale inter-cluster. Ogni cluster viene identificato mediante un centroide o punto medio. L’algoritmo segue una procedura iterativa. Inizialmente crea K partizioni e assegna ad ogni partizione i punti d’ingresso o casualmente o usando alcune informazioni euristiche. Quindi calcola il centroide di ogni gruppo. Costruisce quindi una nuova partizione associando ogni punto d’ingresso al cluster il cui centroide è più vicino ad esso. Quindi vengono ricalcolati i centroidi per i nuovi cluster e così via, finché l’algoritmo non converge. Sebbene sia possibile dimostrare che il procedimento termina sempre, non è detto che il minimo globale sia raggiunto. Questo perché il procedimento potrebbe fermarsi quando vengono trovati dei minimi locali. Il risultato è quindi influenzato dalla scelta dei centri iniziali. Infine, Non garantisce la connessione dei cluster trovati e l’assenza di punti isolati.

L’algoritmo K-Means partiziona l’insieme delle caratteristiche in cluster disgiunti. Nel Fuzzy C-Means[3] ogni vettore di caratteristiche può appartenere contemporaneamente a più cluster, ognuno con il relativo grado di appartenenza. Inoltre come il K-Means, il Fuzzy C-Means ha l’obiettivo di minimizzare una funzione obiettivo scelta a priori, che cambia a seconda della metrica e della misura di distanza scelta; una funzione comunemente usata è:

1. Inizializza la matrice U di appartenenza alle classi in modo random
2. Calcola i centri cj
3. Aggiorna il grado di appartenenza
4. Ripeti i passi 2 e 3 finché il cambiamento di U è minore ad una tolleranza data

Analizziamo quali sono i passi principali per il C-Means:

L’appartenenza non esclusiva di un vettore di caratteristiche permette al Fuzzy C-Means di ovviare al problema dei minimi locali.

In alcuni casi si richiede che i clusters siano omogenei e che non siano presenti oggetti isolati: il Fuzzy C-Means, così come il K-Means, non garantisce la connessione dei cluster trovati e l’assenza di punti isolati. I due algoritmi di clustering che seguono sono stati pensati per segmentare immagini utilizzando informazioni del contesto spaziale.

Il QT Clustering è 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 è il seguente:

–      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

[1] http://en.wikipedia.org/wiki/Cluster_analysis

[2] http://it.wikipedia.org/wiki/K-means

[3]www.to.infn.it/activities/experiments/magic/meetings/feb2005/Agenda-Pisa-2005/l-cavallo.ppt

[4] http://www.mat.uniroma1.it/~caglioti/Sequenze/node28.html

[5] http://www.mat.uniroma1.it/~caglioti/Sequenze/node27.html