K-Means-Algorithmus

k-means clustering ist eine ursprünglich aus der Signalverarbeitung stammende Methode der Vektorquantisierung, die darauf abzielt, n Beobachtungen in k Cluster aufzuteilen, wobei jede Beobachtung zu dem Cluster mit dem nächstgelegenen Mittelwert (Clusterzentren oder Clusterschwerpunkt) gehört, der als Prototyp des Clusters dient. Dies führt zu einer Partitionierung des Datenraums in Voronoi-Zellen. Das k-means-Clustering minimiert die Varianzen innerhalb der Cluster (quadrierte euklidische Abstände), aber nicht die regulären euklidischen Abstände, was das schwierigere Weber-Problem wäre: Der Mittelwert optimiert die quadratischen Fehler, während nur der geometrische Median die euklidischen Abstände minimiert. Bessere euklidische Lösungen können zum Beispiel mit k-Medianen und k-Medoiden gefunden werden. ⓘ

Das Problem ist rechnerisch schwierig (NP-hard); effiziente heuristische Algorithmen konvergieren jedoch schnell zu einem lokalen Optimum. Diese Algorithmen ähneln in der Regel dem Erwartungsmaximierungsalgorithmus für Gaußsche Verteilungsmischungen, der durch einen iterativen Verfeinerungsansatz sowohl bei k-means als auch bei der Gaußschen Mischungsmodellierung eingesetzt wird. Beide verwenden Clusterzentren, um die Daten zu modellieren; allerdings neigt das k-means-Clustering dazu, Cluster mit vergleichbarer räumlicher Ausdehnung zu finden, während das Gaußsche Mischungsmodell Cluster mit unterschiedlichen Formen zulässt. ⓘ

Der unbeaufsichtigte k-means-Algorithmus steht in loser Beziehung zum k-nearest neighbor classifier, einer beliebten überwachten maschinellen Lerntechnik für die Klassifizierung, die aufgrund des Namens oft mit k-means verwechselt wird. Durch die Anwendung des 1-Nächster-Nachbar-Klassifikators auf die durch k-means ermittelten Clusterzentren werden neue Daten in die bestehenden Cluster eingeordnet. Dieses Verfahren wird als Nearest Centroid Classifier oder Rocchio-Algorithmus bezeichnet. ⓘ

Ein k-Means-Algorithmus ist ein Verfahren zur Vektorquantisierung, das auch zur Clusteranalyse verwendet wird. Dabei wird aus einer Menge von ähnlichen Objekten eine vorher bekannte Anzahl von k Gruppen gebildet. Der Algorithmus ist eine der am häufigsten verwendeten Techniken zur Gruppierung von Objekten, da er schnell die Zentren der Cluster findet. Dabei bevorzugt der Algorithmus Gruppen mit geringer Varianz und ähnlicher Größe. ⓘ

Der Algorithmus hat starke Ähnlichkeiten mit dem EM-Algorithmus und zeichnet sich durch seine Einfachheit aus. Erweiterungen sind der k-Median-Algorithmus und der k-Means++ Algorithmus. ⓘ

Beschreibung

Bei einer Menge von Beobachtungen (x₁, x₂, ..., xn), wobei jede Beobachtung ein d-dimensionaler reeller Vektor ist, zielt das k-means-Clustering darauf ab, die n Beobachtungen in k (≤ n) Mengen S = {S₁, S₂, ..., Sk} zu partitionieren, um die Quadratsumme innerhalb des Clusters (WCSS) (d. h. die Varianz) zu minimieren. Formal besteht das Ziel darin, Folgendes zu finden:

{\underset {\mathbf {S} }{\operatorname {arg\,min} }}\sum _{i=1}^{k}\sum _{\mathbf {x} \in S_{i}}\left\|\mathbf {x} -{\boldsymbol {\mu }}_{i}\right\|^{2}={\underset {\mathbf {S} }{\operatorname {arg\,min} }}\sum _{i=1}^{k}|S_{i}|\operatorname {Var} S_{i}

wobei μi der Mittelwert der Punkte in Si ist. Dies ist gleichbedeutend mit der Minimierung der paarweisen quadratischen Abweichungen der Punkte im selben Cluster:

{\underset {\mathbf {S} }{\operatorname {arg\,min} }}\sum _{i=1}^{k}\,{\frac {1}{|S_{i}|}}\,\sum _{\mathbf {x} ,\mathbf {y} \in S_{i}}\left\|\mathbf {x} -\mathbf {y} \right\|^{2}

Die Äquivalenz lässt sich aus der Identität ableiten $|S_{i}|\sum _{\mathbf {x} \in S_{i}}\left\|\mathbf {x} -{\boldsymbol {\mu }}_{i}\right\|^{2}=\sum _{\mathbf {x} \neq \mathbf {y} \in S_{i}}\left\|\mathbf {x} -\mathbf {y} \right\|^{2}$ . Da die Gesamtvarianz konstant ist, ist dies gleichbedeutend mit der Maximierung der Summe der quadrierten Abweichungen zwischen Punkten in verschiedenen Clustern (between-cluster sum of squares, BCSS). Diese deterministische Beziehung ist auch mit dem Gesetz der Gesamtvarianz in der Wahrscheinlichkeitstheorie verwandt. ⓘ

