Clusterbildung mit k-Means
k-Means ist ein konkretes Verfahren des unüberwachten Lernens. Es teilt Datenpunkte in k Gruppen (Cluster) ein, ohne vorher zu wissen, welche Gruppen es gibt. Jeder Cluster hat einen Schwerpunkt (Zentroid), und jeder Punkt wird dem nächstgelegenen Schwerpunkt zugeordnet.
Die Idee
flowchart TD
A["Wähle k Start-<br/>Schwerpunkte"] --> B["Ordne jeden Punkt dem<br/>nächsten Schwerpunkt zu"]
B --> C["Berechne neuen<br/>Schwerpunkt pro Cluster"]
C --> D{"Hat sich etwas<br/>verändert?"}
D -->|"Ja"| B
D -->|"Nein"| E["Fertig!"]
Der Algorithmus ist iterativ: er wiederholt zwei Schritte, bis sich nichts mehr verändert.
- Zuordnen: Jeder Punkt kommt zum nächstgelegenen Schwerpunkt.
- Aktualisieren: Jeder Schwerpunkt wandert in die Mitte seiner Punkte.
k-Means ist ein iteratives Verfahren der Clusterbildung. Es teilt Datenpunkte in k Cluster ein, indem es abwechselnd die Punkte zu den nächsten Schwerpunkten zuordnet und die Schwerpunkte neu berechnet, bis sich die Zuordnung nicht mehr ändert.
Der Algorithmus in Java
Wir benutzen dieselbe Datenpunkt-Klasse aus Kapitel 2, aber ohne Labels — die gibt es im unüberwachten Lernen ja nicht.
Bevor du das Programm ausführst: Schau dir die 9 Punkte im Programm unten an. Sie bilden drei sichtbare Gruppen. Welche? Notiere deine Vermutung.
Tipp
Schau dir die Koordinaten an:
- Punkte nahe (10, 20) bilden eine Gruppe
- Punkte nahe (50, 60) bilden eine Gruppe
- Punkte nahe (80, 20) bilden eine Gruppe
→ 3 Cluster mit je 3 Punkten.
a) Führe das Programm aus. Entspricht die Cluster-Zuordnung deiner Vermutung? Nach wie vielen Iterationen ist der Algorithmus stabil?
b) Ändere k auf 2. Welche zwei der drei sichtbaren Gruppen landen zusammen in einem Cluster?
c) Ändere k auf 4. Es entstehen drei Cluster mit je einem einzigen Punkt und einer mit sechs — die drei sichtbaren Gruppen werden gar nicht gefunden. Schau dir den Konstruktor an: Welche Punkte werden als Startpunkte benutzt? Erkläre damit das Ergebnis.
d) Behalte k = 4 und ändere im Konstruktor die Startpunkte so, dass sie über die Daten verteilt liegen — nimm statt pPunkte[i] die Punkte mit den Indizes 0, 3, 6 und 8. Was kommt jetzt heraus?
Tipp 1: zu c)
Der Konstruktor nimmt die ersten k Punkte als Startschwerpunkte. Schreibe die ersten vier Punkte des Feldes auf und zeichne sie ein. Wo liegen sie?
Tipp 2: zu d)
Du brauchst nur eine Zeile im Konstruktor. Lege dir ein Feld mit den gewünschten Indizes an und greife darüber zu:
int[] start = {0, 3, 6, 8};
for (int i = 0; i < k; i++) {
zentroide[i] = new Datenpunkt(
pPunkte[start[i]].gibGewicht(),
pPunkte[start[i]].gibSuessigkeit(),
""
);
}k-Means hängt von den Startpunkten ab. Bei gleichen Daten und gleichem k können verschiedene Startschwerpunkte zu verschiedenen Clustern führen. Deshalb wird k-Means in der Praxis mehrfach mit unterschiedlichen zufälligen Startpunkten laufen gelassen; genommen wird das Ergebnis mit den kompaktesten Clustern.
Das ist ein wichtiger Unterschied zu k-NN: Dort liefert dieselbe Eingabe immer dasselbe Ergebnis.
k-Means ist unüberwacht: Es gibt keine Labels, und das System findet selbst Gruppen. Es ist iterativ: es wiederholt Zuordnen und Aktualisieren bis zur Stabilität. Und es ist diskriminativ im weiteren Sinn: Es teilt Daten in Gruppen ein, erzeugt aber keine neuen Daten.
Die Iterationen Schritt für Schritt
Im Programm siehst du nur das Endergebnis. Hier kannst du dem Algorithmus bei den zwei Schritten zusehen: Zuordnen und Verschieben. Die Kreuze sind die Schwerpunkte.
a) Drücke mehrmals auf Nächster Schritt. Über der Tabelle steht jedes Mal, was als Nächstes passiert. Nach wie vielen Durchläufen meldet die Komponente, dass sich nichts mehr ändert?
b) Drücke auf Neu starten und lasse den Algorithmus mit Bis zum Ende durchlaufen. Wiederhole das fünfmal. Kommt immer dasselbe heraus?
c) Stelle k auf 2 und dann auf 4. Vergleiche mit deinen Antworten zu b) und c) von oben.
Die Komponente setzt die Startschwerpunkte zufällig auf vorhandene Datenpunkte — das Java-Programm nimmt immer die ersten k. Warum ist der Zufall in der Praxis die bessere Wahl? Der Kasten unter dieser Aufgabe gibt die Antwort.