k-Means-Clustering: Der Startpunkt bestimmt das Ergebnis

k-Means ist der erste Clustering-Algorithmus, den man lernt. Eine seiner Eigenschaften bleibt dabei meist unerwähnt: Das Ergebnis variiert je nach Startpunkt. Dreh den Regler unten. Schau dir an, wie exakt dieselben Punkte bei gleicher Clusteranzahl plötzlich völlig anders aufgeteilt werden.

Rechenbeispiel — k-Means-Clustering: Der Startpunkt bestimmt das Ergebnis

Intra-Cluster-Quadratsumme	1,0989
Iterationen bis zur Konvergenz	2
Spanne der Ergebnisse	430,8%
Verschiedene gefundene Ergebnisse	3 von 24
Dieser Start ist also	der beste gefundene

Das sind die Werte, die der Rechner beim Öffnen der Seite anzeigt. Ändere oben eine Eingabe, um sie neu zu berechnen.

Interaktive Simulation wird geladen...

Lektion

Die Theorie — k-Means-Clustering: Der Startpunkt bestimmt das Ergebnis

k-Means sucht nach k Gruppen. Dafür wiederholt das Verfahren zwei Schritte, bis sich nichts mehr bewegt: Ordne jeden Punkt dem nächsten Zentrum zu. Verschiebe dann jedes Zentrum auf den Mittelwert der Punkte, die es eingesammelt hat. Minimiert wird dabei die Quadratsumme innerhalb der Cluster, also die gesamte quadrierte Distanz jedes Punktes zu seinem eigenen Zentrum. Jeder der beiden Schritte kann diesen Wert nur senken – was der vollständige Beweis dafür ist, dass der Algorithmus stoppt.

Was die einzelnen Symbole bedeuten

k: wie viele Cluster du angefordert hast, was dir nichts in den Daten verrät
WCSS: die gesamte quadrierte Distanz jedes Punktes zu seinem eigenen Zentrum

Setzt voraus: Dass ein Cluster eine runde Wolke von ungefähr gleicher Größe ist, denn die quadrierte euklidische Distanz zu einem Mittelwert kann nichts anderes ausdrücken. Langgezogene, verschachtelte oder sehr ungleiche Gruppen werden von k-Means nicht etwa schlecht gefunden; sie sind schlicht nicht das, wonach das Verfahren sucht.

Jeder einzelne dieser Durchläufe ist konvergiert 🖖

Lass die drei Wolken und k = 3 unverändert und dreh den Regler für die Startposition von 1 bis 24 durch. Zweiundzwanzig der Starts landen bei 1,0989. Die Nummern 17 und 21 landen bei 5,8172 und 5,8331. Das ist 5,3-mal schlechter. Sie verschmelzen zwei der Wolken und schneiden die dritte in der Mitte durch. Bei diesen beiden Durchläufen ist absolut nichts schiefgelaufen. Der Lloyd-Algorithmus konvergiert garantiert. Die Fehlerquadratsumme sinkt mit jedem Schritt und kann nicht unendlich weiter fallen. Er muss also anhalten. In 1.536 Durchläufen über alle Punktsätze, jedes k und beide Initialisierungen hinweg hat kein einziger versagt. Was er jedoch nicht garantiert, ist, an einem sinnvollen Punkt anzuhalten. Die Aussage „der Algorithmus ist konvergiert“ ist also eher eine mathematische Feststellung als eine über deine Daten. Hättest du k-Means nur ein einziges Mal ausgeführt, wüsstest du nicht, welches dieser beiden Ergebnisse du gerade vor dir hast.

k-Means++ halbiert den Schaden und verspricht nichts 🖖

Stell die Startmethode auf k-Means++ um. Die Streuung fällt bei diesem Datensatz auf null zusammen. Alle vierundzwanzig Starts finden 1,0989. Das ist der Trick, den jeder anwendet. Er funktioniert, indem die Startzentren gleichmäßig verteilt werden, statt sie blind auf zufällige Punkte zu setzen. Diese Verbesserung ist allerdings statistischer Natur und keine Garantie. Es lohnt sich, das genaue Ausmaß zu kennen. Gemessen über 112 Kombinationen aus Punktsatz, Stichprobengröße und k fand k-Means++ in 38 Fällen ein strikt besseres Optimum als der zufällige Start. Der Zufall war in 17 Fällen besser. In 57 Fällen herrschte Gleichstand. Die durchschnittliche Streuung über vierundzwanzig Starts fiel von 55,5 % auf 31,7 %. Die Methode halbiert also in etwa das Ausmaß, um das ein unglücklicher Durchlauf danebenliegen kann. In einem von sechs Fällen hättest du mit Dartwerfen jedoch besser abgeschnitten. Stell den Ring auf 90 Punkte und k = 5 für genau so einen Fall. Der zufällige Start erreicht 0,9884, während k-Means++ bei 1,0213 stehen bleibt.