Geschichte

Der Begriff "k-means" wurde erstmals 1967 von James MacQueen verwendet, obwohl die Idee auf Hugo Steinhaus im Jahr 1956 zurückgeht. Der Standardalgorithmus wurde erstmals 1957 von Stuart Lloyd von Bell Labs als Technik für die Pulscodemodulation vorgeschlagen, obwohl er erst 1982 in einem Zeitschriftenartikel veröffentlicht wurde. Im Jahr 1965 veröffentlichte Edward W. Forgy im Wesentlichen dieselbe Methode, weshalb sie manchmal auch als Lloyd-Forgy-Algorithmus bezeichnet wird. ⓘ

Algorithmen

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). ⓘ

Standard-Algorithmus (naives k-means)

Konvergenz von k-means ⓘ

Der am weitesten verbreitete Algorithmus verwendet eine iterative Verfeinerungstechnik. Aufgrund seiner Allgegenwärtigkeit wird er oft als "k-means-Algorithmus" bezeichnet; insbesondere in der Informatik wird er auch als Lloyd-Algorithmus bezeichnet. Manchmal wird er auch als "naiver k-means-Algorithmus" bezeichnet, da es wesentlich schnellere Alternativen gibt. ⓘ

Bei einer anfänglichen Menge von k Mittelwerten m₁⁽¹⁾,...,mk⁽¹⁾ (siehe unten) geht der Algorithmus in zwei Schritten vor:

Zuweisungsschritt: Jede Beobachtung wird dem Cluster mit dem nächstgelegenen Mittelwert zugewiesen, d. h. dem Cluster mit dem geringsten quadratischen euklidischen Abstand. (Mathematisch gesehen bedeutet dies, dass die Beobachtungen entsprechend dem durch die Mittelwerte erzeugten Voronoi-Diagramm aufgeteilt werden).

S_{i}^{(t)}=\left\{x_{p}:\left\|x_{p}-m_{i}^{(t)}\right\|^{2}\leq \left\|x_{p}-m_{j}^{(t)}\right\|^{2}\ \forall j,1\leq j\leq k\right\},

wobei jede

x_{p}

genau einem

S^{(t)}

zugewiesen wird, auch wenn sie zwei oder mehr davon zugeordnet werden könnte.

Aktualisierungsschritt: Neuberechnung der Mittelwerte (Zentroide) für die Beobachtungen, die jedem Cluster zugeordnet sind.

m_{i}^{(t+1)}={\frac {1}{\left|S_{i}^{(t)}\right|}}\sum _{x_{j}\in S_{i}^{(t)}}x_{j}

ⓘ

Der Algorithmus hat konvergiert, wenn sich die Zuordnungen nicht mehr ändern. Es ist nicht garantiert, dass der Algorithmus das Optimum findet. ⓘ

Der Algorithmus wird oft so dargestellt, dass er die Objekte dem nächstgelegenen Cluster nach Entfernung zuordnet. Die Verwendung einer anderen Distanzfunktion als der (quadrierten) euklidischen Distanz kann die Konvergenz des Algorithmus verhindern. Es wurden verschiedene Modifikationen von k-means vorgeschlagen, wie z. B. sphärisches k-means und k-medoids, um die Verwendung anderer Abstandsmaße zu ermöglichen. ⓘ

Initialisierungsmethoden

Häufig verwendete Initialisierungsmethoden sind Forgy und Random Partition. Bei der Forgy-Methode werden nach dem Zufallsprinzip k Beobachtungen aus dem Datensatz ausgewählt und als Ausgangsmittel verwendet. Bei der Random-Partition-Methode wird jeder Beobachtung zunächst zufällig ein Cluster zugewiesen und dann der Aktualisierungsschritt durchgeführt, so dass der anfängliche Mittelwert als Schwerpunkt der zufällig zugewiesenen Punkte des Clusters berechnet wird. Die Forgy-Methode neigt dazu, die anfänglichen Mittelwerte zu streuen, während die Random Partition alle Mittelwerte in der Nähe des Zentrums des Datensatzes platziert. Nach Hamerly et al. ist die Random-Partition-Methode im Allgemeinen für Algorithmen wie das k-harmonische Mittel und Fuzzy k-means vorzuziehen. Für die Erwartungsmaximierung und die Standard-k-means-Algorithmen ist die Forgy-Methode der Initialisierung vorzuziehen. Eine umfassende Studie von Celebi et al. ergab jedoch, dass gängige Initialisierungsmethoden wie Forgy, Random Partition und Maximin oft schlecht abschneiden, während der Ansatz von Bradley und Fayyad "durchweg" in der "besten Gruppe" liegt und k-means++ "im Allgemeinen gut" abschneidet. ⓘ

Demonstration des Standardalgorithmus
1. k anfängliche "Mittelwerte" (in diesem Fall k=3) werden nach dem Zufallsprinzip innerhalb der Datendomäne erzeugt (farbig dargestellt).
2. k Cluster werden erstellt, indem jede Beobachtung mit dem nächstgelegenen Mittelwert verknüpft wird. Die Partitionen stellen hier das durch die Mittelwerte erzeugte Voronoi-Diagramm dar.
3. Der Schwerpunkt jedes der k Cluster wird zum neuen Mittelwert.
4. Die Schritte 2 und 3 werden wiederholt, bis Konvergenz erreicht ist. ⓘ

