Che cos'è il clustering K-Mean?

K-significa che il clustering è un apprendimento senza supervisione 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-significa funziona creazione di un punto di riferimento (un baricentro) per un numero desiderato di classi, e poi assegnazione di punti dati ai cluster di classe in base a quale punto di riferimento è più vicino. Sebbene questa sia una definizione rapida per il clustering K-mean, prendiamoci del tempo per approfondire il clustering K-means e ottenere una migliore intuizione su come funziona.

Definizione di clustering

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

I cluster sono solo gruppi di elementi e il clustering consiste semplicemente nell'inserire elementi in quei gruppi. Nel senso della scienza dei dati, algoritmi di clustering scopo di fare due cose:

• Assicurati che tutti i punti dati in un cluster siano il più simili possibile tra loro.
• Assicurati che tutti i punti dati in cluster diversi siano il più diversi possibile tra loro.

Gli algoritmi di clustering raggruppano gli elementi in base a una metrica di somiglianza. Questo viene spesso fatto trovando il "centroide" 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, determinare i gruppi intrinseci a un set di dati.

K-Means Clustering

K-Means Clustering è uno dei tipi più vecchi e più comunemente utilizzati di algoritmi di clustering e funziona in base a quantizzazione vettoriale. C'è un punto nello spazio selezionato come origine, quindi i vettori vengono disegnati dall'origine a tutti i punti dati nel set di dati.

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

• Posiziona tutte le istanze in sottoinsiemi, dove il numero di sottoinsiemi è uguale a K.
• Trova il punto medio/centroide delle partizioni del cluster appena create.
• Sulla base di questi centroidi, assegna ciascun punto a un cluster specifico.
• Calcola le distanze da ogni punto ai centroidi e assegna punti ai cluster in cui la distanza dal centroide è minima.
• Dopo che i punti sono stati assegnati ai cluster, trova il nuovo centroide dei cluster.

I passaggi precedenti vengono ripetuti fino al termine del processo di formazione.

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

In alternativa, dopo che i centroidi sono stati posizionati, possiamo concepire il clustering K-means come lo scambio avanti e indietro tra due diverse fasi: etichettare i punti dati e aggiornare i centroidi.

Nella seconda fase, viene utilizzata una metrica di distanza come la distanza euclidea per calcolare a quale centroide è più vicino un dato punto, quindi i punti vengono assegnati alla classe di quel centroide. Foto: Weston.pace tramite Wikimedia Commons, GNU Free Doc License (https://commons.wikimedia.org/wiki/File:K_Means_Example_Step_2.svg)

Nella fase di etichettatura dei punti dati, ad ogni punto dati viene assegnata un'etichetta che lo colloca nel cluster appartenente al centroide più vicino. Il baricentro più vicino viene in genere determinato utilizzando la distanza euclidea al quadrato, sebbene sia possibile utilizzare altre metriche di distanza come la distanza di Manhattan, il coseno e la distanza di Jaccard a seconda del tipo di dati inseriti nell'algoritmo di clustering.

Nella terza fase, il centroide viene spostato sulla media di tutti i punti dati. Le classi vengono quindi riassegnate. Foto: Weston.pace tramite Wikiemedia Commons, CC SA 3.0 (https://commons.wikimedia.org/wiki/File:K_Means_Example_Step_3.svg)

Nella fase di aggiornamento del centroide, il centroide viene calcolato trovando la distanza media tra tutti i punti dati attualmente contenuti all'interno di un cluster.

Come scegliere il giusto valore per "K"

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

Una tecnica per selezionare il giusto valore K è chiamata "la tecnica del gomito”. La tecnica del gomito consiste nell'eseguire un algoritmo di clustering delle medie K per un intervallo di diversi valori K e nell'usare una metrica di accuratezza, tipicamente la somma dell'errore quadratico, per determinare quali valori di K danno i migliori risultati. L'errore della somma al quadrato viene determinato calcolando la distanza media tra il baricentro di un cluster e i punti dati in quel cluster.

Il termine "tecnica del gomito" deriva dal fatto che quando si traccia l'SSE rispetto ai diversi valori di K, il tracciato della linea risultante avrà spesso una forma a "gomito", dove l'SSE diminuisce rapidamente per i primi pochi valori di K, ma poi si stabilizza. In tali condizioni, il valore di K situato al gomito è il valore migliore per K, in quanto vi sono rendimenti rapidamente decrescenti dopo questo valore.

Clustering delle medie K mini-batch

Man mano che i set di dati crescono, aumenta anche il tempo di calcolo. Il completamento del clustering K-means di base può richiedere molto tempo quando viene eseguito su enormi set di dati e, di conseguenza, sono state apportate modifiche al clustering K-means per consentire di ridurre i costi spaziali e temporali dell'algoritmo.

Mini-Batch K-significa clustering è una variante del clustering K-significa dove la dimensione dell'insieme di dati considerato è limitata. Il clustering K-significa normale opera sull'intero set di dati/batch contemporaneamente, mentre il clustering K-significa Mini-batch suddivide il set di dati in sottoinsiemi. I mini-batch 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 centroidi.

Nel clustering delle medie K mini-batch, i cluster vengono aggiornati con una combinazione dei valori mini-batch e una frequenza di apprendimento. Il tasso di apprendimento diminuisce nel corso delle iterazioni ed è l'inverso del numero di punti dati inseriti in un cluster specifico. L'effetto della riduzione del tasso di apprendimento è che l'impatto dei nuovi dati è ridotto e la convergenza si ottiene quando, dopo diverse iterazioni, non ci sono cambiamenti nei cluster.

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

Applicazioni del clustering K-medie

Il clustering K-means può essere tranquillamente utilizzato in qualsiasi situazione in cui i punti dati possono essere segmentati in gruppi/classi distinti. Di seguito sono riportati alcuni esempi di casi d'uso comuni per il clustering K-mean.

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 gruppi in base ai livelli di preoccupazione durante il monitoraggio della loro salute, in base a caratteristiche come comorbidità, età, anamnesi del paziente, ecc.

Il clustering K-means può essere utilizzato anche per attività più aperte come la creazione di sistemi di raccomandazione. Gli utenti di un sistema come Netflix possono essere raggruppati in base a modelli di visualizzazione e contenuti simili consigliati. Il clustering K-means potrebbe essere utilizzato per attività di rilevamento di anomalie, evidenziando potenziali casi di frode o articoli difettosi.