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 dei cluster in base a quale punto di riferimento è più vicino. Mentre questa è una definizione rapida per il clustering K-means, prendiamo un po’ di tempo per addentrarci nel clustering K-means e ottenere una migliore intuizione di come funziona.

Definizione del Clustering

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

I cluster sono solo gruppi di elementi, e il clustering è solo l’inserimento di elementi in quei gruppi. 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 più simili possibile l’uno all’altro.
• Assicurarsi che tutti i punti di dati in cluster diversi siano 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 in modo esclusivo. Esistono vari algoritmi di clustering diversi, ma l’obiettivo di tutti gli algoritmi di clustering è lo stesso, determinare i gruppi intrinseci di un set di dati.

Clustering K-Means

Il clustering K-means è uno dei tipi di algoritmi di clustering più antichi e più comunemente utilizzati, e funziona in base alla quantizzazione vettoriale. C’è un punto nello spazio selezionato come origine, e poi vettori vengono disegnati 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 formazione 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 quale centroid un punto dato sia più vicino, e poi i punti vengono assegnati alla classe del 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 del coseno e la distanza di Jaccard a seconda del tipo di dati alimentati nell’algoritmo di clustering.

Nel terzo passo, i centroid vengono spostati sulla media di tutti i punti di dati attualmente contenuti in un cluster. 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, i centroid vengono calcolati 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 “la tecnica del gomito”. La tecnica del gomito consiste nell’eseguire un algoritmo di clustering K-means per una gamma di valori K diversi 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 della linea 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 valore migliore per K, poiché ci sono ritorni rapidamente decrescenti dopo questo valore.

Clustering K-Means Mini-Batch

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 massicci, e di conseguenza, sono stati apportati aggiustamenti al clustering K-means per ridurre i costi spaziali e temporali dell’algoritmo.

Il clustering K-means Mini-Batch è una variante del clustering K-means dove 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 Mini-Batch suddivide il set di dati in sottinsiemi. I mini-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 Mini-Batch, i cluster vengono aggiornati con una combinazione dei valori del mini-lotto e di una velocità di apprendimento. La velocità di apprendimento diminuisce durante le iterazioni, ed è l’inverso del numero di punti di dati collocati 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 Mini-Batch suggeriscono che può ridurre con successo il tempo di calcolo con un leggero compromesso nella qualità del cluster.

Applicazioni del Clustering K-Means

Il clustering K-means può essere utilizzato in sicurezza in qualsiasi situazione in cui i punti di dati possono 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 del documento. 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 durante il monitoraggio della 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 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 delle anomalie, evidenziando potenziali istanze di frode o articoli difettosi.