Der Algorithmus garantiert nicht die Konvergenz zum globalen Optimum. Das Ergebnis kann von den anfänglichen Clustern abhängen. Da der Algorithmus in der Regel schnell ist, ist es üblich, ihn mehrfach mit unterschiedlichen Startbedingungen auszuführen. Allerdings kann die Leistung im schlimmsten Fall langsam sein: Insbesondere konvergieren bestimmte Punktmengen, selbst in zwei Dimensionen, in exponentieller Zeit, d. h. 2Ω(n). Diese Punktmengen scheinen in der Praxis nicht aufzutreten: Dies wird durch die Tatsache bestätigt, dass die geglättete Laufzeit von k-means polynomial ist. ⓘ

Der "Zuweisungsschritt" wird als "Erwartungsschritt" bezeichnet, während der "Aktualisierungsschritt" ein Maximierungsschritt ist, was diesen Algorithmus zu einer Variante des verallgemeinerten Erwartungs-Maximierungs-Algorithmus macht. ⓘ

Komplexität

Die Suche nach der optimalen Lösung für das k-means-Clustering-Problem für Beobachtungen in d Dimensionen ist:

NP-schwer im allgemeinen euklidischen Raum (mit d Dimensionen) selbst für zwei Cluster,
NP-schwer für eine allgemeine Anzahl von Clustern k auch in der Ebene,
wenn k und d (die Dimension) festgelegt sind, kann das Problem exakt in der Zeit gelöst werden $O(n^{dk+1})$ gelöst werden, wobei n die Anzahl der zu clusternden Entitäten ist. ⓘ

Daher werden im Allgemeinen verschiedene heuristische Algorithmen wie der oben beschriebene Lloyd-Algorithmus verwendet. ⓘ

Die Laufzeit von Lloyds Algorithmus (und der meisten Varianten) ist $O(nkdi)$ wobei:

n die Anzahl der d-dimensionalen Vektoren (die geclustert werden sollen) ist
k die Anzahl von Clustern
i die Anzahl der bis zur Konvergenz erforderlichen Iterationen. ⓘ

Bei Daten, die eine Clusterstruktur aufweisen, ist die Anzahl der Iterationen bis zur Konvergenz oft gering, und die Ergebnisse verbessern sich nur geringfügig nach dem ersten Dutzend Iterationen. Lloyds Algorithmus wird daher in der Praxis oft als "linear" komplex angesehen, obwohl er im schlimmsten Fall superpolynomial ist, wenn er bis zur Konvergenz ausgeführt wird. ⓘ

Im ungünstigsten Fall benötigt Lloyds Algorithmus $i=2^{\Omega ({\sqrt {n}})}$ Iterationen, so dass die Komplexität von Lloyds Algorithmus im ungünstigsten Fall superpolynomial ist.
Lloyds k-means Algorithmus hat eine polynomial geglättete Laufzeit. Es wird gezeigt, dass für eine beliebige Menge von n Punkten in $[0,1]^{d}$ wenn jeder Punkt unabhängig durch eine Normalverteilung mit Mittelwert $0$ und Varianz $\sigma ^{2}$ ist, dann ist die erwartete Laufzeit des $k$ -means Algorithmus begrenzt durch $O(n^{34}k^{34}d^{8}\log ^{4}(n)/\sigma ^{6})$ begrenzt, was ein Polynom in n, $k$ , $d$ und $1/\sigma$ .
Für einfache Fälle werden bessere Schranken bewiesen. So wird beispielsweise gezeigt, dass die Laufzeit des k-means-Algorithmus begrenzt ist durch $O(dn^{4}M^{2})$ für $n$ Punkte eines ganzzahligen Gitters $\{1,\dots ,M\}^{d}$ . ⓘ

Der Algorithmus von Lloyd ist der Standardansatz für dieses Problem. Allerdings verbringt er viel Zeit mit der Berechnung der Abstände zwischen jedem der k Clusterzentren und den n Datenpunkten. Da die Punkte in der Regel nach ein paar Iterationen in denselben Clustern verbleiben, ist ein Großteil dieser Arbeit unnötig, was die naive Implementierung sehr ineffizient macht. Einige Implementierungen nutzen die Zwischenspeicherung und die Dreiecksungleichung, um Grenzen zu schaffen und Lloyds Algorithmus zu beschleunigen. ⓘ

Variationen

