Grundlagen Statistik & Algorithmen, Teil 5

Optimale Clusteranalyse und Segmentierung mit dem k-Means-Algorithmus

| Autor / Redakteur: Michael Matzer / Nico Litzel

Kernel-Maschinen werden verwendet, um nichtlinear trennbare Funktionen zu berechnen, um so eine linear trennbare Funktion höherer Ordnung zu erhalten.
Kernel-Maschinen werden verwendet, um nichtlinear trennbare Funktionen zu berechnen, um so eine linear trennbare Funktion höherer Ordnung zu erhalten. (Bild: Kernel Machine.svg / Alisneaky, svg version by User:Zirguezi / CC BY-SA 4.0)

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.

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 homogene 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

Die folgenden Bilder zeigen exemplarisch einen Durchlauf des k-Means-Algorithmus zur Bestimmung von drei Gruppen.
Die folgenden Bilder zeigen exemplarisch einen Durchlauf des k-Means-Algorithmus zur Bestimmung von drei Gruppen. (Bild: K Means Example Step 1-4.svg / Weston.pace / CC BY-SA 3.0)

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

Demonstration eines Problemfalls: Ein k-Means-Ergebnis und reale Schwertlilien-Spezies (rechts) im Iris-Flower-Datensatz, visualisiert mit der Software ELKI. Die Clusterzentren sind durch größere, blassere Symbole gekennzeichnet. Gruppen in den Daten können sich, wie im Schwertlilien-Beispiel,, überlappen und nahtlos ineinander übergehen. In einem solchen Fall kann k-Means diese Gruppen nicht zuverlässig trennen, da die Daten nicht dem verwendeten Cluster-Modell folgen.
Demonstration eines Problemfalls: Ein k-Means-Ergebnis und reale Schwertlilien-Spezies (rechts) im Iris-Flower-Datensatz, visualisiert mit der Software ELKI. Die Clusterzentren sind durch größere, blassere Symbole gekennzeichnet. Gruppen in den Daten können sich, wie im Schwertlilien-Beispiel,, überlappen und nahtlos ineinander übergehen. In einem solchen Fall kann k-Means diese Gruppen nicht zuverlässig trennen, da die Daten nicht dem verwendeten Cluster-Modell folgen. (Bild: gemeinfrei / CC0)

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 homogenen 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.

Das Problem des Handlungsreisenden und seine praktischen Anwendungen

Grundlagen Statistik & Algorithmen, Teil 1

Das Problem des Handlungsreisenden und seine praktischen Anwendungen

18.06.18 - Ob beim Design von künstlichen Neuronalen Netzwerken fürs Deep Learning, in der Logistik oder beim Layout von Leiterplatten – überall stößt man auf das mathematisch lösbare Problem des Handlungsreisenden: Wie lässt sich eine Tour mit mehreren Stationen auf dem kürzesten Weg und mit dem geringsten Aufwand bewältigen? lesen

So verfeinert das Bayes-Theorem Spam-Filter – und mehr

Grundlagen Statistik & Algorithmen, Teil 2

So verfeinert das Bayes-Theorem Spam-Filter – und mehr

25.06.18 - Mithilfe des Satzes von Bayes lassen sich Parameter schätzen und Hypothesen induktiv testen. In einem Spamfilter können so wahrscheinliche Spam-Mails ermittelt werden. Und aus den Symptomen, die bei einem bekannten Test auftreten, lassen sich wahrscheinliche Krankheitsursachen aufspüren. Der Satz von Bayes, der bedingte Wahrscheinlichkeiten beschreibt, ist also ein nahezu universell nutzbares Werkzeug der Statistik. lesen

Speed für Mustererkennung mit dem Rete-Algorithmus

Grundlagen Statistik & Algorithmen, Teil 3

Speed für Mustererkennung mit dem Rete-Algorithmus

02.07.18 - Geschäftsregeln halten zahlreiche Unternehmensprozesse am Laufen, deshalb können sie mitunter sehr umfangreich werden. Der Umfang macht ihre Ausführung zeitaufwendig, weshalb jede Methode, sie zu beschleunigen, willkommen ist. Der Rete-Algorithmus beschleunigte 1979 die damals bestehenden Systeme für die Verarbeitung von Business Rules um den Faktor 3.000. Er ist bis heute die Grundlage zahlreicher Expertensysteme, etwa in der Mustererkennung. lesen

Der Monte-Carlo-Algorithmus und -Simulationen

Grundlagen Statistik & Algorithmen, Teil 4

Der Monte-Carlo-Algorithmus und -Simulationen

10.09.18 - Eine Reihe von Algorithmen dient der Suche von Lösungen, ohne vorher die Antwort zu kennen, und von Entscheidungen, die nach „wahrscheinlich richtig oder falsch“ beurteilt werden. Das ist sinnvoll für das Risiko-Management, aber auch für die Nutzung von Supercomputern. Ein solcher Algorithmus ist der Monte-Carlo-Algorithmus und die darauf basierenden Simulationen lesen

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.

copyright

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