Inhaltsverzeichnis
Der k-Means-Algorithmus
Einführung: Unüberwachtes Lernen
30 Bürger/-innen, die in der Stadt Großschwabhausen arbeiten, wurden darüber befragt, wie weit ihre Arbeitsstätte von ihrem Wohnort entfernt ist und wie oft sie für diese Strecke das eigene Fahrzeug bzw. öffentliche Verkehrsmitteln (ÖPNV) nutzen. Die Antworten sind im Graph rechts dargestellt (je Person ein Datenpunkt).
- a) Beschreiben Sie, in welche Gruppen (Bezeichnung, zugehörige Datenpunkte) man die Personen einteilen könnte.
- b) Diskutieren Sie, wie man das Wissen über diese Gruppen nutzen könnte.
Die Aufgabe, mit der wir uns im folgenden befassen, besteht allgemein darin,
- die Punkte sinnvoll zu Clustern zu gruppieren und
- eine Zuordnungsvorschrift zu finden, mit der man ausgehend von den Koordinaten eines neuen Punktes den Cluster ermitteln kann, dem er zugeordnet wird.
Da es keine gelabelten Trainingsdaten gibt, spricht man von unüberwachtem Lernen (unsupervised learning).
Oft bestehen die Daten aus vielen tausend Datenpunkten im n-dimensionalen Raum mit n > 3, sodass es kaum möglich ist, die Cluster "von Hand" zu ermitteln. Ein Algorithmus, der diese Aufgabe aber meist gut erledigen kann, ist der k-Means-Algorithmus.
Der k-Means-Algorithmus
Der k-Means-Algorithmus bekommt als Eingabe eine Menge ungelabelter Datenpunkte.
1. Parameter k (Anzahl der Cluster) festlegen
Die Anzahl $k$ der Cluster, die der Algorithmus bilden soll, muss vor Beginn des Algorithmus festgelegt werden. In unserem Beispiel entscheiden wir uns für $k = 3$.
Wie man die Anzahl der Cluster automatisiert festlegen kann, erfahren Sie etwas später in diesem Skript.
2. Clusterzentren (zunächst) zufällig festlegen
Die Clusterzentren werden zunächst zufällig festgelegt. Im Beispiel fallen sie auf Orte, an denen bereits Datenpunkte liegen. Das ist aber für das Funktionieren des Algorithmus nicht notwendig.
3. Datenpunkte den Clusterzentren zuordnen
Jeder Datenpunkt wird dem Cluster zugeordnet, zu dem er den kleinsten Abstand hat. In der rechten Abbildung ist die Zuordnung der Datenpunkte zu den Clusterzentren zu sehen.
Wir berechnen den Abstand zweier Punkte $A = (x_a, y_a)$ und $B = (x_b, y_b)$ mit der Ihnen bekannten euklidischen Metrik:
$$d(A, B) = \sqrt{((x_a - x_b)^2 + (y_a - y_b)^2)}$$
Es gibt auch andere Möglichkeiten, den Abstand zweier Punkte im ${\rm I\!R}^n$ zu definieren, i.d.R. kommt bei k-Means aber die euklidische Metrik zum Einsatz.
In der linken Abbildung sieht man gut die Raumbereiche, die den jeweiligen Clusterzentren zugeordnet sind. Überlegen Sie kurz:
- Wie bestimmt man die Geraden, die die Raumbereiche trennen?
- Wie sehen die Raumbereiche aus, wenn es sich um Punktmengen im dreidimensionalen Raum handelt?
4. Neue Lage der Clusterzentren berechnen
Jedes Clusterzentrum wird jetzt in den Schwerpunkt der ihm zugeordneten Datenpunkte verschoben. Dieser hat als Koordinaten $(x_{Zentrum},y_{Zentrum})$ den Mittelwert der Koordinaten der Datenpunkte $(x_i, y_i)$, also
$$x_{Zentrum} = \frac{1}{n} \sum_{i = 0}^{n} x_i$$
$$y_{Zentrum} = \frac{1}{n} \sum_{i = 0}^{n} y_i$$
Wiederholen bis Clusterzuordnung stabil
Man wiederholt jetzt die Schritte 3 und 4 solange, bis sich die Zuordnung der Datenpunkt zu den Clusterzentren nicht mehr ändert. In den folgenden Bildern sehen Sie die nächsten Schritte:
| Schritt | Bild |
|---|---|
| Clusterzuordnung |  |
| Clusterzentren neu berechnen |  |
| Clusterzuordnung |  |
| Clusterzentren neu berechnen |  |
| Clusterzuordnung | Keine Veränderung zur vorherigen Zuordnung ⇒ fertig! |
Online-Verfahren zum Ausprobieren
Auf dieser Seite können Sie den k-Means-Algorithmus selbst ausprobieren.
Auch die obigen Screenshots stammen von dieser Seite.
An die Arbeit: Wir implementieren den k-Means-Algorithmus in Java!
Aufgabe 1
Bearbeiten Sie Buch S. 160/2
Manhattan-Metrik
Eine Alternative zur euklidischen Metrik ist die Manhattan-Metrik (auch "Manhattan-Distanz"), benannt nach dem Straßennetz von Manhattan.
Die Manhattan-Distanz zweier Punkte $A = (a_x, a_y)$ und $B = (b_x, b_y)$ ist definiert als
$$|a_x - b_x| + |a_y - b_y|$$
Notwendigkeit zur Normierung der Koordinaten
Im Beispiel oben sind beide Koordinaten (Pendelstrecke in km und ÖPNV-Anteil in %) ungefähr im Bereich von 1 bis 100 verteilt. Stellen Sie sich vor, eine der Koordinaten nähme nur Werte von 1 - 10 an, die andere Werte von 1 bis 100. Dann würde erstere in die Berechnung der euklidischen Distanz zweier Punkte deutlich weniger stark einfließen als letztere.
Es ist daher notwendig, die Koordinaten vor der Durchführung des k-Means-Algorithmus jeweils zu skalieren. Am einfachsten ermittelt man die kleinsten Koordinaten $x_{min}$ und $y_{min}$ sowie die größten Koordinaten $x_{max}$ und $y_{max}$ und berechnet dann die skalierten Koordinaten folgendermaßen: $$x_{neu} = \frac{x - x_{min}}{x_{max} - x_{min}}$$ $$y_{neu} = \frac{y - y_{min}}{y_{max} - y_{min}}$$ Damit fallen dann alle Koordinaten ins Intervall $[0;\ 1]$, wobei die Werte 0 und 1 sowohl als x- als auch als y-Koordinate mindestens ein Mal vorkommen.
Der Graph rechts veranschaulicht die Herleitung des Terms zur Berechnung von $x_{neu}$:
- Das Intervall $[x_{min}; x_{max}]$ wird auf das Intervall $[0;\ 1]$ abgebildet.
- Am Dreieck kann die Steigung $\frac{1}{x_{max}-x_{min}}$ abgelesen werden.
- Die Differenz $x - x_{min}$ bewirkt eine Verschiebung der Ursprungsgerade um $x_{min}$ nach rechts.
Aufgabe 2
- a) Erweitern Sie das Programm oben so, dass die Koordinaten vor der Durchführung des k-Means-Algorithmus normiert werden.
- b) Fügen Sie der Punktemenge im Programm noch 2 - 3 "Ausreißer" hinzu. Wie beeinflussen sie das Ergebnis des k-Means-Algorithmus?
- c) Überlegen Sie sich einen Algorithmus, der vor Beginn des k-Means-Algorithmus "Ausreißer" identifizieren und entfernen kann. Fügen Sie auch diesen Algorithmus dem Programm oben hinzu und testen sie ihn mit den in b) ergänzten Ausreißern sowie mit neuen Ausreißern.
Automatische Ermittlung einer möglichst guten Clusteranzahl
Es gibt verschiedene Methoden zur automatischen Ermittlung einer möglichst guten Clusteranzahl. Eine davon soll im Folgenden vorgestellt werden:
Zunächst braucht man ein Maß für die Güte der Einteilung einer Punktmenge in Cluster. Eine Möglichkeit besteht darin, die Abstände aller Punkte von ihrem Clusterzentrum zu berechnen und die Quadrate dieser Abstände zu addieren.
Man führt den k-Means-Algorithmus für 2, 3, 4, … Cluster durch und berechnet für jede Clusteranzahl dieses Gütemaß("Summe der Abstandsquadrate von den Clusterzentren"). Trägt man nun die Clusteranzahl nach rechte und das Gütemaß nach oben ab, so erkennt man in vielen Fällen ein "Knie" im Graphen oder zumindest eine Anzahl von Clustern, ab der das Maß kaum noch fällt. Diese Zahl von Clustern wird dann als die beste angesehen.
Aufgabe 3
Implementieren Sie das Verfahren zur automatischen Ermittlung der Clusteranzahl.