Fundamentals of Statistics contains material of various lectures and courses of H. Lohninger on statistics, data analysis and chemometrics......click here for more.

k-Means Clustering

k-Means Clustering gehört zu den einfachsten Austauschverfahren. Es kann auch für größere Datensätze verwendet werden, da es bei wenigen Clusterzentren relativ schnell berechnet werden kann. k-Means Clustering verlangt die Vorgabe der gewünschten Clusterzahl k.

Mathematisch gesehen, entspricht k-Means Clustering einer Optimierung bei der die Zielfunktion

minimiert wird, wobei den Abstand zwischen dem Datenpunkt i und dem Clusterzentrum j definiert.

Algorithmus
1. Initialisierung Zur Initialisierung werden die k vorgegebenen Clusterzentren auf k zufällig ausgewählte Datenpunkte gesetzt. Alternativ kann man auch die ersten k Datenpunkte nehmen. Wichtig ist, dass alle k Clusterzentren unterschiedliche Positionen im p-dimensionalen Raum aufweisen. Die besten Ergebnisse erreicht man wenn man die Clusterzentren so positioniert, dass die Abstände zwischen den initialen Clusterzentren maximal sind. Jedem Clusterzentrum wird eine eindeutige Klassennummer (1 bis k) zugewiesen.
2. Klassifizierung Finde für jeden Datenpunkt das nächste Clusterzentrum und weise dem Datenpunkt die Klassennummer dieses Clusterzentrums zu.
3. Clusterzentren
berechnen
Berechne die Position der Clusterzentren neu, in dem alle Datenpunkte die zu einer bestimmten Klasse gehören gemittelt werden.
4. Iteration Wiederholung ab Schritt 2, bis die Klassifizierung stabil ist.

Nachteile des Verfahrens

Neben dem Vorteil der einfachen und schnellen Implementierung hat das k-Means-Verfahren auch ein paar Nachteile, die nicht übersehen werden sollten:

  • Das Ergebnis der Clusterbildung hängt von den Startpositionen ab. Man sollte daher immer einige Versuche mit unterschiedlichen Startpositionen machen.
  • Es kann zu leeren Klassen kommen, bei denen bestimmten Clusterzentren keine Daten zugeordnet werden.
  • Die Klassifizierung ist nicht skalierungsinvariant. Als Abhilfe kann man - wenn die Daten und die Fragestellung dies zulassen - standardisierte Daten verwenden

Last Update: 2012-10-08