k-Means Vor- und Nachteile

Vorteile von k-Means

Einfach zu implementieren

Skalierbar auf große Datensätze.

Konvergenz wird garantiert.

Kann die Position von Schwerpunkten wärmen.

Passt sich einfach an neue Beispiele an.

verallgemeinert Cluster mit unterschiedlichen Formen und Größen, z. B. elliptische Cluster.

k-Means-Generalisierung

Was passiert, wenn Cluster unterschiedliche Dichten und Größen haben? Sehen Sie sich Abbildung 1 an. Vergleichen Sie die intuitiven Cluster auf der linken Seite mit den Clustern, die tatsächlich von k-means auf der rechten Seite gefunden werden. Der Vergleich zeigt, wie k-Means auf bestimmte Datasets stoßen können.

Zwei Diagramme nebeneinander. Zuerst wird ein Dataset mit einigen offensichtlichen Clustern angezeigt. Die zweite zeigt eine seltsame Zusammenstellung von Beispielen nach der Ausführung von k-means.
Abbildung 1: Nicht allgemeines k-Means-Beispiel

Für Cluster mit natürlicher Unausgeglichenheit wie in Abbildung 1 können Sie die k-Means anpassen (allgemeinisieren). In Abbildung 2 zeigen die Linien die Clustergrenzen nach der Generalisierung von k-Means:

  • Linkes Diagramm: Keine Generalisierung, was zu einer nicht intuitiven Clustergrenze führt.
  • Zentrumsdiagramm: Verschiedene Clusterbreiten zulassen, um Cluster mit unterschiedlicher Größe zu ermöglichen.
  • Rechtes Diagramm: Neben unterschiedlichen Clusterbreiten lassen Sie unterschiedliche Breiten pro Dimension zu, was zu Auslassungswerten anstelle von sphärischen Clustern führt. Dies verbessert das Ergebnis.
Zwei Diagramme nebeneinander. Das erste Beispiel für sphärische Cluster und das zweite Beispiel für nicht sphärische Cluster.
Abbildung 2: Ein sphärisches Clusterbeispiel und ein nicht sphärisches Clusterbeispiel.

In diesem Kurs wird zwar nicht erklärt, wie man k-Means verallgemeinert, aber die einfache Möglichkeit, k-Means zu ändern, ist ein weiterer Grund, warum es effektiv ist. Informationen zum Generalisieren von k-Means finden Sie unter Clustering – K-means Gaussian Mixed Models von Carlos Guestrin von der Carnegie Mellon University.

Nachteile von k-Means

Manuell \(k\) auswählen.

Verwenden Sie das Diagramm „Verlust im Vergleich zu Clustern“, um das optimale (k) zu finden, wie unter Ergebnisse interpretieren erläutert.

Sie sind von den Ausgangswerten abhängig.

Bei einer niedrigen \(k\)können Sie diese Abhängigkeit abmildern, indem Sie k-means mehrmals mit unterschiedlichen Anfangswerten ausführen und das beste Ergebnis auswählen. Mit \(k\)zunehmendem Wert benötigen Sie erweiterte Versionen von k-Means, um bessere Werte der anfänglichen Schwerpunkte (als k-Means-Seeding bezeichnet) auszuwählen. Eine vollständige Erörterung der k-Means-Seeding-Funktion finden Sie unter A Comparative Study of Effiziente Initialization Methods for the K-Means Clustering Algorithm von M. Emre Celebi, Hassan A. Kingravi, Patricio A. Vela.

Clustering-Daten unterschiedlicher Größe und Dichte

k-means hat Probleme beim Clustering von Daten, deren Cluster unterschiedliche Größen und Dichten haben. Zum Clusterieren dieser Daten müssen Sie k-Means verallgemeinern, wie im Abschnitt Vorteile beschrieben.

Clusterausreißer.

Centroids kann von Ausreißern gezogen werden oder Ausreißer ihren eigenen Cluster erhalten, anstatt ignoriert zu werden. Entfernen oder beseitigen Sie Ausreißer vor dem Clustering.

Anhand von Dimensionen skalieren

Wenn die Anzahl der Dimensionen zunimmt, nähert sich ein Entfernungsbasiertes Ähnlichkeitsmesswert einem der angegebenen Beispiele auf einen konstanten Wert an. Verringern Sie die Dimensionalität entweder mit PCA für die Merkmalsdaten oder mit „Spectral Clustering“ zum Ändern des Clustering-Algorithmus, wie unten erläutert.

Fluch der Dimensionalität und Spektralcluster

Diese Diagramme zeigen, wie das Verhältnis der Standardabweichung zum Mittelwert der Entfernung zwischen den Beispielen mit zunehmender Anzahl der Dimensionen abnimmt. Diese Konvergenz bedeutet, dass k-Means weniger effektiv bei der Unterscheidung zwischen Beispielen wird. Diese negative Konsequenz hochdimensionaler Daten wird als Fluch der Dimensionalität bezeichnet.

Drei Diagramme, die zeigen, wie sich die Standardabweichung der Entfernungen zwischen Beispielen mit zunehmender Anzahl von Dimensionen verringert
Abbildung 3: Eine Demonstration des Fluches der Dimensionalität. Jedes Diagramm zeigt die paarweise Entfernung zwischen 200 zufälligen Punkten an.

Spektral-Clustering vermeidet Fluch der Dimensionalität durch Hinzufügen eines Pre-Clustering-Schritts zu Ihrem Algorithmus:

  1. Verringern Sie die Dimensionalität der Merkmalsdaten mithilfe von PCA.
  2. Projizieren Sie alle Datenpunkte in den untergeordneten Bereich.
  3. Clusterieren Sie die Daten in diesem Teilbereich mit dem von Ihnen ausgewählten Algorithmus.

Daher ist das spektrale Clustering kein separater Clustering-Algorithmus, sondern ein Pre-Clustering-Schritt, den Sie mit einem beliebigen Clustering-Algorithmus nutzen können. Die Details des spektralen Clusters sind kompliziert. A Tutorial on Spectral Clustering von Ulrike von Luxburg ansehen

Zurück
Ergebnisse interpretieren
Weiter
k-Means implementieren