Jenks Optimierung der natürlichen Brüche: k-means angewandt auf univariate Daten
k-medians clustering verwendet den Median in jeder Dimension anstelle des Mittelwerts und minimiert auf diese Weise die $L_{1}$ Norm (Taxicab-Geometrie).
k-medoids (auch: Partitioning Around Medoids, PAM) verwendet das Medoid anstelle des Mittelwerts und minimiert auf diese Weise die Summe der Abstände für beliebige Abstandsfunktionen.
Fuzzy C-Means Clustering ist eine weiche Version von k-means, bei der jeder Datenpunkt einen unscharfen Grad der Zugehörigkeit zu jedem Cluster hat.
Gaußsche Mischmodelle, die mit dem Algorithmus der Erwartungsmaximierung (EM-Algorithmus) trainiert werden, erhalten probabilistische Zuordnungen zu Clustern anstelle von deterministischen Zuordnungen und multivariate Gauß-Verteilungen anstelle von Mittelwerten.
k-means++ wählt die anfänglichen Zentren auf eine Weise, die eine nachweisbare obere Schranke für das WCSS-Ziel ergibt.
Der Filterungsalgorithmus verwendet kd-Bäume, um jeden k-means-Schritt zu beschleunigen.
Einige Methoden versuchen, jeden k-means-Schritt mithilfe der Dreiecksungleichung zu beschleunigen.
Lokale Optima werden durch den Austausch von Punkten zwischen Clustern umgangen.
Der sphärische k-means-Clusteralgorithmus ist für Textdaten geeignet.
Hierarchische Varianten wie Bisecting k-means, X-means clustering und G-means clustering teilen wiederholt Cluster auf, um eine Hierarchie aufzubauen, und können auch versuchen, automatisch die optimale Anzahl von Clustern in einem Datensatz zu bestimmen.
Interne Clusterevaluierungsmaße wie die Clustersilhouette können bei der Bestimmung der Anzahl von Clustern hilfreich sein.
Minkowski-gewichtetes k-means berechnet automatisch clusterspezifische Merkmalsgewichte, die die intuitive Idee unterstützen, dass ein Merkmal bei verschiedenen Merkmalen unterschiedliche Relevanzgrade haben kann. Diese Gewichte können auch verwendet werden, um einen gegebenen Datensatz neu zu skalieren, wodurch die Wahrscheinlichkeit erhöht wird, dass ein Clustervaliditätsindex bei der erwarteten Anzahl von Clustern optimiert wird.
Mini-Batch k-means: k-means-Variante mit "Mini-Batch"-Stichproben für Datensätze, die nicht in den Speicher passen.
Otsu-Methode ⓘ

Hartigan-Wong-Verfahren

Die Methode von Hartigan und Wong ist eine Variante des k-means-Algorithmus, die sich auf ein lokales Minimum des Problems der minimalen Quadratsumme mit verschiedenen Lösungsaktualisierungen zubewegt. Bei der Methode handelt es sich um eine lokale Suche, bei der iterativ versucht wird, eine Stichprobe in einen anderen Cluster zu verschieben, solange dieser Prozess die Zielfunktion verbessert. Wenn keine Stichprobe mit einer Verbesserung der Zielfunktion in ein anderes Cluster verschoben werden kann, bleibt die Methode stehen (in einem lokalen Minimum). Ähnlich wie beim klassischen k-means bleibt der Ansatz eine Heuristik, da er nicht unbedingt garantiert, dass die endgültige Lösung global optimal ist. ⓘ

Sei $\varphi (S_{j})$ die individuellen Kosten von $S_{j}$ definiert durch $\sum _{x\in S_{j}}(x-\mu _{j})^{2}$ definiert, wobei $\mu _{j}$ das Zentrum des Clusters. ⓘ

Zuweisungsschritt: Die Methode von Hartigan und Wong beginnt mit der Aufteilung der Punkte in zufällige Cluster. $\{S_{j}\}_{j\in \{1,\cdots k\}}$ . ⓘ

Schritt der Aktualisierung: Als Nächstes bestimmt sie die $n,m\in \{1,\ldots ,k\}$ und $x\in S_{n}$ für die die folgende Funktion ein Maximum erreicht ⓘ

\Delta (m,n,x)=\varphi (S_{n})+\varphi (S_{m})-\varphi (S_{n}\smallsetminus \{x\})-\varphi (S_{m}\cup \{x\}).

ⓘ

Für die $x,n,m$ die dieses Maximum erreichen, $x$ aus dem Cluster $S_{n}$ zum Cluster $S_{m}$ . ⓘ

Beendigung: Der Algorithmus ist beendet, wenn $\Delta (m,n,x)$ kleiner als Null ist für alle $x,n,m$ . ⓘ

Es können verschiedene Strategien zur Annahme von Umzügen verwendet werden. Bei einer Erstverbesserungsstrategie kann jede sich verbessernde Verschiebung angewendet werden, während bei einer Bestverbesserungsstrategie alle möglichen Verschiebungen iterativ getestet werden und nur die beste bei jeder Iteration angewendet wird. Der erstgenannte Ansatz begünstigt die Geschwindigkeit, während der letztgenannte Ansatz im Allgemeinen die Lösungsqualität auf Kosten zusätzlicher Rechenzeit begünstigt. Die Funktion $\Delta$ die zur Berechnung des Ergebnisses einer Verlagerung verwendet wird, kann auch effizient ausgewertet werden, indem man Gleichheit ⓘ

\Delta (x,n,m)={\frac {\mid S_{n}\mid }{\mid S_{n}\mid -1}}\cdot \lVert \mu _{n}-x\rVert ^{2}-{\frac {\mid S_{m}\mid }{\mid S_{m}\mid +1}}\cdot \lVert \mu _{m}-x\rVert ^{2}.

ⓘ

Globale Optimierung und Metaheuristiken

