Vor- und Nachteile von k-Means

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

Vorteile von K-Means

Relativ einfach zu implementieren.

Kann auf große Datenmengen skaliert werden.

Immer konvergiert.

Ermöglicht das Warm-Starten der Positionen der Centroide.

Sie passen sich reibungslos an neue Beispiele an.

Kann auf Cluster verschiedener Formen und Größen generalisiert werden, z. B. elliptische Cluster.

K-Means generalisieren

Bei einer einfachen Implementierung von k-Means kann es bei Clustern mit unterschiedlichen Dichten und Größen zu Problemen kommen. Auf der linken Seite von Abbildung 1 sind die zu erwartenden Cluster zu sehen, auf der rechten Seite die von K-Means vorgeschlagenen Cluster.

Zwei Diagramme nebeneinander. Die erste zeigt einen Datensatz mit relativ offensichtlichen Clustern. Das zweite Bild zeigt eine merkwürdige Gruppierung von Beispielen nach dem Ausführen von k-Means.
Abbildung 1: Nicht generalisiertes K-Means-Beispiel

Für eine bessere Leistung bei ungleichgewichtigen Clustern wie denen in Abbildung 1 können Sie K-Means generalisieren, d. h. anpassen. Abbildung 2 zeigt drei verschiedene Datensätze, die mit zwei verschiedenen Generalisierungen gruppiert sind. Der erste Datensatz zeigt K-Means ohne Generalisierung, während der zweite und dritte Datensatz es zulassen, dass Cluster unterschiedlich breit sind.

Drei Grafiken, die K-Means ohne Generalisierung, dann K-Means mit unterschiedlichen Breiten und dann K-Means mit unterschiedlichen Breiten in verschiedenen Dimensionen zeigen
Abbildung 2: K-Means-Clustering mit und ohne Generalisierung

In diesem Kurs wird nicht erläutert, wie K-Means generalisiert wird. Interessierte sollten sich das Clustering – K-Means-Gauß-Mischmodelle von Carlos Guestrin von der Carnegie Mellon University ansehen.

Nachteile von K-Means

k muss manuell ausgewählt werden.

Die Ergebnisse hängen von den Anfangswerten ab.

Bei niedrigen k-Werten können Sie diese Abhängigkeit verringern, indem Sie K-Means mehrmals mit unterschiedlichen Anfangswerten ausführen und das beste Ergebnis auswählen. Wenn ksteigt, benötigen Sie K-Means-Zufallsstichproben, um bessere Anfangscentroide auszuwählen. Eine ausführliche Beschreibung der K-Means-Zufallsstichproben finden Sie im Artikel „A Comparative Study of Efficient Initialization Methods for the K-means Clustering Algorithm“ von M. Emre Celebi, Hassan A. Kingravi und Patricio A. Vela.

Es ist schwierig, Daten unterschiedlicher Größe und Dichte ohne Verallgemeinerung zu clustern.

Schwierigkeiten beim Clustern von Ausreißern

Die Centroide können von Ausreißern verschoben werden oder Ausreißer erhalten einen eigenen Cluster, anstatt ignoriert zu werden. Sie sollten Ausreißer vor dem Clustern entfernen oder zuschneiden.

Schwierigkeiten bei der Skalierung mit der Anzahl der Dimensionen

Mit zunehmender Anzahl von Dimensionen in den Daten konvergiert ein distanzbasiertes Ähnlichkeitsmaß zu einem konstanten Wert zwischen beliebigen Beispielen. Reduzieren Sie die Dimensionen entweder mithilfe der PCA auf die Feature-Daten oder mithilfe des Spektral-Clusterings, um den Clustering-Algorithmus zu ändern.

Dimensionseffekt und spektrales Clustering

In diesen drei Diagrammen sehen Sie, dass sich die Standardabweichung der Entfernung zwischen den Beispielen im Verhältnis zur durchschnittlichen Entfernung zwischen den Beispielen verringert, wenn die Anzahl der Dimensionen zunimmt. Diese Konvergenz bedeutet, dass K-Means bei zunehmender Dimensionalität der Daten weniger effektiv zwischen Beispielen unterscheiden kann. Dies wird als Dimensionalitätsfluch bezeichnet.

Drei Diagramme, die zeigen, wie die Standardabweichung der Entfernung zwischen Beispielen mit zunehmender Anzahl von Dimensionen abnimmt
Abbildung 3: Eine Demonstration des Dimensionsproblems. Jedes Diagramm zeigt die paarweisen Abstände zwischen 200 Zufallspunkten.

Mit der spektralen Clustering-Methode lässt sich diese Leistungsminderung vermeiden, da dem Algorithmus Schritte vor dem Clustern hinzugefügt werden. So führen Sie ein spektrales Clustering durch:

  1. Reduzieren Sie die Dimensionalität von Merkmaldaten mithilfe der PCA.
  2. Alle Datenpunkte in den untergeordneten Unterraum projizieren.
  3. Clustern Sie die Daten in diesem Unterraum mit dem ausgewählten Algorithmus.

Weitere Informationen zum spektralen Clustering finden Sie in der Anleitung zum spektralen Clustering von Ulrike von Luxburg.

Zurück
Ergebnisse auswerten
Weiter
Autoencoder, Prädiktoren und Einbettungen