Eine stabile, ausgewogene, sichere Antwort auf eine Frage ohne Antwort 🖖

Lade die letzte Voreinstellung. Die Punkte bilden ein regelmäßiges Gitter ganz ohne Cluster. Dennoch teilt k-Means sie in vier Gruppen zu exakt 25 Punkten auf. Schau dir nun an, was jedes verfügbare Diagnosewerkzeug zu diesem Ergebnis sagt. Es ist konvergiert, und zwar in elf Iterationen. Es ist stabil: Alle vierundzwanzig Startpositionen führen zum selben Ergebnis. Ein Neustart verrät dir also nicht, dass etwas nicht stimmt. Die Cluster sind perfekt ausbalanciert. Genau so sieht ein gutes Clustering normalerweise aus. Drei unabhängige Signale weisen in dieselbe Richtung – und trotzdem ist da einfach nichts. Das ist das grundlegende Problem beim Clustering, für das es keine technische Lösung gibt. k-Means beantwortet die Frage, „Wo sollen k Zentren hin?“. Darauf hat der Algorithmus immer eine Antwort. Völlig unabhängig davon, ob die Frage „Wie viele Gruppen stecken in diesen Daten?“ überhaupt eine hat.

Aufgabe vollständig gelöst

Du weißt nicht, wie viele Cluster deine Daten enthalten, und möchtest diese Zahl am Knick der Bewertungskurve ablesen. Wende dieses Verfahren auf alle vier Punktmengen an und zähle, wie oft es funktioniert. Das untere Feld zeigt dir den besten Wert für jedes k von 1 bis 8, wobei der Rückgang gegenüber dem vorherigen k im Hintergrund dargestellt ist.

Öffne diese Aufgabe im Tool
1. Zunächst zur Frage, warum wir nach einem Knick und nicht nach einem Minimum suchen. Wähle als Punktmenge Drei Wolken und lies die Kurve ab: 10,3978 bei k = 1, dann 5,6145, 1,0989, 0,9241, 0,8052, 0,6875, 0,6077, 0,5366. Sie steigt an keiner Stelle. Das ist unmöglich, denn jede Einteilung in k Gruppen lässt sich durch Aufspalten einer Gruppe in eine mit k + 1 Gruppen verwandeln. Durch diese Aufteilung rücken die Punkte nur noch näher an ihr jeweiliges Zentrum heran. Treibst du k bis zur Gesamtzahl der Punkte, bildet jeder Punkt sein eigenes Cluster. Der Wert liegt dann bei exakt 0.
  
  $WCSS (k) = \sum_{j = 1}^{k} \sum_{x \in C_{j}} ∥ x - μ_{j} ∥^{2}, WCSS (k + 1) \leq WCSS (k) three blobs : 10.3978, 5.6145, 1.0989, 0.9241, 0.8052, 0.6875, 0.6077, 0.5366$
2. Die Kurve hat also gar kein Minimum, das man finden könnte. Deshalb müssen wir uns auf die Rückgänge konzentrieren. Bei den Wolken betragen diese 46,0 %, danach 80,4 %, gefolgt von 15,9 %, 12,9 %, 14,6 %, 11,6 % und 11,7 %. Der Rückgang nach k = 3 macht nur noch ein Fünftel des vorherigen aus, bricht also um den Faktor 5,06 ein. Genau mit k = 3 wurden diese Daten erzeugt. Das Verfahren greift hier perfekt. Dies ist das Beispiel, das in allen Lehrbüchern steht.
  
  $drop (k) = 1 - \frac{WCSS ( k + 1 )}{WCSS ( k )}, elbow = ar g max_{k} \frac{drop ( k - 1 )}{drop ( k )} three blobs : 46 . 0%, 80 . 4%, 15 . 9%, 12 . 9%, 14 . 6%, 11 . 6%, 11 . 7% \Rightarrow k = 3, \times 5.06$