Es ist bekannt, dass der klassische k-means-Algorithmus und seine Variationen nur zu lokalen Minima des Minimum-Summe-der-Quadrate-Clustering-Problems konvergieren, das als

{\underset {\mathbf {S} }{\operatorname {arg\,min} }}\sum _{i=1}^{k}\sum _{\mathbf {x} \in S_{i}}\left\|\mathbf {x} -{\boldsymbol {\mu }}_{i}\right\|^{2}.

In vielen Studien wurde versucht, das Konvergenzverhalten des Algorithmus zu verbessern und die Chancen auf das Erreichen des globalen Optimums (oder zumindest lokaler Minima von besserer Qualität) zu maximieren. Die in den vorangegangenen Abschnitten erörterten Initialisierungs- und Neustarttechniken sind eine Alternative, um bessere Lösungen zu finden. In jüngster Zeit haben globale Optimierungsalgorithmen, die auf Branch-and-Bound und semidefiniter Programmierung basieren, "nachweislich optimale" Lösungen für Datensätze mit bis zu 4.177 Entitäten und 20.531 Merkmalen hervorgebracht. Aufgrund der NP-Härte des darunterliegenden Optimierungsproblems steigt die Rechenzeit optimaler Algorithmen für K-means erwartungsgemäß schnell über diese Größe hinaus. Optimale Lösungen für kleine und mittlere Skalen bleiben dennoch wertvoll als Benchmark-Tool, um die Qualität anderer Heuristiken zu bewerten. Um qualitativ hochwertige lokale Minima innerhalb einer kontrollierten Rechenzeit, aber ohne Optimalitätsgarantie zu finden, haben andere Arbeiten Metaheuristiken und andere globale Optimierungstechniken erforscht, z. B. auf der Grundlage inkrementeller Ansätze und konvexer Optimierung, zufälliger Vertauschungen (d. h. iterierter lokaler Suche), variabler Nachbarschaftssuche und genetischer Algorithmen. Es ist bekannt, dass das Auffinden besserer lokaler Minima des minimalen Sum-of-Squares-Clustering-Problems den Unterschied zwischen Misserfolg und Erfolg bei der Wiederherstellung von Clusterstrukturen in hochdimensionalen Merkmalsräumen ausmachen kann. ⓘ

MacQueen’s Algorithmus

MacQueen führte mit dem Begriff "k-Means" einen anderen Algorithmus ein:

Wähle die ersten $k$ Elemente als Clusterzentren
Weise jedes neue Element dem Cluster zu, bei dem sich die Varianz am wenigsten erhöht, und aktualisiere das Clusterzentrum ⓘ

Während es ursprünglich – vermutlich – nicht vorgesehen war, kann man auch diesen Algorithmus iterieren, um ein besseres Ergebnis zu erhalten. ⓘ

Diskussion

Ein typisches Beispiel für die Konvergenz von k-means zu einem lokalen Minimum. In diesem Beispiel widerspricht das Ergebnis des k-means-Clustering (rechte Abbildung) der offensichtlichen Clusterstruktur des Datensatzes. Die kleinen Kreise sind die Datenpunkte, die vier Strahlensterne sind die Zentroide (Mittelwerte). Die Ausgangskonfiguration ist in der linken Abbildung dargestellt. Der Algorithmus konvergiert nach fünf Iterationen, die in den Abbildungen von links nach rechts dargestellt sind. Die Illustration wurde mit dem Java-Applet Mirkes erstellt. ⓘ

k-means Clustering Ergebnis für den Irisblumen-Datensatz und die tatsächlichen Arten, visualisiert mit ELKI. Die Mittelwerte der Cluster sind durch größere, halbtransparente Symbole gekennzeichnet. ⓘ

k-means Clustering vs. EM Clustering auf einem künstlichen Datensatz ("Maus"). Die Tendenz von k-means, gleich große Cluster zu erzeugen, führt hier zu schlechten Ergebnissen, während EM von den im Datensatz vorhandenen Gaußverteilungen mit unterschiedlichem Radius profitiert. ⓘ

Drei Hauptmerkmale von k-means, die es effizient machen, werden oft als seine größten Nachteile angesehen:

Der euklidische Abstand wird als Metrik verwendet und die Varianz wird als Maß für die Streuung der Cluster verwendet.
Die Anzahl der Cluster k ist ein Eingabeparameter: eine ungeeignete Wahl von k kann zu schlechten Ergebnissen führen. Deshalb ist es wichtig, bei der Durchführung von k-means diagnostische Prüfungen zur Bestimmung der Anzahl der Cluster im Datensatz durchzuführen.
Die Konvergenz zu einem lokalen Minimum kann zu kontraintuitiven ("falschen") Ergebnissen führen (siehe Beispiel in Abb.). ⓘ

