Was ist K-Means-Clustering?

K-Means-Clustering ist ein unsupervised Learning-Algorithmus, und von allen unsupervised Learning-Algorithmen ist K-Means-Clustering vielleicht der am weitesten verbreitete, dank seiner Leistung und Einfachheit. Wie funktioniert K-Means-Clustering genau?

Die kurze Antwort ist, dass K-Means-Clustering durch Erstellung eines Referenzpunkts (eines Zentrums) für eine gewünschte Anzahl von Klassen und dann Zuweisung von Datenpunkten zu Klassen-Clustern basierend auf dem nächsten Referenzpunkt funktioniert. Während dies eine schnelle Definition für K-Means-Clustering ist, nehmen wir uns ein wenig Zeit, um tiefer in K-Means-Clustering einzutauchen und ein besseres Verständnis dafür zu bekommen, wie es funktioniert.

Definition von Clustering

Bevor wir die genauen Algorithmen untersuchen, die zur Durchführung von K-Means-Clustering verwendet werden, nehmen wir uns ein wenig Zeit, um Clustering im Allgemeinen zu definieren.

Cluster sind einfach Gruppen von Elementen, und Clustering ist einfach das Zuordnen von Elementen zu diesen Gruppen. Im Sinne der Datenwissenschaft zielen Clustering-Algorithmen darauf ab, zwei Dinge zu tun:

• Sicherzustellen, dass alle Datenpunkte in einem Cluster so ähnlich wie möglich sind.
• Sicherzustellen, dass alle Datenpunkte in verschiedenen Clustern so unähnlich wie möglich sind.

Clustering-Algorithmen gruppieren Elemente basierend auf einem Ähnlichkeitsmaß. Dies geschieht oft durch Finden des “Zentrums” der verschiedenen möglichen Gruppen im Datensatz, wenn auch nicht ausschließlich. Es gibt verschiedene Clustering-Algorithmen, aber das Ziel aller Clustering-Algorithmen ist das gleiche, die Gruppen im Datensatz zu bestimmen.

K-Means-Clustering

K-Means-Clustering ist einer der ältesten und am weitesten verbreiteten Arten von Clustering-Algorithmen und basiert auf Vektorquantisierung. Es gibt einen Punkt im Raum, der als Ursprung gewählt wird, und dann werden Vektoren von dem Ursprung zu allen Datenpunkten im Datensatz gezeichnet.

Im Allgemeinen kann K-Means-Clustering in fünf verschiedene Schritte unterteilt werden:

• Alle Instanzen in Teilmengen einordnen, wobei die Anzahl der Teilmengen gleich K ist.
• Den Mittelpunkt/Zentrum der neu erstellten Cluster-Partitionen finden.
• Basiert auf diesen Zentren, jeden Punkt einem bestimmten Cluster zuweisen.
• Die Entfernungen von jedem Punkt zu den Zentren berechnen und Punkte den Clustern zuweisen, in denen die Entfernung zum Zentrum minimal ist.
• Nachdem die Punkte den Clustern zugewiesen wurden, das neue Zentrum der Cluster finden.

Die obigen Schritte werden wiederholt, bis der Trainingsprozess abgeschlossen ist.

