Was ist K-Means-Clustering?

K-Means-Clustering ist ein unüberwachtes Lernalgorithmus, und von allen unüberwachten Lernalgorithmen 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 Klassenclustern basierend auf dem nächsten Referenzpunkt funktioniert. Obwohl dies eine schnelle Definition für K-Means-Clustering ist, nehmen wir uns Zeit, um tiefer in K-Means-Clustering einzutauchen und ein besseres Verständnis dafür zu erhalten, wie es funktioniert.

Definition von Clustering

Bevor wir die genauen Algorithmen untersuchen, die für die 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:

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

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

K-Means-Clustering

K-Means-Clustering ist einer der ältesten und am häufigsten verwendeten Arten von Clustering-Algorithmen und funktioniert auf der Grundlage von Vektorquantisierung. Es gibt einen Punkt im Raum, der als Ursprung ausgewä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 Subsets einordnen, wobei die Anzahl der Subsets der Anzahl von K entspricht.
• Den Mittelpunkt/Zentrum der neu erstellten Clusterpartitionen 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 die 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 der euklidische Abstand verwendet, um zu berechnen, welches Zentrum ein gegebener Punkt am nächsten ist, und dann werden die Punkte der Klasse 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 einer Klasse zugewiesen, die dem nächstgelegenen Zentrum gehört. Das nächstgelegene Zentrum wird typischerweise unter Verwendung des quadrierten euklidischen Abstands bestimmt, obwohl auch andere Entfernungsmaße wie der Manhattan-Abstand, Cosinus und Jaccard-Abstand verwendet werden können, abhängig von der Art der Daten, die in den Clustering-Algorithmus eingegeben werden.

Im dritten Schritt werden die Zentren zur Durchschnittsposition aller Datenpunkte bewegt. 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 Aktualisierung der Zentren werden die Zentren durch das Finden des Mittelwerts der Entfernungen zwischen allen Datenpunkten im Cluster berechnet.

Auswahl des richtigen Wertes für “K”

Da K-Means-Clustering ein unüberwachter 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, den 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 die Berechnung des Mittelwerts der Entfernungen zwischen dem Zentrum eines Clusters und den Datenpunkten in diesem Cluster bestimmt.

Der Begriff “Ellbogen-Technik” kommt von der Tatsache, dass die resultierende Linienplot, wenn man die SSE in Bezug auf die verschiedenen Werte von K plottet, 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 die 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 Subsets unterteilt. Mini-Batches werden zufällig aus dem gesamten Datensatz ausgewählt und für jede neue Iteration wird ein neues zufälliges Sample ausgewählt und verwendet, um die Position der Zentren zu aktualisieren.

Bei Mini-Batch-K-Means-Clustering werden Cluster mit einer Kombination von Mini-Batch-Werten 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 sind. Der Effekt der Reduzierung der Lernrate ist, dass der Einfluss neuer Daten reduziert 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 mit einem leichten Kompromiss bei der Clusterqualität reduzieren kann.

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 häufige Anwendungsfälle von K-Means-Clustering.

K-Means-Clustering kann auf Dokumentenklassifizierung angewendet werden, bei der Dokumente basierend auf Merkmalen wie Themen, Tags, Wortverwendung, Metadaten und anderen Dokumentmerkmalen 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 basierend auf ihren Sorgen in Gruppen zu unterteilen, wenn ihre Gesundheit überwacht wird, basierend auf Merkmalen wie Begleiterkrankungen, 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 ihren Sehmustern gruppiert und ähnliche Inhalte empfohlen werden. K-Means-Clustering kann auch für Aufgaben zur Anomalie-Erkennung verwendet werden, um potenzielle Fälle von Betrug oder fehlerhaften Elementen hervorzuheben.