Wie bereits erwähnt, lassen sich viele Clustering-Algorithmen nicht auf die Datasets skalieren.
die beim maschinellen Lernen verwendet werden, die oft Millionen von Beispielen umfassen. Beispiel:
Agglomerative oder divisive hierarchische Clustering-Algorithmen betrachten alle Paare
von Punkten und haben die Komplexität \(O(n^2 log(n))\) und \(O(n^2)\),
Dieser Kurs konzentriert sich auf k-Means, weil er auf \(O(nk)\)skaliert wird, wobei \(k\)
ist die Anzahl der vom Nutzer ausgewählten Cluster. Dieser Algorithmus gruppiert Punkte
\(k\) Cluster, indem sie die Abstände zwischen den einzelnen Punkten minimieren
Schwerpunkt des Clusters (siehe Abbildung 1).
Daher behandelt k-Means Daten effektiv so, dass sie aus einer Reihe von grob
kreisförmige Verteilungen und versucht, Cluster zu finden, die diesen
Verteilungen. 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 geht so vor:
Geben Sie eine erste Schätzung für \(k\)an, die später überarbeitet werden kann. In diesem Fall
wählen wir beispielsweise \(k = 3\)aus.
Schwerpunkte \(k\) zufällig auswählen
<ph type="x-smartling-placeholder"></ph>
Abbildung 1: k-Means bei der Initialisierung
Weisen Sie jeden Punkt dem nächstgelegenen Schwerpunkt zu, \(k\) um erste Cluster zu erhalten.
<ph type="x-smartling-placeholder"></ph>
Abbildung 2: Erste Cluster
Berechnen Sie für jeden Cluster einen neuen Schwerpunkt, indem Sie die mittlere Position von
allen Punkten im Cluster. Die Pfeile in Abbildung 4 zeigen die Veränderung bei
Schwerpunktpositionen.
<ph type="x-smartling-placeholder"></ph>
Abbildung 3: Neu berechnete Schwerpunkte
Ordnen Sie jeden Punkt dem nächsten neuen Schwerpunkt zu.
<ph type="x-smartling-placeholder"></ph>
Abbildung 4: Cluster nach der Neuzuweisung
Wiederholen Sie die Schritte 4 und 5 und berechnen Sie Schwerpunkte und Clusterzugehörigkeit neu, bis
Punkte ändern Cluster nicht mehr. Bei großen Datasets können Sie
den Algorithmus vor der Konvergenz basierend
auf anderen Kriterien anhalten.
Da die Schwerpunkte anfänglich zufällig gewählt werden, kann k-Means
und bei aufeinanderfolgenden Durchläufen sehr unterschiedliche Ergebnisse liefern. Lösung
Problem zu lösen, führen Sie k-means mehrmals aus und wählen Sie das Ergebnis mit der besten Qualität aus.
Messwerte. (Wir werden die Qualitätsmetriken später in diesem Kurs beschreiben.) Sie benötigen eine
erweiterte Version von k-Means zur Auswahl besserer Anfangsschwerpunktpositionen.