In der Anfangsphase werden Zentren irgendwo unter den Datenpunkten platziert.
Foto: Weston.pace via wikimedia commons, GNU Free Documentation License (https://commons.wikimedia.org/wiki/File:K_Means_Example_Step_1.svg)

Alternativ können wir, nachdem die Zentren platziert wurden, K-Means-Clustering als Wechseln zwischen zwei verschiedenen Phasen betrachten: Datenpunkte beschriften und Zentren aktualisieren.

Im zweiten Schritt wird ein Entfernungsmaß wie die euklidische Entfernung verwendet, um zu berechnen, welches Zentrum ein gegebener Punkt am nächsten liegt, und dann werden die Punkte dem Cluster des Zentrums zugewiesen. Foto: Weston.pace via Wikimedia Commons, GNU Free Doc License (https://commons.wikimedia.org/wiki/File:K_Means_Example_Step_2.svg)

In der Phase der Beschriftung von Datenpunkten wird jeder Datenpunkt einem Cluster zugewiesen, der dem nächsten Zentrum gehört. Das nächste Zentrum wird typischerweise unter Verwendung der quadrierten euklidischen Entfernung bestimmt, obwohl andere Entfernungsmaße wie Manhattan-Entfernung, Cosinus und Jaccard-Entfernung je nach Art der in den Clustering-Algorithmus eingegebenen Daten verwendet werden können.

Im dritten Schritt werden die Zentren zum Mittelwert aller Datenpunkte im Cluster verschoben. Die Klassen werden dann neu zugewiesen. Foto: Weston.pace via Wikiemedia Commons, CC SA 3.0 (https://commons.wikimedia.org/wiki/File:K_Means_Example_Step_3.svg)

In der Phase der Zentrumaktualisierung werden die Zentren durch Finden des Mittelwerts der Entfernungen zwischen allen Datenpunkten im Cluster berechnet.

Wie wählt man den richtigen Wert für “K”?

Da K-Means-Clustering ein unsupervised Algorithmus ist und die Anzahl der Klassen im Voraus nicht bekannt ist, wie entscheidet man sich für die richtige Anzahl von Klassen/den richtigen Wert für K?

Eine Technik zur Auswahl des richtigen K-Werts ist die sogenannte “Ellbogen-Technik”. Die Ellbogen-Technik besteht darin, einen K-Means-Clustering-Algorithmus für eine Reihe von verschiedenen K-Werten auszuführen und ein Genauigkeitsmaß, typischerweise die Summe der quadrierten Fehler, zu verwenden, um zu bestimmen, welche Werte von K die besten Ergebnisse liefern. Die Summe der quadrierten Fehler wird durch Berechnen des Mittelwerts der Entfernung zwischen dem Zentrum eines Clusters und den Datenpunkten in diesem Cluster bestimmt.

Der Begriff “Ellbogen-Technik” kommt von der Tatsache, dass, wenn man die SSE in Bezug auf die verschiedenen Werte von K plottet, die resultierende Linie oft eine “Ellbogen”-Form hat, bei der die SSE für die ersten paar Werte von K schnell abnimmt, aber dann abflacht. In solchen Fällen ist der Wert von K, der am Ellbogen liegt, der beste Wert für K, da es nach diesem Wert schnell abnehmende Renditen gibt.

Mini-Batch-K-Means-Clustering

Da Datensätze größer werden, nimmt auch die Rechenzeit zu. Das grundlegende K-Means-Clustering kann bei der Ausführung auf große Datensätze viel Zeit in Anspruch nehmen, und als Ergebnis wurden Anpassungen an K-Means-Clustering vorgenommen, um die räumlichen und zeitlichen Kosten des Algorithmus zu reduzieren.

Mini-Batch-K-Means-Clustering ist eine Variante von K-Means-Clustering, bei der die Größe des Datensatzes, der berücksichtigt wird, begrenzt ist. Normales K-Means-Clustering wird auf dem gesamten Datensatz/Batch auf einmal ausgeführt, während Mini-Batch-K-Means-Clustering den Datensatz in Teilmengen unterteilt. Mini-Batches werden zufällig aus dem gesamten Datensatz ausgewählt und für jede neue Iteration wird ein neuer zufälliger Stichprobenwert ausgewählt und zur Aktualisierung der Position der Zentren verwendet.

Bei Mini-Batch-K-Means-Clustering werden Cluster mit einer Kombination der Mini-Batch-Werte und einer Lernrate aktualisiert. Die Lernrate nimmt über die Iterationen ab, und sie ist das Inverse der Anzahl der Datenpunkte, die in einem bestimmten Cluster platziert werden. Die Wirkung der Verringerung der Lernrate ist, dass der Einfluss neuer Daten verringert wird und die Konvergenz erreicht wird, wenn nach mehreren Iterationen keine Änderungen in den Clustern mehr vorliegen.

Die Ergebnisse von Studien über die Wirksamkeit von Mini-Batch-K-Means-Clustering deuten darauf hin, dass es die Rechenzeit erfolgreich reduzieren kann, mit einem leichten Trade-off in der Clusterqualität.

Anwendungen von K-Means-Clustering

K-Means-Clustering kann sicher in jeder Situation verwendet werden, in der Datenpunkte in verschiedene Gruppen/Klassen unterteilt werden können. Hier sind einige Beispiele für gängige Anwendungsfälle für K-Means-Clustering.

K-Means-Clustering kann auf Dokumentenklassifizierung angewendet werden, indem Dokumente basierend auf Merkmalen wie Themen, Tags, Wortverwendung, Metadaten und anderen Dokumentenmerkmalen gruppiert werden. Es kann auch verwendet werden, um Benutzer als Bots oder nicht-Bots basierend auf Aktivitätsmustern wie Posts und Kommentaren zu klassifizieren. K-Means-Clustering kann auch verwendet werden, um Menschen in Gruppen basierend auf Besorgnisniveaus bei der Überwachung ihrer Gesundheit zu unterteilen, basierend auf Merkmalen wie Komorbiditäten, Alter, Patientengeschichte usw.

K-Means-Clustering kann auch für offene Aufgaben wie die Erstellung von Empfehlungssystemen verwendet werden. Benutzer eines Systems wie Netflix können basierend auf Anzeigemustern gruppiert und ähnliche Inhalte empfohlen werden. K-Means-Clustering kann auch für Anomalie-Erkennungsaufgaben verwendet werden, um potenzielle Fälle von Betrug oder fehlerhaften Artikeln hervorzuheben.