Che cos’è il Clustering K-Means?

Il clustering K-means è un algoritmo di apprendimento non supervisionato, e tra tutti gli algoritmi di apprendimento non supervisionato, il clustering K-means potrebbe essere il più utilizzato, grazie alla sua potenza e semplicità. Come funziona esattamente il clustering K-means?

La risposta breve è che il clustering K-means funziona creando un punto di riferimento (un centroid) per un numero desiderato di classi, e poi assegnando i punti di dati alle classi in base a quale punto di riferimento è più vicino. Mentre questa è una definizione rapida per il clustering K-means, prendiamoci un po’ di tempo per esplorare più a fondo il clustering K-means e capire meglio come funziona.

Definizione del Clustering

Prima di esaminare gli algoritmi esatti utilizzati per eseguire il clustering K-means, prendiamoci un po’ di tempo per definire il clustering in generale.

I cluster sono solo gruppi di elementi, e il clustering è solo l’azione di raggruppare gli elementi. Nel senso della scienza dei dati, gli algoritmi di clustering mirano a fare due cose:

• Assicurarsi che tutti i punti di dati in un cluster siano il più simili possibile l’uno all’altro.
• Assicurarsi che tutti i punti di dati in cluster diversi siano il più dissimili possibile l’uno dall’altro.

Gli algoritmi di clustering raggruppano gli elementi in base a una metrica di similarità. Ciò viene spesso fatto trovando il “centroid” dei diversi gruppi possibili nel set di dati, anche se non esclusivamente. Esistono diversi algoritmi di clustering, ma l’obiettivo di tutti gli algoritmi di clustering è lo stesso, ovvero determinare i gruppi intrinseci di un set di dati.

Clustering K-Means

Il clustering K-means è uno dei più vecchi e comuni tipi di algoritmi di clustering, e funziona in base alla quantizzazione vettoriale. C’è un punto nello spazio scelto come origine, e poi vengono disegnati vettori dall’origine a tutti i punti di dati nel set di dati.

In generale, il clustering K-means può essere suddiviso in cinque passaggi diversi:

• Collocare tutte le istanze in sottinsiemi, dove il numero di sottinsiemi è uguale a K.
• Trovare il punto medio/centroid dei nuovi cluster creati.
• In base a questi centroid, assegnare ogni punto a un cluster specifico.
• Calcolare le distanze da ogni punto ai centroid, e assegnare i punti ai cluster dove la distanza dal centroid è minima.
• Dopo che i punti sono stati assegnati ai cluster, trovare il nuovo centroid dei cluster.

I passaggi sopra vengono ripetuti fino a quando il processo di training non è completato.