3. Betrachten wir nun das Gitter, das überhaupt keine Cluster aufweist. Hier lauten die Rückgänge 41,6 %, 34,1 %, 36,8 %, 16,4 %, 16,9 %, 12,8 % und 15,7 %. Nach k = 4 verzeichnen wir einen Einbruch um den Faktor 2,25. Das ist exakt das Muster, nach dem du suchen sollst. Das Ellbogenkriterium liefert als Ergebnis „vier Cluster“ für eine Menge, die in Wahrheit gar keine besitzt.
  
  $lattice : 41 . 6%, 34 . 1%, 36 . 8%, 16 . 4%, 16 . 9%, 12 . 8%, 15 . 7% \Rightarrow k = 4, \times 2.25$
4. Als Nächstes kommt der Ring. Hier existieren tatsächlich zwei Gruppen. Seine Rückgänge lauten 37,2 %, 32,8 %, 38,5 %, 33,4 %, 43,1 %, 25,3 % und 15,3 %. Es gibt keinen eindeutigen Trend, sondern nur zwei Abstürze am Ende. Der schärfste Einbruch liegt nach k = 6. Die Methode liefert sechs, doch die richtige Antwort ist zwei.
  
  $ring : 37 . 2%, 32 . 8%, 38 . 5%, 33 . 4%, 43 . 1%, 25 . 3%, 15 . 3% \Rightarrow k = 6, \times 1.70$
5. Zuletzt Ungleichmäßig, also drei Cluster unterschiedlicher Größe: 43,8 %, 48,4 %, 35,4 %, 24,7 %, 16,1 %, 14,4 %, 21,8 %. Wir sehen einen sanften Abstieg ohne jeden Einbruch. Der stärkste Faktor beträgt gerade einmal 1,53 und bildet definitiv keinen Knick. Die Kurve verrät dir hier nichts, obwohl die Daten ganz klar drei Cluster enthalten.
  
  $uneven : 43 . 8%, 48 . 4%, 35 . 4%, 24 . 7%, 16 . 1%, 14 . 4%, 21 . 8% \Rightarrow k = 5, \times 1.53$
Antwort

Ein Treffer aus vier Versuchen. Bei den Wolken lag die Methode richtig, beim Gitter hat sie vier Cluster erfunden, für den Ring sechs vorgeschlagen, obwohl er nur zwei besitzt, und bei der ungleichmäßigen Menge komplett geschwiegen. Dieses Muster ist kein Zufall. Der Knick ist genau dann deutlich ausgeprägt, wenn die Cluster rund, ähnlich groß und gut voneinander getrennt sind. In diesem Fall hättest du sie allerdings auch einfach mit bloßem Auge zählen können. Er verschwindet bei allen Mengen, bei denen du wirklich Hilfe gebraucht hättest. Das solltest du im Hinterkopf behalten, bevor du diese Kurve benutzt, um jemandem gegenüber eine bestimmte Zahl zu rechtfertigen. Aus diesem Grund steht das Ellbogenkriterium auch nur gleichberechtigt neben dem Silhouettenkoeffizienten, der Gap-Statistik und den Informationskriterien, anstatt über ihnen. Keines dieser Verfahren ist auf dieser Seite abgebildet. Jedes von ihnen stellt auf seine eigene Weise dieselbe Frage, welche die Bewertungskurve nicht beantworten kann. Es geht nicht darum, „wo k Zentren platziert werden würden“. Darauf gibt es schließlich immer eine Antwort. Die eigentliche Frage lautet: „Gibt es hier überhaupt Gruppen?“

$set three blobs lattice ring uneven elbow says 3465 truth 3023 sharpness \times 5.06 \times 2.25 \times 1.70 \times 1.53$

Lernpfad

Eine Gerade an Daten anpassen

Quellen (3)

The algorithm itself. Written in 1957 for quantising a signal into levels, circulated as a Bell Labs memorandum, and not published for twenty-five years: S. P. Lloyd, “Least squares quantization in PCM.” IEEE Transactions on Information Theory 28(2), 129–137, 1982.
The initialisation the second insight block measures — and the source of the bound that makes it worth using, which is a guarantee about the EXPECTED score rather than about any single run: D. Arthur and S. Vassilvitskii, “k-means++: The Advantages of Careful Seeding.” In Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA ’07), 1027–1035. SIAM, 2007.
Where the elbow reading comes from, and it was proposed with more caution than it is usually repeated with: R. L. Thorndike, “Who belongs in the family?” Psychometrika 18(4), 267–276, 1953.

Vom 42Math-Team · Anhand veröffentlichter Quellen geprüft. Korrekturen willkommen.