Der k-means Algorithmus

Was ist der k-means Algorithmus

K-means ist ein Clusterverfahren, das heißt, dass Elemente mit gleichen oder ähnlichen Eigenschaften gruppiert werden. Dabei werden die Cluster durch ein Zentrum im n-dimensionalen Raum repräsentiert, wobei n die Anzahl der Eigenschaften angibt.

Das Erbebnis dieser Clusteranalyse ist eine Gruppierung aller Elemente in k Cluster, wobei der Wert für k als Konstante für den Algorithmus gesetzt wird.

Ablauf des Algorithmus

Für dieses Verfahren muss die Anzahl der Cluster k eine positive Zahl sein.

Der Ablauf besteht aus folgenden Schritten:

1. Ordne k zufällige Elemente je einem Cluster zu
2. Ordne jedem Element das Cluster mit dem nahesten Zentrum zu
3. Berechne Clusterzentren neu
4. Springe zu Schritt 2 wenn sich Clusterzentren geändert haben
5. Fertig

Als Ergebnis erhält man Cluster mit einer lokal minimalen Summe der Abstände der Clusterzentren zu seinen Elementen.

Voraussetzungen

Um die Clusterzentren zu berechnen und die Entfernungen der Elemente zu diesen, sind folgende Voraussetzungen zu beachten:

• Der Parameter k, also die Anzahl der Cluster, muss im Voraus bekannt sein.
• Jedes Element besitzt einen Vektor x={x₁ x₂, …, x_n}, wobei x_i metrisch ist.
• Es existiert eine Funktion f(x,y) zur Berechnung eines Abstands der Vektoren x und y

Vor- und Nachteile

• k-Means ist einfach anzuwenden
• Das Verfahren konvergiert sehr schnell zu einem lokalen Minimum
• Der Speicherbedarf ist gering; die Laufzeit ist linear
• Findet nicht immer die beste Lösung
• Hängt von den gewählten (zufälligen) Startpunkten ab
• Anzahl der Cluster muss vorher gewählt werden, was bei ungeeigneten Werten von k unintuitive Lösungen ergibt
• Findet durch die Minimierung der Distanz nur konvexe Cluster
• Ausreißer verfälschen das Ergebnis sehr stark

Möglichkeiten zu Verbesserung

Eine einfache Möglichkeit, das Ergebnis zu verbessern, ist es, den Algorithmus mehrfach aufzurufen und (bei verschiedenen Startwerten) das beste Ergebnis zu wählen.

Eine weitere Möglichkeit ist es, die Startpunkte geeignet zu wählen, wozu es verschiedene Ansätze gibt, wie zum Beispiel k-means++.

Der Simulator

In dem hier dargestellten Simulator werden die Elemente im zweidimensionalen, Euklidischen Raum dargestellt. Dadurch zeigen sich Cluster anschaulich durch eine räumliche Nähe.

Auf der Zeichenfläche im unteren Bereich können beliebig viele Elemente auf der zweidimensionalen Ebene eingetragen werden. Mit dem Berechnen-Button (Play-Zeichen) erfolgt die Berechnung der Cluster. Dabei wird der Wert aus "Anzahl der Cluster k" entsprechend berücksichtigt. Für eine anschaulichere Darstellung können Umkreise um die Clusterzentren gezeichnet werden.
Um ein besseres Ergebnis bei der Berechnung zu erhalten, können mehrere Iterationen eingeschaltet werden und durch "Anzahl der Iterationen" entsprechend gewählt werden.
Möchte man eine Berechnung zurücksetzen, klickt man den Button links vom Berechnen-Button. Rechts von diesem kann mit Einzelschritt durch die verschiedenen Schritte des Algorithmus gegangen werden.

Zur Veranschaulichung von Eigenschaften des Verfahrens gibt es den Bereich "Beispiele", welche selbsterklärend sind.
Unter den Buttons zum Berechnen befinden sich zwei Buttons zum Entfernen aller Elemente und hinzufügen von zufällig gesetzten Elementen. Dabei werden soviel Elemente hinzugefügt, wie im Textfeld eingetragen sind (Standard 100).
Schließlich befindet sich eine Statistik auf der rechten Seite. Oberst wird angezeigt, wieviele Iterationen bereits berechnet sind und wie die Durchschnittsdistanzen dieser sind. Dazu fährt man mit der Maus über den Text. Darunter befinden sich Werte zur kleinsten Durchschnittsdistanz (über alle Iterationen) und die aktuelle Durchschnittsdistanz (nur beim Einzelschritt). Schließlich folgt eine Darstellung des letzten ausgeführten Schritt im Einzelschritt. Beim normalen Berechnen erscheint hier immer "Fertig".