Vantaggi e svantaggi di K-means

K-means è utile ed efficiente in molti contesti di machine learning, ma presenta alcuni punti deboli distinti.

Vantaggi del k-means

È relativamente semplice da implementare.

Si adatta a set di dati di grandi dimensioni.

Converge sempre.

Consente di avviare in modo graduale le posizioni dei centroidi.

Si adatta facilmente a nuovi esempi.

Può essere generalizzato a cluster di forme e dimensioni diverse, ad esempio cluster ellittici.

Generalizzazione di K-means

Un'implementazione semplice di k-means può avere difficoltà con cluster di diverse dimensioni e densità. Il lato sinistro della Figura 1 mostra i cluster che ci aspetteremmo di vedere, mentre il lato destro mostra i cluster proposti da k-means.

Figura 1: esempio di K-means non generalizzato.

Per un rendimento migliore in cluster sbilanciati come quelli mostrati nella Figura 1, puoi generalizzare, ovvero adattare, k-means. La Figura 2 mostra tre diversi set di dati raggruppati con due generalizzazioni diverse. Il primo set di dati mostra il metodo k-means senza generalizzazione, mentre il secondo e il terzo consentono ai cluster di variare in larghezza.

Figura 2: clustering K-means con e senza generalizzazione.

Questo corso non spiega come generalizzare k-means, ma chi è interessato dovrebbe consultare Clustering – k-means Gaussian mixture models di Carlos Guestrin della Carnegie Mellon University.

Svantaggi del clustering K-means

\(k\) deve essere scelto manualmente.

I risultati dipendono dai valori iniziali.

Per valori bassi \(k\), puoi attenuare questa dipendenza eseguendo k-means più volte con valori iniziali diversi e scegliendo il risultato migliore. Man mano che \(k\) aumenta, devi utilizzare il seeding k-means per scegliere meglio i centroidi iniziali. Per una discussione completa del seeding k-means, consulta "A Comparative Study of Efficient Initialization Methods for the K-means Clustering Algorithm," di M. Emre Celebi, Hassan A. Kingravi e Patricio A. Vela.

Difficoltà a raggruppare dati di dimensioni e densità diverse senza generalizzazione.

Difficoltà a raggruppare gli outlier.

I centroidi possono essere trascinati dagli outlier o gli outlier potrebbero avere un proprio cluster invece di essere ignorati. Valuta la possibilità di rimuovere o tagliare le anomalie prima del clustering.

Difficoltà di scalabilità in base al numero di dimensioni.

Man mano che il numero di dimensioni nei dati aumenta, una misura della somiglianza basata sulla distanza converrebbe a un valore costante tra qualsiasi esempio dato. Riduci la dimensionalità utilizzando il PCA sui dati delle funzionalità o il clustering spettrale per modificare l'algoritmo di clustering.

Maledizione della dimensionalità e clustering spettrale

In questi tre grafici, nota come, con l'aumentare delle dimensioni, la deviazione standard della distanza tra gli esempi diminuisce rispetto alla distanza media tra gli esempi. Questa convergenza significa che k-means diventa meno efficace nel distinguere tra esempi man mano che la dimensionalità dei dati aumenta. Questo fenomeno è noto come maledizione della dimensionalità.

Figura 3: una dimostrazione della maledizione della dimensionalità. Ogni grafico mostra le distanze tra coppie di 200 punti casuali.

Puoi evitare questo calo del rendimento con il clustering spettrale, che aggiunge all'algoritmo i passaggi di pre-clustering. Per eseguire il clustering spettrale:

1. Riduci la dimensionalità dei dati delle funzionalità utilizzando l'analisi PCA.
2. Proietta tutti i punti dati nello spazio sottospaziale di dimensioni inferiori.
3. Raggruppa i dati in questo sottospazio utilizzando l'algoritmo scelto.

Per ulteriori informazioni sul clustering spettrale, consulta A Tutorial on Spectral Clustering di Ulrike von Luxburg.

Termini chiave:

• clustering spettrale