k-Means Clusteranalyse

Die k-Means Clusteranalyse ist eine der einfachsten und gängigsten Verfahren zur Clusteranalyse. Damit stellt das k-Means-Verfahren eines der am weitesten verbreiteten Verfahren dar. Es handelt sich dabei um ein partitionierendes Verfahren, welches besonders für große Datenmengen geeignet ist.

Das k-Means-Verfahren zielt darauf ab, die Datenpunkte so auf die k Cluster zu verteilen, dass die Summe der Entfernungen von jedem Punkt zum jeweiligen Cluster Centroid minimiert wird.

k-Means Verfahren

Vereinfacht ausgedrückt gruppiert die k-Means Clusteranalyse ähnliche Datenpunkte und ermöglicht so, zugrunde liegende Muster zu erkennen. Das k-Means Verfahren bzw. der k-means Algorithmus funktionieren nun folgendermaßen:

1) Anzahl der Cluster definieren

Um die Gruppen bzw. Cluster zu finden, muss zunächst die Anzahl der Cluster definiert werden. Die Anzahl der Cluster ist das "k" in k-means. In diesem Beispiel wurde k gleich 3 gewählt.

2) Cluster-Mittelpunkte zufällig festlegen

Im zweiten Schritt werden die initialen Cluster Centroids festgelegt. Dieses geschieht in der Regel zufällig. Wir haben 3 Cluster ausgewählt, daher werden drei Centroids zufällig positioniert. Jedes der Centroids repräsentiert nun ein Cluster.

3) Punkte den Clustern zuordnen

Nun wird die Distanz vom ersten Punkt zu jedem der Cluster Centroids gemessen. Anschließend wird der Punkt dann dem jeweiligen Cluster zugeordnet, welcher am nächsten ist. Dies wird nun für alle weiteren Punkte wiederholt. Anschließend sind dann alle Punkte initial einem Cluster zugeordnet.

4) Mittelwert von jedem Cluster berechnen

Im vierten Schritt wird von jedem Cluster der Mittelwert berechnet. Diese Mittelwerte sind die neuen Centroids der Cluster. Die Cluster-Centroids werden also in die Cluster Mittelpunkte verlegt.

5) Punkte den neuen Clustern zuordnen

Da nun die Centroids an einem anderen Punkt liegen können, wird gleich wie in Punkt 3) wieder jedem Punkt der Cluster zugeordnet, welcher ihm am nächsten ist.

Schritt 4) und 5) wiederholen

Nun werden Schritt 4) und 5) so lange wiederholt, bis sich die Cluster Aufteilung nicht mehr ändert. Wenn sich die Cluster in einer Iteration nicht mehr verändern, ist das Verfahren zu Ende!

Der k-Means-Algorithmus setzt sich dabei aus folgenden, wiederholt durchzuführenden Schritten zusammen:

In diesem Verfahren liegt also eine Repräsentation der k-Cluster durch ihre Schwerpunkte vor, wodurch das Verfahren auch seinen Namen erhalten hat: k-Means-Methode. Dieses nicht-hierarchische Verfahren ermöglicht es, im Unterschied zu hierarchischen Verfahren, dass sich die Zuordnungen der Objekte zu den Clustern im Laufe des Prozesses ändern können. Die Clusterzuordnungen sind also nicht endgültig.

Ein Nachteil des Verfahrens ist darin begründet, dass die Clusterlösung von der Reihenfolge der Objekte in der Startpartition (erste Clusterlösung) abhängt. Es ist daher ratsam, mit unterschiedlichen Startpartitionen zu arbeiten, bei denen sich die Reihenfolgen der Cluster und der Objekte in den Clustern unterscheiden. Jene Lösung, die durch unterschiedliche Startpartitionen am öftesten bestätigt wird, sollte schließlich gewählt werden.

DATAtab berechnet daher 10-mal die Clusteranalyse mit jeweils zufällig bestimmten Startpunkten und wählt aus diesen 10 Clusteranalysen die beste aus. Diese wird dann den BenutzerInnen angezeigt. Diese beste Lösung ist dadurch definiert, dass sie die kleinste Summe der Abstände zwischen den Punkten und dem jeweiligen Cluster aufweist.

Optimale Cluster Anzahl

Die Zahl der Cluster muss beim k-Means Verfahren vor Beginn festgelegt werden und wird daher nicht durch das Cluster Verfahren bestimmt. Aber was ist nun die optimale Anzahl an Clustern beim k-Means Verfahren? Hierfür gibt es mit der Ellenbogen-Methode einen gängigen Weg, um die geeignete Anzahl der Cluster zu bestimmen.

Die Ellenbogen-Methode (Elbow Method)

Mit jedem neuen Cluster wird die Gesamtvariation in jedem Cluster kleiner und kleiner. Im Extremfall, wenn es gleich viele Cluster wie Punkte gibt, ist das Ergebnis null. In den meisten Fällen wird die Verkleinerung der Gesamtvariation ab einem bestimmten Punkt kleiner. Dieser Punkt wird dann als optimale Clusteranzahl verwendet.