Clustering nel Machine Learning: 5 algoritmi di clustering essenziali

Il clustering in sé non è un algoritmo specifico ma il compito generale da risolvere. Puoi raggiungere questo obiettivo usando vari algoritmi che differiscono molto nel modo in cui definiscono un cluster e in come li trovano in modo efficiente. 

Costruire l’intuizione dietro il clustering

Prima di entrare nei dettagli algoritmici, costruiamo un po’ di intuizione usando un semplice esempio con dataset di frutta. Supponiamo di avere una grande collezione di dataset di immagini contenenti tre frutti: (i) fragole, (ii) pere e (iii) mele. 

Nel dataset, tutte le immagini sono mescolate, e il tuo caso d’uso è raggruppare frutti simili, cioè creare tre gruppi, ciascuno contenente un solo tipo di frutto. Questo è esattamente ciò che fa un algoritmo di clustering. 

Criteri chiave di successo per l’analisi di clustering

Il clustering, a differenza di casi d’uso supervisionati come classificazione o regressione, non può essere completamente automatizzato end-to-end. È invece un processo iterativo di scoperta di informazioni che richiede competenza di dominio e giudizio umano, spesso necessari per apportare modifiche ai dati e ai parametri del modello per ottenere il risultato desiderato. 

Ancora più importante, poiché il clustering è apprendimento non supervisionato e non usa dati etichettati, non possiamo calcolare metriche di performance come accuracy, AUC, RMSE ecc. per confrontare diversi algoritmi o tecniche di preprocessing. Di conseguenza, valutare le prestazioni dei modelli di clustering diventa davvero impegnativo e soggettivo. 

I criteri chiave di successo nei modelli di clustering ruotano attorno a:

• È interpretabile?
• L’output del clustering è utile per il business?
• Hai appreso nuove informazioni o scoperto pattern nei dati di cui non eri a conoscenza prima del clustering?

Misurare la qualità del clustering

Senza dati etichettati non puoi calcolare accuracy o AUC. Due metriche aiutano a quantificare quanto bene i tuoi cluster sono separati. Due misure comuni:

• Il Silhouette Score misura quanto un punto è simile al proprio cluster rispetto al cluster vicino più prossimo. Va da -1 a 1; valori sopra 0,5 indicano cluster ben separati.
• Il Davies-Bouldin Index misura la similarità media tra ciascun cluster e il cluster a lui più simile — più basso è, meglio è.

Entrambe sono disponibili in scikit-learn: sklearn.metrics.silhouette_score(X, labels) e sklearn.metrics.davies_bouldin_score(X, labels).

1. K-Means

K-Means è l’algoritmo più utilizzato per i compiti di clustering, soprattutto perché i passaggi sono facili da seguire e l’implementazione in scikit-learn è semplice. È un algoritmo basato su centroidi in cui l’utente deve definire il numero di cluster da creare. 

Questo valore in genere deriva da un caso d’uso aziendale oppure provando diversi numeri di cluster e poi valutando l’output. 

Il clustering K-Means è un algoritmo iterativo che crea cluster non sovrapposti, cioè ogni istanza del dataset può appartenere esclusivamente a un solo cluster. Il modo più semplice per farsi un’idea dell’algoritmo K-Means è seguirne i passaggi insieme al diagramma d’esempio qui sotto. Puoi anche trovare una descrizione dettagliata del processo nei nostri tutorial K-Means Clustering in Python e K-Means Clustering in R. 

1. L’utente specifica il numero di cluster.
2. Inizializza casualmente i centroidi in base al numero di cluster. Nel diagramma sotto, nell’Iterazione 1, nota che tre centroidi sono inizializzati casualmente in blu, rosso e verde.
3. Calcola la distanza tra i punti dati e ciascun centroide e assegna ogni punto al centroide più vicino.
4. Ricalcola la media del centroide in base a tutti i punti assegnati; questo cambia la posizione del centroide, come si vede nelle Iterazioni 2 - 9, fino alla convergenza.
5. L’iterazione continua finché non cambia la media del centroide o si raggiunge un parametro max_iter, ossia il numero massimo di iterazioni definito dall’utente durante il training. In scikit-learn, max_iter è impostato a 300 per default.

