Zum Inhalt springen
Zurück zu den Suchergebnissen

K-means Clustering

Eingeführt von
MacQueen, J. B.; Lloyd, S. P.
Jahr
1967 (formalized 1982)
Typ
Partitional clustering
Familie
Machine learning

Dieser Text ist eine maschinelle Übersetzung und wurde noch nicht geprüft. Original auf Englisch lesen

Schriftgröße

Was leistet sie?

K-means ist ein klassischer unüberwachter partitiver Clustering-Algorithmus, der einen Datensatz iterativ in K nicht überlappende Gruppen unterteilt, indem jede Beobachtung ihrem nächstgelegenen Zentroiden zugeordnet und die Zentroiden als Mittelwert ihrer zugeordneten Punkte aktualisiert werden.

Es ist eines der am weitesten verbreiteten explorativen Werkzeuge im maschinellen Lernen und in der Datenanalyse.

Die Intuition hinter der Methode

Stellen Sie sich vor, Sie lassen K Magnete auf einer Landkarte von Datenpunkten fallen. Jeder Punkt wird von seinem nächstgelegenen Magneten angezogen, und dann bewegt sich jeder Magnet zum Schwerpunkt der von ihm angezogenen Punkte. Wiederholen Sie diesen Zieh-und-Bewegungs-Zyklus, bis sich nichts mehr bewegt: Die Magnete haben K natürliche Gruppierungen gefunden. K-means formalisiert genau diese Idee und minimiert die gesamte quadrierte Distanz jedes Punktes zu seinem Clusterzentrum, der sogenannten Within-Cluster Sum of Squares (WCSS oder Trägheit).

Geschichte

Die K-means-Idee wurde unabhängig von MacQueen 1967 eingeführt, der den Begriff prägte, und von Stuart Lloyd bei Bell Labs in den 1950er Jahren als effizienter iterativer Algorithmus formalisiert (veröffentlicht 1982). Die k-means++-Initialisierungsverbesserung von Arthur und Vassilvitskii im Jahr 2007 adressierte das Problem der Empfindlichkeit gegenüber lokalen Minima. Heute bleibt K-means eine Eckpfeiler-Methode des unüberwachten Lernens, die in praktisch jedem Lehrplan für Data Science gelehrt wird.

Wann wird sie eingesetzt?

K-means eignet sich für exploratives Clustering großer, rein numerischer Datensätze, wenn Sie eine schnelle, skalierbare Partitionierung benötigen und bereit sind, K im Voraus festzulegen oder es mit der Elbow- oder Silhouette-Methode zu suchen. Es funktioniert gut für Kundensegmentierung, Bildkompression, Gruppierung von Dokumententhemen und Vorverarbeitung vor überwachtem Lernen. Vermeiden Sie es, wenn Cluster nicht-sphärisch sind, stark variierende Größen oder Dichten aufweisen, wenn Merkmale kategorisch oder ordinal sind (verwenden Sie stattdessen k-modes oder k-prototypes), wenn die Anzahl der Cluster völlig unbekannt ist und Experimente mit variierendem K nicht durchführbar sind oder wenn die Daten viele Ausreißer enthalten (verwenden Sie stattdessen DBSCAN oder robuste Varianten).

Grenzen und Hinweise

  • Erfordert, dass K im Voraus spezifiziert wird; eine schlechte Wahl von K führt zu bedeutungslosen Clustern.
  • Geht von sphärischen, ähnlich großen Clustern aus; längliche, unregelmäßige oder unterschiedlich skalierte Cluster werden falsch aufgeteilt oder zusammengeführt.
  • Empfindlich gegenüber Ausreißern: Ein einzelner extremer Punkt kann einen Zentroiden weit vom Kern des Clusters wegziehen.
  • Funktioniert nur mit numerischen kontinuierlichen Merkmalen; kategorische Daten erfordern einen anderen Algorithmus (k-modes).
  • Konvergiert zu einem lokalen Minimum; Ergebnisse können bei verschiedenen Läufen mit unterschiedlichen Zufallssamen variieren, es sei denn, k-means++ oder mehrere Neustarts werden verwendet.

