Definition Was ist der k-Means-Algorithmus?

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.

Anbieter zum Thema

IBM Deutschland GmbH

Fujitsu Technology Solutions GmbH

Disy Informationssysteme GmbH

Der k-Means-Algorithmus ist eines der am häufigsten verwendeten mathematischen Verfahren zur Gruppierung von Objekten (Clusteranalyse). 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 zurecht kommt, 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 zur Ermittlung der Clusterzentren ist 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. Für den k-Means-Algorithmus existieren verschiedene Erweiterungen wie k-Means++ oder der k-Median-Algorithmus.

Ziele der Clusteranalyse mit dem k-Means-Algorithmus

Die Clusteranalyse ist ein Verfahren, mit dem sich eine bestimmte Anzahl von Objekten in homogene Gruppen einteilen lässt. Ziel ist es, 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 den jeweiligen Clusterzentren an, bis keine signifikante Veränderung mehr stattfindet.

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

• 2. Zuordnung der Datenpunkte zu den verschiedenen Clustern auf Basis des Abstands 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 stark von den gewählten Startpunkten abhängig. Zu 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. Verwendet man eine ungeeignete Anzahl von Clusterzentren als Startwerte, können sich unter Umständen komplett andere Lösungen oder 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.

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. Sind die Clusterzentren als Startwerte bestimmt, konvergiert der anschließend ausgeführte k-Means-Algorithmus sehr schnell und in wenigen Schleifendurchläufen. Typischerweise lässt sich eine Verdopplung der Geschwindigkeit erreichen.

Anwendungen des k-Means-Algorithmus

Der k-Means-Algorithmus findet in vielen Bereichen 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 eingesetzt. Mit den Ergebnissen des Algorithmus ist beispielsweise die Trennung von Vorder- und Hintergrund oder das Erkennen von einzelnen Objekten möglich.

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 homogenen Gruppen lassen sich klar voneinander trennen. Mithilfe spezifischer Marketingmaßnahmen sind die Gruppen effizienter und mit größerer Erfolgsaussicht ansprechbar.

(ID:45405605)