Kurs:Maschinelles Lernen/k-Means Algorithmus

Vorherige Seite: K4 - Neuronale Netze trainieren
Nächste Seite: K5 - DBSCAN

Intuition

Wenn die Eingabedaten ${\vec {x}}\in \mathbb {R} ^{d}$ in Clustern vorliegen, dann werden sie dies in Form von "Datenwolken", die als Sphären im $d$-Dimensionalen Raum betrachtet werden können. Eine solche Sphäre verfügt über einen Mittelpunkt. Ein Datenpunkt kann dann der Sphäre zugeordnet werden, deren Mittelpunkt er am nächsten liegt.

Mathematische Formulierung

Das Risiko, das in diesem Fall zu minimieren ist, muss mit dem Abstand der Datenpunkten zu den Sphärenmittelpunkten zusammenhängen. Es wird davon ausgegangen, dass es $k$ Cluster gibt. Diese Anzahl wird nicht vom Algorithmus bestimmt, sondern muss zuvor gewählt werden, es handelt sich hierbei also um einen Hyperparameter. Werden die Cluster mit $C_{a}$ und ihre Mittelpunkte durch ${\vec {c}}_{a}$ mit $a\in \{1,\dots ,k\}$ beschrieben, so kann für das Risiko der Ansatz

${\hat {R}}=\sum _{a=1}^{k}\sum _{{\vec {x}}_{i}\in C_{a}}|{\vec {x}}_{i}-{\vec {c}}_{a}|^{2}$

gemacht werden. Wird hierfür das Minimum bzgl. der ${\vec {c}}_{a}$ gesucht, also gefordert, dass der Gradient von ${\hat {R}}$ verschwindet, so kann die Bedingung

${\vec {c}}_{a}={\frac {1}{|C_{a}|}}\sum _{{\vec {x}}_{i}\in C_{a}}{\vec {x}}_{i}$

gefunden werden. Das bedeutet, dass die Mittelpunkte eines Clusters bei bekannter Clusterzugehörigkeit durch diese Formel bestimmt werden müssen. Dabei soll $|C_{a}|$ die Anzahl der Datenpunkte im Cluster beschreiben.

Der Algorithmus

Im Jahr 1957 erarbeitete Stuart Lloyd den folgenden Algorithmus, der 1982 veröffentlicht wurde:

1. Die Mittelpunkte ${\vec {c}}_{a}$ der Cluster $k$ werden initialister. (Zum Beispiel zufällig oder durch geschicktes Schätzen)
2. Für jedes ${\vec {x}}_{i}$ des vorliegenden Datensatzes $D$ wird der nächstgelegene Mittelpunkt ${\vec {c}}_{a}$ gefunden und der Datenpunkt dem entsprechenden Cluster $C_{a}$ hinzugefügt
3. Es werden nach der obigen Formel die neuen Mittelpunkte der Cluster bestimmt.
4. Wenn sich das Risiko (oder die ${\vec {c}}_{a}$ nicht mehr "maßgeblich" verändern, wird der ALgorithmus beendet, ansonsten wird zurück zu Punkt 2 gesprungen.

Da der Algorithmus die Mittelwerte (engl. means) von $k$ Clustern findet, wird er als k-Means-Algorithmus bezeichnet.

Diskussion

Der Algorithmus wird zwar auf ein lokales Minimum führen, hat aber verschiedene Probleme

• Die Cluster die gefunden werden, sind abhängig von der Wahl von $k$. Dieses Problem kann umgangen werden, wenn der Algorithmus mit verschiedenen Werten von $k$ initialisiert wird und jenes Cluster verwendet wird, dass das geringste Risiko aufweist.
• Die gefundenen Cluster sind davon abhängig, welche Startwerte für die ${\vec {c}}_{a}$ gewählt wurden. Dieses Problem kann ebenfalls durch eine mehrfache Initialisierung umgangen werden. Es wird auch hier jene Konfiguration mit dem geringsten Risiko bevorzugt.
• Eine der Grundannahmen für den Algorithmus sind kugelförmige Cluster. Diese Annahme ist aber nicht immer gerechtfertigt, weshalb sich für das menschliche Auge offensichtliche Fehlklassifikationen ergeben können. Dementsprechend ist die Rechtfertigung dieser Annahme zu rechtfertigen, oder die Klassenzugeörigkeit aufzuweichen, wie es im folgenden Abschnitt erklärt wird.

Fuzzy-k-Means

Statt einer festen Zugehörigkeit zu einem Cluster können stattdessen Wahrscheinlichkeiten gesucht werden, dass der Datenpunkt ${\vec {x}}_{i}$ zum Cluster $C_{a}$ gehört. Diese Wahrscheinlichkeit wird mit $w_{ai}$ bezeichnet. Da der Datenpunkt im Datensatz vorkommt, müssen sich die Wahrscheinlichkeiten für einen Datenpunkt über alle Cluster zu Eins summieren, so dass

$\sum _{a=1}^{k}w_{ai}=1$

gilt. Falls ein Datenpunkt nun zu mehr als zu einem Cluster zugeordnet wird, wird der Ausdruck

$\sum _{a=1}^{k}w_{ai}^{b}$

mit einem $b>1$ einen Wert kleiner als Eins annehmen. Damit wird die neue Risikofunktion

${\hat {R}}=\sum _{a=1}^{k}\sum _{i=1}^{N}w_{ai}^{b}|{\vec {x}}_{i}-{\vec {c}}_{a}|^{2}$

eingeführt. Die Größe $b$ ist dabei ein neuer Hyperparameter. Für $b=1$ reduiziert sich dieses Riskio auf das im Fall des k-Means-Algorithmus. Für $b\to \infty$ geht das Risiko unabhängig der Wahl der Wahrscheinlichkeiten und Mittelpunkte gegen Null, und es werden keine Unterscheidungen der Cluster mehr möglich sein. Das bedeutet, je größer $b$ ist, desto verschwommener (engl. fuzzy) werden die Grenzen zwischen den Clustern. Daher wird $b$ als Fuzziness und der Algorithmus als Fuzzy-k-Means-Algorithmus bezeichnet. Eine typische Wahl für $b$ ist $b=2$.

Es lässt sich zeigen, dass in diesem Fall die Mittelpunkte der Cluster durch

${\vec {c}}_{a}={\frac {\sum _{i=1}^{N}w_{ai}^{b}{\vec {x}}_{i}}{\sum _{i=1}^{N}w_{ai}^{b}}}$

bestimmt werden können.

Um die Wahrscheinlichkeiten zu finden, muss das Risiko unter der Nebenbedingung

$\sum _{a=1}^{k}w_{ai}=1$

minimiert werden. Zu diesem Zweck kann die Lagrange-Funktion

$L(w_{ai},\alpha _{i})=\sum _{a=1}^{k}\sum _{i=1}^{N}w_{ai}^{b}|{\vec {x}}_{i}-{\vec {c}}_{a}|^{2}-\sum _{i=1}^{N}\alpha _{i}\left(\sum _{a=1}^{k}w_{ai}-1\right)$

mit den Lagrange-Multiplikatoren $\alpha _{i}$ betrachtet werden. Aus einer Minimierung und dem Ausnutzen der Nebenbedingungen kann für die Lagrange-Multiplikatoren der Zusammenhang

$\left({\frac {\alpha _{i}}{b}}\right)^{\frac {1}{b-1}}={\frac {1}{\sum _{a=1}^{k}{\frac {1}{|{\vec {x}}_{i}-{\vec {c}}_{a}|^{2/(b-1)}}}}}$

gefunden werden. Und damit zeigt sich, dass sich die Gewichte durch

$w_{ai}={\frac {\left({\frac {1}{|{\vec {x}}_{i}-{\vec {c}}_{a}|}}\right)^{\frac {2}{b-1}}}{\sum _{a'=1}^{k}\left({\frac {1}{|{\vec {x}}_{i}-{\vec {c}}_{a'}|}}\right)^{\frac {2}{b-1}}}}={\frac {1}{\sum _{a'=1}^{k}\left({\frac {|{\vec {x}}_{i}-{\vec {c}}_{a}|}{|{\vec {x}}_{i}-{\vec {c}}_{a'}|}}\right)^{\frac {2}{b-1}}}}$

bestimmen lassen.