Die Bedingungen der Quelle ersetzen weder eine unabhängige wissenschaftliche Prüfung noch die Validierung durch eine Analyse-Engine.

Stärken

  • Schnell und skalierbar: O(nKdi) pro Iteration, praktisch auf Millionen von Beobachtungen mit moderatem K und Dimensionen.
  • Einfach zu implementieren, in jedem wichtigen ML-Framework weit verbreitet und leicht verständlich für nicht-technische Zielgruppen.
  • Funktioniert gut bei großen, gut getrennten, annähernd sphärischen Clustern ähnlicher Größe.
  • Die k-means++-Initialisierung reduziert die Empfindlichkeit gegenüber Startbedingungen im Vergleich zur zufälligen Initialisierung erheblich.
  • Deterministisch innerhalb eines festen Zufallssamens, wodurch Ergebnisse reproduzierbar sind.

Anwendungen

  • Kundensegmentierung für Marketing und Personalisierung basierend auf Verhaltens- oder demografischen Merkmalen.
  • Bildkompression durch Quantisierung von Pixelfarben auf K repräsentative Werte (Farbquantisierung).
  • Dokumenten- und Textclustering als Schritt in Topic-Modeling-Pipelines nach der Vektorisierung.
  • Vorverarbeitung für Anomalieerkennung: Punkte, die weit von jedem Zentroiden entfernt sind, sind potenzielle Ausreißer.
  • Initialisierungsschritt für komplexere Algorithmen wie Gaußsche Mischmodelle oder hierarchisches Clustering.
  • Genexpressionsanalyse zur Gruppierung von Genen oder Proben mit ähnlichen Expressionsprofilen.

So funktioniert es

So funktioniert es

1

K Cluster-Zentroiden werden im Merkmalsraum platziert, entweder durch zufällige Auswahl von K Datenpunkten (Forgy) oder durch die intelligentere k-means++-Strategie, die initiale Zentroiden verteilt, um die Wahrscheinlichkeit schlechter lokaler Minima zu reduzieren. Die Wahl der Initialisierung ist wichtig: k-means++ liefert typischerweise eine schnellere Konvergenz und bessere Endergebnisse.

2

Jede Beobachtung wird dem Cluster zugeordnet, dessen Zentroid am nächsten liegt, gemessen an der Euklidischen Distanz. Diese harte Zuordnung erzeugt K nicht überlappende Partitionen der Daten. Formal wird jeder Punkt x_i dem Cluster c_i = argmin_k ||x_i - mu_k||^2 zugeordnet.

Formel
c_i = \arg\min_k \|x_i - \mu_k\|^2
3

Jeder Zentroid wird als arithmetisches Mittel aller Punkte neu berechnet, die derzeit diesem Cluster zugeordnet sind: mu_k = (1/|C_k|) mal die Summe aller x_i in C_k. Dieser Schritt garantiert, dass der neue Zentroid die WCSS innerhalb jedes Clusters bei gegebener aktueller Zuordnung minimiert.

Formel
\mu_k = \frac{1}{|C_k|} \sum_{x_i \in C_k} x_i
4

Die Schritte der Zuordnung und Aktualisierung wechseln sich ab, bis sich die Positionen der Zentroiden nicht mehr ändern (oder sich um weniger als einen Toleranzschwellenwert ändern) oder eine maximale Anzahl von Iterationen erreicht ist. Der Algorithmus konvergiert garantiert zu einem lokalen Minimum der WCSS, aber nicht notwendigerweise zum globalen Minimum.

5

Die Qualität der Lösung wird anhand der gesamten WCSS (Trägheit) J = Summe über die Cluster von Summe über die zugeordneten Punkte von ||x_i - mu_k||^2 bewertet. Die Wahl von K ist ein separates Problem, das durch die Elbow-Methode, Silhouette-Scores oder Gap-Statistiken behandelt wird, da der Algorithmus selbst K im Voraus spezifiziert haben muss.

