Il k-means divide i dati in k cluster minimizzando la somma delle distanze quadratiche tra punti e centroidi del cluster assegnato. È uno degli algoritmi più usati nell’analisi dei cluster per la sua semplicità e scalabilità.
L’algoritmo di Lloyd alterna due passi: assegnare ogni punto al centroide più vicino e aggiornare ogni centroide come media dei punti assegnati.
È efficiente e diffuso, ma assume cluster compatti e quasi sferici. È sensibile a scala delle variabili, outlier, scelta di k e inizializzazione. Per questo si usano standardizzazione, k-means++ e più restart.
Funzione obiettivo
Dati punti x_1,\dots,x_n\in\mathbb{R}^p, il k-means cerca una partizione C_1,\dots,C_k e centroidi \mu_1,\dots,\mu_k che minimizzino
La norma euclidea al quadrato fa sì che il centroide ottimo di un cluster sia la media aritmetica dei suoi punti:
L’obiettivo misura compattezza interna, non separazione concettuale. Due cluster possono avere basso errore interno e tuttavia non corrispondere a classi interpretabili nel dominio.
Algoritmo di Lloyd
La procedura standard alterna:
- assegnazione:
- aggiornamento:
Ogni iterazione non aumenta la funzione obiettivo e l’algoritmo converge in un numero finito di passi a un minimo locale. Non c’è però garanzia di trovare il minimo globale.
Inizializzazione e k-means++
L’inizializzazione casuale può portare a soluzioni diverse. Per questo si usano più restart e si conserva la soluzione con minore J. k-means++ sceglie i centroidi iniziali in modo più disperso, assegnando maggiore probabilità ai punti lontani dai centri già scelti.
Questa inizializzazione non elimina i minimi locali, ma riduce la probabilità di partire da configurazioni molto sfavorevoli.
Scelta di k
Il numero k non è stimato automaticamente dalla versione base dell’algoritmo. Si scelgono spesso più valori e si confrontano errore interno, interpretabilità e stabilità. Il metodo del gomito osserva la curva di J al variare di k: quando l’aggiunta di cluster produce benefici marginali ridotti, si individua un possibile compromesso.
In pratica la scelta di k deve tenere conto dello scopo: segmentazione operativa, compressione, esplorazione, preprocessing o individuazione di profili.
Scala delle variabili e outlier
Poiché il k-means usa distanze euclidee, variabili con scala più grande dominano il risultato. Standardizzare le feature è quasi sempre necessario quando le unità di misura sono diverse.
Gli outlier sono problematici perché il centroide è una media. Pochi punti estremi possono spostare molto il centro di un cluster. In questi casi possono essere più adatti metodi basati su medoid, densità o modelli probabilistici.
Quando funziona bene
Il k-means è adatto quando i cluster sono compatti, separati e di forma circa sferica nello spazio delle feature. È meno adatto a cluster allungati, non convessi, annidati o con densità molto diverse. Per forme più complesse può essere preferibile DBSCAN o un modello di mixture.
L’algoritmo è spesso usato anche come compressione vettoriale: i centroidi diventano prototipi rappresentativi dei dati.
Errori comuni
Un errore frequente è interpretare i cluster come gruppi reali senza validazione. k-means produce sempre una partizione anche quando i dati non hanno struttura naturale. Un secondo errore è confrontare risultati ottenuti con variabili non standardizzate, facendo dipendere i cluster dalle unità di misura invece che dal fenomeno.
Per esercizi e applicazioni operative, è utile confrontare k-means con metodi alternativi e visualizzare i cluster con riduzioni dimensionali, come nella PCA, senza dimenticare che la visualizzazione può distorcere distanze e separazioni.