Caratteristiche e funzionamento degli algoritmi di clustering in informatica

Gli algoritmi di clustering sono utilizzati allo scopo di partizionare unità statistiche in una serie di gruppi omogenei al loro interno e quanto più possibili eterogenei tra loro. L’obbiettivo degli algoritmi è quello di identificare dei cluster, cioè dei sottoinsieme di individui aventi caratteristiche simili tra loro e al contempo stesso diverse dal resto della popolazione o più precisamente dagli altri gruppi identificati. Sebbene la classificazione è un mezzo efficace per distinguere gruppi o classi di oggetti essa richiede una etichettatura del training set che risulta molto onerosa infatti spesso è preferibile partizionare i dati in gruppi sulla base delle loro similarità ovvero utilizzando clustering e poi assegnare le varie etichette. L’analisi dei cluster viene utilizzata in numerose applicazioni come il riconoscimento dei pattern, l’analisi dei dati, le ricerche di mercati ecc.

 

Il clustering è una disciplina piuttosto giovane e sta attraversando un enorme sviluppo trovando applicazione nella disciplina di Web Mining, del machine learning. Il primo passo è quello di selezionare un insieme di individui e variabili che concorrono all’analisi mentre la fase successiva è quella relativa alla formazione dei gruppi dove la dottrina distingue due grandi famiglie: i metodi gerarchici e quelli non gerarchici. I primi si basano su processi iterativi, mentre i secondi arrivano a formulare un’organizzazione attraverso gruppi fissati a priori dal ricercatore. Un’altra scelta da effettuare è quella dell’indice di prossimità, che serve per calcolare la matrice delle distanze tra le unità in analisi. Infine lo steep conclusivo consiste nella valutazione del risultato ottenuto tenendo presente lo scopo dell’analisi. Di solito la scelta ottimale si configura come un connubio tra la precisione e la correttezza, fornite da un numero di partizioni elevate e dalla loro semplicità interpretativa.

Esistono diversi algoritmi di clustering e la loro scelta dipende dai dati che si vogliono analizzare e dallo scopo dell’applicazione. In generale i principali metodi di clustering possono essere classificati come:

1. Metodi di partizionamento: dato un database di n oggetti il metodo di partizionamento costruisce k partizioni di dati, dove ciascuna partizione rappresenta un cluster in cui k è minore o uguale ad n. In altre parole l’algoritmo classifica i dati in k gruppi che nel loro insieme soddisfano i seguenti requisiti:
   1. ciascun gruppo deve contenere almeno un oggetto
   2. ciascun oggetto deve appartenere esattamente ad un gruppo.
   3. Il criterio generale di un buon partizionamento è che gli oggetti devono essere correlati l’un l’altro, mentre gli oggetti di cluster differenti devono essere molto distanti tra loro.
2. Metodi gerarchici: crea una decomposizione gerarchica di un dato insieme di oggetti ed in base al partizionamento delle unità si distinguono, in metodo agglomerativo detto anche approccio “botton up” dove ciascun oggetto forma inizialmente un gruppo separato e successivamente gli oggetti vicini gli uni agli altri vengono fusi fino a quando non si ottiene un unico gruppo, mentre in metodo scissorio detto anche approccio “top down” dove gli oggetti si trovano nello stesso cluster ed ad ogni iterazione successiva questo viene diviso in cluster più piccoli fino a quando non si verifica una condizione di terminazione. I metodi gerarchici soffrono il fatto che una volta compiuto il passo sia di fusione che di suddivisione non possono più tornare indietro permettendo di avere un costo computazionale gestibile pur sapendo che se si effettua un errore non si può più tornare indietro.
3. Metodi basati sulla densità: intesi come metodi di partizionamento che clasterizzano gli oggetti basandosi sulla loro distanza. L’idea che sta alla base di questo metodo è quella di far sviluppare un cluster fino a quando la densità (numero di oggetti) non eccede una determinata soglia. Questo metodo utilizza la tecnica DBSCAN la quale costruisce cluster in base ad un’analisi di connettività basata sulla densità.
4. Metodi basati sulla griglia: questi metodi quantizzano lo spazio degli oggetti in un numero finito di celle che formano una struttura a griglia. Il principale vantaggio di questo approccio sta nella velocità di calcolo che è indipendente dal numero di oggetti ma che dipende soltanto dal numero di celle in ciascuna dimensione nello spazio quantizzato.

Alcuni algoritmi di clustering inglobano idee di diversi metodi di clustering, così che resta difficile definire in alcune occasioni se un algoritmo appartiene ad un metodo piuttosto che ad un altro.