Algoritmi di clustering: From Start To State Of The Art

Non è un brutto momento per essere un Data Scientist. Le persone serie possono trovare interesse in te se giri la conversazione verso i “Big Data”, e il resto della folla della festa sarà incuriosita quando menzioni “Intelligenza Artificiale” e “Machine Learning”. Anche Google pensa che non sei male, e che stai migliorando ancora di più. Ci sono un sacco di algoritmi “intelligenti” che aiutano gli scienziati dei dati a fare le loro magie. Può sembrare tutto complicato, ma se capiamo e organizziamo un po’ gli algoritmi, non è nemmeno così difficile trovare e applicare quello che ci serve.

I corsi sul data mining o sul machine learning di solito iniziano con il clustering, perché è sia semplice che utile. È una parte importante di un’area un po’ più ampia dell’apprendimento non supervisionato, dove i dati che vogliamo descrivere non sono etichettati. Nella maggior parte dei casi si tratta di casi in cui l’utente non ci ha dato molte informazioni su quale sia l’output atteso. L’algoritmo ha solo i dati e dovrebbe fare il meglio che può. Nel nostro caso, dovrebbe eseguire il clustering – separando i dati in gruppi (cluster) che contengono punti dati simili, mentre la dissimilarità tra i gruppi è la più alta possibile. I punti dati possono rappresentare qualsiasi cosa, come i nostri clienti. Il clustering può essere utile se, per esempio, vogliamo raggruppare utenti simili e poi eseguire diverse campagne di marketing su ogni cluster.

K-Means Clustering

Dopo la necessaria introduzione, i corsi di Data Mining continuano sempre con K-Means; un algoritmo di clustering efficace, ampiamente utilizzato e completo. Prima di eseguirlo effettivamente, dobbiamo definire una funzione di distanza tra i punti dei dati (per esempio, la distanza euclidea se vogliamo raggruppare punti nello spazio), e dobbiamo impostare il numero di cluster che vogliamo (k).

L’algoritmo inizia selezionando k punti come centroidi di partenza (‘centri’ dei cluster). Possiamo semplicemente selezionare qualsiasi k punti casuali, o possiamo usare qualche altro approccio, ma scegliere punti casuali è un buon inizio. Poi, ripetiamo iterativamente due passi:

1. Passo di assegnazione: ognuno degli m punti del nostro dataset viene assegnato a un cluster che è rappresentato dal più vicino dei k centroidi. Per ogni punto, calcoliamo le distanze da ogni centroide, e scegliamo semplicemente il meno distante.

2. Fase di aggiornamento: per ogni cluster, viene calcolato un nuovo centroide come media di tutti i punti nel cluster. Dal passo precedente, abbiamo un insieme di punti che sono assegnati a un cluster. Ora, per ogni tale insieme, calcoliamo una media che dichiariamo un nuovo centroide del cluster.

Dopo ogni iterazione, i centroidi si spostano lentamente, e la distanza totale da ogni punto al suo centroide assegnato diventa sempre più bassa. I due passi sono alternati fino alla convergenza, cioè fino a quando non ci sono più cambiamenti nell’assegnazione dei cluster. Dopo un certo numero di iterazioni, lo stesso insieme di punti sarà assegnato ad ogni centroide, portando quindi di nuovo agli stessi centroidi. K-Means è garantito per convergere verso un optimum locale. Tuttavia, questo non deve necessariamente essere la migliore soluzione globale (optimum globale).

Il risultato finale del clustering può dipendere dalla selezione dei centroidi iniziali, quindi si è pensato molto a questo problema. Una soluzione semplice è semplicemente eseguire K-Means un paio di volte con assegnazioni iniziali casuali. Possiamo poi selezionare il miglior risultato prendendo quello con la minima somma delle distanze da ogni punto al suo cluster – il valore di errore che stiamo cercando di minimizzare in primo luogo.

Altri approcci alla selezione dei punti iniziali possono contare sulla selezione di punti distanti. Questo può portare a risultati migliori, ma potremmo avere un problema con gli outlier, quei rari punti soli che sono semplicemente “fuori” che potrebbero essere solo degli errori. Poiché sono lontani da qualsiasi cluster significativo, ogni punto di questo tipo può finire per essere il proprio “cluster”. Un buon equilibrio è la variante K-Means++ , la cui inizializzazione sceglierà ancora punti casuali, ma con probabilità proporzionale alla distanza quadrata dai centroidi precedentemente assegnati. I punti che sono più lontani avranno maggiori probabilità di essere selezionati come centroidi di partenza. Di conseguenza, se c’è un gruppo di punti, la probabilità che un punto del gruppo venga selezionato diventa più alta man mano che le loro probabilità si sommano, risolvendo il problema degli outlier di cui abbiamo parlato.

