Definition

Was ist der k-Means-Algorithmus?

| Autor / Redakteur: Tutanch / Nico Litzel

(Bild: © aga7ta - stock.adobe.com)

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.

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.

Kommentare werden geladen....

Kommentar zu diesem Artikel abgeben

Der Kommentar wird durch einen Redakteur geprüft und in Kürze freigeschaltet.

Anonym mitdiskutieren oder einloggen Anmelden

Avatar
Zur Wahrung unserer Interessen speichern wir zusätzlich zu den o.g. Informationen die IP-Adresse. Dies dient ausschließlich dem Zweck, dass Sie als Urheber des Kommentars identifiziert werden können. Rechtliche Grundlage ist die Wahrung berechtigter Interessen gem. Art 6 Abs 1 lit. f) DSGVO.
  1. Avatar
    Avatar
    Bearbeitet von am
    Bearbeitet von am
    1. Avatar
      Avatar
      Bearbeitet von am
      Bearbeitet von am

Kommentare werden geladen....

Kommentar melden

Melden Sie diesen Kommentar, wenn dieser nicht den Richtlinien entspricht.

Kommentar Freigeben

Der untenstehende Text wird an den Kommentator gesendet, falls dieser eine Email-hinterlegt hat.

Freigabe entfernen

Der untenstehende Text wird an den Kommentator gesendet, falls dieser eine Email-hinterlegt hat.

Aktuelle Beiträge zu diesem Thema

Optimale Clusteranalyse und Segmentierung mit dem k-Means-Algorithmus

Grundlagen Statistik & Algorithmen, Teil 5

Optimale Clusteranalyse und Segmentierung mit dem 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, so etwa in der Bildverarbeitung und in der Kundensegmentierung. lesen

So kommen Sie mit den passenden Algorithmen zum Ziel

Machine Learning

So kommen Sie mit den passenden Algorithmen zum Ziel

Einfache Algorithmen sind das tägliche Brot vieler Programmierer. Wer etwa eine Software erstellt, die den Preis eines Hauses basierend auf der Größe ausgibt, schreibt normalerweise einen Algorithmus, der abhängig vom Input (Hausgröße) einen bestimmten Output (Preis) berechnet. Wenn es um Machine Learning geht, steigen die Anforderungen an die Programmierung und die Mathematik. lesen

Top 10 der Business Intelligence Trends für das Jahr 2017

Kommentar von Lars Milde, Tableau

Top 10 der Business Intelligence Trends für das Jahr 2017

2016 lagen Self-Service-Analysen im Trend. Viele Unternehmen führten den modernen Business-Analytics-Ansatz ein, bei dem IT und Geschäftsbetrieb zusammenarbeiten, um die eigenen Daten optimal zu nutzen. Die IT begann, skalierbare und ausbaufähige Technologien zu nutzen, Geschäftsanwender teilten ihre Daten und arbeiteten gemeinsam daran. lesen

Tableau 10.0 angekündigt und als Beta verfügbar

Leistungsfähigere Analysen

Tableau 10.0 angekündigt und als Beta verfügbar

Voraussichtlich noch in diesem Monat wird Tableau 10.0 veröffentlicht. Bis dahin ist die Analytics-Software als Beta-Version verfügbar. Die neue Version bietet unter anderem ein vollständig überarbeitetes Design und mehr Funktionen. lesen

copyright

Dieser Beitrag ist urheberrechtlich geschützt. Sie wollen ihn für Ihre Zwecke verwenden? Infos finden Sie unter www.mycontentfactory.de (ID: 45405605 / Definitionen)