Mit Sammlungen den Überblick behalten
Sie können Inhalte basierend auf Ihren Einstellungen speichern und kategorisieren.
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:
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.
Wählen Sie \(k\) Zentren zufällig aus.
Abbildung 1: K-Means bei der Initialisierung
Weisen Sie jeden Punkt dem nächstgelegenen Schwerpunkt zu, um \(k\) Anfangscluster zu erhalten.
Abbildung 2: Anfangscluster.
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.
Weisen Sie jeden Punkt dem nächstgelegenen neuen Centroid neu zu.
Abbildung 4: Cluster nach der Neuzuordnung.
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.
[null,null,["Zuletzt aktualisiert: 2025-02-25 (UTC)."],[[["\u003cp\u003eThe k-means clustering algorithm groups data points into clusters by minimizing the distance between each point and its cluster's centroid.\u003c/p\u003e\n"],["\u003cp\u003eK-means is efficient, scaling as O(nk), making it suitable for large datasets in machine learning, unlike hierarchical clustering methods.\u003c/p\u003e\n"],["\u003cp\u003eThe algorithm iteratively refines clusters by recalculating centroids and reassigning points until convergence or a stopping criteria is met.\u003c/p\u003e\n"],["\u003cp\u003eDue to random initialization, k-means can produce varying results; running it multiple times and selecting the best outcome based on quality metrics is recommended.\u003c/p\u003e\n"],["\u003cp\u003eK-means assumes data is composed of circular distributions, which may not be accurate for all real-world data containing outliers or density-based clusters.\u003c/p\u003e\n"]]],[],null,["# What is k-means clustering?\n\nAs previously mentioned, many clustering algorithms don't scale to the datasets\nused in machine learning, which often have millions of examples. For example,\nagglomerative or divisive hierarchical clustering algorithms look at all pairs\nof points and have complexities of \\\\(O(n\\^2 log(n))\\\\) and \\\\(O(n\\^2)\\\\),\nrespectively.\n\nThis course focuses on k-means because it scales as \\\\(O(nk)\\\\), where \\\\(k\\\\)\nis the number of clusters chosen by the user. This algorithm groups points into\n\\\\(k\\\\) clusters by minimizing the distances between each point and its\ncluster's centroid (see Figure 1).\n\nAs a result, k-means effectively treats data as composed of a number of roughly\ncircular distributions, and tries to find clusters corresponding to these\ndistributions. But real-world data contains outliers and density-based clusters\nand might not match the assumptions underlying k-means.\n\nk-means clustering algorithm\n----------------------------\n\nThe algorithm follows these steps:\n\n1. Provide an initial guess for \\\\(k\\\\), which can be revised later. For this\n example, we choose \\\\(k = 3\\\\).\n\n2. Randomly choose \\\\(k\\\\) centroids.\n\n \u003cbr /\u003e\n\n **Figure 1: k-means at initialization.**\n\n \u003cbr /\u003e\n\n3. Assign each point to the nearest centroid to get \\\\(k\\\\) initial clusters.\n\n \u003cbr /\u003e\n\n **Figure 2: Initial clusters.**\n\n \u003cbr /\u003e\n\n4. For each cluster, calculate a new centroid by taking the mean position of\n all points in the cluster. The arrows in Figure 4 show the change in\n centroid positions.\n\n \u003cbr /\u003e\n\n **Figure 3: Recomputed centroids.**\n\n \u003cbr /\u003e\n\n5. Reassign each point to the nearest new centroid.\n\n \u003cbr /\u003e\n\n **Figure 4: Clusters after reassignment.**\n\n \u003cbr /\u003e\n\n6. Repeat steps 4 and 5, recalculating centroids and cluster membership, until\n points no longer change clusters. In the case of large datasets, you can\n stop the algorithm before convergence based on other criteria.\n\nBecause the centroid positions are initially chosen at random, k-means can\nreturn significantly different results on successive runs. To solve this\nproblem, run k-means multiple times and choose the result with the best quality\nmetrics. (We'll describe quality metrics later in this course.) You'll need an\nadvanced version of k-means to choose better initial centroid positions.\n\nThough a deep understanding of the math is not necessary, for those who are\ncurious, k-means is a special case of the\n[expectation-maximization algorithm](https://wikipedia.org/wiki/Expectation%E2%80%93maximization_algorithm). See\n[lecture notes on the topic](https://alliance.seas.upenn.edu/%7Ecis520/dynamic/2021/wiki/index.php?n=Lectures.EM#toc-1.2) from UPenn."]]
