Zum Inhalt springen

Was ist k-Means Clustering?

Das k-Means Clustering ist ein Verfahren zur Bildung von Gruppen innerhalb eines großen Datensatzes. Der Algorithmus versucht in mehreren Schritten jeden Datenpunkt genau einer Gruppe zuzuordnen, sodass die Daten innerhalb eines Clusters möglichst nah beieinander sind und die Cluster untereinander möglichst weit auseinanderliegen.

Was ist Clustering?

Clustering bezeichnet das Suchen von Untergruppen innerhalb eines Datensatzes, sodass Datenpunkte innerhalb einer Gruppe möglichst gleich sind und Datenpunkte zwischen verschiedenen Gruppen möglichst unterschiedlich. Das Clustering findet auf der Basis von Eigenschaften, sogenannten Features, statt. Das heißt die Gruppen werden basierend darauf gebildet, dass die Datenpunkte innerhalb eines Clusters ähnliche Feature Ausprägungen haben.

Da es keine vordefinierten Gruppen gibt, an denen sich der Algorithmus während des Lernens orientieren könnte, zählt das Clustering zum Unsupervised (Machine) Learning. Die Zuordnung zu Gruppen passiert einzig und allein auf den Strukturen innerhalb des Datensatzes, die das Modell selbstständig erlernen muss.

Bei der Arbeit mit großen Datenmengen hilft das Clustering dabei einen ersten Eindruck über die Feature Ausprägungen und die Verteilung der Datenpunkte zu bekommen. Darüber hinaus gibt es auch viele andere Anwendungen für das Clustering:

  • Marktsegmentierung: Man versucht ähnliche Kundengruppen mit vergleichbarem Kaufverhalten oder sonstigen Eigenschaften zu finden.
  • Bildsegmentierung: Es wird versucht innerhalb eines Bildes die Stellen zu finden, die zu einem bestimmten Objekt gehören, bspw. alle Pixel, die Teil eines Autos bzw. der Straße sind.
  • Dokumentenclustering: Innerhalb eines Schriftstückes wird versucht Passagen mit ähnlichen Inhaltsschwerpunkten zu finden.

Wie funktioniert der k-Means Algorithmus?

Der k-Means Algorithmus ist ein spezielles Clusteringverfahren, das iterativ versucht insgesamt k-Cluster im Datensatz zu finden, sodass jeder Datenpunkt genau einer Gruppe angehört. Im Groben gibt es dabei insgesamt fünf Schritte, die wir uns im Detail anschauen werden:

  1. Wir müssen die Anzahl der Cluster k bestimmen.
  2. Es werden zufällig k Datenpunkte als Clusterzentren, die sogenannten Zentroide, bestimmt.
  3. Alle anderen Datenpunkte werden demjenigen Cluster zugeordnet, dessen Clusterzentrum den geringsten Abstand zum Datenpunkt hat.
  4. Nun wird ein neues Clusterzentrum für jede Gruppe berechnet. Es entspricht dem Punkt im Cluster, der den geringsten Abstand zu allen anderen Datenpunkten in der Gruppe hat.
  5. Wenn sich das Clusterzentrum gar nicht (oder nur sehr wenig) verändert hat, stoppt der Algorithmus hier. Wenn nicht, geht er zurück zu Schritt 3 und ordnet die Datenpunkte wieder dem nächstem Cluster zu.
Das Bild zeigt den Ablauf beim k-Means Clustering.
k-Means Clustering Prozess

Wie findet man die richtige Anzahl an Cluster?

Ein großer Nachteil der k-Means Clustering Methode ist, dass man schon vor dem Training des Modells die Anzahl der endgültigen Gruppen festlegen muss. Dies ist natürlich ohne Kenntnis des Datensatzes eigentlich unmöglich.

Die sogenannte Ellbogen-Methode unterstützt dabei, die richtige Anzahl an Clustern zu finden. Für verschiedene k-Werte wird die Summe aller quadrierten Abstände vom Clusterzentrum zu den Datenpunkten berechnet. Für ein einziges Cluster ist diese Summe maximal und sie wird null, wenn wir genauso viele Cluster, wie Datenpunkte haben, denn dann ist jeder Datenpunkt einfach ein Cluster und der Abstand zwischen Clusterzentrum und Datenpunkt entsprechend 0. Dazwischen versuchen wir das Optimum zu finden, also den Punkt an dem die Abstände innerhalb eines Clusters möglichst gering und die Anzahl der Cluster auch möglichst gering ist.

Das Bild zeigt die Ellbogenmethode beim k-Means Clustering.
Ellbogen Methode | Foto: O’Reilly Media

Aus diesem Diagramm versuchen wir dann das sogenannte Knie oder Ellbogen zu finden, also den Punkt im Graphen, der den markanten Knick hat. Ab diesem Punkt nimmt die Distanz der Punkte im Cluster nicht mehr so stark ab, wie vorher. Somit verbessern neue Cluster das Gesamtergebnis nicht mehr so stark wie zuvor. In diesem Fall sollten wir also k = 3 wählen, um ein optimales Ergebnis zu bekommen.

Das solltest Du mitnehmen

  • K-Means Clustering ist ein Verfahren zur Bildung von Gruppen von großen Datensätzen und zählt zu den Unsupervised Learning Verfahren.
  • Nach Möglichkeit sind Punkte innerhalb einer Gruppe / eines Clusters relativ ähnlich, während Datenpunkte aus verschiedenen Clustern möglichst unterschiedlich sind.
  • Die K-Means Clustering Methode wird beispielsweise eingesetzt, um Kundensegmente bestimmen zu können oder um Bereich in Bildern zu finden, die dasselbe zeigen.
  • Mithilfe der sogenannten Ellbogen Methode können wir im Vorhinein die optimale Anzahl der Clusterzentren finden.

Andere Beiträge zum Thema K-Means Clustering

  • Auf dieser Seite kann man ein k-Means Clustering Modell Schritt für Schritt beim Trainieren beobachten.
close
Das Logo zeigt einen weißen Hintergrund den Namen "Data Basecamp" mit blauer Schrift. Im rechten unteren Eck wird eine Bergsilhouette in Blau gezeigt.

Verpass keine neuen Beiträge!

Wir versenden keinen Spam! Lies die Details gerne in unserer Datenschutzrichtlinie nach.

Cookie Consent mit Real Cookie Banner