Fonte immagine: Learnbymarketing.com

2. MeanShift

A differenza di K-Means, l’algoritmo MeanShift non richiede di specificare il numero di cluster. L’algoritmo determina automaticamente il numero di cluster, un chiaro vantaggio rispetto a K-Means quando non sai quanti cluster contengono i dati. 

MeanShift è anch’esso basato su centroidi e assegna iterativamente ogni punto ai cluster. Il caso d’uso più comune per MeanShift è la segmentazione di immagini.

L’algoritmo MeanShift si basa sulla stima della densità tramite kernel. In modo simile a K-Means, MeanShift assegna iterativamente ciascun punto al centroide di cluster più vicino, inizializzato casualmente, e ogni punto viene spostato nello spazio in base a dove si concentrano più punti, cioè verso la Moda (nel contesto di MeanShift, la moda è l’area con massima densità di punti). 

Per questo motivo MeanShift è noto anche come algoritmo “Mode-seeking”. I passaggi dell’algoritmo MeanShift sono i seguenti:

• Scegli un punto casuale e crea una finestra attorno a quel punto.
• Calcola la media di tutti i punti all’interno di questa finestra.
• Sposta la finestra seguendo la direzione della moda. 
• Ripeti i passaggi fino alla convergenza.

Fonte immagine: ResearchGate

Per una guida passo passo a MeanShift in pratica, vedi il nostro tutorial su Mean Shift Clustering.

3. DBSCAN

DBSCAN, ovvero Density-Based Spatial Clustering of Applications with Noise, è un algoritmo di clustering non supervisionato che parte dal presupposto che i cluster siano regioni dense separate da regioni a densità più bassa. 

Il più grande vantaggio rispetto a K-Means e MeanShift è la robustezza agli outlier: non include i punti anomali in alcun cluster. 

Gli algoritmi DBSCAN richiedono solo due parametri all’utente: 

• Il raggio del cerchio da creare attorno a ciascun punto, noto anche come epsilon

• minPoints, che definisce il numero minimo di punti richiesti dentro quel cerchio affinché il punto sia classificato come Core.

Ogni punto è circondato da un cerchio di raggio epsilon, e DBSCAN li identifica come Core, Border o Noise. Un punto è considerato Core se il cerchio che lo circonda contiene almeno il numero di punti specificato dal parametro minPoints. 

È considerato Border se il numero di punti è inferiore al minimo richiesto, ed è considerato Noise se non ci sono altri punti entro un raggio epsilon da alcun punto. I punti Noise non sono assegnati a nessun cluster (in pratica, sono outlier).

Alcuni casi d’uso comuni di DBSCAN sono:

• Si comporta molto bene nel separare cluster ad alta densità da quelli a bassa densità;
• Funziona molto bene su dataset non lineari, e
• Può essere usato per la rilevazione di anomalie, perché separa i punti di rumore e non li assegna ad alcun cluster.

DBSCAN vs K-Means

Confrontando DBSCAN con K-Means, le differenze più comuni sono: 

• K-Means raggruppa tutte le istanze del dataset, mentre DBSCAN non assegna i punti di rumore (outlier) a un cluster valido
• K-Means fatica con cluster non globali, mentre DBSCAN li gestisce senza problemi
• K-Means assume che tutti i punti del dataset provengano da una distribuzione gaussiana, mentre DBSCAN non fa assunzioni sui dati.

Puoi approfondire nella nostra guida all’algoritmo di clustering DBSCAN, che copre il tuning dei parametri ed esempi pratici. 

Fonte immagine: Medium

4. Clustering Gerarchico

Il clustering gerarchico è un metodo che costruisce una gerarchia di cluster. Esistono due varianti. 

