Was ist k-Means-Clustering?

Wie bereits erwähnt, sind viele Clustering-Algorithmen nicht für die Datensätze geeignet, die im Bereich maschinelles Lernen verwendet werden und oft Millionen von Beispielen enthalten. Agglomerative oder divisive hierarchische Clusteralgorithmen betrachten beispielsweise alle Punktepaare und haben eine Komplexität von $O(n^2 log(n))$ bzw. $O(n^2)$.

In diesem Kurs liegt der Schwerpunkt auf K-Means, da es mit $O(nk)$skaliert, wobei $k$die vom Nutzer ausgewählte Anzahl der Cluster ist. Dieser Algorithmus gruppiert Punkte in$k$ -Cluster, indem die Entfernungen zwischen den einzelnen Punkten und dem Schwerpunkt des Clusters minimiert werden (siehe Abbildung 1).

Daher behandelt K-Means Daten effektiv als aus einer Reihe von ungefähr kreisförmigen Verteilungen bestehend und versucht, Cluster zu finden, die diesen Verteilungen entsprechen. Reale Daten enthalten jedoch Ausreißer und dichtebasierte Cluster und stimmen möglicherweise nicht mit den Annahmen überein, die K-Means zugrunde liegen.

K-Means-Clustering-Algorithmus

Der Algorithmus umfasst folgende Schritte:

1. Geben Sie eine erste Schätzung für $k$an, die später überarbeitet werden kann. Wählen Sie für dieses Beispiel $k = 3$aus.

2. Wählen Sie $k$  Zentren zufällig aus.

   

   Abbildung 1: K-Means bei der Initialisierung

3. Weisen Sie jeden Punkt dem nächstgelegenen Schwerpunkt zu, um $k$ Anfangscluster zu erhalten.

   

   Abbildung 2: Anfangscluster.

4. Berechnen Sie für jeden Cluster einen neuen Centroid, indem Sie die Mittelposition aller Punkte im Cluster ermitteln. Die Pfeile in Abbildung 4 zeigen die Änderung der Schwerpunktpositionen.

   

   Abbildung 3: Neu berechnete Schwerpunkte.

5. Weisen Sie jeden Punkt dem nächstgelegenen neuen Centroid neu zu.

   

   Abbildung 4: Cluster nach der Neuzuordnung.

6. Wiederholen Sie die Schritte 4 und 5 und berechnen Sie die Centroide und die Clustermitgliedschaft neu, bis sich die Punkte nicht mehr in Clustern ändern. Bei großen Datensätzen können Sie den Algorithmus anhand anderer Kriterien vor der Konvergenz beenden.

Da die Positionen der Schwerpunkte anfangs zufällig ausgewählt werden, können bei aufeinanderfolgenden Durchläufen mit K-Means deutlich unterschiedliche Ergebnisse erzielt werden. Führen Sie K-Means mehrmals aus und wählen Sie das Ergebnis mit den besten Qualitätsmesswerten aus. Qualitätsmesswerte werden später in diesem Kurs beschrieben. Sie benötigen eine erweiterte Version von K-Means, um bessere anfängliche Centroid-Positionen auszuwählen.

Ein tiefes Verständnis der Mathematik ist nicht erforderlich. Für Interessierte: K-Means ist ein Spezialfall des Erwartungswert-Maximierungs-Algorithmus. Vorlesungsnotizen zum Thema der UPenn