Clustering mit Hilfe des K-Means-Algorithmus

Gruppierungen von Kunden, verschiedenen Produkten oder auch Erkennung von Segmenten in Bildern. All diese Aufgaben können durch Clustering bewerkstelligt werden. Clustering Algorithmen ermöglichen es Daten in Gruppen einzuteilen. Der K-Means-Algorithmus (engl. Means = Mittelwerte) ist ein Vertreter des Clusterings. Dieser Artikel beschreibt, dessen Ein- und Ausgänge, die grundlegende Funktionsweise und abschließend dessen Vor- und Nachteile. Viel Spaß beim Lesen! :)

Wie schon bei den Grundlagen maschinellen Lernens besprochen, ist die Eingabe bei Cluster-Algorithmen eine Menge an Datensätzen mit ihren Eigenschaften beziehungsweise Merkmalen. Im Gegensatz zur Klassifikation, gibt es hierbei kein Klassenmerkmal oder Label (siehe beispielsweise Bayes-Algorithmus). Hier betrachten wir vor Allem kontinuierliche Merkmale (Größe, Länge, Preis, etc.). Speziell bei dem K-Means-Algorithmus, gibt es aber auch noch eine Konstante K als Eingabe. K bestimmt, wie viele Gruppen letztendlich gebildet werden sollen. Unten wird darauf eingegangen, was die Nachteile dabei sind. Die Ausgabe beziehungsweise das Ergebnis des K-Means-Algorithmus sind die K Gruppen bestehend aus den Datensätzen.

Das Vorgehen beim Clustering mit K-Means ist recht einfach. Zunächst muss klar sein, wie der Abstand zwischen zwei Datenpunkten bestimmt wird. Ziel ist es den Abstand zwischen den Datenpunkten innerhalb einer Gruppe zu minimieren und den Abstand zwischen den Gruppen zu maximieren. Die untere Grafik zeigt ein Beispiel mit zwei Dimensionen (zwei Merkmalen). Links oben ist der Ausgangszustand mit den Datenpunkten (grau) zu sehen.

Zunächst muss die Anzahl der Gruppen (= K) festgelegt werden (im Beispiel sind es drei). Zu Beginn des Algorithmus werden K Punkte zufällig ausgewählt (im Beispiel ist K = 3: blau, rot und grün). Diese drei Zentrumspunkte sollen im Laufe des Vorgehens zu den Mittelpunkten der Gruppen wandern, deswegen wird der Algorithmus auch K-Means genannt.

Im nächsten Schritt wird jeder Datenpunkt zum nächstgelegenen Zentrumspunkt zugeordnet (siehe rechts oben). Wie zusehen ist, ist die Zuordnung noch nicht so ganz wie wir sie erwarten würden. Deshalb wird nun die Position der Zentrumspunkte korrigiert, sodass diese im Mittelpunkt ihrer aktuellen Gruppe liegen. Die neue Position kann über den Durchschnittswert der Punkte der Gruppe in jeder Dimension bestimmt werden.

Durch die Verschiebung verändern sich die Abstände der Datenpunkte zu den Zentrumspunkten (siehe links unten). Somit müssen auch die Gruppen angepasst und die Positionen der Zentrumspunkte korrigiert werden. Diese Schritte werden solange wiederholt, bis sich die Positionen der Zentrumspunkte nicht mehr verändern (siehe rechts unten). Et voilà, das Ergebnis ist die Zuordnung aller Datenpunkte zu einer der K Gruppen.

Ein großer Nachteil des K-Means-Algorithmus ist, dass die Anzahl der Gruppen schon im Vorhinein festgelegt werden muss. Häufig ist jedoch nicht klar wie viele Gruppen es geben wird. Dem kann entgegengewirkt werden, indem der Algorithmus mit verschiedenen K's durchgeführt wird. Bei jeder Durchführung kann dann überprüft werden, ob die Abstände innerhalb der Gruppen und zwischen den Gruppen besser geworden ist.

Ein weiterer Nachteil ist die zufällige Bestimmung der Mittelpunkte am Anfang. Unterschiedliche Konstellationen können zu unterschiedlichen Ergebnissen führen. Dieses Problem wird damit gelöst, dass der Algorithmus mehrere Male durchgeführt wird. Die Gruppierung, die am häufigsten auftritt, ist dann das Ergebnis.

Auch Ausreißer stellen ein Problem für K-Means dar. Ausreißer sind Datenpunkte, die sehr weit von allen anderen entfernt liegen. Dadurch werden natürlich die Mittelpunkte und damit die Gruppen verzehrt. Eine Möglichkeit damit umzugehen ist, den Median (auch Zentralwert genannt) anstelle des Mittelpunktes zu verwenden. Der Median ist dann der zentrale Datenpunkt in einer Gruppe.

(Bei der Zahlenfolge 1, 1, 3, 5, 45 ist die 3 der Median beziehungsweise Zentralwert.)

Trotz dieser Nachteile ist K-Means dennoch ein sehr populärer Algorithmus für das Clustern von Daten. Das liegt vor Allem daran, dass er sehr schlicht und einfach zu verstehen ist. Hinzu kommt, dass er auch ein sehr schneller Algorithmus ist. Die Laufzeit steigt lediglich linear mit der Anzahl an Daten, der Anzahl an Gruppen und der Anzahl an Wiederholungen. Diese beiden Faktoren sind beispielsweise auch bei immens vielen Daten und verteilter Verarbeitung von großem Vorteil.

• Prof. Dr. Heiko Paulheim: Vorlesungsunterlagen Data Mining - Clustering. Universität Mannheim, 2017.
• Lillian Pierson: Data Science für Dummies. Wiley VCH-Verlag, 2009.
• Pang-Ning Tan, Michael Steinbach, Vipin Kumar: Introduction to Data Mining. Pearson, 2006.