Clustering K-means
- Introdotto da
- MacQueen, J. B.; Lloyd, S. P.
- Anno
- 1967 (formalized 1982)
- Tipo
- Partitional clustering
- Famiglia
- Machine learning
Questo testo è una traduzione automatica e non è ancora stato revisionato. Leggi l’originale in inglese
A cosa serve?
K-means è un classico algoritmo di clustering partizionale non supervisionato che divide un dataset in K gruppi non sovrapposti, assegnando iterativamente ogni osservazione al suo centroide più vicino e aggiornando i centroidi come la media dei punti ad essi assegnati.
È uno degli strumenti esplorativi più utilizzati nell'apprendimento automatico e nell'analisi dei dati.
L’intuizione alla base del metodo
Immaginate di far cadere K magneti su una mappa di punti dati. Ogni punto è attratto dal magnete più vicino, e poi ogni magnete si sposta nel baricentro dei punti che ha attratto. Ripetete questo ciclo di attrazione e spostamento finché nulla si muove: i magneti hanno trovato K raggruppamenti naturali. K-means formalizza esattamente questa idea, minimizzando la somma totale dei quadrati delle distanze da ogni punto al centro del suo cluster, chiamata somma dei quadrati intra-cluster (WCSS o inerzia).
Storia
L'idea del k-means fu introdotta indipendentemente da MacQueen nel 1967, che coniò il termine, e formalizzata come un efficiente algoritmo iterativo da Stuart Lloyd ai Bell Labs negli anni '50 (pubblicato nel 1982). Il miglioramento dell'inizializzazione k-means++ di Arthur e Vassilvitskii nel 2007 ha affrontato il problema della sensibilità al minimo locale. Oggi k-means rimane un metodo di apprendimento non supervisionato fondamentale insegnato in praticamente ogni curriculum di data science.
Quando usarlo
K-means è adatto per il clustering esplorativo di grandi dataset puramente numerici quando è necessaria una partizione veloce e scalabile e si è a proprio agio nello specificare K in anticipo o nel cercarlo con il metodo del gomito o silhouette. Funziona bene per la segmentazione dei clienti, la compressione delle immagini, il raggruppamento di argomenti di documenti e il pre-processing prima dell'apprendimento supervisionato. Evitarlo quando i cluster non sono sferici, hanno dimensioni o densità molto variabili, quando le caratteristiche sono categoriche o ordinali (usare k-modes o k-prototypes invece), quando il numero di cluster è completamente sconosciuto e gli esperimenti con K variabile non sono fattibili, o quando i dati contengono molti outlier (usare DBSCAN o varianti robuste invece).
Limiti e considerazioni
- Richiede che K sia specificato in anticipo; una scelta errata di K produce cluster privi di significato.
- Presuppone cluster sferici e di dimensioni simili; cluster allungati, irregolari o con scale diverse vengono divisi o uniti in modo errato.
- Sensibile agli outlier: un singolo punto estremo può allontanare un centroide dalla maggior parte del cluster.
- Funziona solo con caratteristiche numeriche continue; i dati categorici richiedono un algoritmo diverso (k-modes).
- Converge a un minimo locale; i risultati possono variare tra diverse esecuzioni con seed casuali diversi, a meno che non si utilizzi k-means++ o più riavvii.
Le condizioni della fonte non sostituiscono una revisione scientifica indipendente né la validazione da parte di un motore di analisi.
Punti di forza
- Veloce e scalabile: O(nKdi) per iterazione, pratico su milioni di osservazioni con K e dimensioni moderate.
- Semplice da implementare, ampiamente disponibile in ogni framework di ML principale e facile da spiegare a un pubblico non tecnico.
- Funziona bene su cluster grandi, ben separati e approssimativamente sferici di dimensioni simili.
- L'inizializzazione k-means++ riduce sostanzialmente la sensibilità alle condizioni di partenza rispetto all'inizializzazione casuale.
- Deterministico all'interno di un seed casuale fisso, rendendo i risultati riproducibili.
Applicazioni
- Segmentazione dei clienti per marketing e personalizzazione basata su feature comportamentali o demografiche.
- Compressione delle immagini quantizzando i colori dei pixel a K valori rappresentativi (quantizzazione del colore).
- Clustering di documenti e testi come passaggio nelle pipeline di modellazione di argomenti dopo la vettorizzazione.
- Pre-processing per il rilevamento delle anomalie: i punti lontani da qualsiasi centroide sono candidati outlier.
- Passaggio di inizializzazione per algoritmi più complessi come i modelli di miscela gaussiana o il clustering gerarchico.
- Analisi dell'espressione genica per raggruppare geni o campioni con profili di espressione simili.
Come funziona
Come funziona
K centroidi di cluster vengono posizionati nello spazio delle caratteristiche, sia selezionando casualmente K punti dati (Forgy) sia tramite la strategia più intelligente k-means++ che distribuisce i centroidi iniziali per ridurre la probabilità di minimi locali scadenti. La scelta dell'inizializzazione è importante: k-means++ tipicamente porta a una convergenza più rapida e a soluzioni finali migliori.
Ogni osservazione viene assegnata al cluster il cui centroide è più vicino secondo la distanza euclidea. Questa assegnazione "hard" crea K partizioni non sovrapposte dei dati. Formalmente, ogni punto x_i è assegnato al cluster c_i = argmin_k ||x_i - mu_k||^2.
Formula
c_i = \arg\min_k \|x_i - \mu_k\|^2
Ogni centroide viene ricalcolato come la media aritmetica di tutti i punti attualmente assegnati a quel cluster: mu_k = (1/|C_k|) moltiplicato per la somma di tutti gli x_i in C_k. Questo passaggio garantisce che il nuovo centroide minimizzi il WCSS all'interno di ciascun cluster data l'assegnazione corrente.
Formula
\mu_k = \frac{1}{|C_k|} \sum_{x_i \in C_k} x_iI passaggi di assegnazione e aggiornamento si alternano finché le posizioni dei centroidi non cambiano più (o cambiano di meno di una soglia di tolleranza) o viene raggiunto un numero massimo di iterazioni. L'algoritmo è garantito convergere a un minimo locale del WCSS, anche se non necessariamente al minimo globale.
La qualità della soluzione è valutata con il WCSS totale (inerzia) J = somma sui cluster della somma sui punti assegnati di ||x_i - mu_k||^2. La scelta di K è una questione separata affrontata dal metodo del gomito (elbow method), dai punteggi silhouette o dalle statistiche del gap, poiché l'algoritmo stesso richiede che K sia specificato in anticipo.
Formula
J = \sum_{k=1}^{K} \sum_{x_i \in C_k} \|x_i - \mu_k\|^2Errori comuni
- Dimenticare di standardizzare le feature prima del clustering — le variabili su scale grandi domineranno i calcoli di distanza.
- Selezionare K ispezionando solo il WCSS in-sample senza il grafico del gomito o la validazione silhouette, portando a K trivialmente piccoli o grandi.
- Eseguire una sola inizializzazione e accettare il primo risultato senza più riavvii per proteggersi da minimi locali scadenti.
- Includere variabili categoriche o ordinali nella matrice delle feature senza un'appropriata codifica o passare a k-modes.
- Trattare le etichette dei cluster come identità di gruppo significative senza convalida esterna, specialmente quando i cluster non sono ben separati.
Domande frequenti
Come scelgo il numero giusto di cluster K?
Eseguire k-means per un intervallo di valori K, tracciare la somma dei quadrati intra-cluster rispetto a K e cercare un "gomito" dove il tasso di diminuzione rallenta bruscamente. Integrare questo con i punteggi silhouette, che misurano quanto ogni punto è simile al proprio cluster rispetto ai cluster vicini; una silhouette media più alta indica cluster meglio definiti.
Perché ottengo risultati diversi ad ogni esecuzione?
K-means è sensibile all'inizializzazione e converge a un minimo locale piuttosto che globale del WCSS. Utilizzare l'inizializzazione k-means++ e impostare un seed casuale fisso per la riproducibilità. Eseguire l'algoritmo più volte con seed diversi e mantenere la soluzione con l'inerzia più bassa è una buona pratica.
K-means funziona con dati categorici?
No. K-means si basa sulla distanza euclidea e sulle medie dei centroidi, che non sono definite per le variabili categoriche. Per dati puramente categorici utilizzare k-modes; per dati misti numerici e categorici utilizzare k-prototypes.
Quando dovrei preferire DBSCAN o GMM rispetto a k-means?
Utilizzare DBSCAN quando i cluster hanno forme irregolari o è necessaria la rilevazione automatica degli outlier senza specificare K. Utilizzare i Modelli di Miscela Gaussiana (GMM) quando si desiderano assegnazioni di cluster "soft" (probabilistiche) o cluster di diverse dimensioni e orientamenti, a costo di una maggiore complessità computazionale.
Devo scalare le mie feature?
Sì, quasi sempre. K-means utilizza la distanza euclidea, quindi le feature con grandi intervalli numerici domineranno il clustering. Applicare la standardizzazione z-score o la scalatura min-max prima di adattare k-means, a meno che tutte le feature non siano già sulla stessa scala.
Metodi correlati
Fonti
Lloyd, S. P. (1982). Least squares quantization in PCM. IEEE Transactions on Information Theory, 28(2), 129–137.
Apri il riferimento DOICopiato.MacQueen, J. B. (1967). Some methods for classification and analysis of multivariate observations. Proceedings of the 5th Berkeley Symposium on Mathematical Statistics and Probability, 1, 281–297.
Apri il riferimento della pubblicazioneCopiato.