Nella fase iniziale, i centroid vengono posizionati da qualche parte tra i punti di dati.
Foto: Weston.pace via wikimedia commons, GNU Free Documentation License (https://commons.wikimedia.org/wiki/File:K_Means_Example_Step_1.svg)

In alternativa, dopo che i centroid sono stati posizionati, possiamo concepire il clustering K-means come un’alternanza tra due fasi diverse: etichettare i punti di dati e aggiornare i centroid.

Nel secondo passo, una metrica di distanza come la distanza euclidea viene utilizzata per calcolare a quale centroid un punto dato è più vicino, e poi i punti vengono assegnati al cluster di quel centroid. Foto: Weston.pace via Wikimedia Commons, GNU Free Doc License (https://commons.wikimedia.org/wiki/File:K_Means_Example_Step_2.svg)

Nella fase di etichettatura dei punti di dati, ogni punto di dati viene assegnato a un’etichetta che lo colloca nel cluster appartenente al centroid più vicino. Il centroid più vicino viene solitamente determinato utilizzando la distanza euclidea al quadrato, anche se possono essere utilizzate altre metriche di distanza come la distanza di Manhattan, la distanza di Cosine e la distanza di Jaccard a seconda del tipo di dati immessi nell’algoritmo di clustering.

Nel terzo passo, i centroid vengono spostati alla media di tutti i punti di dati. Le classi vengono quindi riassegnate. Foto: Weston.pace via Wikiemedia Commons, CC SA 3.0 (https://commons.wikimedia.org/wiki/File:K_Means_Example_Step_3.svg)

Nella fase di aggiornamento del centroid, il centroid viene calcolato trovando la media della distanza tra tutti i punti di dati attualmente contenuti in un cluster.

Come Scegliere il Valore Giusto per “K”

Considerando che il clustering K-means è un algoritmo non supervisionato e il numero di classi non è noto in anticipo, come si decide sul numero appropriato di classi/il valore giusto per K?

Una tecnica per selezionare il valore giusto di K è chiamata “tecnica del gomito”. La tecnica del gomito consiste nell’eseguire un algoritmo di clustering K-means per una gamma di diversi valori di K e utilizzare una metrica di accuratezza, solitamente la Somma degli Errori al Quadrato, per determinare quali valori di K danno i migliori risultati. La Somma degli Errori al Quadrato viene determinata calcolando la media della distanza tra il centroid di un cluster e i punti di dati in quel cluster.

Il termine “tecnica del gomito” deriva dal fatto che quando si traccia la SSE in relazione ai diversi valori di K, il grafico risultante avrà spesso una forma a “gomito”, dove la SSE diminuisce rapidamente per i primi valori di K, ma poi si livella. In tali condizioni, il valore di K situato al gomito è il miglior valore per K, poiché ci sono ritorni rapidamente decrescenti dopo questo valore.

Clustering K-Means a Lotti

Man mano che i set di dati crescono, anche il tempo di calcolo cresce. Il clustering K-means di base può richiedere molto tempo per essere completato quando viene eseguito su set di dati enormi, e di conseguenza, sono stati apportati alcuni aggiustamenti al clustering K-means per ridurre i costi spaziali e temporali dell’algoritmo.

Il clustering K-means a lotti è una variante del clustering K-means in cui la dimensione del set di dati considerato è limitata. Il clustering K-means normale opera sull’intero set di dati/batch alla volta, mentre il clustering K-means a lotti suddivide il set di dati in sottinsiemi. I lotti vengono campionati casualmente dall’intero set di dati e per ogni nuova iterazione viene selezionato un nuovo campione casuale e utilizzato per aggiornare la posizione dei centroid.

Nel clustering K-means a lotti, i cluster vengono aggiornati con una combinazione dei valori del lotto e di una velocità di apprendimento. La velocità di apprendimento diminuisce durante le iterazioni, ed è l’inverso del numero di punti di dati posizionati in un cluster specifico. L’effetto della riduzione della velocità di apprendimento è che l’impatto dei nuovi dati viene ridotto e la convergenza viene raggiunta quando, dopo diverse iterazioni, non ci sono più cambiamenti nei cluster.

I risultati degli studi sull’efficacia del clustering K-means a lotti suggeriscono che può ridurre con successo il tempo di calcolo con un leggero compromesso nella qualità dei cluster.

Applicazioni del Clustering K-Means

Il clustering K-means può essere utilizzato in sicurezza in qualsiasi situazione in cui i punti di dati possano essere segmentati in gruppi/classi distinti. Ecco alcuni esempi di casi d’uso comuni per il clustering K-means.

Il clustering K-means potrebbe essere applicato alla classificazione dei documenti, raggruppando i documenti in base a caratteristiche come argomenti, tag, utilizzo delle parole, metadati e altre caratteristiche dei documenti. Potrebbe anche essere utilizzato per classificare gli utenti come bot o non bot in base a modelli di attività come post e commenti. Il clustering K-means può anche essere utilizzato per raggruppare le persone in base ai livelli di preoccupazione quando si monitora la loro salute, in base a caratteristiche come comorbidità, età, storia del paziente, ecc.

Il clustering K-means può anche essere utilizzato per compiti più aperti come la creazione di sistemi di raccomandazione. Gli utenti di un sistema come Netflix (NFLX ) possono essere raggruppati insieme in base ai modelli di visualizzazione e raccomandati contenuti simili. Il clustering K-means potrebbe essere utilizzato per compiti di rilevamento di anomalie, evidenziando potenziali istanze di frode o articoli difettosi.