K-Means++ è anche l’inizializzazione predefinita per l’implementazione K-Means di Scikit-learn di Python. Se stai usando Python, questa potrebbe essere la tua libreria di scelta. Per Java, la libreria Weka può essere un buon inizio:

Java (Weka)

// Load some dataInstances data = DataSource.read("data.arff");// Create the modelSimpleKMeans kMeans = new SimpleKMeans();// We want three clusterskMeans.setNumClusters(3);// Run K-MeanskMeans.buildClusterer(data);// Print the centroidsInstances centroids = kMeans.getClusterCentroids();for (Instance centroid: centroids) { System.out.println(centroid);}// Print cluster membership for each instancefor (Instance point: data) { System.out.println(point + " is in cluster " + kMeans.clusterInstance(point));}

Python (Scikit-learn)

> >> from sklearn import cluster, datasets> >> iris = datasets.loadiris()> >> Xiris = iris.data> >> yiris = iris.target> >> kmeans = cluster.KMeans(nclusters=3)> >> kmeans.fit(Xiris)KMeans(copy_x=True, init='k-means++', ...> >> print(kmeans.labels)> >> print(yiris)

Nell’esempio Python di cui sopra, abbiamo usato un set di dati standard di esempio ‘Iris’, che contiene petali e sepali di fiori per tre diverse specie di iris. Li abbiamo raggruppati in tre cluster, e abbiamo confrontato i cluster ottenuti con le specie reali (target), per vedere che corrispondono perfettamente.

In questo caso, sapevamo che c’erano tre diversi cluster (specie), e K-Means ha riconosciuto correttamente quali vanno insieme. Ma come facciamo a scegliere un buon numero di cluster k in generale? Questo tipo di domande sono abbastanza comuni nel Machine Learning. Se richiediamo più cluster, essi saranno più piccoli, e quindi l’errore totale (totale delle distanze dai punti ai loro cluster assegnati) sarà minore. Quindi, è una buona idea impostare solo un k più grande? Potremmo finire con l’avere k = m, cioè ogni punto è il suo centroide, con ogni cluster che ha solo un punto. Sì, l’errore totale è 0, ma non abbiamo ottenuto una descrizione più semplice dei nostri dati, né è abbastanza generale da coprire alcuni nuovi punti che potrebbero apparire. Questo si chiama overfitting, e noi non lo vogliamo.

Un modo per affrontare questo problema è quello di includere qualche penalità per un numero maggiore di cluster. Quindi, ora stiamo cercando di minimizzare non solo l’errore, ma errore + penalità. L’errore convergerà verso zero man mano che aumentiamo il numero di cluster, ma la penalità crescerà. Ad alcuni punti, il guadagno dall’aggiunta di un altro cluster sarà inferiore alla penalità introdotta, e avremo il risultato ottimale. Una soluzione che usa il Criterio di Informazione Bayesiano (BIC) per questo scopo si chiama X-Means .

Un’altra cosa che dobbiamo definire correttamente è la funzione di distanza. A volte questo è un compito semplice, un compito logico data la natura dei dati. Per i punti nello spazio, la distanza euclidea è una soluzione ovvia, ma può essere difficile per caratteristiche di diverse ‘unità’, per variabili discrete, ecc. Questo può richiedere molta conoscenza del dominio. Oppure, possiamo chiedere aiuto al Machine Learning. Possiamo effettivamente cercare di imparare la funzione di distanza. Se abbiamo un set di allenamento di punti che sappiamo come dovrebbero essere raggruppati (cioè punti etichettati con i loro cluster), possiamo usare tecniche di apprendimento supervisionato per trovare una buona funzione, e poi applicarla al nostro set di destinazione che non è ancora clusterizzato.

Il metodo usato in K-Means, con i suoi due passi alternati assomiglia ad un metodo di Expectation-Maximization (EM). In realtà, può essere considerato una versione molto semplice di EM. Tuttavia, non dovrebbe essere confuso con il più elaborato algoritmo di clustering EM anche se condivide alcuni degli stessi principi.

EM Clustering

Così, con il clustering K-Means ogni punto è assegnato ad un solo cluster, e un cluster è descritto solo dal suo centroide. Questo non è molto flessibile, poiché possiamo avere problemi con i cluster che si sovrappongono, o quelli che non sono di forma circolare. Con l’EM Clustering, possiamo ora fare un passo avanti e descrivere ogni cluster per il suo centroide (media), covarianza (in modo da poter avere cluster ellittici), e peso (la dimensione del cluster). La probabilità che un punto appartenga a un cluster è ora data da una distribuzione di probabilità gaussiana multivariata (multivariata – dipende da più variabili). Questo significa anche che possiamo calcolare la probabilità che un punto sia sotto una ‘campana’ gaussiana, cioè la probabilità che un punto appartenga a un cluster.

Ora iniziamo la procedura EM calcolando, per ogni punto, le probabilità che esso appartenga a ciascuno dei cluster attuali (che, di nuovo, possono essere creati casualmente all’inizio). Questo è il passo E. Se un cluster è davvero un buon candidato per un punto, avrà una probabilità vicina a uno. Tuttavia, due o più cluster possono essere candidati accettabili, quindi il punto ha una distribuzione di probabilità sui cluster. Questa proprietà dell’algoritmo, dei punti che non appartengono solo ad un cluster è chiamata “soft clustering”.

Il passo M ora ricalcola i parametri di ogni cluster, usando le assegnazioni dei punti al precedente set di cluster. Per calcolare la nuova media, la covarianza e il peso di un cluster, ogni dato puntuale viene ponderato per la sua probabilità di appartenere al cluster, come calcolato nel passo precedente.

Alternando questi due passi, la log-likelihood totale aumenta fino a convergere. Di nuovo, il massimo può essere locale, quindi possiamo eseguire l’algoritmo più volte per ottenere cluster migliori.

Se ora vogliamo determinare un singolo cluster per ogni punto, possiamo semplicemente scegliere il più probabile. Avendo un modello di probabilità, possiamo anche usarlo per generare dati simili, cioè per campionare più punti che sono simili ai dati che abbiamo osservato.

Propagazione di affinità

La Propagazione di affinità (AP) è stata pubblicata da Frey e Dueck nel 2007, e sta diventando sempre più popolare grazie alla sua semplicità, applicabilità generale e performance. Sta cambiando il suo status da stato dell’arte a standard de facto.

I principali svantaggi di K-Means e algoritmi simili sono il dover selezionare il numero di cluster e la scelta del set iniziale di punti. L’Affinity Propagation, invece, prende come input le misure di somiglianza tra coppie di punti dati, e simultaneamente considera tutti i punti dati come potenziali esemplari. I messaggi a valore reale sono scambiati tra i punti dati fino a quando non emerge gradualmente un set di esemplari di alta qualità e i cluster corrispondenti.

Come input, l’algoritmo richiede di fornire due set di dati:

1. Similarità tra punti dati, che rappresentano quanto un punto sia adatto ad essere l’esemplare di un altro. Se non c’è somiglianza tra due punti, in quanto non possono appartenere allo stesso cluster, questa somiglianza può essere omessa o impostata a -Infinito a seconda dell’implementazione.

2. Preferenze, che rappresentano l’idoneità di ogni punto dati ad essere un esemplare. Possiamo avere qualche informazione a priori su quali punti potrebbero essere favoriti per questo ruolo, e quindi possiamo rappresentarlo attraverso le preferenze.

Sia le somiglianze che le preferenze sono spesso rappresentate attraverso una singola matrice, dove i valori sulla diagonale principale rappresentano le preferenze. La rappresentazione a matrice è buona per serie di dati densi. Dove le connessioni tra i punti sono rade, è più pratico non immagazzinare l’intera matrice n x n in memoria, ma tenere invece una lista di somiglianze con i punti connessi. Dietro la scena, ‘scambiare messaggi tra punti’ è la stessa cosa che manipolare matrici, ed è solo una questione di prospettiva e di implementazione.

L’algoritmo poi gira attraverso un certo numero di iterazioni, fino a quando converge. Ogni iterazione ha due passi di message-passing:

1. Calcolo delle responsabilità: La responsabilità r(i, k) riflette l’evidenza accumulata di quanto il punto k sia adatto a servire come esemplare per il punto i, tenendo conto di altri potenziali esemplari per il punto i. La responsabilità è inviata dal punto dati i al punto candidato esemplare k.

2. Calcolo delle disponibilità: La disponibilità a(i, k) riflette l’evidenza accumulata per quanto sarebbe appropriato per il punto i scegliere il punto k come suo esemplare, tenendo conto del supporto da altri punti che il punto k dovrebbe essere un esemplare. La disponibilità è inviata dal punto candidato esemplare k al punto i.

Per calcolare le responsabilità, l’algoritmo usa le somiglianze originali e le disponibilità calcolate nell’iterazione precedente (inizialmente, tutte le disponibilità sono impostate a zero). Le responsabilità sono impostate sulla somiglianza di input tra il punto i e il punto k come suo esemplare, meno la più grande somma di somiglianza e disponibilità tra il punto i e altri esemplari candidati. La logica dietro al calcolo di quanto un punto sia adatto per un esemplare è che è favorito di più se la preferenza iniziale a priori era più alta, ma la responsabilità diventa più bassa quando c’è un punto simile che si considera un buon candidato, così c’è una ‘competizione’ tra i due fino a quando uno è deciso in qualche iterazione.

Calcolare le disponibilità, quindi, usa le responsabilità calcolate come prova se ogni candidato sarebbe un buon esemplare. La disponibilità a(i, k) è impostata sull’autoresponsabilità r(k, k) più la somma delle responsabilità positive che il candidato esemplare k riceve da altri punti.

Infine, possiamo avere diversi criteri di arresto per terminare la procedura, come quando le variazioni dei valori scendono sotto una certa soglia, o il numero massimo di iterazioni è raggiunto. In qualsiasi punto della procedura di Propagazione dell’Affinità, la somma delle matrici Responsabilità (r) e Disponibilità (a) ci dà le informazioni di clustering di cui abbiamo bisogno: per il punto i, il k con il massimo r(i, k) + a(i, k) rappresenta l’esemplare del punto i. Oppure, se ci serve solo l’insieme degli esemplari, possiamo scansionare la diagonale principale. Se r(i, i) + a(i, i) > 0, il punto i è un esemplare.

Abbiamo visto che con K-Means e algoritmi simili, decidere il numero di cluster può essere difficile. Con AP, non dobbiamo specificarlo esplicitamente, ma può ancora aver bisogno di qualche regolazione se otteniamo più o meno cluster di quelli che potremmo trovare ottimali. Fortunatamente, semplicemente regolando le preferenze possiamo abbassare o alzare il numero di cluster. Impostando le preferenze su un valore più alto si otterrà un maggior numero di cluster, poiché ogni punto è “più sicuro” della sua idoneità ad essere un esemplare ed è quindi più difficile “batterlo” e includerlo sotto il “dominio” di qualche altro punto. Al contrario, impostando preferenze più basse si otterrà di avere meno cluster; come se dicessero “no, no, per favore, tu sei un esemplare migliore, mi unirò al tuo cluster”. Come regola generale, possiamo impostare tutte le preferenze sulla similarità mediana per un numero medio-grande di cluster, o sulla similarità più bassa per un numero moderato di cluster. Tuttavia, un paio di esecuzioni con la regolazione delle preferenze possono essere necessarie per ottenere il risultato che si adatta esattamente alle nostre esigenze.

Propagazione di affinità gerarchica è anche degno di nota, come una variante dell’algoritmo che affronta la complessità quadratica dividendo il set di dati in un paio di sottoinsiemi, raggruppandoli separatamente, e quindi eseguendo il secondo livello di clustering.

In The End…

C’è un’intera gamma di algoritmi di clustering, ognuno con i suoi pro e contro per quanto riguarda il tipo di dati con cui lavorano, la complessità temporale, i punti deboli e così via. Per citare altri algoritmi, per esempio c’è l’Hierarchical Agglomerative Clustering (o Linkage Clustering), buono per quando non abbiamo necessariamente cluster circolari (o iper-sferici), e non sappiamo il numero di cluster in anticipo. Inizia con ogni punto che è un cluster separato, e lavora unendo due cluster più vicini in ogni passo fino a quando tutto è in un unico grande cluster.

Con l’Hierarchical Agglomerative Clustering, possiamo facilmente decidere il numero di cluster dopo tagliando il dendrogramma (diagramma ad albero) orizzontalmente dove ci sembra adatto. È anche ripetibile (dà sempre la stessa risposta per lo stesso set di dati), ma è anche di una complessità maggiore (quadratica).

Poi, DBSCAN (Density-Based Spatial Clustering of Applications with Noise) è anche un algoritmo degno di nota. Raggruppa i punti che sono strettamente impacchettati insieme, espandendo i cluster in qualsiasi direzione dove ci sono punti vicini, trattando così diverse forme di cluster.

Questi algoritmi meritano un articolo a parte, e possiamo esplorarli in un post separato più avanti.

Ci vuole esperienza con qualche prova ed errore per sapere quando usare un algoritmo o l’altro. Fortunatamente, abbiamo una serie di implementazioni in diversi linguaggi di programmazione, quindi provarle richiede solo un po’ di voglia di giocare.