Clustering K-Means — Algoritmo e Come Funziona

Il clustering k-means è un modo per raggruppare dati numerici in $k$ cluster. Se scegli $k$ e usi la versione euclidea standard, l’algoritmo ripete un ciclo: assegna ogni punto al centro più vicino, poi sposta ogni centro sulla media dei punti assegnati.

In parole semplici, cerca di fare in modo che i punti dello stesso gruppo siano vicini tra loro e che i punti di gruppi diversi siano più lontani. È veloce e utile, ma funziona bene solo quando questi "gruppi" sono abbastanza compatti e la distanza ha davvero significato.

Che cosa ottimizza il clustering k-means

Nella forma euclidea standard, k-means cerca di rendere i punti all’interno di ogni cluster il più possibile vicini al centroide di quel cluster. Un obiettivo comune è

$$\sum_{j=1}^{k} \sum_{x_i \in C_j} \|x_i - \mu_j\|^2$$

Qui, $C_j$ è il $j$-esimo cluster e $\mu_j$ è il suo centroide.

Questa è la somma dei quadrati entro il cluster. Valori più piccoli significano che i punti assegnati sono distribuiti più strettamente attorno ai loro centroidi.

Questo obiettivo spiega le due parti dell’algoritmo:

• Se i centroidi sono fissi, la scelta migliore è assegnare ogni punto al centroide più vicino.
• Se le assegnazioni sono fisse, il centroide migliore è la media dei punti assegnati.

Per questo la regola di aggiornamento non è arbitraria. Le "means" di k-means sono letteralmente medie aritmetiche.

Come funziona l’algoritmo k-means

Il ciclo usuale è breve:

1. Scegli $k$ centroidi iniziali.
2. Assegna ogni punto al centroide più vicino.
3. Ricalcola ogni centroide come media dei punti assegnati.
4. Ripeti finché le assegnazioni smettono di cambiare o il miglioramento diventa molto piccolo.

Questo processo di solito converge rapidamente, ma non necessariamente al miglior clustering possibile. Centroidi iniziali diversi possono portare a risultati finali diversi, quindi l’inizializzazione conta.

Esempio di clustering k-means passo dopo passo

Prendi questi punti dati unidimensionali:

$$1,\ 2,\ 3,\ 10,\ 11,\ 12$$

Supponiamo di volere $k = 2$ cluster e di partire con centroidi in $1$ e $10$. È un buon esempio perché i centroidi si spostano davvero dopo il primo aggiornamento.

Passo 1: assegna i punti al centroide più vicino

I punti $1, 2, 3$ sono più vicini a $1$.

I punti $10, 11, 12$ sono più vicini a $10$.

Quindi i cluster sono

$$C_1 = \{1,2,3\}, \qquad C_2 = \{10,11,12\}$$

Passo 2: aggiorna i centroidi

Il nuovo centroide del primo cluster è

$$\mu_1 = \frac{1+2+3}{3} = 2$$

Il nuovo centroide del secondo cluster è

$$\mu_2 = \frac{10+11+12}{3} = 11$$

Entrambi i centroidi si sono spostati, da $1$ a $2$ e da $10$ a $11$.

Passo 3: assegna di nuovo

Ora controlla di nuovo il centroide più vicino usando $2$ e $11$.

I punti $1, 2, 3$ appartengono ancora al primo cluster, e i punti $10, 11, 12$ appartengono ancora al secondo cluster. Poiché le assegnazioni non cambiano più, l’algoritmo è convergente.

Questo è un esempio pulito perché i dati si separano naturalmente in due gruppi compatti. I dataset reali sono più disordinati, ed è lì che k-means può iniziare a trarre in inganno.

Quando k-means funziona bene

K-means funziona meglio quando queste condizioni sono approssimativamente vere:

• Le caratteristiche sono numeriche.
• La distanza euclidea è un modo ragionevole per misurare la somiglianza.
• I cluster sono abbastanza compatti, non lunghi o curvi.
• Le caratteristiche sono state scalate in modo che una variabile non domini le altre.

Se queste condizioni non valgono, il risultato può comunque sembrare ordinato pur non cogliendo la vera struttura dei dati.

Errori comuni con k-means

Trattare k-means come un metodo di clustering universale

K-means funziona meglio quando i cluster sono ragionevolmente compatti e la media è un riassunto sensato. Non è una buona scelta predefinita per ogni dataset.

Ignorare la scalatura delle caratteristiche

Se una caratteristica è misurata su una scala molto più grande di un’altra, può dominare il calcolo della distanza. Standardizzare o normalizzare le caratteristiche è spesso importante prima di eseguire k-means.

Supporre che la risposta sia unica

K-means può convergere a minimi locali diversi a partire da punti iniziali diversi. Per questo si usano comunemente esecuzioni ripetute o metodi come l’inizializzazione k-means++.

Usare caratteristiche non numeriche o codificate male

Poiché i centroidi sono medie, il k-means standard è pensato per variabili numeriche. Se una caratteristica è categorica, calcolare una media aritmetica potrebbe non avere senso.

Usarlo su cluster fortemente non sferici

Se i gruppi reali sono lunghi, curvi o molto disomogenei in densità, k-means può dividere un gruppo naturale o unirne due diversi. Il metodo preferisce cluster compatti basati sui centroidi.

Dimenticare che gli outlier possono spostare i centroidi

Poiché i centroidi sono medie, i valori estremi possono spostarli in modo evidente. Se gli outlier sono importanti nei tuoi dati, controlla questo aspetto prima di fidarti del risultato.

Dove si usa il clustering k-means

K-means si usa spesso per raggruppamenti esplorativi, segmentazione di clienti o comportamenti, quantizzazione dei colori nelle immagini e come baseline rapida nell’apprendimento non supervisionato.

È più utile quando hai caratteristiche numeriche, vuoi un modello semplice e veloce e ti aspetti cluster approssimativamente compatti nello spazio euclideo.

Un semplice modello mentale

Immagina di posizionare $k$ puntine mobili su un grafico a dispersione. Ogni punto si collega alla puntina più vicina. Poi ogni puntina scivola verso la posizione media dei punti collegati a essa. Ripeti finché le puntine smettono di muoversi in modo significativo.

Questa immagine non è solo intuizione. È quasi l’intero algoritmo.

Prova un problema di clustering simile

Prendi un piccolo insieme di punti su una retta, scegli $k = 2$ ed esegui a mano un ciclo completo di assegnazione-aggiornamento. Poi cambia i centroidi iniziali oppure aggiungi un outlier e osserva come cambia il risultato. Se vuoi fare un passo in più, prova una tua versione su un piccolo dataset e confronta cosa succede prima e dopo la scalatura delle caratteristiche.