2.5 k-Means

Der Algorithmus

📄 03_dimred.pdf, Folie 44

k-Means (auch Vektorquantisierung, vector quantization) teilt $N$ Datenpunkte in $K$ Cluster ein. Jeder Cluster wird durch sein Zentrum (mean, Mittelwert) $\boldsymbol\mu_k$ repräsentiert.

1. Initialisierung: Gegeben sind die Datenpunkte $\mathbf x_n$, $n=1\dots N$. Setze $K$ Clusterzentren auf Zufallswerte $\boldsymbol\mu_k^{(0)}$.
2. Zuweisungsschritt (assignment): Weise jeden Datenpunkt $\mathbf x_n$ dem nächstliegenden Clusterzentrum $\hat k_n$ zu:

$$\hat k_n=\arg\min_k\lVert\mathbf x_n-\boldsymbol\mu_k\rVert^2,$$

mit der Indikatorvariable $r_{kn}=1$, falls $k=\hat k_n$, sonst $r_{kn}=0$. 3. Anpassungsschritt (update): Berechne eine neue Position für jedes Clusterzentrum aus den ihm zugewiesenen Datenpunkten:

$$\boldsymbol\mu_k=\frac{\sum_n r_{kn}\mathbf x_n}{\sum_n r_{kn}}.$$

4. Wiederhole Zuweisungs- und Anpassungsschritt, bis sich die Zuweisungen nicht mehr ändern.

Lesehilfe für die Formeln:

• $r_{kn}$ ist eine $K\times N$-Tabelle aus Nullen und Einsen. In jeder Spalte (jedem Punkt) steht genau eine 1, beim zugehörigen Cluster. Das ist die harte Zuweisung.
• $\sum_n r_{kn}$ zählt die Punkte in Cluster $k$.
• $\sum_n r_{kn}\mathbf x_n$ summiert genau die Punkte in Cluster $k$.
• Der Quotient ist also schlicht der Mittelwert der Punkte im Cluster, daher der Name k-Means.
• Das Quadrat in $\lVert\cdot\rVert^2$ ändert nichts am $\arg\min$ (die Wurzel ist monoton), spart aber die Wurzelberechnung.

Fallstrick: leere Cluster

Ergänzung: Bekommt ein Zentrum im Zuweisungsschritt keinen einzigen Punkt, ist $\sum_n r_{kn}=0$ und das Update teilt durch null. Übliche Abhilfen: das Zentrum neu zufällig setzen (z.B. auf einen zufälligen Datenpunkt) oder es an seiner alten Position lassen. Deshalb initialisiert man die Zentren in der Praxis meist auf $K$ zufällig gewählte Datenpunkte statt auf beliebige Zufallswerte.

Durchgerechnetes Beispiel

Ergänzung, nicht auf den Folien. Eindimensionale Daten $1, 2, 3, 8, 9, 10$, $K=2$, ungünstige Initialisierung $\mu_1=1$, $\mu_2=2$.

Iteration 1.

Punkt	Abstand zu $\mu_1=1$	Abstand zu $\mu_2=2$	Cluster
1	0	1	1
2	1	0	2
3	2	1	2
8, 9, 10	7, 8, 9	6, 7, 8	2

Update: $\mu_1=1$, $\mu_2=\frac{2+3+8+9+10}{5}=6.4$.

Iteration 2.

Punkt	Abstand zu $\mu_1=1$	Abstand zu $\mu_2=6.4$	Cluster
1	0	5.4	1
2	1	4.4	1 (gewechselt)
3	2	3.4	1 (gewechselt)
8, 9, 10	7, 8, 9	1.6, 2.6, 3.6	2

Update: $\mu_1=\frac{1+2+3}{3}=2$, $\mu_2=\frac{8+9+10}{3}=9$.

Iteration 3. Zuweisung mit $\mu_1=2$, $\mu_2=9$: $\{1,2,3\}$ zu Cluster 1, $\{8,9,10\}$ zu Cluster 2. Nichts ändert sich, fertig.

Die Summe der quadrierten Abstände zum eigenen Zentrum (siehe unten, $J$) sinkt dabei von Iteration zu Iteration:

nach Update in Iteration	Zentren	$J$
1	$1;\ 6.4$	$0+(4.4^2+3.4^2+1.6^2+2.6^2+3.6^2)=53.2$
2	$2;\ 9$	$(1+0+1)+(1+0+1)=4$

📄 03_dimred.pdf, Folie 45 zeigt dasselbe Wechselspiel in 2D mit 40 Punkten und $K=4$: Assignment, Update, Assignment, … Die zwei Läufe (Run 1, Run 2) mit verschiedenen Startwerten enden in verschiedenen Lösungen.

