k-Means-Algorithmus

Der Begriff „k-means“ wurde zuerst von MacQueen 1967 verwendet,[2] die Idee geht jedoch auf Hugo Steinhaus 1957 zurück.[3] Der heutzutage meist als „k-means-Algorithmus“ bezeichnete Standard-Algorithmus wurde 1957 von Lloyd zur Puls-Code-Modulation vorgeschlagen, aber erst 1982 in einer Informatik-Zeitschrift publiziert[4] und deckt sich weitestgehend mit der Methode von Forgy, die 1965 publiziert wurde.[5] Eine weitere Variante ist die von Hartigan und Wong, die unnötige Distanzberechnungen vermeidet, indem sie auch den Abstand zum zweitnächsten Mittelpunkt verwendet.[6][7] Eine genaue Zuordnung der Algorithmen wird oft falsch gemacht: Insbesondere wird oft der Algorithmus von Lloyd/Forgy beschrieben, als Quelle jedoch MacQueen genannt.

Ziel von k-Means ist es, den Datensatz so in ${\displaystyle k}$ Partitionen zu teilen, dass die Summe der quadrierten Abweichungen von den Cluster-Schwerpunkten minimal ist. Mathematisch entspricht dies der Optimierung der Funktion

${\displaystyle J=\sum _{i=1}^{k}\sum _{\mathbf {x} _{j}\in S_{i}}{\|\mathbf {x} _{j}-{\boldsymbol {\mu }}_{i}\|^{2}}}$

mit den Datenpunkten ${\displaystyle \mathbf {x} _{j}}$ und den Schwerpunkten ${\displaystyle {\boldsymbol {\mu }}_{i}}$ der Cluster ${\displaystyle S_{i}}$. Diese Zielfunktion basiert auf der Methode der kleinsten Quadrate und man spricht auch von Clustering durch Varianzminimierung,[8] da die Summe der Varianzen der Cluster minimiert wird. Da zudem ${\displaystyle \|\mathbf {x} _{j}-{\boldsymbol {\mu }}_{i}\|^{2}}$ die quadrierte Euklidische Distanz ist, ordnet k-Means effektiv jedes Objekt dem nächstgelegenen (nach Euklidischer Distanz) Clusterschwerpunkt zu. Umgekehrt ist das arithmetische Mittel ein Kleinste-Quadrate-Schätzer, optimiert also ebenfalls dieses Kriterium.

Da die Suche nach der optimalen Lösung schwer ist (NP-schwer), wird im Normalfall ein approximativer Algorithmus verwendet wie die Heuristiken von Lloyd oder MacQueen. Da die Problemstellung von k abhängig ist, muss dieser Parameter vom Benutzer festgelegt werden. Es existieren jedoch auch Ansätze, durch Verwendung eines zweiten Objektes diesen Parameter zu wählen (vgl. X-Means, Akaike-Informationskriterium, bayessches Informationskriterium und Silhouettenkoeffizient).

Lloyd-Algorithmus

Konvergenz von k-means

Der am häufigsten verwendete k-Means-Algorithmus ist der Lloyd-Algorithmus, der oft als „der k-means-Algorithmus“ bezeichnet wird, obwohl Lloyd diesen Namen nicht verwendet hat. Lloyds Algorithmus besteht aus drei Schritten:

1. Initialisierung: Wähle ${\displaystyle k}$ zufällige Mittelwerte (Means): ${\displaystyle \mathbf {m} _{1}^{(1)},\ldots ,\mathbf {m} _{k}^{(1)}}$ aus dem Datensatz.
2. Zuordnung: Jedes Datenobjekt wird demjenigen Cluster zugeordnet, bei dem die Cluster-Varianz am wenigsten erhöht wird.
   ${\displaystyle S_{i}^{(t)}=\left\{\mathbf {x} _{j}:{\big \|}\mathbf {x} _{j}-\mathbf {m} _{i}^{(t)}{\big \|}^{2}\leq {\big \|}\mathbf {x} _{j}-\mathbf {m} _{i^{*}}^{(t)}{\big \|}^{2}{\text{ für alle }}i^{*}=1,\ldots ,k\right\}}$
3. Aktualisieren: Berechne die Mittelpunkte der Cluster neu:
   ${\displaystyle \mathbf {m} _{i}^{(t+1)}={\frac {1}{|S_{i}^{(t)}|}}\sum _{\mathbf {x} _{j}\in S_{i}^{(t)}}\mathbf {x} _{j}}$

Die Schritte 2–3 werden dabei so lange wiederholt, bis sich die Zuordnungen nicht mehr ändern.

k-Means optimiert die quadratischen Abweichungen von einem Mittelwert. Es kann daher nur mit numerischen Attributen verwendet werden, bei denen ein sinnvoller Mittelwert berechnet werden kann. Kategorielle Attribute (bspw. „Auto“, „LKW“, „Fahrrad“) können nicht verwendet werden, da hier kein Mittelwert berechnet werden kann.

Der Parameter ${\displaystyle k}$, die Anzahl der Cluster, muss im Voraus bekannt sein. Er kann jedoch auch experimentell bestimmt werden. Das Problem ist, dass die verschiedenen Cluster miteinander verglichen werden müssen und die Kostenfunktion mit steigendem ${\displaystyle k}$ monoton sinkt. Eine Lösung ist der Silhouettenkoeffizient, der eine von ${\displaystyle k}$ unabhängige Bewertung von Clusterungen liefert. Hierbei wird nicht nur geprüft, wie weit ein Punkt vom eigenen Clusterschwerpunkt entfernt ist, sondern es gehen auch die Entfernungen von anderen Clusterschwerpunkten in die Bewertung des Clustering mit ein.

