Vor- und Nachteile von k-Means

K-Means ist in vielen Kontexten des maschinellen Lernens nützlich und effizient, Schwächen aufweisen.

Vorteile von k-Means

Relativ einfache Implementierung.

Skaliert auf große Datasets.

Konvergiert immer.

Ermöglicht einen Warmstart für die Schwerpunkte.

Flüssige Anpassung an neue Beispiele

Sie können auf Cluster mit unterschiedlichen z. B. elliptische Gruppen.

k-Means generalisieren

Eine einfache Implementierung von k-Means kann bei Clustern mit unterschiedlichen Dichten und Größen. Auf der linken Seite in Abbildung 1 sind die Cluster zu erwarten sind, während rechts die von k-Means vorgeschlagenen Cluster angezeigt werden.

<ph type="x-smartling-placeholder">

</ph>

Abbildung 1: Ungeneralisiertes k-Means-Beispiel

Um eine bessere Leistung bei unausgeglichenen Clustern wie in Abbildung 1 zu erzielen, verallgemeinern, also anpassen, k-Means. Abbildung 2 zeigt drei verschiedene Datasets mit zwei verschiedenen Generalisierungen geclustert. Das erste Dataset zeigt k-Means ohne Generalisierung. Mit dem zweiten und dritten können Cluster in der Breite variieren.

<ph type="x-smartling-placeholder">

</ph>

Abbildung 2: k-Means-Clustering mit und ohne Generalisierung

In diesem Kurs geht es nicht um die Verallgemeinerung von k-Means. siehe Clustering – k-means Gauß'sche Mischung Modelle von Carlos Guestrin von der Carnegie Mellon University.

Nachteile von k-Means

\(k\) muss manuell ausgewählt werden.

Ergebnisse hängen von Anfangswerten ab.

Bei niedrigem \(k\)können Sie diese Abhängigkeit abschwächen, indem Sie mehrere k-means-Anweisungen ausführen mit unterschiedlichen Anfangswerten und wählen das beste Ergebnis aus. Wie \(k\) steigt, benötigen Sie k-Means-Aussaat, um eine bessere Anfangswahrscheinlichkeit Schwerpunkte Eine umfassende Beschreibung der k-Means-Seeding finden Sie unter „Ein vergleichender Untersuchung effizienter Initialisierungsmethoden für das K-Means-Clustering Algorithm“ von M. Emre Celebi, Hassan A. Kingravi und Patricio A. Vela.

Schwierigkeiten beim Clustering von Daten unterschiedlicher Größe und ohne Verallgemeinerung.

Schwierigkeiten beim Clustering von Ausreißern.

Zentren können von Ausreißern gezogen werden oder Ausreißer erhalten möglicherweise ihren eigenen Cluster anstatt ignoriert zu werden. Entfernen oder beschneiden Sie Ausreißer, bevor Clustering.

Schwierigkeiten beim Skalieren mit der Anzahl der Dimensionen.

Mit zunehmender Anzahl von Dimensionen in den Daten ist eine entfernungsbasierte Ähnlichkeit zwischen gegebenen Beispielen zu einem konstanten Wert konvergiert. Reduzieren Dimensionalität entweder durch PCA für die Featuredaten oder mithilfe von Spektralclustering zur Änderung des Clusterings Algorithmus.

Fluch der Dimensionalität und Spektral-Clustering

Beachten Sie in diesen drei Diagrammen, wie die Standardabweichung Abstand zwischen Beispielen kleiner im Verhältnis zur mittleren Entfernung zwischen Beispiele. Dieses Konvergenz bedeutet, dass k-Means bei der Unterscheidung zwischen wenn die Dimensionalität der Daten zunimmt. Dies wird als den Fluch der Dimensionalität.

<ph type="x-smartling-placeholder">

</ph>

Abbildung 3: Ein Beispiel für den Fluch der Dimensionalität. Jedes Diagramm zeigt die paarweisen Abstände zwischen 200 zufälligen Punkten.

Sie können diesen Leistungseinbruch durch Spektralclustering, Dadurch werden dem Algorithmus Vor-Clustering-Schritte hinzugefügt. Um spektrale Daten durchzuführen Clustering:

1. Reduzieren Sie die Dimensionalität von Featuredaten mithilfe von PCA.
2. Projizieren Sie alle Datenpunkte in den untergeordneten Raum.
3. Gruppieren Sie die Daten in diesem untergeordneten Raum mithilfe des von Ihnen gewählten Algorithmus.

Anleitung zu Spektralanalyse Clustering von Ulrike von Luxburg für weitere Informationen Clustering.

Wichtige Begriffe:

• Spektral-Clustering