K-Means-Clustering ist eine Methode der Vektorquantisierung, die ursprünglich aus der Signalverarbeitung stammt und eine Menge von Beobachtungen in k Cluster aufteilt, wobei jede Beobachtung zu dem Cluster mit dem nächsten Mittelwert gehört, der als Cluster-Zentroid bezeichnet wird. Dies führt zu einer Partitionierung des Datenraums in Voronoi-Zellen. Der Algorithmus wird häufig im maschinellen Lernen für Aufgaben wie Kundensegmentierung, Bildkompression und Mustererkennung eingesetzt und ist eine grundlegende Technik in der künstlichen Intelligenz und der Datenanalyse.
Das Ziel von k-Means ist es, die Summe der quadratischen Abweichungen innerhalb der Cluster (WCSS) zu minimieren, also die Summe der quadrierten euklidischen Abstände zwischen jedem Punkt und seinem Cluster-Zentroid. Dies ist äquivalent zur Minimierung der paarweisen quadrierten Abweichungen von Punkten innerhalb desselben Clusters. Allerdings minimiert k-Means quadrierte euklidische Abstände, nicht die regulären euklidischen Abstände; Letzteres würde die Lösung des schwierigeren Weber-Problems erfordern. Für die Minimierung euklidischer Abstände sind Alternativen wie k-Medians oder k-Medoids besser geeignet.
Das Problem, die optimale k-Means-Clusterung zu finden, ist rechnerisch schwierig (NP-schwer), aber effiziente heuristische Algorithmen konvergieren schnell zu einem lokalen Optimum. Der gebräuchlichste Ansatz ist der Lloyd-Algorithmus, der iterativ Punkte dem nächsten Zentroid zuweist und dann die Zentroide als Mittelwert der zugewiesenen Punkte aktualisiert. Diese iterative Verfeinerung ähnelt dem Erwartungs-Maximierungs-Algorithmus, der für Gaußsche Mischmodelle verwendet wird, aber k-Means tendiert dazu, Cluster mit vergleichbarer räumlicher Ausdehnung zu finden, während Gaußsche Mischungen unterschiedliche Formen erlauben.
Algorithmus und Implementierung
Der Standard-k-Means-Algorithmus beginnt mit einer anfänglichen Menge von k Zentroiden, die zufällig oder mit Methoden wie k-Means++ gewählt werden können, um die Konvergenz zu verbessern. Der Algorithmus wiederholt zwei Schritte bis zur Konvergenz: Zuordnung, bei der jede Beobachtung dem Cluster mit dem nächsten Zentroid zugewiesen wird, und Aktualisierung, bei der jeder Zentroid als Mittelwert aller Punkte in seinem Cluster neu berechnet wird. Konvergenz wird typischerweise erkannt, wenn sich die Zuordnungen nicht mehr ändern oder wenn die Verbesserung der WCSS unter einen Schwellenwert fällt.
Es gibt mehrere Varianten, darunter Mini-Batch-k-Means für große Datensätze und sphärisches k-Means für Textdaten. Die Wahl von k wird oft mit der Ellbogen-Methode, der Silhouetten-Analyse oder der Gap-Statistik bestimmt. Die Zeitkomplexität des Algorithmus beträgt ungefähr O(nkd*i), wobei n die Anzahl der Beobachtungen, d die Dimensionalität und i die Anzahl der Iterationen ist.
Beziehung zu anderen Methoden
K-Means ist ein unüberwachter Algorithmus, was bedeutet, dass er keine beschrifteten Daten benötigt. Er hat eine lockere Beziehung zum k-Nearest-Neighbor-Klassifikator (k-NN), einer überwachten Technik. Die Anwendung des 1-Nearest-Neighbor-Klassifikators auf die Cluster-Zentren, die durch k-Means erhalten werden, klassifiziert neue Daten in bestehende Cluster; dies ist als Nearest-Centroid-Klassifikator oder Rocchio-Algorithmus bekannt. Diese Verbindung zeigt, wie unüberwachtes Clustering überwachte Aufgaben unterstützen kann.
K-Means ist auch mit Gaußschen Mischmodellen (GMMs) verwandt. Beide verwenden Cluster-Zentren, um Daten zu modellieren, aber GMMs erlauben Clustern unterschiedliche Formen und Größen, während k-Means sphärische Cluster mit ähnlicher Varianz annimmt. Folglich ist k-Means einfacher und schneller, aber weniger flexibel.
Anwendungen und Einschränkungen
K-Means wird in vielen Bereichen eingesetzt. In Amazon Web Services und Google Cloud ist es ein gängiges Werkzeug zur Analyse des Nutzerverhaltens und zur Optimierung der Ressourcenzuteilung. In der Bildverarbeitung wird es für Bildsegmentierung und Farbquantisierung verwendet. Im Marketing segmentiert es Kunden anhand von Kaufmustern. Der Algorithmus ist auch ein Baustein für komplexere Methoden wie die Merkmalsextraktion im Deep Learning und die Datenvorverarbeitung in der generativen KI.
Allerdings hat k-Means Einschränkungen. Es erfordert, dass die Anzahl der Cluster k im Voraus angegeben wird, was nicht immer bekannt ist. Es ist empfindlich gegenüber der anfänglichen Zentroid-Auswahl, obwohl k-Means++ dies abschwächt. Es nimmt an, dass Cluster konvex und isotrop sind, was für reale Daten möglicherweise nicht zutrifft. Ausreißer können Zentroide verzerren, und der Algorithmus kann in lokalen Optima konvergieren. Trotz dieser Probleme machen seine Einfachheit und Effizienz es zu einer beliebten Wahl.
Historischer Kontext und Entwicklung
Der k-Means-Algorithmus wurde erstmals 1956 von Hugo Steinhaus vorgeschlagen und später 1957 von Stuart Lloyd bei den Bell Labs verfeinert (wenn auch erst 1982 veröffentlicht). Der Name "k-Means" wurde 1967 von James MacQueen geprägt. Seitdem wurden zahlreiche Verbesserungen entwickelt, darunter k-Means++ für eine bessere Initialisierung und die Mini-Batch-Variante für Skalierbarkeit. Der Algorithmus bleibt ein fester Bestandteil der Lehrpläne im maschinellen Lernen und ist in wichtigen Bibliotheken wie scikit-learn und TensorFlow implementiert.