Die Cluster im Datensatz müssen etwa gleich groß sein, da der Algorithmus den Datensatz stets an der Mitte zwischen zwei Clusterzentren partitioniert.

Der Datensatz darf nicht viel Rauschen bzw. nicht viele Ausreißer enthalten. Fehlerhafte Datenobjekte verschieben die berechneten Clusterzentren oft erheblich, und der Algorithmus hat keine Vorkehrungen gegen derartige Effekte (vgl. DBSCAN, das „Noise“-Objekte explizit vorsieht).

k-Means Ergebnis und reale Schwertlilien-Spezies im Iris Flower Datensatz, visualisiert mit ELKI. Die Clusterzentren sind durch größere, blassere Symbole gekennzeichnet.

k-Means ist ein leistungsfähiger Algorithmus, jedoch nicht ohne Schwachstellen. Ein k-Means-Algorithmus muss nicht die beste mögliche Lösung finden. Die gefundene Lösung hängt stark von den gewählten Startpunkten ab. Der einfachste Ansatz ist, den Algorithmus mehrmals hintereinander mit verschiedenen Startwerten zu starten und die beste Lösung zu nehmen. Es gibt aber auch viele Überlegungen, wie eine geeignete Verteilung der Startwerte erreicht werden kann. Zu nennen sind unter anderem k-means++, aber auch mit dem Ziehen kleiner Stichproben können die Clusterzentren vor dem Start von k-means angenähert werden. Außerdem macht es einen Unterschied, ob man beliebige Clusterzentren wählt, oder jeden Punkt einem beliebigen Cluster zuordnet und dann die Clusterzentren ermittelt.

Ein weiterer Nachteil ist, dass die Anzahl der Clusterzentren ${\displaystyle k}$ im Voraus gewählt wird. Bei Verwendung eines ungeeigneten ${\displaystyle k}$ können sich komplett andere, unter Umständen unintuitive Lösungen ergeben. Bei einem „falschen“ ${\displaystyle k}$ kann kein gutes Clustering erfolgen. Die Lösung ist, verschiedene Werte für ${\displaystyle k}$ zu probieren und dann ein geeignetes zu wählen, zum Beispiel mit Hilfe des Silhouettenkoeffizienten, oder durch Vergleich der verschiedenen Clusteringkosten.

Gruppen in den Daten können sich, wie in dem gezeigten Schwertlilien-Beispiel, überlappen und nahtlos ineinander übergehen. In einem solchen Fall kann k-Means diese Gruppen nicht zuverlässig trennen, da die Daten nicht dem verwendeten Cluster-Modell folgen.

Des Weiteren sucht k-Means stets konvexe Cluster (bedingt durch die Minimierung des Abstandes zum Clusterschwerpunkt). Andere Algorithmen wie DBSCAN können auch beliebig geformte „dichtebasierte“ Cluster finden. Was ebenfalls von k-Means nicht unterstützt wird, sind hierarchische Cluster (also Cluster, die wiederum eine Clusterstruktur aufweisen), wie sie beispielsweise mit OPTICS gefunden werden können.

Als letztes wird in k-means jeder Punkt einem Cluster zugewiesen, es gibt keine Möglichkeit Ausreißer zu erkennen. Diese können das Ergebnis stark verfälschen. Abhilfe kann hier eine vorherige Noisereduktion schaffen, oder andere Algorithmen, wie DBSCAN, die automatisch Noise erkennen.

Die folgenden Bilder zeigen exemplarisch einen Durchlauf eines k-Means-Algorithmus zur Bestimmung von drei Gruppen:

	Drei Clusterzentren wurden zufällig gewählt.
	Die durch Rechtecke repräsentierten Objekte (Datenpunkte) werden jeweils dem Cluster mit dem nächsten Clusterzentrum zugeordnet.
	Die Zentren (jeweilige Schwerpunkte) der Cluster werden neu berechnet.
	Die Objekte werden neu verteilt und erneut dem Cluster zugewiesen, dessen Zentrum am nächsten ist.

In der Bildverarbeitung wird der k-Means-Algorithmus oft zur Segmentierung verwendet. Als Entfernungsmaß ist die euklidische Distanz häufig nicht ausreichend und es können andere Abstandsfunktionen, basierend auf Pixelintensitäten und Pixelkoordinaten verwendet werden. Die Ergebnisse werden zur Trennung von Vordergrund und Hintergrund und zur Objekterkennung benutzt. Der Algorithmus ist weit verbreitet und ist in gängigen Bildverarbeitungsbibliotheken wie OpenCV, Scikit-image[16] und itk implementiert.

K-means und seine Varianten sind in verschiedener Open-Source-Software verfügbar.

• Dlib[17]
• ELKI enthält die Varianten von Lloyd und MacQueen, dazu verschiedene Strategien für die Startwerte wie k-means++, und Varianten des Algorithmus wie k-medians, k-medoids und PAM.
• GNU R enthält die Varianten von Hartigan, Lloyd und MacQueen, und zusätzliche Variationen im Erweiterungspaket „flexclust“.
• OpenCV enthält eine auf Bildverarbeitung optimierte Version von k-means (inkl. k-means++ seeding)
• Scikit-learn enthält k-means, inkl. Elkans Variante und k-means++.
• Weka enthält k-means (inkl. k-means++ seeding) und die Erweiterung x-means.

• David MacKay: Information Theory, Inference and Learning Algorithms. Cambridge University Press, 2003, ISBN 0-521-64298-1, Chapter 20. An Example Inference Task: Clustering, S. 284–292 (inference.phy.cam.ac.uk [PDF]).
• Gary Bradski, Adrian Kaehler: Learning OpenCV Computer Vision with the OpenCV Library. O’Reilly, 2001, ISBN 978-0-596-51613-0.