Eine wesentliche Einschränkung von k-means ist sein Clustermodell. Das Konzept basiert auf kugelförmigen Clustern, die trennbar sind, so dass der Mittelwert gegen das Zentrum des Clusters konvergiert. Es wird davon ausgegangen, dass die Cluster eine ähnliche Größe haben, so dass die Zuordnung zum nächstgelegenen Clusterzentrum die richtige Zuordnung ist. Wendet man zum Beispiel k-means mit einem Wert von $k=3$ auf den bekannten Irisblumen-Datensatz anwendet, gelingt es dem Ergebnis oft nicht, die drei im Datensatz enthaltenen Iris-Arten zu trennen. Mit $k=2$ werden die beiden sichtbaren Cluster (von denen einer zwei Arten enthält) entdeckt, während bei $k=3$ einer der beiden Cluster in zwei gerade Teile aufgeteilt wird. In der Tat $k=2$ ist für diesen Datensatz besser geeignet, obwohl der Datensatz 3 Klassen enthält. Wie bei jedem anderen Clustering-Algorithmus setzt auch das k-means-Ergebnis voraus, dass die Daten bestimmte Kriterien erfüllen. Bei einigen Datensätzen funktioniert er gut, bei anderen nicht. ⓘ

Das Ergebnis von k-means kann als Voronoi-Zellen der Clustermittelwerte betrachtet werden. Da die Daten auf halber Strecke zwischen den Clustermitteln aufgeteilt werden, kann dies zu suboptimalen Aufteilungen führen, wie im Beispiel "Maus" zu sehen ist. Die vom Algorithmus der Erwartungsmaximierung (wohl eine Verallgemeinerung von k-means) verwendeten Gauß-Modelle sind flexibler, da sie sowohl Varianzen als auch Kovarianzen haben. Das EM-Ergebnis ist daher in der Lage, Cluster unterschiedlicher Größe viel besser zu berücksichtigen als k-means und auch korrelierte Cluster (nicht in diesem Beispiel). Im Gegensatz dazu erfordert EM die Optimierung einer größeren Anzahl von freien Parametern und wirft einige methodische Probleme aufgrund von verschwindenden Clustern oder schlecht konditionierten Kovarianzmatrizen auf. K-means ist eng mit der nichtparametrischen Bayes'schen Modellierung verwandt. ⓘ

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 $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 $k$ monoton sinkt. Eine Lösung ist der Silhouettenkoeffizient, der eine von $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. ⓘ

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). ⓘ

Anwendungen

Das k-means-Clustering lässt sich auch auf große Datensätze relativ einfach anwenden, insbesondere wenn man Heuristiken wie den Lloyd-Algorithmus verwendet. Es wurde unter anderem in den Bereichen Marktsegmentierung, Computer Vision und Astronomie erfolgreich eingesetzt. Er wird häufig als Vorverarbeitungsschritt für andere Algorithmen verwendet, beispielsweise um eine Startkonfiguration zu finden. ⓘ

Vektorquantisierung

Zwei-Kanal-Farbbild (zur Veranschaulichung - nur rote und grüne Kanäle). ⓘ

Vektorquantisierung der im obigen Bild vorhandenen Farben in Voronoi-Zellen unter Verwendung von k-means. ⓘ

k-means stammt aus der Signalverarbeitung und findet in diesem Bereich immer noch Verwendung. In der Computergrafik beispielsweise besteht die Aufgabe der Farbquantisierung darin, die Farbpalette eines Bildes auf eine feste Anzahl von Farben k zu reduzieren. Der k-means-Algorithmus kann für diese Aufgabe leicht verwendet werden und liefert konkurrenzfähige Ergebnisse. Ein Anwendungsfall für diesen Ansatz ist die Segmentierung von Bildern. Weitere Einsatzgebiete der Vektorquantisierung sind nicht-zufällige Stichproben, da k-means leicht dazu verwendet werden kann, k verschiedene, aber prototypische Objekte aus einem großen Datensatz für die weitere Analyse auszuwählen. ⓘ

Cluster-Analyse

Bei der Clusteranalyse kann der k-means-Algorithmus verwendet werden, um den Eingabedatensatz in k Partitionen (Cluster) zu unterteilen. ⓘ

Der reine k-means-Algorithmus ist jedoch nicht sehr flexibel und als solcher nur bedingt geeignet (es sei denn, die oben beschriebene Vektorquantisierung ist tatsächlich der gewünschte Anwendungsfall). Insbesondere ist der Parameter k bekanntermaßen schwer zu wählen (wie oben erläutert), wenn er nicht durch externe Zwänge vorgegeben ist. Eine weitere Einschränkung besteht darin, dass der Algorithmus nicht mit beliebigen Abstandsfunktionen oder auf nicht-numerischen Daten verwendet werden kann. Für diese Anwendungsfälle sind viele andere Algorithmen besser geeignet. ⓘ

Lernen von Merkmalen

Das k-means-Clustering wurde als Schritt des Merkmalslernens (oder Wörterbuchlernens) sowohl beim (halb-)überwachten Lernen als auch beim unüberwachten Lernen verwendet. Der grundlegende Ansatz besteht darin, zunächst eine k-means-Clustering-Darstellung zu trainieren, wobei die eingegebenen Trainingsdaten (die nicht gekennzeichnet sein müssen) verwendet werden. Zur Projektion beliebiger Eingabedaten in den neuen Merkmalsraum berechnet dann eine "Kodierungsfunktion", z. B. das Schwellenwert-Matrixprodukt der Daten mit den Zentroidpositionen, den Abstand zwischen den Daten und jedem Zentroid oder einfach eine Indikatorfunktion für den nächstgelegenen Zentroid bzw. eine glatte Transformation des Abstands. Alternativ kann der Proben-Cluster-Abstand durch ein Gaußsches RBF transformiert werden, um die versteckte Schicht eines Radialbasisfunktionsnetzes zu erhalten. ⓘ

