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

Wir müssen die Anzahl der Cluster k bestimmen.
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.
Alle anderen Datenpunkte werden demjenigen Cluster zugeordnet, dessen Clusterzentrum den geringsten Abstand zum Datenpunkt hat.
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.
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 und das Clustering im Allgemeinen sind beliebt im Bereich des unüberwachten Lernens. Vor allem dann, wenn der Datensatz keine Labels besitzt, die konkrete vorhergesagt werden können, und trotzdem eine Gruppierung der Daten stattfinden soll. In diesem Abschnitt stellen wir einige der häufigsten Anwendungen des k-Means Clusterings vor.

Bildsegmentierung: Wenn Menschen Bilder anschauen erstellen sie bewusst oder unbewusst Segmente, die einzeln verarbeitet werden. In der Positionierung der Elemente steckt nämlich auch eine Information, also beispielsweise, ob ein Gegenstand in der Bildmitte oder in der rechten oberen Ecke zu sehen ist. Das k-Means Clustering ist dafür ein Vorverarbeitungsschritt in der Computer Vision, um Segmente mit ähnlicher Farbgebung oder Texturmerkmalen zu erkennen.
Kundensegmentierung: Unternehmen versuchen ihre Marketingstrategien an verschiedene Kundengruppen gezielt anzupassen, um eine möglichst ansprechende Kommunikation erstellen zu können. Dafür müssen diese Gruppen so gut definiert sein, dass die Kunden innerhalb einer Gruppe möglichst ähnlich sind und mit demselben Marketinginstrument angesprochen werden können. Das k-Means Clustering zeichnet sich dadurch aus, dass die Homogenität eines Clusters möglich hoch ist und wird deshalb oft in der Kundensegmentierung genutzt.
Anomalieerkennung: Bei der Erkennung von betrügerischen Aktivitäten beispielsweise bei E-Mails oder Banktransaktionen treffen häufig eine Großzahl von “gutartigen” Aktionen auf eine geringe Menge an Anomalien. Trotzdem können diese Betrugsaktivitäten einen großen Schaden anrichten, beispielsweise wenn eine falsche Banküberweisung getätigt wird. Deshalb sind Unternehmen bemüht eine möglichst genaue Anomalieerkennung zu nutzen, bei der häufig auch das k-Means Clustering zum Einsatz kommt.
Genomisches Clustering: In der Biologie versucht man zusammenhänge Gene oder Proteine zu finden, die auf Grundlage ihrer funktionellen Ähnlichkeiten zusammengefasst werden können. Auch hierfür kann das k-Means Clustering eingesetzt werden.
Analyse sozialer Netzwerke: Ähnlich wie bei der Kundensegmentierung wird auch in sozialen Netzwerken versucht, Nutzer mit ähnlichen Interessen oder ähnlichem Verhalten zu finden, um sie entweder miteinander in Verbindung zu bringen oder ihnen ähnliche Inhalte vorzuschlagen. Je nach Aufbau der Daten kann dafür ein k-Means Clustering zum Einsatz kommen.
Clustering von Dokumenten: Innerhalb von Unternehmen befinden sich oft eine Vielzahl von Dokumenten, die entweder Dopplungen sind oder die sich um ein ähnliches Thema drehen. Um Ordnung in diese riesigen Datensammlungen zu bringen kann man das k-Means Clustering nutzen.

Diese Auswahl an Beispielen zeigt deutlich die Vielfältigkeit des k-Means Clusterings und ihre breite Anwendbarkeit. Durch die Einfachheit und Vielseitigkeit ist dieser Algorithmus eine beliebte Wahl, wenn Daten gruppiert werden sollen.

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?

Zur Evaluierung des k-Means Clusterings können verschiedene Kennzahlen nach dem Training berechnet werden, um die Qualität der Cluster zu bewerten. Einige der gängigsten Kennzahlen sind:

Summe der Quadrate innerhalb eines Clusters: Dies ist die Summe der Abstände zwischen jedem Punkt in einem Cluster und dem Zentroid. Dieser Wert sollte minimiert werden, um ein entsprechend kompaktes Cluster mit ähnlichen Datenpunkten zu erhalten. Jedoch reicht dieser Wert als einzige Bewertung nicht aus, da er nur innerhalb eines Clusters misst.
Silhouetten-Wert: Mit dieser Kennzahl wird berechnet, wie gut die Zuordnung eines Datenpunkts zu einem Cluster ist und ob dieser nicht besser zu einem anderen Cluster passt. Die Werte liegen zwischen -1 und 1, wobei Werte um die -1 auf eine schlechte Zuordnung des Datenpunkts hinweisen.
Davies-Bouldin-Index (DBI): Dieser Index gibt Aufschluss darüber, wie ähnlich ein Cluster zu seinem nächst ähnlichen Cluster ist. Dabei sollte die Ähnlichkeit zwischen zwei Clustern möglichst gering sein, um eine klare Trennung zwischen Gruppen zu erzielen.
Calinski-Harabasz-Index (CHI): Mit dieser Kennzahl wird das Verhältnis der Varianz außerhalb eines Clusters zur Varianz innerhalb des Clusters berechnet. Ein hoher CHI – Wert weist dabei auf eine gute Gruppierung hin, da die Varianz innerhalb des Clusters niedrig und außerhalb des Clusters hoch ist.

Dies sind einige der wichtigsten Kennzahlen zur Bewertung eines Clusterings. Hierbei ist wichtig zu beachten, dass für die Evaluierung des Modells mehrere Kennzahlen berechnet und in die Bewertung mit einbezogen werden sollten, um aussagekräftige Ergebnisse zu erhalten.

Was sind die Grenzen von k-Means Clustering?

Trotz der weiten Verbreitung des k-Means Clustering hat auch dieser Algorithmus gewisse Nachteile oder Einschränkungen, die in der praktischen Anwendung beachtet werden sollten.

Der größte Nachteil des k-Means Clustering ist, dass die Anzahl der Cluster vor dem Start des Trainings bekannt sein muss. Zwar gibt es Möglichkeiten, die optimale Anzahl anhand der Daten zu finden, jedoch kann diese Anzahl nicht mit der übereinstimmen, die die Anwendung erfordert. Da die Clusteranzahl eine entscheidende Größe ist, die die Qualität der Ergebnisse massiv beeinflusst, sollte man hier genaue Untersuchungen anstellen.

Ein weiterer Nachteil tritt auch zu Beginn des Trainings auf, nämlich die Empfindlichkeit gegenüber der Initialisierung der Clusterzentren. Je nachdem welche Methode dafür gewählt wird, kann es zu unterschiedlichen Clusterzugehörigkeiten bei mehreren Trainingsdurchläufen kommen. Deshalb sollte man teilweise mehrere Durchläufe des Clusterings mit unterschiedlichen Initialisierungen durchführen, um eine stabile Vorhersage für die Gruppenzugehörigkeit zu bekommen.

Des Weiteren setzt das k-Means Clustering voraus, dass die Gruppen kugelförmig sind und somit alle die gleiche Varianz haben. Der Algorithmus optimiert darauf, dass die Abstände der Punkte zum Clusterzentrum innerhalb einer Gruppe minimiert werden. Dies impliziert jedoch, dass die optimale Gruppe innerhalb einer Kugel um das Clusterzentrum liegt. Gerade bei komplexeren Datenstrukturen ist dies nicht immer der Fall.

Ein letzter Nachteil ist die Anfälligkeit gegenüber Ausreißern, die sehr stark von anderen Daten abweichen und deshalb auch sehr weit vom Centroid entfernt liegen. Dadurch wird das Training und die Clusterzuweisung stark beeinträchtigt und es kann den Durchlauf des Algorithmus unnötig in die Länge ziehen. Nach Möglichkeit sollte deshalb vor dem Clustering eine Datenvorverarbeitung stattfinden, um Ausreißer aus dem Datensatz zu entfernen.

Trotz dieser Nachteile ist das k-Means Clustering ein leistungsfähiger Algorithmus innerhalb des Unsupervised Learnings, der für viele Anwendungen in der Praxis genutzt werden kann. Es ist jedoch vor allem sehr wichtig sich im Vorhinein über die Anzahl der Cluster und die Initialisierungsmethode Gedanken zu machen, um aussagekräftige Ergebnisse zu erhalten.

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.