Un unico punto di riferimento per la clusterizzazione K-Means

Un'unica guida di riferimento per la clusterizzazione K-Means

Come raggruppare punti dati simili in modo che abbia senso? Beh, K-Means è una delle risposte. Questo articolo racchiude praticamente tutto sulla clustering di K-Means. Detto ciò, non ho scritto il codice 🙂

SOMMARIO —

1. Cos’è il clustering di K-Means
2. Proprietà dei cluster
3. Algoritmo per il clustering di K-Means
4. Convergenza/Criteri di arresto
5. Inizializzazione del centroide: K-Means ++
6. Scelta di un K ottimale
7. Valutazione della qualità del cluster

I piccioni dello stesso piumaggio volano insieme

• Tendenze future nell’integrazione dei dati
• Primi importanti articoli di Visione Artificiale della Settimana dal 9/10 al 15/10
• ChatGPT’ contro ‘BARD

1. Cos’è il clustering di K-Means?

Il clustering di K-Means è un algoritmo di apprendimento non supervisionato che ci aiuta a raggruppare insieme punti dati simili nel nostro insieme di dati in cluster. Questi cluster rappresentano le caratteristiche condivise dai punti dati, che segnano la loro somiglianza.

In termini semplici, K-Means è simile a KNN, dove guardiamo i K punti più vicini per la somiglianza. Nel clustering di K-Means, formiamo K cluster in modo che i punti raggruppati in un cluster siano simili e condividano caratteristiche comuni. Il diagramma qui sotto lo renderà più chiaro:

K-Means ci aiuta a ottenere un grafico come quello sopra semplicemente passando i nostri dati come parametro di input. Poiché stiamo solo formando cluster basati sui punti dati che abbiamo, non abbiamo bisogno di un’etichetta y per questi punti. Pertanto, raggruppamento è un algoritmo di apprendimento non supervisionato, in cui non richiediamo l’etichetta dei punti dati.

Applicazioni del clustering —

1. Segmentazione dei clienti 2. Segmentazione dei documenti 3. Segmentazione delle immagini 4. Sistemi di raccomandazione, ecc.

2. Proprietà dei cluster

Ora, questi cluster hanno alcune proprietà, seguendo le quali diventano significativi.

1. Tutti i punti dati all’interno di un cluster dovrebbero essere il più simili possibile — I punti dati all’interno di un cluster sono molto vicini tra loro. Questo significa che nello spazio delle caratteristiche, i punti dati rappresentano caratteristiche simili. Inoltre, i punti simili si raggruppano meglio. Quindi i punti all’interno di un cluster dovrebbero essere il più simili possibile affinché il cluster abbia senso.
2. I punti dati provenienti da cluster diversi dovrebbero essere il più diversi possibile — I punti dati provenienti da cluster diversi sono molto lontani tra loro. Ciò significa che nello spazio delle caratteristiche, questi punti rappresentano caratteristiche molto diverse. Inoltre, punti diversi non si raggrupperebbero mai. Pertanto, i punti provenienti da cluster diversi dovrebbero essere il più diversi possibile affinché i cluster abbiano senso.
3. Ogni cluster ha un centroide — Ogni cluster che formiamo ha un centroide intorno al quale sono associati tutti i punti. Questo centroide è il punto che ci aiuta a formare i cluster ed è regolato in base alla media dei punti all’interno del cluster.

~Beh, non preoccuparti così tanto delle proprietà, è solo teoria noiosa. La parte divertente è la prossima

3. Algoritmo per il clustering

Qui è dove entriamo nel dettaglio di come questo algoritmo genera bellissimi cluster.

Algo —

• [Step 1] — Scegliere il numero di cluster desiderati (K) — Questo può essere scelto arbitrariamente per ora, poiché decideremo successivamente come scegliere il valore K. Di solito si sceglie un valore casuale di K=3 per iniziare l’algoritmo.
• [Step 2] — Selezionare K punti casuali come centri di ogni cluster (K-centroids) — Questi punti vengono selezionati casualmente per formare i centroidi per ogni cluster. Questi punti possono essere scelti casualmente dai nostri dati o da un’altra fonte.
• [Step 3] — Assegnare ogni punto dati al centroide più vicino — Calcoliamo quindi la distanza di ogni punto nel nostro dataset da tutti i centroidi K. Il punto viene assegnato al centroide che ha la distanza minore da quel centroide. Questo può essere visualizzato come mostrato di seguito:

Questo viene ripetuto per ogni punto e, alla fine, ogni punto viene assegnato a uno dei centroidi. In questo modo, otteniamo K-cluster. In generale, utilizziamo la distanza euclidea per calcolare la distanza tra punti e centroidi.

