k-Means Clusteranalyse

Author: Hans Lohninger

Eines der ältesten und robustesten Clusteranalyseverfahren ist k-Means, bei dem in iterativer Weise, mit zufälligen Clusterzentren beginnend, eine vorgegebene Zahl an Cluster gefunden wird. 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

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.

Die folgende Abbildung zeigt die Verschiebung der Clusterzentren für ein einfaches zweidimensionales Beispiel:

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