Diese Verwendung von k-means wurde erfolgreich mit einfachen, linearen Klassifikatoren für halbüberwachtes Lernen in NLP (insbesondere für die Erkennung von benannten Entitäten) und in der Computer Vision kombiniert. Bei einer Aufgabe zur Objekterkennung wurde festgestellt, dass es eine vergleichbare Leistung wie anspruchsvollere Ansätze zum Lernen von Merkmalen wie Autocoder und beschränkte Boltzmann-Maschinen aufweist. Für eine gleichwertige Leistung sind jedoch im Allgemeinen mehr Daten erforderlich, da jeder Datenpunkt nur zu einem "Merkmal" beiträgt. ⓘ

Beziehung zu anderen Algorithmen

Gaußsches Mischmodell

Der langsame "Standardalgorithmus" für k-means-Clustering und der damit verbundene Erwartungsmaximierungsalgorithmus ist ein Spezialfall eines Gaußschen Mischungsmodells, nämlich der Grenzfall, bei dem alle Kovarianzen diagonal und gleich sind und eine infinitesimal kleine Varianz haben. Anstelle von kleinen Varianzen kann auch eine harte Clusterzuweisung verwendet werden, um eine weitere Äquivalenz von k-means clustering zu einem Spezialfall der "harten" Gaußschen Mischungsmodellierung zu zeigen. Dies bedeutet nicht, dass es effizient ist, die Gaußsche Mischungsmodellierung zur Berechnung von k-means zu verwenden, sondern nur, dass es einen theoretischen Zusammenhang gibt und dass die Gaußsche Mischungsmodellierung als Verallgemeinerung von k-means interpretiert werden kann; im Gegenteil, es wurde vorgeschlagen, die k-means-Clusteringmethode zu verwenden, um Ausgangspunkte für die Gaußsche Mischungsmodellierung bei schwierigen Daten zu finden. ⓘ

K-SVD

Eine weitere Verallgemeinerung des k-means-Algorithmus ist der K-SVD-Algorithmus, der Datenpunkte als spärliche lineare Kombination von "Codebuch-Vektoren" schätzt. k-means entspricht dem Spezialfall der Verwendung eines einzigen Codebuch-Vektors mit einem Gewicht von 1. ⓘ

Hauptkomponentenanalyse

Die entspannte Lösung von k-means-Clustering, die durch die Clusterindikatoren spezifiziert wird, wird durch die Hauptkomponentenanalyse (PCA) gegeben. Die Intuition ist, dass k-means sphärisch geformte (kugelartige) Cluster beschreibt. Wenn die Daten 2 Cluster haben, ist die Linie, die die beiden Zentren verbindet, die beste eindimensionale Projektionsrichtung, die auch die erste PCA-Richtung ist. Das Schneiden der Linie im Massenschwerpunkt trennt die Cluster (dies ist die kontinuierliche Entspannung des diskreten Clusterindikators). Wenn die Daten drei Cluster haben, ist die 2-dimensionale Ebene, die von den drei Clusterschwerpunkten aufgespannt wird, die beste 2-D-Projektion. Diese Ebene wird auch durch die ersten beiden PCA-Dimensionen definiert. Gut voneinander getrennte Cluster werden effektiv durch kugelförmige Cluster modelliert und somit durch k-means entdeckt. Nicht kugelförmige Cluster sind schwer zu trennen, wenn sie nahe beieinander liegen. Beispielsweise lassen sich zwei halbmondförmige Cluster, die im Raum miteinander verflochten sind, nicht gut trennen, wenn sie auf den PCA-Unterraum projiziert werden. k-means sollte bei diesen Daten nicht gut funktionieren. Es ist einfach, Gegenbeispiele für die Aussage zu finden, dass der Unterraum des Clusterschwerpunkts durch die Hauptrichtungen aufgespannt wird. ⓘ

Mean-Shift-Clustering

Grundlegende Mean-Shift-Clustering-Algorithmen behalten einen Satz von Datenpunkten bei, der genauso groß ist wie der Eingabedatensatz. Zu Beginn wird dieser Satz aus dem Eingabedatensatz kopiert. Dann wird diese Menge iterativ durch den Mittelwert derjenigen Punkte in der Menge ersetzt, die innerhalb eines bestimmten Abstands zu diesem Punkt liegen. Im Gegensatz dazu beschränkt k-means diese aktualisierte Menge auf k Punkte, die in der Regel viel kleiner sind als die Anzahl der Punkte im Eingabedatensatz, und ersetzt jeden Punkt in dieser Menge durch den Mittelwert aller Punkte im Eingabedatensatz, die näher an diesem Punkt liegen als alle anderen (z. B. innerhalb der Voronoi-Partition jedes Aktualisierungspunkts). Ein Mittelwertverschiebungsalgorithmus, der dem k-means-Verfahren ähnelt und als Likelihood-Mittelwertverschiebung bezeichnet wird, ersetzt die Menge der zu ersetzenden Punkte durch den Mittelwert aller Punkte in der Eingabemenge, die innerhalb eines bestimmten Abstands von der sich ändernden Menge liegen. Einer der Vorteile von Mean-Shift gegenüber k-means ist, dass die Anzahl der Cluster nicht vorgegeben ist, da Mean-Shift wahrscheinlich nur wenige Cluster findet, wenn nur eine kleine Anzahl vorhanden ist. Mean Shift kann jedoch sehr viel langsamer sein als k-means und erfordert immer noch die Auswahl eines Bandbreitenparameters. Mean Shift hat weiche Varianten. ⓘ