• Agglomerativo: approccio bottom-up in cui all’inizio ogni osservazione è il proprio cluster e, salendo dal basso verso l’alto, le osservazioni vengono unite a coppie e le coppie in cluster. 
• Divisivo: approccio top-down: tutte le osservazioni partono in un cluster unico e vengono suddivise ricorsivamente scendendo dall’alto verso il basso.

Nell’analisi dei dati provenienti dai social network, il clustering gerarchico è di gran lunga il metodo più comune e popolare. I nodi (rami) nel grafo sono confrontati tra loro in base al grado di similarità. Collegando insiemi più piccoli di nodi correlati tra loro, si possono creare raggruppamenti più grandi.

Il maggiore vantaggio del clustering gerarchico è che è facile da comprendere e implementare. Di solito l’output viene analizzato tramite un’immagine come quella qui sotto, chiamata dendrogramma.

Puoi saperne di più nel nostro tutorial sul clustering gerarchico, che mostra come costruire e leggere dendrogrammi in Python. 

Fonte immagine: ResearchGate

5. BIRCH

BIRCH sta per Balanced Iterative Hierarchical Based Clustering. Si usa su dataset molto grandi in cui K-Means non riesce a scalare in pratica. L’algoritmo BIRCH suddivide grandi quantità di dati in piccoli cluster cercando di conservare quante più informazioni possibile. I gruppi più piccoli vengono poi clusterizzati per ottenere l’output finale, invece di clusterizzare direttamente i grandi dataset. 

BIRCH viene spesso usato a supporto di altri algoritmi di clustering generando un riassunto delle informazioni che gli altri algoritmi possono utilizzare. L’utente deve definire il numero di cluster per l’addestramento di BIRCH, in modo simile a K-Means.

Uno dei vantaggi di BIRCH è che può clusterizzare progressivamente e dinamicamente punti dati multidimensionali. Questo serve a creare cluster della massima qualità sotto vincoli dati di memoria e tempo. Nella maggior parte dei casi, BIRCH ha bisogno di un’unica scansione del database, il che lo rende scalabile. 

Il caso d’uso più comune di BIRCH è come alternativa a K-Means efficiente in termini di memoria, per clusterizzare grandi dataset che K-Means non riesce a gestire per limiti di memoria o calcolo.

Applicazioni di business del Clustering

Il clustering ha ampie applicazioni in molti settori: media, sanità, manifattura, retail, e ovunque ci siano grandi quantità di dati non etichettati. Ecco alcuni esempi pratici.

Segmentazione dei clienti

I clienti vengono categorizzati usando algoritmi di clustering in base al loro comportamento d’acquisto o ai loro interessi per sviluppare campagne di marketing mirate. 

Immagina di avere 10 milioni di clienti e di voler creare campagne di marketing personalizzate o focalizzate. È improbabile che tu sviluppi 10 milioni di campagne: cosa fare allora? Potremmo usare il clustering per raggruppare i 10 milioni di clienti in 25 cluster e poi progettare 25 campagne invece di 10 milioni.

Fonte immagine: Medium

Retail Clustering

Nel retail ci sono molte opportunità per il clustering. Ad esempio, puoi raccogliere dati su ciascun negozio e clusterizzare a livello di store per generare insight che ti indichino quali sedi sono simili tra loro in base ad attributi come traffico pedonale, vendite medie, numero di SKU, ecc. 

Un altro esempio potrebbe essere il clustering a livello di categoria. Nel diagramma qui sotto abbiamo otto negozi. I colori diversi rappresentano cluster diversi. In questo esempio ci sono quattro cluster. 

Nota che la categoria deodoranti nello Store 1 è rappresentata dal cluster rosso, mentre nello Store 2 è rappresentata dal cluster blu. Questo indica che Store 1 e Store 2 hanno target di mercato completamente diversi per la categoria deodoranti.

Fonte immagine: dotactiv.com

Clustering nella cura clinica / gestione delle malattie

La sanità e le scienze cliniche offrono applicazioni particolarmente forti per il clustering. Un esempio è la ricerca pubblicata da Komaru & Yoshida et al. 2020, in cui sono stati raccolti dati demografici e di laboratorio per 101 pazienti, poi segmentati in 3 cluster. 