Was wird bei k-Means optimiert?

📄 03_dimred.pdf, Folie 46

k-Means partitioniert die Datenpunkte so, dass die summierte Varianz innerhalb jedes Clusters minimiert wird:

$$\text{minimiere}_{\boldsymbol\mu_k}\quad\sum_{k=1}^{K}\frac{\sum_n r_{kn}(\mathbf x_n-\boldsymbol\mu_k)^2}{\sum_n r_{kn}-1}.$$

Der Bruch ist die (erwartungstreu geschätzte) Varianz der Punkte in Cluster $k$, summiert über alle Cluster.

Ergänzung zur üblichen Form der Zielfunktion: In der Literatur (z.B. Bishop) wird meist die Summe der quadrierten Abstände ohne Division durch die Clustergröße angegeben,

$$J=\sum_{k=1}^K\sum_{n=1}^N r_{kn}\lVert\mathbf x_n-\boldsymbol\mu_k\rVert^2$$

(within-cluster sum of squares, die y-Achse der Grafik auf der Folie heißt genau so). Genau $J$ ist es, was der Algorithmus schrittweise verkleinert. Beide Kriterien messen „wie kompakt sind die Cluster“, gewichten große Cluster aber unterschiedlich.

Warum konvergiert k-Means?

Ergänzung, Begründung für „konvergiert beweisbar immer“ von 📄 03_dimred.pdf, Folie 43:

• Zuweisungsschritt (Zentren fest): Jeder Punkt wechselt zum nächsten Zentrum. Sein Beitrag zu $J$ kann dadurch nur kleiner werden oder gleich bleiben.
• Anpassungsschritt (Zuweisung fest): Für einen festen Cluster wird $\sum_n r_{kn}\lVert\mathbf x_n-\boldsymbol\mu_k\rVert^2$ durch den Mittelwert minimiert. Ableitung nach $\boldsymbol\mu_k$ null setzen: $-2\sum_n r_{kn}(\mathbf x_n-\boldsymbol\mu_k)=\mathbf 0\Rightarrow\boldsymbol\mu_k=\sum_n r_{kn}\mathbf x_n/\sum_n r_{kn}$. Das ist genau die Update-Formel. Auch dieser Schritt kann $J$ also nicht vergrößern.
• $J$ ist nach unten durch 0 beschränkt, und es gibt nur endlich viele Zuordnungen von $N$ Punkten zu $K$ Clustern (höchstens $K^N$). Da $J$ nie steigt, kann keine Zuordnung zweimal mit echt verschiedenem $J$ auftreten, der Algorithmus kommt also nach endlich vielen Schritten zum Stillstand.

Das ist ein Spezialfall eines Wechselverfahrens (alternating optimization): Man optimiert abwechselnd nach einem Teil der Variablen, während der andere festgehalten wird. (Ergänzung: Der EM-Algorithmus für Gaußsche Mischmodelle funktioniert nach demselben Muster, mit weichen statt harten Zuweisungen.)

Lokale Minima

Leider kann der Algorithmus in lokalen Minima hängen bleiben. Ein Auffinden des globalen Minimums ist nicht garantiert, das globale Problem ist NP-hart.

Ergänzung, ein kleines Beispiel: Vier Punkte an den Ecken eines flachen Rechtecks, $(0,0)$, $(0,1)$, $(4,0)$, $(4,1)$, und $K=2$.

• Gute Lösung: linke Seite $\{(0,0),(0,1)\}$, rechte Seite $\{(4,0),(4,1)\}$, Zentren $(0,0.5)$ und $(4,0.5)$, $J=4\cdot0.5^2=1$.
• Start mit $\mu_1=(2,0)$, $\mu_2=(2,1)$: Die unteren beiden Punkte liegen näher an $\mu_1$, die oberen näher an $\mu_2$. Die Updates ergeben wieder $(2,0)$ und $(2,1)$. Der Algorithmus ist sofort fertig, mit $J=4\cdot2^2=16$.

Die zweite Lösung ist ein stabiler Fixpunkt, aber 16-mal schlechter. Abhilfe in der Praxis: k-Means mehrmals mit verschiedenen Zufallsstarts laufen lassen und das Ergebnis mit dem kleinsten $J$ nehmen (scikit-learn macht das mit n_init). Bessere Startwerte liefert z.B. k-means++ (Zentren werden weit auseinander gewählt).

Wahl der Anzahl der Cluster $K$

Das Kriterium lässt sich dazu verwenden, die Anzahl der Cluster $K$ festzulegen (Ellenbogen-Methode, elbow method):