• [Step 4] — Calcolare i nuovi centroidi — Dopo aver assegnato ogni punto a uno dei centroidi, calcoliamo i nuovi centroidi per ogni cluster prendendo la media di tutti i punti in ciascun cluster. I nuovi centroidi possono essere calcolati prendendo la media delle coordinate x e delle coordinate y di tutti i punti dati separatamente.

Qui ‘m’ è il numero di punti dati in un determinato cluster.

• [Step 5] — Ripetere i passaggi 3 e 4 fino al raggiungimento della convergenza/condizione di arresto

Visualizziamo:

1. [Step 1] — Supponiamo di scegliere k = 22. [Step 2] —

3. [Step 3] —

4. [Step 4] —

5. [Step 5] —

4. Convergenza/Condizione di arresto

L’algoritmo sopra se non converge, si ripeterà all’infinito. Pertanto, abbiamo bisogno di alcuni criteri di stop per l’algoritmo sopra. Ci sono alcuni criteri di stop, che quando incontrati dovrebbero far fermare l’algoritmo. Questi sono:

1. I punti dati assegnati a un cluster specifico rimangono gli stessi – Eseguiamo l’algoritmo finché i punti dati non vengono assegnati a nuovi cluster. Questo richiede molto tempo.
2. I centroidi rimangono gli stessi – Eseguiamo l’algoritmo finché i nuovi centroidi calcolati sono gli stessi dei precedenti. Questo richiede molto tempo.
3. La distanza dei punti dati dal centroide è minima – Impostiamo una soglia per la distanza dei punti dati dal centroide. Quando questa soglia viene raggiunta, l’algoritmo si fermerà. Questo è veloce, ma dobbiamo selezionare attentamente la soglia di distanza.
4. È stato raggiunto un numero fisso di iterazioni: impostiamo una soglia per il numero di iterazioni e ci fermiamo quando questa soglia viene raggiunta. Questo è veloce, ma un’impostazione errata della soglia può portare a formazioni di cluster scadenti.

Possiamo implementare queste condizioni di stop nel nostro algoritmo per una convergenza anticipata e un clustering appropriato.

5. Inizializzazione dei centroidi

In K-Means, inizializziamo i centroidi in modo casuale. Ciò può comportare alcuni problemi e portare a una formazione di cluster scadente.

• Se il centroide è un punto lontano (outlier), potrebbe non esserci alcun punto dati assegnato a questo centroide. Ciò può comportare l’assegnazione di più di un cluster allo stesso centroide.
• Se due o più centroidi sono inizializzati molto vicini tra loro, ciò può comportare l’assegnazione di più di un centroide allo stesso cluster.

Entrambi questi problemi possono essere visualizzati nel diagramma sottostante:

Pertanto, abbiamo bisogno di un metodo migliore per l’inizializzazione dei centroidi. Possiamo utilizzare uno dei due approcci menzionati:

1. Ripetere K-Means diverse volte fino a ottenere i migliori cluster
2. Utilizzare l’algoritmo K-Means++

Il primo è molto inefficiente in termini di complessità temporale per ovvie ragioni. Pertanto utilizziamo l’algoritmo K-Means++ per l’inizializzazione dei centroidi.

K-Means++

Questo è solo un algoritmo per l’inizializzazione dei centroidi, il resto del processo è lo stesso dell’algoritmo K-Means.

Algoritmo —

1. Selezionare il primo centroide in modo casuale
2. Calcolare la distanza di ogni punto dal centroide più vicino (primo centroide all’inizio dell’algoritmo)
3. Assegnare valori di probabilità a ogni punto. I valori di probabilità sono proporzionali alla distanza del punto dal centroide precedente. Ciò significa che un punto con la massima distanza dal centroide avrà il valore di probabilità più alto di essere selezionato come prossimo centroide.
4. Ripetere questi passaggi fino a quando non abbiamo K centroidi.

Grazie a questa inizializzazione, si assicura che ogni centroide sia il più lontano possibile dagli altri. Pertanto, non più di un centroide può essere assegnato allo stesso cluster e non più di un cluster è assegnato allo stesso centroide.

Dopo di ciò, l’algoritmo K-Means riprende, dove i punti dati vengono quindi assegnati al centroide più vicino e così via.

6. Scelta di un K ottimale

Scegliere un valore ottimale di K è molto importante in quanto potrebbe portare a cluster strutturati in modo bello o a cluster disorganizzati e inefficaci.

Esistono diversi modi per scegliere il valore di K, ma il modo più ottimale è attraverso un metodo chiamato metodo del gomito (Elbow method). Il nostro obiettivo qui è trovare il valore di K per il quale l’errore somma dei quadrati all’interno dei cluster (WCSSE) è il minimo.