Formel
J = \sum_{k=1}^{K} \sum_{x_i \in C_k} \|x_i - \mu_k\|^2

Häufige Fallstricke

  • Vergessen, Merkmale vor dem Clustering zu standardisieren – Variablen mit großen Skalen dominieren die Distanzberechnungen.
  • Auswahl von K durch alleinige Inspektion der In-Sample WCSS ohne Elbow-Plot oder Silhouette-Validierung, was zu trivial kleinen oder großen K führt.
  • Ausführen nur einer Initialisierung und Akzeptieren des ersten Ergebnisses ohne mehrere Neustarts, um sich vor schlechten lokalen Minima zu schützen.
  • Einbeziehung von kategorischen oder ordinalen Variablen in die Merkmalsmatrix ohne entsprechende Kodierung oder Wechsel zu k-modes.
  • Behandlung von Cluster-Labels als bedeutungsvolle Gruppenidentitäten ohne externe Validierung, insbesondere wenn Cluster nicht gut getrennt sind.

Häufig gestellte Fragen

Wie wähle ich die richtige Anzahl von Clustern K?

Führen Sie k-means für eine Reihe von K-Werten aus, zeichnen Sie die Within-Cluster Sum of Squares gegen K auf und suchen Sie nach einem 'Ellenbogen', an dem die Abnahmerate stark abflacht. Ergänzen Sie dies mit Silhouette-Scores, die messen, wie ähnlich jeder Punkt seinem eigenen Cluster im Vergleich zu benachbarten Clustern ist; ein höherer durchschnittlicher Silhouette-Score deutet auf besser definierte Cluster hin.

Warum erhalte ich bei jedem Durchlauf unterschiedliche Ergebnisse?

K-means ist empfindlich gegenüber der Initialisierung und konvergiert zu einem lokalen statt einem globalen Minimum der WCSS. Verwenden Sie die k-means++-Initialisierung und setzen Sie einen festen Zufallssamen für die Reproduzierbarkeit. Das mehrmalige Ausführen des Algorithmus mit unterschiedlichen Samen und Beibehalten der Lösung mit der niedrigsten Trägheit ist eine gute Praxis.

Funktioniert k-means mit kategorischen Daten?

Nein. K-means basiert auf der Euklidischen Distanz und Zentroidenmitteln, die für kategoriale Variablen nicht definiert sind. Für rein kategoriale Daten verwenden Sie k-modes; für gemischte numerische und kategoriale Daten verwenden Sie k-prototypes.

Wann sollte ich DBSCAN oder GMM gegenüber k-means bevorzugen?

Verwenden Sie DBSCAN, wenn Cluster unregelmäßige Formen haben oder Sie automatische Ausreißererkennung benötigen, ohne K anzugeben. Verwenden Sie Gaußsche Mischmodelle (GMM), wenn Sie weiche (probabilistische) Cluster-Zuordnungen oder Cluster unterschiedlicher Größe und Ausrichtung wünschen, allerdings auf Kosten höherer Rechenkomplexität.

Muss ich meine Merkmale skalieren?

Ja, fast immer. K-means verwendet die Euklidische Distanz, daher dominieren Merkmale mit großen numerischen Bereichen das Clustering. Wenden Sie Z-Score-Standardisierung oder Min-Max-Skalierung vor dem Anpassen von k-means an, es sei denn, alle Merkmale sind bereits auf derselben Skala.

Verwandte Methoden

Quellen

  1. Lloyd, S. P. (1982). Least squares quantization in PCM. IEEE Transactions on Information Theory, 28(2), 129–137.

    DOI-Referenz öffnen
    Kopiert.
  2. MacQueen, J. B. (1967). Some methods for classification and analysis of multivariate observations. Proceedings of the 5th Berkeley Symposium on Mathematical Statistics and Probability, 1, 281–297.

    Publikationsreferenz öffnen
    Kopiert.