Ogni cluster era caratterizzato da condizioni diverse. Per esempio, il cluster 1 ha pazienti con WBC & CRP bassi. Il cluster 2 ha pazienti con BMP & Siero alti, e il cluster 3 ha pazienti con Siero basso. Ogni cluster rappresenta una diversa traiettoria di sopravvivenza data la mortalità a 1 anno dopo emodialisi.

Fonte immagine: elsevierhealth.com

Segmentazione di immagini

La segmentazione di immagini è la classificazione di un’immagine in gruppi diversi. Molta ricerca è stata fatta sulla segmentazione tramite clustering. Questo tipo di clustering è utile quando vuoi isolare oggetti in un’immagine per analizzarli individualmente e capire cosa sono. 

Nell’esempio sotto, a sinistra c’è l’immagine originale e a destra il risultato dell’algoritmo di clustering. Si vedono chiaramente 4 cluster, cioè 4 oggetti diversi nell’immagine determinati in base ai pixel (tigre, erba, acqua e sabbia).

Confronto tra algoritmi di clustering

Ci sono 10 algoritmi di clustering non supervisionati implementati in scikit-learn, una popolare libreria di machine learning per Python. Ci sono differenze di fondo nel modo in cui ciascun algoritmo determina e assegna i cluster nel dataset. 

Le differenze sottostanti nella modalità matematica di questi algoritmi si riducono a quattro aspetti con cui possiamo confrontarli:

• Parametri richiesti dal modello 
• Scalabilità 
• Casi d’uso 
• Geometria, cioè la metrica usata per il calcolo delle distanze. 

Nel diagramma sotto, ogni colonna rappresenta l’output di un diverso algoritmo di clustering, come K-Means, Affinity Propagation, MeanShift, ecc. In totale ci sono 10 algoritmi addestrati sullo stesso dataset.

Alcuni algoritmi hanno prodotto lo stesso output. Nota che Agglomerative Clustering, DBSCAN, OPTICS e Spectral Clustering hanno portato agli stessi cluster. 

Tuttavia, se confronti l’output di K-Means con quello di MeanShift, noterai che hanno fornito risultati diversi. Con K-Means ci sono solo due gruppi (cluster: blu e arancione), mentre con MeanShift ce ne sono tre, cioè blu, verde e arancione. 

Fonte immagine: scikit-learn

Purtroppo (o per fortuna) nel clustering non c’è una risposta giusta o sbagliata. Sarebbe semplice poter dire “L’algoritmo X qui è il migliore”. 

Questo non è possibile, ed è per questo che il clustering è un compito molto impegnativo. 

In definitiva, quale algoritmo funzioni meglio non dipende da una metrica facilmente misurabile, ma dall’interpretazione e dall’utilità dell’output per il caso d’uso specifico.

Come scegliere l’algoritmo di clustering giusto

Ogni algoritmo è adatto a condizioni di dati diverse. Usa questa tabella come punto di partenza, poi testane almeno due sui tuoi dati reali prima di scegliere.

Un punto di partenza pratico: prova prima K-Means per velocità, passa a DBSCAN se i tuoi dati hanno forme irregolari o outlier, e usa il clustering Gerarchico quando vuoi esplorare visivamente la struttura dei cluster tramite un dendrogramma prima di scegliere k.

Pensieri finali

Il clustering è più difficile da applicare rispetto a tecniche supervisionate come classificazione e regressione per due motivi: non puoi misurare la performance rispetto a target etichettati e parametri come il numero di cluster richiedono giudizio di dominio più che selezione algoritmica. 

Il clustering è una competenza preziosa in molti ruoli: data scientist, ingegneri ML e analisti si imbattono spesso in problemi che il clustering può risolvere. 

Se vuoi approfondire il clustering e il machine learning non supervisionato e impararne l’implementazione in Python e R, i corsi qui sotto possono aiutarti a fare progressi: 

• Cluster Analysis in Python
• Cluster Analysis in R
• Unsupervised Learning in Python
• Unsupervised Learning in R