Unabhängige Komponentenanalyse

Unter der Annahme der Sparsamkeit und wenn die Eingabedaten mit der Whitening-Transformation vorverarbeitet sind, liefert k-means die Lösung für die Aufgabe der linearen unabhängigen Komponentenanalyse (ICA). Dies hilft bei der Erklärung der erfolgreichen Anwendung von k-means beim Lernen von Merkmalen. ⓘ

Bilaterale Filterung

k-means geht implizit davon aus, dass die Reihenfolge des Eingabedatensatzes keine Rolle spielt. Der bilaterale Filter ähnelt k-means und der Mittelwertverschiebung insofern, als er einen Satz von Datenpunkten beibehält, die iterativ durch Mittelwerte ersetzt werden. Allerdings beschränkt der bilaterale Filter die Berechnung des (kernelgewichteten) Mittelwerts auf Punkte, die in der Reihenfolge der Eingabedaten nahe beieinander liegen. Dadurch eignet er sich für Probleme wie die Entrauschung von Bildern, bei denen die räumliche Anordnung der Pixel in einem Bild von entscheidender Bedeutung ist. ⓘ

Software-Implementierungen

Verschiedene Implementierungen des Algorithmus weisen Leistungsunterschiede auf, wobei die schnellste bei einem Testdatensatz in 10 Sekunden fertig ist und die langsamste 25.988 Sekunden (~7 Stunden) benötigt. Die Unterschiede lassen sich auf die Qualität der Implementierung, Unterschiede in Sprache und Compiler, unterschiedliche Abbruchkriterien und Genauigkeitsstufen sowie die Verwendung von Indizes zur Beschleunigung zurückführen. ⓘ

Freie Software/Open Source

Die folgenden Implementierungen sind unter Free/Open-Source-Software-Lizenzen und mit öffentlich zugänglichem Quellcode verfügbar. ⓘ

Accord.NET enthält C#-Implementierungen für k-means, k-means++ und k-modes.
ALGLIB enthält parallelisierte C++- und C#-Implementierungen für k-means und k-means++.
AOSP enthält eine Java-Implementierung für k-means.
CrimeStat implementiert zwei räumliche k-means-Algorithmen, von denen einer es dem Benutzer erlaubt, die Startorte zu definieren.
ELKI enthält k-means (mit Lloyd- und MacQueen-Iteration sowie verschiedenen Initialisierungen wie k-means++) und verschiedene erweiterte Clustering-Algorithmen.
Smile enthält k-means und verschiedene andere Algorithmen und Ergebnisvisualisierung (für Java, Kotlin und Scala).
Julia enthält eine k-means-Implementierung im JuliaStats Clustering-Paket.
KNIME enthält Knoten für k-means und k-medoids.
Mahout enthält ein MapReduce-basiertes k-means.
mlpack enthält eine C++-Implementierung von k-means.
Octave enthält k-means.
OpenCV enthält eine k-means-Implementierung.
Orange enthält eine Komponente für k-means Clustering mit automatischer Auswahl von k und Cluster Silhouette Scoring.
PSPP enthält k-means. Der Befehl QUICK CLUSTER führt ein k-means-Clustering für den Datensatz durch.
R enthält drei k-means-Varianten.
SciPy und scikit-learn enthalten mehrere k-means-Implementierungen.
Spark MLlib implementiert einen verteilten k-means-Algorithmus.
Torch enthält ein unsup-Paket, das k-means-Clustering bietet.
Weka enthält k-means und x-means. ⓘ

Proprietär

Die folgenden Implementierungen sind unter proprietären Lizenzbedingungen verfügbar und verfügen möglicherweise nicht über öffentlich zugänglichen Quellcode. ⓘ

Ayasdi
Mathematica
MATLAB
OriginPro
RapidMiner
SAP HANA
SAS
SPSS
Stata ⓘ

Problemstellung

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

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

mit den Datenpunkten $\mathbf {x} _{j}$ und den Schwerpunkten ${\boldsymbol {\mu }}_{i}$ der Cluster $S_{i}$ . Diese Zielfunktion basiert auf der Methode der kleinsten Quadrate und man spricht auch von Clustering durch Varianzminimierung, da die Summe der Varianzen der Cluster minimiert wird. Da zudem $\|\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. ⓘ

Erweiterungen

K-Median

Im k-Median-Algorithmus wird im Zuweisungschritt statt der euklidischen Distanz die Manhattan-Distanz verwendet. Im Updateschritt wird der Median statt des Mittelwerts verwendet. ⓘ

Beispiel

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.

Anwendung in der Bildverarbeitung

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 und itk implementiert. ⓘ