Vantaggi dei media k
Implementazione relativamente semplice.
Scala a set di dati di grandi dimensioni.
Garanzia di convergenza.
Può riavviare le posizioni dei centroidi.
Si adatta facilmente a nuovi esempi.
Generalizza a cluster di forme e dimensioni diverse, ad esempio cluster ellittici.
Generale k-means
Cosa succede quando i cluster hanno densità e dimensioni diverse? Osserva la Figura 1. Confronta i cluster intuitivi sul lato sinistro con i cluster effettivamente trovati da k-mean sul lato destro. Il confronto mostra in che modo gli elementi k-means possono verificarsi in determinati set di dati.
Per raggruppare cluster in squilibri naturali come quelli mostrati nella Figura 1, puoi adattare (generalizzare) i valori k-mean. Nella Figura 2, le righe mostrano i limiti dei cluster dopo la generalizzazione di k-mean come segue:
- Grafico a sinistra: nessuna generalizzazione, con conseguente limite di cluster non intuitivo.
- Grafico centrale: consenti larghezze del cluster diverse, generando cluster più intuitivi di dimensioni diverse.
- Grafico a destra: oltre a larghezze del cluster diverse, consente larghezze diverse per dimensione, generando ellittici anziché cluster sferici, migliorando il risultato.
Anche se questo corso non spiega come generalizzare i k-mean, ricorda che la modifica dei k-mean è un altro motivo per cui è efficace. Per informazioni sulla generalizzazione dei metodi k-means, consulta la sezione Clustering – Modelli di mix gaussiano K-means di Carlos guestrin della Carnegie Mellon University.
Svantaggi dei metodi k-mean
Scelta manuale \(k\) .
Usa il grafico "Perdita e cluster" per trovare la formula (k) ottimale, come spiegato nella sezione Interpretare i risultati.
Dipendere dai valori iniziali.
Per un \(k\)basso, puoi mitigare questa dipendenza eseguendo k-mean più volte con valori iniziali diversi e scegliendo il risultato migliore. Man mano che \(k\) aumenta, sono necessarie versioni avanzate di k-means per scegliere valori migliori dei centroidi iniziali (chiamati k-means seeding). Per una discussione completa su k- significa seeding, consulta A Comparative Study of Effective Initialization Methods for the K-Means Clustering Algorithm di M. Emre Celebi, Hassan A. Kingravi, Patricio A Vela.
Clustering dei dati con varie dimensioni e densità.
k-means ha difficoltà a eseguire il clustering di dati in cui le dimensioni e la densità dei cluster sono di vario tipo. Per raggruppare tali dati, devi generalizzare k-mean come descritto nella sezione Vantaggi.
Cluster dei valori anomali.
I centroidi possono essere trascinati da valori anomali o i valori anomali potrebbero avere un proprio cluster anziché essere ignorati. Valuta la possibilità di rimuovere o ritagliare i valori anomali prima di eseguire il clustering.
Scalabilità con un numero di dimensioni.
Con l'aumentare del numero di dimensioni, una misura di similitudine basata sulla distanza converge a un valore costante tra qualsiasi esempio. Riduci la dimensionalità utilizzando PCA sui dati delle funzionalità o utilizzando il "clustering spettrale" per modificare l'algoritmo di clustering come spiegato di seguito.
Maledizione della dimensione e del clustering spettrale
Questi grafici mostrano come il rapporto tra la deviazione standard e la media della distanza diminuisce quando il numero di dimensioni aumenta. Questa convergenza significa che k-mean diventa meno efficace nel distinguere gli esempi. Questa conseguenza negativa dei dati di grandi dimensioni viene chiamata la maledizione della dimensionalità.
Il clustering spettrale evita la maledizione della dimensionamento aggiungendo un passaggio di pre-clustering al tuo algoritmo:
- Riduci la dimensione dei dati delle funzionalità utilizzando gli annunci PCA.
- Proietta tutti i punti dati nello spazio secondario di dimensioni inferiori.
- Raggruppa i dati in questo sottospazio utilizzando l'algoritmo che hai scelto.
Pertanto, il clustering spettrale non è un algoritmo di clustering separato, ma un passaggio di pre-clustering che puoi utilizzare con qualsiasi algoritmo di clustering. I dettagli del clustering spettrale sono complicati. Consulta Un tutorial sul clustering spettrale di Ulrike von Luxburg.