Die K-Means-Clusteranalyse ist eine Methode der Vektorquantisierung, die ursprünglich aus der Signalverarbeitung stammt und n Beobachtungen in k Cluster aufteilt, wobei jede Beobachtung zu dem Cluster mit dem nächsten Mittelwert (dem Clusterzentrum oder Zentroid) gehört. Dies führt zu einer Partitionierung des Datenraums in Voronoi-Zellen. Der Algorithmus wird häufig im maschinellen Lernen für unüberwachte Datenanalysen eingesetzt, wie etwa Kundensegmentierung, Bildkompression und Mustererkennung.
K-Means minimiert die Varianzen innerhalb der Cluster, gemessen an quadrierten euklidischen Distanzen, jedoch nicht an regulären euklidischen Distanzen, was das schwierigere Weber-Problem darstellen würde. Der Mittelwert optimiert quadrierte Fehler, während nur der geometrische Median euklidische Distanzen minimiert. Beispielsweise lassen sich bessere euklidische Lösungen mit K-Medians und K-Medoids finden.
Das Problem ist rechnerisch schwierig (NP-schwer); dennoch konvergieren effiziente heuristische Algorithmen schnell zu einem lokalen Optimum. Diese ähneln üblicherweise dem Erwartungs-Maximierungs-Algorithmus für Mischungen von Gauß-Verteilungen, der einen iterativen Verfeinerungsansatz verwendet, der sowohl von K-Means als auch von Gaußschen Mischmodellen genutzt wird. Beide verwenden Clusterzentren zur Modellierung der Daten; jedoch tendiert die K-Means-Clusteranalyse dazu, Cluster mit vergleichbarer räumlicher Ausdehnung zu finden, während das Gaußsche Mischmodell Clustern unterschiedliche Formen erlaubt.
Der unüberwachte K-Means-Algorithmus hat eine lose Beziehung zum K-Nearest-Neighbor-Klassifikator, einer beliebten überwachten maschinellen Lerntechnik zur Klassifikation, die aufgrund des Namens oft mit K-Means verwechselt wird. Die Anwendung des 1-Nearest-Neighbor-Klassifikators auf die durch K-Means erhaltenen Clusterzentren klassifiziert neue Daten in die bestehenden Cluster, bekannt als Nearest-Centroid-Klassifikator oder Rocchio-Algorithmus.
Formale Definition
Gegeben eine Menge von Beobachtungen (x1, x2, ..., xn), wobei jede Beobachtung ein d-dimensionaler reeller Vektor ist, zielt die K-Means-Clusteranalyse darauf ab, die n Beobachtungen in k (≤ n) Mengen S = {S1, S2, ..., Sk} zu partitionieren, um die Summe der Quadrate innerhalb der Cluster (WCSS), d.h. die Varianz, zu minimieren. Formal besteht das Ziel darin, zu finden:
argmin über S der Summe von i=1 bis k der Summe über x in Si von ||x - μi||^2,
wobei μi der Mittelwert (auch Zentroid genannt) der Punkte in Si ist und ||·|| die übliche L2-Norm darstellt. Dies ist äquivalent zur Minimierung der paarweisen quadrierten Abweichungen der Punkte im selben Cluster, wie durch die Identität gezeigt wird, dass die Summe der quadrierten Distanzen zum Mittelwert gleich der durchschnittlichen paarweisen quadrierten Distanz ist.
Algorithmus
Der gebräuchlichste Algorithmus, oft als Lloyd-Algorithmus bezeichnet, verwendet einen iterativen Verfeinerungsansatz. Er beginnt mit einer anfänglichen Menge von k Zentroiden und wechselt dann zwischen zwei Schritten: Zuordnung und Aktualisierung. Im Zuordnungsschritt wird jede Beobachtung dem Cluster zugeordnet, dessen Zentroid am nächsten liegt, typischerweise unter Verwendung der euklidischen Distanz. Im Aktualisierungsschritt wird der Zentroid jedes Clusters als Mittelwert der zugeordneten Punkte neu berechnet. Diese Schritte wiederholen sich, bis sich die Zuordnungen nicht mehr ändern, was auf eine Konvergenz zu einem lokalen Optimum hinweist.
Die Initialisierung ist entscheidend; die K-Means++-Methode, die anfängliche Zentroide verteilt, ist eine beliebte Heuristik zur Verbesserung der Qualität der endgültigen Clusterung. Der Algorithmus reagiert empfindlich auf die Wahl von k, und Methoden wie die Ellbogenmethode oder die Silhouettenanalyse werden verwendet, um eine angemessene Anzahl von Clustern zu schätzen.
Eigenschaften und Einschränkungen
K-Means nimmt an, dass Cluster kugelförmig und von ähnlicher Größe sind, was seine Anwendbarkeit auf Daten mit komplexen Clusterformen einschränkt. Er reagiert auch empfindlich auf Ausreißer, da der Mittelwert durch extreme Werte beeinflusst wird. Der Algorithmus konvergiert zu einem lokalen Optimum, nicht unbedingt zum globalen, und unterschiedliche Initialisierungen können unterschiedliche Ergebnisse liefern. Trotz dieser Einschränkungen machen seine Einfachheit und Skalierbarkeit ihn zu einer beliebten Wahl für große Datensätze, insbesondere in Datenanreicherungs- und Vorverarbeitungspipelines.
Anwendungen
K-Means wird in verschiedenen Bereichen eingesetzt. In der künstlichen Intelligenz dient er als Basislinie für Clusteraufgaben. In der Computer Vision wird er für Bildsegmentierung und Farbquantisierung verwendet. Im Marketing hilft er, Kunden basierend auf dem Kaufverhalten zu segmentieren. In der Verarbeitung natürlicher Sprache kann er Dokumente oder Worteinbettungen clustern. Der Algorithmus ist auch ein Baustein für fortgeschrittenere Techniken wie Deep-Learning-Merkmalslernen und Generative AI-Modelle.
Beziehung zu anderen Methoden
K-Means ist mit Gaußschen Mischmodellen (GMM) verwandt, da beide iterative Verfeinerung und Clusterzentren verwenden. GMM erlaubt jedoch Clustern unterschiedliche Formen und Kovarianzen, während K-Means isotrope Cluster annimmt. Der Nearest-Centroid-Klassifikator, der aus K-Means abgeleitet ist, ist eine einfache überwachte Klassifikationsmethode. K-Means wird oft mit K-Nearest-Neighbors (k-NN) verwechselt, aber sie sind unterschiedlich: K-Means ist unüberwacht, während k-NN überwacht ist.
Geschichte und Entwicklung
Das Konzept von K-Means wurde erstmals 1956 von Hugo Steinhaus vorgeschlagen, und der Begriff "K-Means" wurde 1967 von James MacQueen geprägt. Der Lloyd-Algorithmus, 1957 veröffentlicht, aber erst 1982 weithin bekannt, ist die Standardimplementierung. Im Laufe der Jahre wurden zahlreiche Varianten entwickelt, wie Mini-Batch-K-Means für großskalige Daten und Fuzzy-C-Means für weiche Clusterung.