Was ist K-Means-Clustering?

K-bedeutet Clustering ist ein unbeaufsichtigtes Lernen Algorithmus, und von allen unbeaufsichtigten Lernalgorithmen ist K-Means-Clustering aufgrund seiner Leistungsfähigkeit und Einfachheit möglicherweise der am weitesten verbreitete. Wie funktioniert K-Means-Clustering genau?

Die kurze Antwort ist, dass K-Means-Clustering funktioniert Einen Referenzpunkt (einen Schwerpunkt) erstellen für eine gewünschte Anzahl von Kursen und dann Zuweisen von Datenpunkten zu Klassenclustern basierend darauf, welcher Referenzpunkt am nächsten liegt. Während dies eine kurze Definition für K-Means-Clustering ist, nehmen wir uns etwas Zeit, um tiefer in K-Means-Clustering einzutauchen und einen besseren Einblick in seine Funktionsweise zu bekommen.

Clustering definieren

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

Cluster sind lediglich Gruppen von Elementen, und beim Clustering werden Elemente lediglich in diese Gruppen eingeteilt. Im datenwissenschaftlichen Sinne Clustering-Algorithmen Ziel ist es, zwei Dinge zu tun:

• Stellen Sie sicher, dass alle Datenpunkte in einem Cluster einander so ähnlich wie möglich sind.
• Stellen Sie sicher, dass alle Datenpunkte in verschiedenen Clustern möglichst unterschiedlich sind.

Clustering-Algorithmen gruppieren Elemente basierend auf einer Ähnlichkeitsmetrik. Dies geschieht häufig, jedoch nicht ausschließlich, durch Ermitteln des „Schwerpunkts“ der verschiedenen möglichen Gruppen im Datensatz. Es gibt eine Vielzahl unterschiedlicher Clustering-Algorithmen, aber das Ziel aller Clustering-Algorithmen ist das gleiche: die Bestimmung der Gruppen, die einem Datensatz innewohnen.

K-bedeutet Clustering

K-Means-Clustering ist einer der ältesten und am häufigsten verwendeten Arten von Clustering-Algorithmen und basiert auf Vektorquantisierung. Es wird ein Punkt im Raum als Ursprung ausgewählt und dann werden Vektoren vom Ursprung zu allen Datenpunkten im Datensatz gezeichnet.

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

• Ordnen Sie alle Instanzen in Teilmengen ein, wobei die Anzahl der Teilmengen gleich K ist.
• Finden Sie den mittleren Punkt/Schwerpunkt der neu erstellten Clusterpartitionen.
• Ordnen Sie jeden Punkt anhand dieser Schwerpunkte einem bestimmten Cluster zu.
• Berechnen Sie die Abstände von jedem Punkt zu den Schwerpunkten und weisen Sie den Clustern Punkte zu, bei denen der Abstand vom Schwerpunkt am geringsten ist.
• Nachdem die Punkte den Clustern zugewiesen wurden, ermitteln Sie den neuen Schwerpunkt der Cluster.

Die oben genannten Schritte werden wiederholt, bis der Trainingsprozess abgeschlossen ist.

