Mit Google fortfahren
k-Means-Algorithmus: Ablauf, Beispiel und Grenzen
Der k-Means-Algorithmus teilt ungelabelte, numerische Daten in genau $k$ Gruppen ein. Dabei ordnet er jeden Datenpunkt dem nächsten Clusterzentrum zu und verschiebt jedes Zentrum anschließend zum Mittelwert seiner Gruppe. Zuordnung und Aktualisierung wiederholen sich, bis sich die Einteilung nicht mehr ändert.
Hake ab, was du schon kannst — und komm am Ende hierher zurück!
Welche Aufgabe löst k-Means?
Beim Clustering suchst du Gruppen ähnlicher Datenpunkte, ohne dass richtige Gruppennamen vorgegeben sind. Ein solcher Datenpunkt kann zum Beispiel durch zwei numerische Merkmale als Koordinate $(x|y)$ beschrieben werden.
Cluster und Zentroid
Ein Cluster ist eine Gruppe ähnlicher Datenpunkte. Sein Zentroid oder Clusterzentrum ist der Mittelwert aller Punkte dieser Gruppe. Das Zentroid muss daher kein tatsächlich vorhandener Datenpunkt sein.
Das $k$ im Namen ist die vorher festgelegte Anzahl der Cluster. k-Means ist ein hartes Clustering-Verfahren: Jeder Punkt gehört in einem Durchlauf genau einem Cluster an.
Wie läuft der Algorithmus ab?
Der meist gemeinte Standardablauf ist der Lloyd-Algorithmus:
- Initialisieren: Wähle $k$ Datenpunkte als anfängliche Zentren.
- Zuordnen: Berechne für jeden Punkt den Abstand zu allen Zentren und ordne ihn dem nächsten zu.
- Aktualisieren: Berechne für jeden Cluster den Mittelwert jeder Koordinate. Dieser Mittelwert wird das neue Zentrum.
- Prüfen: Haben sich Zuordnungen oder Zentren geändert, beginne erneut bei Schritt 2. Sind sie stabil, endet der Lauf.
Für zwei Punkte $(x_1|y_1)$ und $(x_2|y_2)$ ist die euklidische Distanz
$$d=\sqrt{(x_1-x_2)^2+(y_1-y_2)^2}.$$
Zum Vergleichen genügt auch die quadrierte Distanz $d^2$, weil die Quadratwurzel die Reihenfolge der Abstände nicht verändert.
Zuordnen verändert die Gruppen. Aktualisieren verändert die Zentren. Erst das Wiederholen beider Schritte macht daraus k-Means.
Wähle in jeder Lücke die passende Form und prüfe anschließend deine Antworten.
Nach der Initialisierung werden Punkte dem jeweils Zentrum zugeordnet. Danach wird jedes Zentrum als seiner Gruppe neu berechnet. Der Lauf endet, wenn die Einteilung bleibt.
Wie entsteht eine Lösung Schritt für Schritt?
Wir verfolgen acht Punkte mit $k=2$:
| Punkt | Koordinate | |
|---|---|---|
| A | $(0 | 0)$ |
| B | $(2 | 4)$ |
| C | $(5 | 1)$ |
| D | $(8 | 1)$ |
| E | $(5 | 7)$ |
| F | $(6 | 5)$ |
| G | $(9 | 8)$ |
| H | $(12 | 2)$ |
Als Anfangszentren dienen $C=(5|1)$ und $F=(6|5)$.
Für $A=(0|0)$ und das erste Zentrum $(5|1)$ gilt:
$$d^2=(0-5)^2+(0-1)^2=26.$$
Also ist $d=\sqrt{26}\approx 5{,}1$. Zum zweiten Zentrum beträgt der Abstand etwa $7{,}8$. Deshalb gehört A zunächst zum ersten Cluster.
Nach demselben Vergleich für alle Punkte lautet die erste Einteilung:
- Cluster 1: A, C, D
- Cluster 2: B, E, F, G, H
Nun werden die Koordinaten getrennt gemittelt:
$$Z_1=\left(\frac{0+5+8}{3}\middle|\frac{0+1+1}{3}\right)=\left(\frac{13}{3}\middle|\frac{2}{3}\right)\approx(4{,}3|0{,}7)$$
$$Z_2=\left(\frac{2+5+6+9+12}{5}\middle|\frac{4+7+5+8+2}{5}\right)=(6{,}8|5{,}2)$$
Mit diesen neuen Zentren wird erneut zugeordnet. Jetzt wechselt B in Cluster 1. Die zweite Einteilung ist:
- Cluster 1: A, B, C, D mit $Z_1=(3{,}75|1{,}5)\approx(3{,}8|1{,}5)$
- Cluster 2: E, F, G, H mit $Z_2=(8|5{,}5)$
Ein dritter Zuordnungsschritt lässt diese Gruppen unverändert. Auch die Mittelwerte bleiben gleich: Der Algorithmus endet.
Entscheidend ist nicht die Farbe oder der Name eines Clusters, sondern der Wechsel von B: Verschobene Zentren können eine neue Zuordnung auslösen.
Was optimiert k-Means?
k-Means versucht, die Punkte innerhalb jedes Clusters möglichst kompakt um ihr Zentrum zu sammeln. Für Cluster $S_1,\dots,S_k$, Punkte $\mathbf{x}_j$ und Zentren $\boldsymbol{\mu}_i$ lautet die Zielfunktion:
$$J=\sum_{i=1}^{k}\sum_{\mathbf{x}_j\in S_i}\left\|\mathbf{x}_j-\boldsymbol{\mu}_i\right\|^2.$$
$J$ ist die Summe der quadrierten Punkt-Zentrum-Abstände, auch SSE oder Trägheit genannt. Beim Zuordnen wählt jeder Punkt den kleinsten Beitrag. Bei festem Cluster minimiert der arithmetische Mittelwert diese Summe. Deshalb passen Zuordnungs- und Aktualisierungsschritt genau zum Ziel.
Der Algorithmus findet nicht garantiert die weltweit beste Einteilung. Er verbessert die gewählte Startlösung schrittweise und kann in einem lokalen Optimum enden.
Wie wählst du Startzentren und k?
Schlechte Anfangszentren können zu einer ungünstigen Lösung oder zu mehr Iterationen führen. Deshalb sind mehrere Läufe mit verschiedenen Starts sinnvoll. k-Means++ verteilt die Startzentren gezielter: Punkte weit weg von bereits gewählten Zentren erhalten eine größere Auswahlwahrscheinlichkeit.
Die Clusterzahl $k$ bestimmt die Feinheit der Einteilung. Größeres $k$ senkt die Summe der quadrierten Abstände immer weiter; im Extremfall kann jeder Punkt sein eigenes Cluster bilden. Der kleinste Wert von $J$ allein liefert daher keine sinnvolle Wahl.
Bei der Ellenbogen-Methode vergleichst du mehrere Werte von $k$:
- Führe k-Means für verschiedene Clusterzahlen aus.
- Trage $k$ gegen die jeweilige Summe innerhalb der Cluster auf.
- Suche den Bereich, ab dem zusätzliche Cluster die Summe nur noch wenig verringern.
Dieser Knick ist eine Entscheidungshilfe, kein automatisch eindeutiger Beweis für das beste $k$.
Wann passt k-Means – und wann nicht?
k-Means passt besonders zu numerischen Daten, deren Gruppen kompakt, ungefähr ähnlich groß und hinreichend getrennt sind. Typische Anwendungen sind Kunden- oder Dokumentgruppen sowie die Segmentierung und Komprimierung von Bildern.
Achte auf diese Grenzen:
- Nur sinnvolle Mittelwerte: Reine Kategorien wie „Auto“, „LKW“ und „Fahrrad“ lassen sich nicht unmittelbar mitteln.
- Ausreißer: Extreme Werte ziehen den Mittelwert und damit das Zentroid in ihre Richtung.
- Form der Gruppen: Die Zuordnung zum nächsten Zentrum bevorzugt kompakte, konvexe Cluster. Stark gebogene oder verschachtelte Gruppen passen schlecht.
- Überlappung und ungleiche Größen: Nahtlos übergehende oder sehr verschieden große Gruppen können falsch getrennt werden.
- Keine Ausreißerkategorie: Jeder Punkt wird einem Cluster zugeordnet.
- Startabhängigkeit: Ein stabiler Endzustand ist nicht automatisch die global beste Lösung.
Karteikasten
Überlege zuerst selbst und drehe die Karte anschließend zum Prüfen um.
Alles auf einen Blick
- k-Means
- Eingabe: numerische Daten und Clusterzahl $k$
- Start: $k$ Zentren wählen
- Schleife: zuordnen, mitteln, prüfen
- Ziel: quadrierte Abstände innerhalb der Cluster verkleinern
- Auswahl: mehrere Starts und geeignete Clusterzahl vergleichen
- Grenzen: Ausreißer, Überlappung, unregelmäßige oder ungleiche Gruppen