WCSSE rappresenta la somma delle distanze quadrate dei punti dati dal centroide all’interno dello stesso cluster.

Metodo del Gomito

Il Metodo del Gomito è una tecnica con cui possiamo selezionare un valore K guardando il risultato dato da ogni K.

Il WCSSE viene calcolato per tutti i cluster e rappresentato graficamente in funzione dei diversi valori di K. Il punto nel grafico in cui il WCSSE diminuisce rapidamente è il punto che stiamo cercando. Questo punto ci indica quel particolare valore di K per cui il WCSSE diminuisce rapidamente e diventa quasi costante. Quindi, dopo questo punto, aumentare il valore di K non riduce molto il WCSSE e quindi questo punto è il valore K ottimale.

I passaggi per il Metodo del Gomito sono i seguenti:

• Scegliamo un K in un intervallo (ad esempio da 1 a 10)
• Per ogni valore di K in questo intervallo, troviamo il WCSSE per tutti i cluster.
• Quindi rappresentiamo graficamente il WCSSE in funzione di K, dove K è sull’asse X.
• Il K in cui il valore del WCSSE diminuisce rapidamente e forma una forma ad arco, è il valore ottimale di K che scegliamo.

Dal grafico precedente, possiamo vedere che per un valore K di 5, il WCSSE diminuisce rapidamente e diventa quasi costante dopo. Pertanto, oltre 5 cluster, il WCSSE non diminuisce molto. Quindi, scegliamo K= 5.

7. Valutazione della Qualità del Cluster

Per fare in modo che i cluster abbiano senso, dobbiamo valutare la qualità di ogni cluster. Per qualità, intendo quanto bene i nostri cluster spieghino i nostri dati. Per fare ciò, dobbiamo tornare alle nostre proprietà di cluster. Un cluster che rispetta tutte le proprietà è considerato un buon cluster. Quindi, come possiamo valutare matematicamente le proprietà del cluster?

Ci sono due modi: 1. Inerzia 2. Indice Dunn

1. INERZIA

L’inerzia si riferisce alla somma totale delle distanze tra i punti e il centroide del cluster specifico. Questo può essere considerato anche come la distanza tra cluster intra, poiché stiamo calcolando la distanza tra i punti all’interno del cluster. Per un centroide di cluster C1, possiamo definire l’inerzia come:

dove i varia da 1 a m (numero di punti in quel cluster)

L’immagine sopra rappresenta la distanza inter-cluster o inerzia.

Perché un cluster sia significativo, la distanza tra i suoi punti e il centroide dovrebbe essere il più piccola possibile. In questo modo il cluster soddisfa la prima proprietà.

Quindi, il valore di inerzia dovrebbe essere il più piccolo possibile per un buon cluster.

2. INDICE DUNN

L’indice Dunn è la misura della seconda proprietà dei cluster. Misura quanto distanti sono i cluster l’uno dall’altro, indicando la differenza tra le proprietà di due cluster. L’indice Dunn lo fa calcolando sia la distanza intra-cluster sia la distanza inter-cluster.

La distanza inter-cluster si riferisce alla distanza tra due cluster. Ora, questa differenza può dipendere anche da come la misuriamo.

– Potrebbe essere la differenza tra i centroidi dei due cluster – Potrebbe essere la differenza tra i punti più lontani dai due cluster – Potrebbe essere la differenza tra i punti più vicini dai due cluster.

Indipendentemente dai criteri scelti per misurare la distanza inter-cluster, l’indice di Dunn può essere rappresentato come:

Perché due cluster siano il più possibile diversi/lontani, il numeratore dovrebbe essere molto grande e il denominatore dovrebbe essere molto piccolo. Pertanto,

• La distanza minima tra qualsiasi due cluster [min(distancia inter-cluster)] dovrebbe essere molto grande affinché il numeratore sia un valore grande.
• La distanza massima tra i punti e il centroide di un cluster [max(distanza intra-cluster)] dovrebbe essere un valore molto piccolo affinché il denominatore sia un valore piccolo.

Perché un cluster sia significativo, la distanza inter-cluster deve essere il più grande possibile. Di conseguenza, il cluster potrebbe soddisfare la seconda proprietà.

Quindi, l’indice di Dunn deve essere il più grande possibile per un buon cluster.

Bene, questo era quasi tutto sulla Clustering K-Means, nella teoria. Lo coderò.

Dai un’occhiata anche a questi argomenti—

1. KNN
2. Regressione Logistica
3. Support Vector Machine
4. Naive Bayes
5. Metriche di Valutazione — Classificazione