In der Anfangsphase werden Schwerpunkte irgendwo zwischen den Datenpunkten platziert.
Foto: Weston.pace über Wikimedia Commons, GNU Free Documentation License (https://commons.wikimedia.org/wiki/File:K_Means_Example_Step_1.svg)

Alternativ können wir uns K-Means-Clustering nach dem Platzieren der Schwerpunkte als Hin- und Herwechseln zwischen zwei verschiedenen Phasen vorstellen: Beschriften von Datenpunkten und Aktualisieren von Schwerpunkten.

Im zweiten Schritt wird eine Distanzmetrik wie die euklidische Distanz verwendet, um zu berechnen, welchem ​​Schwerpunkt ein bestimmter Punkt am nächsten liegt, und dann werden die Punkte der Klasse dieses Schwerpunkts zugewiesen. Foto: Weston.pace über Wikimedia Commons, GNU Free Doc License (https://commons.wikimedia.org/wiki/File:K_Means_Example_Step_2.svg)

In der Datenpunkt-Beschriftungsphase wird jedem Datenpunkt eine Beschriftung zugewiesen, die ihn in den Cluster einordnet, der zum nächstgelegenen Schwerpunkt gehört. Der nächstgelegene Schwerpunkt wird normalerweise anhand der quadrierten euklidischen Distanz bestimmt, obwohl je nach Art der Daten, die in den Clustering-Algorithmus eingespeist werden, auch andere Distanzmetriken wie Manhattan-Distanz, Kosinus- und Jaccard-Distanz verwendet werden können.

Im dritten Schritt wird der Schwerpunkt auf den Durchschnitt aller Datenpunkte verschoben. Anschließend werden die Klassen neu zugeordnet. Foto: Weston.pace über Wikiemedia Commons, CC SA 3.0 (https://commons.wikimedia.org/wiki/File:K_Means_Example_Step_3.svg)

Im Schwerpunktaktualisierungsschritt wird der Schwerpunkt berechnet, indem der mittlere Abstand zwischen allen Datenpunkten ermittelt wird, die derzeit in einem Cluster enthalten sind.

So wählen Sie den richtigen Wert für „K“

Wenn man bedenkt, dass es sich beim K-Means-Clustering um einen unbeaufsichtigten Algorithmus handelt und die Anzahl der Klassen nicht im Voraus bekannt ist, wie entscheidet man dann über die angemessene Anzahl von Klassen/den richtigen Wert für K?

Eine Technik zur Auswahl des richtigen K-Werts heißt „die Ellenbogentechnik“. Die Ellbogentechnik besteht darin, einen K-Mittelwert-Clustering-Algorithmus für einen Bereich verschiedener K-Werte auszuführen und eine Genauigkeitsmetrik, typischerweise die Summe der quadratischen Fehler, zu verwenden, um zu bestimmen, welche K-Werte die besten Ergebnisse liefern. Die Summe der quadratischen Fehler wird durch Berechnen des mittleren Abstands zwischen dem Schwerpunkt eines Clusters und den Datenpunkten in diesem Cluster bestimmt.

Der Begriff „Ellenbogentechnik“ rührt daher, dass beim Zeichnen des SSE im Hinblick auf die verschiedenen Werte von K das resultierende Liniendiagramm häufig eine „Ellenbogenform“ aufweist, bei der der SSE für die ersten paar Werte von K schnell abnimmt. aber dann flacht es ab. Unter solchen Bedingungen ist der Wert von K am Ellenbogen der beste Wert für K, da die Erträge nach diesem Wert schnell abnehmen.

Mini-Batch-K-Means-Clustering

Wenn die Datensätze größer werden, nimmt auch die Rechenzeit zu. Einfaches K-Means-Clustering kann lange dauern, wenn es auf großen Datensätzen ausgeführt wird. Aus diesem Grund wurden Optimierungen am K-Means-Clustering vorgenommen, um die räumlichen und zeitlichen Kosten des Algorithmus zu reduzieren.

Mini-Batch K-bedeutet Clustering ist eine Variante des K-Means-Clusterings wobei die Größe des betrachteten Datensatzes begrenzt ist. Beim normalen K-Means-Clustering wird der gesamte Datensatz/Batch auf einmal bearbeitet, beim Mini-Batch-K-Means-Clustering Zerlegt den Datensatz in Teilmengen. Mini-Batches werden zufällig aus dem gesamten Datensatz entnommen und für jede neue Iteration wird eine neue Zufallsstichprobe ausgewählt und verwendet, um die Position der Schwerpunkte zu aktualisieren.

Beim Mini-Batch-K-Means-Clustering werden Cluster mit einer Kombination aus den Mini-Batch-Werten und einer Lernrate aktualisiert. Die Lernrate nimmt im Laufe der Iterationen ab und ist das Gegenteil der Anzahl der Datenpunkte, die in einem bestimmten Cluster platziert werden. Die Reduzierung der Lernrate führt dazu, dass die Auswirkungen neuer Daten verringert werden und Konvergenz erreicht wird, wenn nach mehreren Iterationen keine Änderungen in den Clustern auftreten.

Ergebnisse von Studien zur Wirksamkeit des Mini-Batch-K-Means-Clusterings legen nahe, dass es die Rechenzeit erfolgreich verkürzen kann, bei einem leichten Kompromiss bei 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 segmentiert werden können. Hier sind einige Beispiele für häufige Anwendungsfälle für K-Mean-Clustering.

K-Means-Clustering könnte auf die Dokumentklassifizierung angewendet werden, indem Dokumente basierend auf Merkmalen wie Themen, Tags, Wortverwendung, Metadaten und anderen Dokumentmerkmalen gruppiert werden. Es könnte auch verwendet werden, um Benutzer anhand von Aktivitätsmustern wie Beiträgen und Kommentaren als Bots oder Nicht-Bots zu klassifizieren. K-Means-Clustering kann auch verwendet werden, um Menschen auf der Grundlage des Grads der Besorgnis bei der Überwachung ihrer Gesundheit in Gruppen einzuteilen, basierend auf Merkmalen wie Komorbiditäten, Alter, Patientengeschichte usw.

K-Means-Clustering kann auch für offenere Aufgaben wie die Erstellung von Empfehlungssystemen verwendet werden. Benutzer eines Systems wie Netflix können anhand ihres Sehverhaltens und empfohlener ähnlicher Inhalte in Gruppen eingeteilt werden. K-Means-Clustering könnte für Anomalieerkennungsaufgaben verwendet werden, um potenzielle Betrugsfälle oder fehlerhafte Artikel hervorzuheben.