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 und ,
Dieser Kurs konzentriert sich auf k-Means, weil er auf skaliert wird, wobei
ist die Anzahl der vom Nutzer ausgewählten Cluster. Dieser Algorithmus gruppiert Punkte
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 an, die später überarbeitet werden kann. In diesem Fall
wählen wir beispielsweise aus.
Schwerpunkte 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, 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.
[null,null,["Zuletzt aktualisiert: 2024-07-22 (UTC)."],[[["The k-means clustering algorithm groups data points into clusters by minimizing the distance between each point and its cluster's centroid."],["K-means is efficient, scaling as O(nk), making it suitable for large datasets in machine learning, unlike hierarchical clustering methods."],["The algorithm iteratively refines clusters by recalculating centroids and reassigning points until convergence or a stopping criteria is met."],["Due to random initialization, k-means can produce varying results; running it multiple times and selecting the best outcome based on quality metrics is recommended."],["K-means assumes data is composed of circular distributions, which may not be accurate for all real-world data containing outliers or density-based clusters."]]],[]]