Che cosa è un algoritmo di clustering ?
Il clustering è una tecnica di Machine Learning che coinvolgeil raggruppamento di punti dati. Dato un insieme di punti dati, possiamo utilizzare un algoritmo di clustering per classificare ciascun punto dati in un gruppo specifico. In teoria, i punti dati che si trovano nello stesso gruppo dovrebbero avere proprietà e/o caratteristiche simili, mentre i punti dati in gruppi diversi dovrebbero avere proprietà e/o caratteristiche molto diverse. Il clustering è un metodo di apprendimento non supervisionato ed è una tecnica comune per l'analisi statistica dei dati utilizzata in molti campi.
Nella Scienza dei dati, possiamo utilizzare l'analisi di clustering per acquisire alcune preziose informazioni da nostri dati da vedere ciò che raggruppa i punti di dati in autunno, quando si applica un algoritmo di clustering. Oggi esamineremo 5 popolari algoritmi di clustering che i data scientist devono conoscere e i loro pro e contro!
1° Algoritmo di Clustering : K-Means
K-Means è probabilmente l'algoritmo di clustering più noto. Viene insegnato in molte lezioni introduttive di data science e machine learning. È facile da capire e implementare nel codice! Dai un'occhiata al grafico qui sotto per un'illustrazione.
Come funziona l'algoritmo K-Means
Per iniziare, selezioniamo prima un numero di classi/gruppi da utilizzare e inizializziamo in modo casuale i rispettivi punti centrali. Per capire il numero di classi da utilizzare, è bene dare una rapida occhiata ai dati e cercare di identificare eventuali raggruppamenti distinti. I punti centrali sono vettori della stessa lunghezza di ciascun vettore di punti dati e sono le "X" nel grafico sopra.
Ciascun punto dati viene classificato calcolando la distanza tra quel punto e il centro di ciascun gruppo, quindi classificando il punto come appartenente al gruppo il cui centro è più vicino ad esso.
Sulla base di questi punti classificati, ricalcoliamo il centro del gruppo prendendo la media di tutti i vettori del gruppo.
Ripeti questi passaggi per un determinato numero di iterazioni o fino a quando i centri di gruppo non cambiano molto tra le iterazioni. Puoi anche scegliere di inizializzare casualmente i centri di gruppo alcune volte, quindi selezionare la corsa che sembra aver fornito i migliori risultati.
K-Means ha il vantaggio di essere abbastanza veloce, poiché tutto ciò che stiamo facendo è calcolare le distanze tra i punti e i centri del gruppo; pochissimi calcoli! Ha quindi una complessità lineare O ( n ).
D'altra parte, K-Means ha un paio di svantaggi. Innanzitutto, devi selezionare quanti gruppi/classi ci sono. Questo non è sempre banale e idealmente con un algoritmo di clustering vorremmo che li capisse per noi perché il punto è ottenere alcune informazioni dai dati. K-means inizia anche con una scelta casuale di centri di cluster e quindi può produrre risultati di clustering diversi su diverse esecuzioni dell'algoritmo. Pertanto, i risultati potrebbero non essere ripetibili e mancare di coerenza. Altri metodi cluster sono più coerenti.
K-Medians è un altro algoritmo di clustering correlato a K-Means, tranne per il fatto che invece di ricalcolare i punti centrali del gruppo usando la media usiamo il vettore mediano del gruppo. Questo metodo è meno sensibile ai valori anomali (a causa dell'utilizzo della mediana) ma è molto più lento per i set di dati più grandi poiché l'ordinamento è richiesto su ogni iterazione durante il calcolo del vettore mediano.
2° Algoritmo di Clustering : Mean-Shift
Il clustering dello spostamento medio è un algoritmo basato su finestre scorrevoli che tenta di trovare aree dense di punti dati. È un algoritmo basato sul centroide, il che significa che l'obiettivo è individuare i punti centrali di ciascun gruppo/classe, che funziona aggiornando i candidati per i punti centrali come media dei punti all'interno della finestra scorrevole. Queste finestre candidate vengono quindi filtrate in una fase di post-elaborazione per eliminare i quasi duplicati, formando l'insieme finale di punti centrali e i loro gruppi corrispondenti. Dai un'occhiata al grafico qui sotto per un'illustrazione.
Come funziona l'algoritmo di Clustering Mean-Shift
Per spiegare lo spostamento medio considereremo un insieme di punti nello spazio bidimensionale come nell'illustrazione sopra. Iniziamo con una finestra scorrevole circolare centrata in un punto C (selezionato casualmente) e avente raggio r come nucleo. Lo spostamento medio è un algoritmo in salita che comporta lo spostamento iterativo di questo kernel in una regione di densità più elevata ad ogni passo fino alla convergenza.
Ad ogni iterazione, la finestra scorrevole viene spostata verso regioni di maggiore densità spostando il punto centrale sulla media dei punti all'interno della finestra (da cui il nome). La densità all'interno della finestra scorrevole è proporzionale al numero di punti al suo interno. Naturalmente spostandosi sulla media dei punti nella finestra si sposterà gradualmente verso aree di maggiore densità di punti.
Continuiamo a spostare la finestra scorrevole secondo la media finché non c'è una direzione in cui uno spostamento può ospitare più punti all'interno del kernel. Guarda il grafico sopra; continuiamo a muovere il cerchio finché non aumentiamo più la densità (cioè il numero di punti nella finestra).
Questo processo dei passaggi da 1 a 3 viene eseguito con molte finestre scorrevoli finché tutti i punti non si trovano all'interno di una finestra. Quando più finestre scorrevoli si sovrappongono, viene conservata la finestra contenente il maggior numero di punti. I punti dati vengono quindi raggruppati in base alla finestra scorrevole in cui risiedono.
Di seguito è mostrata un'illustrazione dell'intero processo dall'inizio alla fine con tutte le finestre scorrevoli. Ogni punto nero rappresenta il baricentro di una finestra scorrevole e ogni punto grigio è un punto dati.
A differenza del clustering K-means, non è necessario selezionare il numero di cluster poiché lo spostamento medio lo scopre automaticamente. Questo è un enorme vantaggio. Anche il fatto che i centri del cluster convergano verso i punti di massima densità è abbastanza desiderabile in quanto è abbastanza intuitivo da comprendere e si adatta bene in un senso naturalmente guidato dai dati. Lo svantaggio è che la selezione della dimensione/raggio della finestra “r” può essere non banale.
3° Algoritmo di Clustering : Clustering spaziale basato sulla densità di applicazioni con rumore (DBSCAN)
Come fuziona l'algoritmo di Clustering DBSCAN
DBSCAN inizia con un punto dati di partenza arbitrario che non è stato visitato. L'intorno di questo punto viene estratto utilizzando una distanza epsilon ε (Tutti i punti che si trovano all'interno della distanza ε sono punti dell'intorno).
Se c'è un numero sufficiente di punti (secondo minPoints) all'interno di questo intorno, il processo di clustering inizia e il punto dati corrente diventa il primo punto nel nuovo cluster. In caso contrario, il punto verrà etichettato come rumore (in seguito questo punto rumoroso potrebbe diventare parte del cluster). In entrambi i casi quel punto è contrassegnato come “visitato”.
Per questo primo punto nel nuovo ammasso, anche i punti all'interno del suo intorno a distanza diventano parte dello stesso ammasso. Questa procedura per far appartenere tutti i punti nell'intorno allo stesso cluster viene quindi ripetuta per tutti i nuovi punti che sono stati appena aggiunti al gruppo cluster.
Questo processo dei passaggi 2 e 3 viene ripetuto fino a quando tutti i punti del cluster sono stati determinati, ovvero tutti i punti all'interno dell'intorno ε del cluster sono stati visitati ed etichettati.
Una volta terminato il cluster corrente, viene recuperato ed elaborato un nuovo punto non visitato, che porta alla scoperta di un ulteriore cluster o rumore. Questo processo si ripete finché tutti i punti non vengono contrassegnati come visitati. Poiché alla fine di questo sono stati visitati tutti i punti, ogni punto sarà stato contrassegnato come appartenente a un cluster o come rumore.
DBSCAN presenta alcuni grandi vantaggi rispetto ad altri algoritmi di clustering. In primo luogo, non richiede affatto un numero fisso di cluster. Identifica anche i valori anomali come rumori, a differenza dello spostamento medio che li getta semplicemente in un cluster anche se il punto dati è molto diverso. Inoltre, può trovare abbastanza bene cluster di dimensioni e forma arbitraria.
Lo svantaggio principale di DBSCAN è che non funziona come gli altri quando i cluster sono di densità variabile. Questo perché l'impostazione della soglia di distanza e dei minPoints per identificare i punti di vicinato varierà da cluster a cluster al variare della densità. Questo inconveniente si verifica anche con dati di dimensioni molto elevate poiché anche in questo caso la soglia di distanza diventa difficile da stimare.
4° Algoritmo di Clustering : Clustering di aspettativa-massimizzazione (EM) utilizzando i modelli di miscela gaussiana (GMM)
Uno dei principali svantaggi di K-Means è il suo uso ingenuo del valore medio per il centro del cluster. Possiamo capire perché questo non è il modo migliore di fare le cose guardando l'immagine qui sotto. Sul lato sinistro, sembra abbastanza ovvio all'occhio umano che ci siano due ammassi circolari con raggio diverso' centrati alla stessa media. K-Means non può gestirlo perché i valori medi dei cluster sono molto vicini tra loro. K-Means fallisce anche nei casi in cui i cluster non sono circolari, sempre a causa dell'utilizzo della media come centro del cluster.
Come funziona l'algoritmo Clustering EM utilizzando GMM
Iniziamo selezionando il numero di cluster (come fa K-Means) e inizializzando casualmente i parametri della distribuzione gaussiana per ciascun cluster. Si può provare a fornire una buona stima dei parametri iniziali dando anche una rapida occhiata ai dati. Anche se nota, come si può vedere nel grafico sopra, questo non è necessario al 100% poiché le gaussiane iniziano come molto scarse ma vengono rapidamente ottimizzate.
Date queste distribuzioni gaussiane per ogni cluster, calcola la probabilità che ogni punto dati appartenga a un particolare cluster. Più un punto è vicino al centro della gaussiana, più è probabile che appartenga a quell'ammasso. Questo dovrebbe avere un senso intuitivo poiché con una distribuzione gaussiana stiamo assumendo che la maggior parte dei dati si trovi più vicino al centro del cluster.
Sulla base di queste probabilità, calcoliamo un nuovo set di parametri per le distribuzioni gaussiane in modo da massimizzare le probabilità dei punti dati all'interno dei cluster. Calcoliamo questi nuovi parametri utilizzando una somma ponderata delle posizioni dei punti dati, dove i pesi sono le probabilità del punto dati appartenente a quel particolare cluster. Per spiegarlo visivamente possiamo dare un'occhiata al grafico sopra, in particolare il cluster giallo come esempio. La distribuzione inizia casualmente alla prima iterazione, ma possiamo vedere che la maggior parte dei punti gialli si trova a destra di quella distribuzione. Quando calcoliamo una somma ponderata per le probabilità, anche se ci sono alcuni punti vicino al centro, la maggior parte di essi si trova a destra. Quindi, naturalmente, la media della distribuzione viene spostata più vicino a quell'insieme di punti. Possiamo anche vedere che la maggior parte dei punti sono "in alto a destra in basso a sinistra". Pertanto la deviazione standard cambia per creare un'ellisse più adatta a questi punti, per massimizzare la somma ponderata dalle probabilità.
I passaggi 2 e 3 vengono ripetuti iterativamente fino alla convergenza, dove le distribuzioni non cambiano molto da un'iterazione all'altra.
Ci sono 2 vantaggi chiave nell'utilizzo dei GMM. In primo luogo i GMM sono molto più flessibili in termini di covarianza dei cluster rispetto alle K-Means; a causa del parametro di deviazione standard, i cluster possono assumere qualsiasi forma di ellisse, piuttosto che essere ristretti a cerchi. K-Means è in realtà un caso speciale di GMM in cui la covarianza di ciascun cluster lungo tutte le dimensioni si avvicina a 0. In secondo luogo, poiché i GMM utilizzano le probabilità, possono avere più cluster per punto dati. Quindi, se un punto dati si trova nel mezzo di due cluster sovrapposti, possiamo semplicemente definire la sua classe dicendo che appartiene X-percento alla classe 1 e Y-percento alla classe 2. Cioè i GMM supportano l' appartenenza mista .
4° Algoritmo di Clustering : Clustering gerarchico aggregato
Gli algoritmi di clustering gerarchico si dividono in 2 categorie: top-down o bottom-up. Gli algoritmi bottom-up trattano ogni punto dati come un singolo cluster all'inizio e quindi successivamente uniscono (o agglomerano ) coppie di cluster fino a quando tutti i cluster sono stati uniti in un singolo cluster che contiene tutti i punti dati. Il clustering gerarchico bottom-up è quindi chiamato clustering gerarchico agglomerativo o HAC . Questa gerarchia di cluster è rappresentata come un albero (o dendrogramma). La radice dell'albero è l'unico grappolo che raccoglie tutti i campioni, le foglie sono i grappoli con un solo campione. Dai un'occhiata al grafico qui sotto per un'illustrazione prima di passare ai passaggi dell'algoritmo
Come funziona l'algoritmo di Clustering gerarchico aggregato
Iniziamo trattando ogni punto dati come un singolo cluster, ovvero se ci sono X punti dati nel nostro set di dati, allora abbiamo X cluster. Selezioniamo quindi una metrica di distanza che misuri la distanza tra due cluster. Ad esempio, utilizzeremo il collegamento medio che definisce la distanza tra due cluster come la distanza media tra i punti dati nel primo cluster e i punti dati nel secondo cluster.
Ad ogni iterazione, combiniamo due cluster in uno. I due cluster da combinare sono selezionati come quelli con il legame medio più piccolo. Cioè, secondo la nostra metrica di distanza selezionata, questi due gruppi hanno la distanza più piccola tra loro e quindi sono i più simili e dovrebbero essere combinati.
Il passaggio 2 viene ripetuto finché non raggiungiamo la radice dell'albero, ovvero abbiamo un solo cluster che contiene tutti i punti dati. In questo modo possiamo selezionare quanti cluster vogliamo alla fine, semplicemente scegliendo quando smettere di combinare i cluster cioè quando smettiamo di costruire l'albero!
Il clustering gerarchico non richiede di specificare il numero di cluster e possiamo persino selezionare quale numero di cluster sembra migliore poiché stiamo costruendo un albero. Inoltre, l'algoritmo non è sensibile alla scelta della distanza metrica; tutti tendono a funzionare ugualmente bene mentre con altri algoritmi di clustering, la scelta della metrica della distanza è fondamentale. Un caso d'uso particolarmente valido dei metodi di clustering gerarchico è quando i dati sottostanti hanno una struttura gerarchica e si desidera ripristinare la gerarchia; altri algoritmi di clustering non possono farlo. Questi vantaggi del clustering gerarchico vanno a scapito di una minore efficienza, poiché ha una complessità temporale di O(n³) , a differenza della complessità lineare di K-Means e GMM.
Conclusione
Ci sono i tuoi 5 migliori algoritmi di clustering che uno scienziato dei dati dovrebbe conoscere! Concluderemo con una fantastica visualizzazione delle prestazioni di questi algoritmi e di alcuni altri, per gentile concessione di Scikit Learn! Molto bello vedere come i diversi algoritmi si confrontano e contrastano con dati diversi!
Quale Algoritmo di Clustering usare sui miei dati ?
_gif.gif)
.png)
Complimenti, un articolo eccellente, di notevole interesse. Grazie per questo gioiellino!