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

Intuition

Bearbeiten

Wenn die Eingabedaten   in Clustern vorliegen, dann kann man sich dies in Form von "Datenwolken" vorstellen, die in einem  -Dimensionalen Raum vorliegen. Eine solche Datenwolke/Cluster verfügt über einen Mittelpunkt. Ein Datenpunkt kann dann der Datenwolke zugeordnet werden, deren Mittelpunkt er am nächsten liegt.

Mathematische Formulierung

Bearbeiten

Das Risiko, das in diesem Fall zu minimieren ist, muss mit dem Abstand der Datenpunkten zu den Sphärenmittelpunkten zusammenhängen.

Clusteranzahl

Bearbeiten

Es wird davon ausgegangen, dass es   Cluster gibt. Diese Anzahl wird nicht vom Algorithmus bestimmt, sondern muss zuvor gewählt werden, es handelt sich hierbei also um einen Hyperparameter.

Fehlerfunktion

Bearbeiten

Die Entfernung von Datenpunkten zu den Clustermittelpunkten kann man dabei als Fehler auffassen. Werden die Cluster mit   und ihre Mittelpunkte durch   mit   beschrieben, so kann für das Risiko der Ansatz

 

gemacht werden.

Suche nach einem minimalen Fehler

Bearbeiten

Wird hierfür das Minimum bzgl. der   gesucht, also gefordert, dass der Gradient von   verschwindet, so kann die Bedingung

 

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

Der Algorithmus

Bearbeiten

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

  1. Die Mittelpunkte   der Cluster   werden initialister. (Zum Beispiel zufällig oder durch geschicktes Schätzen)
  2. Für jedes   des vorliegenden Datensatzes   wird der nächstgelegene Mittelpunkt   gefunden und der Datenpunkt dem entsprechenden Cluster   hinzugefügt
  3. Es werden nach der obigen Formel die neuen Mittelpunkte der Cluster bestimmt.
  4. Wenn sich das Risiko (oder die   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   Clustern findet, wird er als k-Means-Algorithmus bezeichnet.

Diskussion

Bearbeiten

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  . Dieses Problem kann umgangen werden, wenn der Algorithmus mit verschiedenen Werten von   initialisiert wird und jenes Cluster verwendet wird, dass das geringste Risiko aufweist.
  • Die gefundenen Cluster sind davon abhängig, welche Startwerte für die   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

Bearbeiten

Statt einer festen Zugehörigkeit zu einem Cluster können stattdessen Wahrscheinlichkeiten gesucht werden, dass der Datenpunkt   zum Cluster   gehört. Diese Wahrscheinlichkeit wird mit   bezeichnet. Da der Datenpunkt im Datensatz vorkommt, müssen sich die Wahrscheinlichkeiten für einen Datenpunkt über alle Cluster zu Eins summieren, so dass

 

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

 

mit einem   einen Wert kleiner als Eins annehmen. Damit wird die neue Risikofunktion

 

eingeführt. Die Größe   ist dabei ein neuer Hyperparameter. Für   reduiziert sich dieses Riskio auf das im Fall des k-Means-Algorithmus. Für   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   ist, desto verschwommener (engl. fuzzy) werden die Grenzen zwischen den Clustern. Daher wird   als Fuzziness und der Algorithmus als Fuzzy-k-Means-Algorithmus bezeichnet. Eine typische Wahl für   ist  .

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

 

bestimmt werden können.

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

 

minimiert werden. Zu diesem Zweck kann die Lagrange-Funktion

 

mit den Lagrange-Multiplikatoren   betrachtet werden. Aus einer Minimierung und dem Ausnutzen der Nebenbedingungen kann für die Lagrange-Multiplikatoren der Zusammenhang

 

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

 

bestimmen lassen.