Grundlagen Statistik & Algorithmen, Teil 5 Optimale Clusteranalyse und Segmentierung mit dem k-Means-Algorithmus
Autor / Redakteur: Michael Matzer / Nico Litzel
Der k-Means-Algorithmus ist ein Rechenverfahren, das sich für die Gruppierung von Objekten, die sogenannte Clusteranalyse, einsetzen lässt. Dank der effizienten Berechnung der Clusterzentren und dem geringen Speicherbedarf eignet sich der Algorithmus sehr gut für die Analyse großer Datenmengen, wie sie im Big-Data-Umfeld üblich sind, so etwa in der Bildverarbeitung und in der Kundensegmentierung.
Anbieter zum Thema
Der k-Means-Algorithmus ist eines der am häufigsten verwendeten mathematischen Verfahren zur Gruppierung von Objekten (Clusteranalyse), beispielsweise von Bilddaten. Der Algorithmus ist in der Lage, aus einer Menge ähnlicher Objekte mit einer vorher bekannten Anzahl von Gruppen die jeweiligen Zentren der Cluster zu ermitteln. Da es sich um ein sehr effizientes Verfahren handelt, das mit vielen verschiedenen Datentypen zurechtkommt und der Speicherbedarf gering ist, eignet sich der k-Means-Algorithmus für die Datenanalyse im Big-Data-Umfeld.
Die Laufzeit des Algorithmus ist linear zur Anzahl der vorhandenen Datenpunkte und die Anzahl der Schleifendurchläufe (Iterationen) zur Ermittlung der Clusterzentren ist relativ klein. Die Idee für den k-Means-Algorithmus stammt ursprünglich von Hugo Steinhaus aus dem Jahr 1957. Erst 1982 wurde der Algorithmus in einer Informatik-Zeitschrift veröffentlicht. Es besteht eine große Ähnlichkeit zum sogenannten Expectation-Maximization-Algorithmus. Eine weitere Variante ist die von Hartigan und Wong, die unnötige Distanzberechnungen vermeidet, indem sie auch den Abstand zum zweitnächsten Mittelpunkt verwendet. Für den k-Means-Algorithmus existieren verschiedene Erweiterungen wie k-Means++ oder der k-Median-Algorithmus (dazu später mehr).
Ziele der Clusteranalyse mit dem k-Means-Algorithmus
Die Clusteranalyse ist ein Verfahren, mit dem sich eine bestimmte Anzahl von Objekten in hom*ogene Gruppen einteilen lässt. Das Ziel besteht darin, dass die verschiedenen Objekte innerhalb einer Gruppe sich nach der erfolgten Einteilung möglichst ähnlich sind. Die Eigenschaften der Objekte sind in Dimensionen eingeteilt. Die Gruppen nennen sich Cluster. Der k-Means-Algorithmus lässt sich für mehrdimensionale Objekte anwenden und nähert sich durch sich ständig wiederholende Neuberechnungen (Iterationen) den jeweiligen Clusterzentren an, bis keine signifikante Veränderung mehr stattfindet. Diese Clusterzentren lassen sich entsprechend kenntlich machen, etwa durch Farbe (siehe dazu die Abbildungen).
Typischer Ablauf des k-Means-Algorithmus
Der k-Means-Algorithmus findet Anwendung auf Daten oder Objekte in einem n-dimensionalen Raum. Das Verfahren verläuft in folgenden Schritten:
- 1. Wahl von k-Punkten als Anfangszentren der Berechnung (dieser Schritt ist von entscheidender Bedeutung);
- 2. Zuordnung der Datenpunkte zu den verschiedenen Clustern auf Basis des Abstands (siehe „Distanzen“) zu den Zentren
- 3. Neuberechnung der Clusterzentren
- 4. Wiederholung ab Schritt 2 – bis sich die Lage der Zentren nicht mehr ändert.
In den ersten Durchläufen des Algorithmus treten noch große Änderungen der Zentren auf. Mit zunehmenden Schleifendurchläufen werden die Veränderungen immer kleiner. Wesentlich für einen effizienten Ablauf des Algorithmus ist die Wahl der Anfangszentren.
Probleme bei der Anwendung des k-Means-Verfahrens
Ein Problem bei der Anwendung des k-Means-Algorithmus stellt die Vorgabe der Anzahl der Cluster und die Wahl der Anfangszentren dar. Die gefundene Lösung ist daher stark von den gewählten Startpunkten abhängig. Zur Wahl der Startpunkte ist die Kenntnis einer gewissen Clusterstruktur notwendig, die aus Voranalysen der Daten stammen könnte. In vielen Fällen erfolgt der Durchlauf des Algorithmus mit unterschiedlichen Startwerten. Die verschiedenen Ergebnisse liefern Hinweise auf eine möglichst plausible Struktur der Cluster.
Achtung: Verwendet man eine ungeeignete Anzahl von Clusterzentren als Startwerte, können sich unter Umständen komplett andere Lösungen oder sogar ungeeignete Clustereinteilungen ergeben.
Auch problematisch für den k-Means-Algorithmus sind Datenmengen, die sich überlappen oder in Teilen nahtlos ineinander übergehen. In diesen Fällen ist das k-Means-Verfahren nicht in der Lage, die verschiedenen Gruppen zuverlässig voneinander zu trennen. Daten mit hierarchischen Clusterstrukturen werden ebenfalls nicht unterstützt. Sind Ausreißer in der Datenmenge vorhanden, können diese das Ergebnis stark verfälschen, da k-Means keine Ausreißer erkennt und jedes Objekt einem Cluster zuordnet. In diesen Fällen ist vor der Auswertung mit dem k-Means-Algorithmus eine Bereinigung der Daten (Noisereduktion) durchzuführen.
Alternativen und Variationen
J. B. MacQueen führte einen anderen Algorithmus ein, den er „k-Means“ nannte:
- 1. Wähle die ersten k Elemente als Clusterzentren
- 2. Weise jedes neue Element dem Cluster zu, bei dem sich die Varianz am wenigsten erhöht, und aktualisiere das Clusterzentrum
Man kann auch diesen Algorithmus iterieren, um ein besseres Ergebnis zu erhalten.
Die Erweiterung k-Means++
Für den k-Means-Algorithmus existiert die Erweiterung k-Means++. Sie beschreibt ein Verfahren, mit dem die Clusterzentren als Startwerte nicht mehr zufällig, sondern nach einer Vorschrift gewählt werden. Dabei werden die Clusterzentren als Startwerte bestimmt. In der Regel konvergiert der nachfolgende k-Means Algorithmus in wenigen Schritten. Die Ergebnisse sind so gut wie bei einem üblichen k-Means-Algorithmus, jedoch ist der Algorithmus typischerweise fast doppelt so schnell wie der k-Means-Algorithmus.
Eine weitere Erweiterung ist K-Median. Im k-Median-Algorithmus wird im Zuweisungsschritt statt der euklidischen Distanz die Manhattan-Distanz verwendet. Im Updateschritt wird der Median statt des Mittelwerts verwendet.
Variationen
- k-Means ++ versucht bessere Startpunkte zu finden.
- Der Filtering-Algorithmus verwendet als Datenstruktur einen K-d-Baum.
- Der k-Means-Algorithmus kann unter Berücksichtigung der Dreiecksungleichung beschleunigt werden.
- „Bisecting k-means“ beginnt mit k = 2 und teilt dann immer den größten Cluster, bis das gewünschte k erreicht ist.
- „X-means“ beginnt mit k = 2 und erhöht k so lange, bis sich ein sekundäres Kriterium nicht weiter verbessert.
Die Erweiterung K-Medoids (PAM)
Der Algorithmus PAM (Partitioning Around Medoids, 1990) – auch bekannt als k-Medoids – kann als Variante des k-Means-Algorithmus interpretiert werden, die mit beliebigen Distanzen konvergiert.
- 1. Wähle k Objekte als Cluster-Schwerpunkte (Medoid) aus
- 2. Ordne jedes Objekt dem nächsten Cluster-Schwerpunkt zu
- 3. Für jeden Cluster-Schwerpunkt und jeden Nicht-Cluster-Schwerpunkt vertausche die Rollen
- 4. Berechne für jede Vertauschung die Summe der Distanzen oder Unähnlichkeiten
- 5. Wähle als neue Cluster-Schwerpunkte die Vertauschung, die die kleinste Summe liefert
- 6. Wiederhole 2. bis 5. solange, bis sich die Cluster-Schwerpunkte nicht mehr ändern
In der ursprünglichen Version von PAM macht hierbei der erste Schritt – die Wahl der initialen Medoiden – einen großen Teil des Algorithmus aus. Da in jeder Iteration stets nur die beste Vertauschung durchgeführt wird, ist der Algorithmus nahezu deterministisch (bis auf exakt gleiche Distanzen). Achtung: Dadurch ist der Algorithmus aber auch meist sehr langsam!
Während k-Means die Summe der Varianzen minimiert, minimiert k-Medoids die Distanzen. Insbesondere kann dieser Algorithmus mit beliebigen Distanzfunktionen verwendet werden und konvergiert dennoch garantiert. Man sieht: Die Erweiterungen und Alternativen des k-Means-Algorithmus erlauben eine willkommene Ausweitung des Anwendungsbereichs des Algorithmus. Meist lässt sich eine doppelte Ausführungsgeschwindigkeit erzielen.
Anwendungen des k-Means-Algorithmus
Der k-Means-Algorithmus findet in vielen Bereichen der Informationstechnik Anwendung. Aufgrund seiner Effizienz und des geringen Speicher- und Rechenbedarfs eignet er sich für die Datenanalyse großer Datenmengen im Big-Data-Umfeld.
In der Bildverarbeitung wird k-Means häufig zur Segmentierung der Bilddaten (siehe Schwertlilien-Abbildung) eingesetzt. Als Entfernungsmaß ist die euklidische Distanz häufig nicht ausreichend und es können andere Abstandsfunktionen, basierend auf Pixelintensitäten und Pixelkoordinaten verwendet werden.
Mit den Ergebnissen des Algorithmus ist beispielsweise die Trennung von Vorder- und Hintergrund oder das Erkennen von einzelnen Objekten möglich. Das ist für die Vorbereitung der Bilderkennung und Bild-Verschlagwortung mithilfe von Deep-Learning-Methoden sehr nützlich. Das DL-Framework Torch und Scikit-learn umfassen k-Means.
Ein weiterer wichtiger Anwendungsbereich sind das Marketing und die Analyse des Kundenverhaltens. k-Means findet in vorliegenden Kundendaten verschiedene Gruppen von Kunden mit jeweils ähnlichem Kundenverhalten. Die von k-Means ermittelten hom*ogenen Gruppen (Kundensegmente, Zielgruppen) lassen sich klar voneinander trennen. Mithilfe spezifischer Marketingmaßnahmen sind die Gruppen effizienter und mit größerer Erfolgsaussicht ansprechbar. Dies ist für Marketingkampagnen, etwa in sozialen Netzwerken, von hoher Bedeutung.
Software
Der Algorithmus ist weit verbreitet und ist in gängigen Bildverarbeitungsbibliotheken wie OpenCV und itk implementiert. Eine ausführliche Software-Liste findet man im entsprechenden Artikel der englischsprachigen Wikipedia, der sowohl freie, quelloffene Software wie ELKI als auch proprietäre Programme wie etwa SAS, IBM SPSS oder SAP HANA erwähnt. Gut zu wissen, wenn man Statistiker ist: Sowohl die R-Distribution GNU-R als auch die Machine Learning Bibliothek (MLIib) in Apache Spark enthalten k-Means. Dass allein R bereits drei k-Means-Variationen umfasst, unterstreicht die hohe Bedeutung und weite Verbreitung dieses Algorithmus.
(ID:45588052)
