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. Diese Informationen können dann wiederum für Marketingaktivitäten oder neue Produktinnovationen genutzt werden.
• 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. Dies kann auch als Vorverarbeitumgsschritt für Machine Learning Modelle genutzt werden.
• 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. Für die Wahl der anfänglichen Clusterzentren gibt es verschiedene, sogenannte Initialisierungsmethoden. Die Leistung des Algorithmus kann je nach Anwendungsfall stark von den initialen Zentroiden abhängen, weshalb verschiedene Anfangsszenarien ausprobiert werden sollten.
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.

Welche Anwendungen hat das k-Means Clustering?

Das K-Means-Clustering ist ein beliebter Algorithmus für unüberwachtes maschinelles Lernen, der in verschiedenen Bereichen eine breite Palette von Anwendungen bietet. Einige gängige Anwendungen des K-Means-Clustering sind:

• Bildsegmentierung: Das K-Means-Clustering kann verwendet werden, um ein Bild auf der Grundlage von Farb- oder Texturmerkmalen in verschiedene Regionen zu unterteilen. Dies ist in Bereichen wie Computer Vision und medizinische Bildgebung nützlich.
• Kundensegmentierung: K-Means-Clustering kann verwendet werden, um Kunden auf der Grundlage ihres Verhaltens oder ihrer demografischen Daten zu gruppieren. Dies ist für Unternehmen nützlich, um ihre Kunden besser zu verstehen und ihre Marketingstrategien entsprechend anzupassen.
• Erkennung von Anomalien: K-means Clustering kann verwendet werden, um Anomalien oder Ausreißer in einem Datensatz zu erkennen, was bei der Erkennung von Betrug oder defekten Geräten nützlich sein kann.
• Genomisches Clustering: K-means Clustering kann verwendet werden, um Gene oder Proteine auf der Grundlage ihrer Expression oder funktionellen Ähnlichkeiten zu clustern, was in der biologischen Forschung nützlich sein kann.
• Analyse sozialer Netzwerke: K-means clustering kann verwendet werden, um Benutzer in einem sozialen Netzwerk auf der Grundlage ihrer Interessen oder ihres Verhaltens zu gruppieren, was für gezielte Werbung oder Empfehlungssysteme nützlich sein kann.
• Clustering von Dokumenten: K-means Clustering kann verwendet werden, um Dokumente auf der Grundlage ihres Inhalts zu gruppieren, was für die Organisation und das Abrufen großer Dokumentensammlungen nützlich sein kann.

Dies sind nur einige Beispiele für die zahlreichen Anwendungen von K-means Clustering. Die Vielseitigkeit und Einfachheit des Algorithmus machen ihn zu einer beliebten Wahl für viele Clustering-Aufgaben in verschiedenen Bereichen.

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.

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.

Wie bewertet man die Leistung eines k-Means Clusters?

Es gibt mehrere Möglichkeiten, die Leistung eines k-means-Clustering-Algorithmus zu bewerten. Hier sind einige gängige Bewertungsmaßstäbe:

• Summe der Quadrate innerhalb eines Clusters: Damit wird die Gesamtsumme der Abstände zwischen jedem Punkt in einem Cluster und dem Schwerpunkt dieses Clusters gemessen. Je niedriger die WSS ist, desto kompakter sind die Cluster. Ein niedriger WSS-Wert deutet jedoch nicht unbedingt auf eine gute Clustering-Lösung hin, da er nur den Abstand innerhalb jedes Clusters misst.
• Silhouetten-Wert: Damit wird gemessen, wie gut ein Datenpunkt im Vergleich zu anderen Clustern in den ihm zugewiesenen Cluster passt. Der Silhouetten-Score reicht von -1 bis 1, wobei Werte, die näher an 1 liegen, auf einen gut geclusterten Punkt hinweisen und Werte, die näher an -1 liegen, auf einen schlecht geclusterten Punkt.
• Davies-Bouldin-Index (DBI): Dieser misst die durchschnittliche Ähnlichkeit zwischen jedem Cluster und seinem ähnlichsten Cluster. Ein niedriger DBI weist auf eine bessere Clustering-Lösung hin.
• Calinski-Harabasz-Index (CHI): Dieser misst das Verhältnis der Varianz zwischen den Clustern zur Varianz innerhalb der Cluster. Ein höherer CHI weist auf eine bessere Clustering-Lösung hin.
• Externe Validierungsmaße: Diese Maße vergleichen die Clustering-Ergebnisse mit einer bekannten Basiswahrheit, z. B. manuell zugewiesenen Labels. Übliche externe Validierungsmaße sind der angepasste Rand-Index und das F-Maß.

Es ist wichtig zu beachten, dass es nicht die eine „beste“ Bewertungsmetrik für k-means Clustering gibt, da jede Metrik ihre eigenen Stärken und Schwächen hat. Daher empfiehlt es sich, mehrere Bewertungsmetriken zu verwenden, um ein umfassenderes Verständnis der Clustering-Ergebnisse zu erhalten.

Was sind die Grenzen von k-Means Clustering?

Das k-Means-Clustering ist ein weit verbreiteter Algorithmus für unüberwachtes maschinelles Lernen, der jedoch mehrere Einschränkungen aufweist, die bei seiner praktischen Anwendung berücksichtigt werden sollten.

Eine der wichtigsten Einschränkungen des k-Means-Clustering ist, dass die Anzahl der Cluster im Voraus festgelegt werden muss. Dies kann in Situationen, in denen die optimale Anzahl von Clustern nicht im Voraus bekannt ist, schwierig sein, und die Auswahl einer falschen Anzahl von Clustern kann zu schlechten Ergebnissen führen.

Eine weitere Einschränkung ist seine Empfindlichkeit gegenüber der Initialisierung. Der Algorithmus reagiert empfindlich auf die Anfangspositionen der Clusterschwerpunkte, was je nach der verwendeten Initialisierungsmethode zu unterschiedlichen Ergebnissen führen kann. Dies bedeutet, dass mehrere Durchläufe des Algorithmus mit unterschiedlichen Initialisierungen erforderlich sein können, um eine stabile Clustering-Lösung zu erhalten.

Beim k-Means-Clustering wird außerdem davon ausgegangen, dass die Cluster kugelförmig sind und die gleiche Varianz haben. Dies ist in Situationen, in denen die Daten eine komplexere Struktur aufweisen oder in denen die Cluster unterschiedliche Formen und Größen haben, möglicherweise nicht angemessen. In solchen Fällen können alternative Clustering-Algorithmen besser geeignet sein.

Schließlich kann das k-means-Clustering empfindlich auf Ausreißer reagieren, da diese die Zentroide vom Hauptcluster wegziehen können. Dies kann zu suboptimalen Clusterzuweisungen führen und erfordert möglicherweise Vorverarbeitungsschritte wie die Entfernung von Ausreißern, um die Ergebnisse zu verbessern.

Insgesamt ist das k-means-Clustering zwar ein leistungsfähiger Algorithmus für das unüberwachte maschinelle Lernen, hat aber mehrere Einschränkungen, die bei der Anwendung in der Praxis berücksichtigt werden sollten. Es ist wichtig, die Anzahl der Cluster und die Initialisierungsmethode sorgfältig auszuwählen und die Ergebnisse mit geeigneten Metriken und Visualisierungen zu bewerten. Darüber hinaus kann es notwendig sein, alternative Clustering-Algorithmen in Situationen in Betracht zu ziehen, in denen die Annahmen des k-means Clustering nicht erfüllt sind.

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.