1. Algorithmus für unterschiedliche $K$ durchlaufen lassen.
2. Summierte Varianz innerhalb jedes Clusters gegen $K$ auftragen.
3. $K$ nach dem letzten großen Abfall auswählen.

In der Grafik der Folie fällt die Kurve von $K=1$ bis $K=3$ stark und danach kaum noch. Also wählt man $K=3$.

Fallstrick

Man darf nicht einfach das $K$ mit der kleinsten Varianz nehmen. Die Varianz innerhalb der Cluster sinkt mit wachsendem $K$ immer weiter, bei $K=N$ (jeder Punkt sein eigener Cluster) ist sie 0. Gesucht ist der Punkt, ab dem zusätzliche Cluster kaum noch etwas bringen.

Problematische Fälle

📄 03_dimred.pdf, Folie 47

Die Folie (aus MacKay) zeigt zwei typische Fehlschläge:

• Oben: Cluster unterschiedlicher Größe/Streuung. Ein großer, breit gestreuter Cluster links und ein kleiner, dichter rechts. k-Means mit $K=2$ teilt den großen Cluster und schlägt einige seiner Randpunkte dem kleinen Cluster zu. Grund: k-Means zieht die Grenze genau in der Mitte zwischen den Zentren (Mittelsenkrechte), unabhängig davon, wie weit die Cluster streuen.
• Unten: langgestreckte Cluster. Zwei parallele, senkrecht langgezogene Cluster. k-Means schneidet sie quer durch, weil es implizit runde (isotrope) Cluster annimmt: Die Distanz ist in allen Richtungen gleich gewichtet.

Ergänzung: Die Clustergrenzen von k-Means sind immer linear (die Zellen sind die Voronoi-Zellen der Zentren). Abhilfe bei länglichen Clustern: Daten vorher geeignet skalieren, oder ein Gaußsches Mischmodell verwenden, das pro Cluster eine eigene Kovarianzmatrix lernt.

Reale Daten: Iris-Datensatz

📄 03_dimred.pdf, Folie 48

Der Iris-Datensatz (150 Blüten, 3 Arten, 4 Merkmale) links mit k-Means ($K=3$) geclustert, rechts mit den wahren Arten eingefärbt. Iris setosa wird sauber als eigener Cluster gefunden. Versicolor und virginica überlappen, und k-Means zieht die Grenze zwischen ihnen anders als die tatsächliche Artgrenze. Die Clusterung ist also nur teilweise mit den echten Klassen deckungsgleich. Das ist bei unüberwachten Verfahren normal: k-Means kennt die Arten nicht und optimiert nur Kompaktheit.

Probleme von k-Means

📄 03_dimred.pdf, Folie 49

Ad-hoc-Festlegungen (auf der Folie „Ad-hoc-Merkmale“):

• Die Anzahl der Cluster wird von vornherein festgelegt.
• Wie soll man sich entscheiden, wenn mehrere Clusterungen möglich sind (vgl. 📄 03_dimred.pdf, Folie 40)?
• Ist der Mittelwert wirklich ein guter Repräsentant für einen Cluster? (Er ist z.B. empfindlich gegenüber Ausreißern und muss selbst kein sinnvoller Datenpunkt sein.)
• Gibt es bessere Distanzfunktionen als die euklidische?

Algorithmische Probleme:

• Nur die Distanz zählt, die Größe des Clusters wird nicht berücksichtigt (siehe oben, kleiner dichter Cluster „stiehlt“ Punkte).
• Keine Repräsentation der Form eines Clusters (nur ein Zentrum, keine Kovarianz).
• Harte Zuweisung: Jeder Datenpunkt trägt nur zu einem Cluster bei, und jeder Punkt hat innerhalb seines Clusters das gleiche Gewicht. Ein Punkt genau auf der Grenze zählt voll für eine Seite.

Ergänzung: Fast alle diese Punkte adressiert das Gaußsche Mischmodell (Gaussian Mixture Model, mit EM-Algorithmus trainiert): eigene Kovarianzmatrix pro Cluster (Form), Mischungsgewichte (Größe) und weiche Zuweisungen (Wahrscheinlichkeiten statt 0/1). k-Means ist der Grenzfall eines solchen Modells mit gleichen, isotropen Kovarianzen und harten Zuweisungen.

In scikit-learn

Ergänzung.

import numpy as np
from sklearn.cluster import KMeans

X = np.array([[1], [2], [3], [8], [9], [10]], float)
km = KMeans(n_clusters=2, n_init=10, random_state=0).fit(X)
print(km.cluster_centers_.ravel())   # [2. 9.] (Reihenfolge kann variieren)
print(km.labels_)                    # Clusterindex pro Punkt
print(km.inertia_)                   # J = 4.0, Grundlage für die Ellenbogen-Methode