6.3 Partitionierende Verfahren: $k$-Means und Varianten

Partitionierende Verfahren unterteilen den gesamten Datenraum in Bereiche, d.h. sie ziehen Grenzen im Raum, die Datencluster voneinander trennen. Das bekannteste partitionierende (und wohl auch das überhaupt am meisten eingesetzte) Verfahren ist $k$-Means. Genau genommen beschreibt $k$-Means nicht einen spezifischen Algorithmus, sondern das grundsätzliche Verfahren, Daten mit Hilfe von Varianzminimierung (vgl. Methode der kleinsten Quadrate im Kapitel zur Linearen Regression) mit möglichst geringem rechnerischen Aufwand in genau $k$ Cluster zu partitionieren. Ziel ist es dabei, jeden Datenpunkt $x$ einem Cluster $C_i$ so zuzuordnen, dass die folgende Summe minimiert wird:

$$\sum _{i=1}^k\sum _{x\in C_i}{||x-{\mu }_i||}^2$$

Dabei bezeichnet ${\mu }_i$ den Schwerpunkt bzw. das Centroid von $C_i$, d.h. das arithmetische Mittel (engl.: means) aller in $C_i$ enthaltenen Punkte. Das Verfahren sucht also für ein gegebenes $k$ eine Einteilung in $k$ Cluster, so dass die Distanzen der Punkte innerhalb jedes Clusters zum Zentrum des Clusters möglichst gering ist.

Ein Beispiel für ein Clustering mit $k=4$ von Datenpunkten im zweidimensionalen Raum ist in der Abbildung 6.1 zu sehen.

Abbildung 6.1: Clustering Beispiel: A zeigt die Grundverteilung der generierten Daten an. B zeigt die durch KMeans ermittelten Cluster (große Punkte zeigen den Clustermittelpunkt )

Da die Lösung des o.g. Minimierungsproblems NP-schwer ist, werden in der Praxis approximative Algorithmen verwendet, die zwar nicht notwendigerweise zur optimalen Lösung führen, dafür aber schnell sind. Der bekannteste und einfachste dafür eingesetzte Algorithmus ist der von Lloyd (Lloyd 1982), der häufig als der $k$-Means-Algorithmus bezeichnet wird. Dieser ist iterativ und wird im Folgenden beschrieben.

\begin{algorithm}
\caption{$k$-Means}
\begin{algorithmic}
  \STATE Wähle (zufällig) $k$ Punkte als initiale Schwerpunkte der $k$ Cluster
  \REPEAT
    \STATE Bilde $k$ Cluster durch Zuweisung jedes Punkts zum nächstliegenden Schwerpunkt
    \STATE Aktualisiere den Schwerpunkt jedes Clusters als Mittelwerte der enthaltenen Punkte
  \UNTIL{ bis die Schwerpunkte sich nicht mehr ändern }
\end{algorithmic}
\end{algorithm}

Die folgende animierte Abbildung zeigt den Ablauf des Algorithmus.

Um das Verfahren zu verwenden, müssen die einbezogenen Attribute nummerisch und so beschaffen sein, das der jeweilige Mittelwert eine sinnvolle Bedeutung hat. Der Algorithmus konvergiert (endet) in jedem Fall, sofern als Distanzfunktion die euklidische Distanz verwendet wird. In der Praxis zeigt sich außerdem, dass der Algorithmus schnell konvergiert, obwohl die Laufzeit theoretisch im schlechtesten Fall exponentiell in der Zahl der Punkte wächst.

Festzuhalten ist außerdem, dass dieses Verfahren approximativ ist, also kein garantiertes Optimum liefert. Die entstehenden Cluster hängen von der initialen Wahl der Centroide ab. Zur Verbesserung der Ergebnisse kann der Algorithmus mehrfach – mit unterschiedlichen Startschwerpunkten – ausgeführt werden und das beste Ergebnis verwendet werden.

Ein Nachteil von $k$-Means ist die feste Wahl von $k$ als Startparameter, wodurch zwingend genau $k$ Cluster erzeugt werden, was möglicherweise nicht zur tatsächlichen Clustertendenz der Daten passt. Man kann den Algorithmus für eine Reihe verschiedener $k$ durchführen und die Ergebnisse z.B. mit Hilfe des Silhouettenkoeffizienten [TODO: Ref] miteinander vergleichen.

Da $k$-Means aus geometrischer Sicht die Daten gemäß des Voronoi-Diagramms partitioniert (die Clustergrenzen verlaufen immer genau entlang der Mittelsenkrechten zwischen zwei Centroiden), stellen die Cluster stets konvexe Mengen dar, d.h. für je zwei Punkte des Clusters liegen auch alle Punkte auf der Verbindungsgerade im diesem Cluster. Für nicht konvexe Cluster ist das Verfahren daher nicht geeignet. (Ein Beispiel findet sich in Abbildung 6.3).

Schließlich ist zu bedenken, dass $k$-Means immer jeden Punkt einem Cluster zuordnet. Ausreißer können damit nicht erkannt werden, sondern im Gegenteil bestehende Cluster stark verzerren.

Um auch mit anderen Distanzmaßen als der euklidischen Distanz umgehen zu können, sind Varianten von $k$-Means entwickelt worden, z.B. $k$-Median, welches zur Ähnlichkeitsbestimmung die Manhattan-Distanz und zur Neuberechnung der Centroide den Median anstelle des arithmetischen Mittels verwendet. In der Variante $k$-Medoids wird als neuer Cluster-Schwerpunkt immer ein tatsächlich existierender Datenpunkt gewählt, und zwar derjenige, für den die Summe der Distanzen zu allen anderen Punkten im Cluster minimiert wird (also der “zentralste” Datenpunkt im Cluster, das so genannte Medoid). Damit konvergiert das Verfahren für beliebige Distanzmaße, ist aber deutlich weniger effizient zu berechnen.

References

Lloyd, S. 1982. “Least Squares Quantization in Pcm.” IEEE Transactions on Information Theory 28 (2): 129–37. https://doi.org/10.1109/TIT.1982.1056489.