Clustering-Algorithmus ausführen

Beim maschinellen Lernen stoßen Sie manchmal auf Datasets, die Millionen von Beispielen enthalten können. ML-Algorithmen müssen effizient auf diese großen Datasets skaliert werden. Viele Clustering-Algorithmen skalieren jedoch nicht, da sie die Ähnlichkeit zwischen allen Punktpaaren berechnen müssen. Das bedeutet, dass ihre Laufzeiten mit dem Quadrat der Anzahl von Punkten erhöht werden, angegeben als \(O(n^2)\). Beispielsweise sehen sich Agglomerativ- oder dividative Hierarchie-Clustering-Algorithmen alle Paare von Punkten an und haben eine Komplexität von \(O(n^2 log(n))\) und \(O(n^2)\).

In diesem Kurs konzentrieren wir uns auf k-Means, da er als \(O(nk)\)skaliert wird. Dabei ist \(k\)die Anzahl der Cluster. k-means gruppiert Punkte in \(k\) Clustern, indem die Abstände zwischen Punkten und dem Schwerpunkt des Clusters minimiert werden (siehe Abbildung 1 unten). Der Schwerpunkt eines Clusters ist der Mittelwert aller Punkte im Cluster.

Wie gezeigt, findet k-means ungefähr kreisförmige Cluster. Das bedeutet konzeptionell, dass k-Means Daten effektiv aus einer Reihe von ungefähr zirkulären Verteilungen behandelt und versucht, Cluster zu finden, die diesen Distributionen entsprechen. In Wirklichkeit enthalten Daten Ausreißer und passen möglicherweise nicht in ein solches Modell.

Bevor Sie k-means ausführen, müssen Sie die Anzahl der Cluster \(k\)auswählen. Beginnen Sie mit einer Vermutung für \(k\). Später besprechen wir, wie Sie diese Zahl optimieren können.

k-Means-Clustering-Algorithmus

So werden k-means in \(k\) -Clustern gruppiert:

Abbildung 1: k-Means bei der Initialisierung

Schritt 1

Der Algorithmus wählt für jeden Cluster einen Schwerpunkt aus. In unserem Beispiel wählen wir \(k\) von 3 aus, sodass der Algorithmus 3 Schwerpunkte auswählt.

Abbildung 2: Erste Cluster

Schritt 2

Der Algorithmus weist jeden Punkt dem nächstgelegenen Schwerpunkt zu, um \(k\) erste Cluster zu erhalten.

Abbildung 3: Neuberechnung von Schwerpunkten

Schritt 3

Für jeden Cluster berechnet der Algorithmus den Schwerpunkt neu. Dazu wird der Durchschnitt aller Punkte im Cluster verwendet. Die Änderungen der Schwerpunkte sind in Abbildung 3 durch Pfeile dargestellt. Da sich die Schwerpunkte ändern, weist der Algorithmus die Punkte dem nächstgelegenen Schwerpunkt zu. Abbildung 4 zeigt die neuen Cluster nach der Neuzuweisung.

Abbildung 4: Cluster nach der Neuzuweisung

Schritt 4

Der Algorithmus wiederholt die Berechnung der Schwerpunkte und die Zuweisung von Punkten, bis sich die Cluster nicht mehr ändern. Wenn Sie große Datasets gruppieren, müssen Sie den Algorithmus beenden, bevor Sie die Konvergenz erreichen. Verwenden Sie stattdessen andere Kriterien.

Für diesen Kurs brauchen Sie die mathematischen Grundlagen nicht zu verstehen. Wenn Sie neugierig sind, finden Sie unten einen mathematischen Nachweis.

Klicken Sie auf das Pluszeichen für den mathematischen Nachweis.

Minimieren Sie anhand der Beispiele, die \(k\) -Clustern zugewiesen sind, die Summe der Entfernungen von Beispielen zu ihren Schwerpunkten. \(n\) Wobei:

• \(A_{nk} = 1\) wenn das \(n\)Beispiel dem \(k\). Cluster zugewiesen ist, andernfalls 0
• \(\theta_k\) ist der Schwerpunkt des Clusters \(k\)

Wir möchten den folgenden Ausdruck minimieren: $$\min_{A,\theta} \sum_{n=1}^N \sum_{k=1}^{K} A_{nk} ||\theta_k - x_n ||^2$$ subject: $$A_{nk} \in \{0,1\} \forall n,k$$ und $$\sum^{K}_{k=1}A_{nk}=1 \forall n$$ Wenn Sie den Ausdruck in Bezug auf die Clusterschwerpunkte \(\theta_k\)minimieren möchten, verwenden Sie die Ableitung in Bezug auf \(\theta_k\) und setzen Sie sie auf 0. $$f(\theta) = \sum^{N}_{n=1} \sum_{k=1}^{K} A_{nk} ||\theta_k - x_n||^2$$ $$\frac{\partial f}{\partial \theta_k} = 2 \sum_{n=1}^{N} A_{nk}(\theta_k - x_n) = 0$$ $$\implies \sum_{n=1}^{N} A_{nk}\theta_{k} = \sum^N_{n=1} A_{nk}x_{n}$$ $$\theta_k \sum_{n=1}^{N} A_{nk} = \sum_{n=1}^{N} A_{nk} x_n$$ $$\theta_k = \frac{\sum^N_{n=1} A_{nk} x_n}{\sum^N_{n=1} A_{nk}}$$ Der Zähler ist die Summe aller beispielmäßigen Entfernungen im Cluster. Der Nenner ist die Anzahl der Beispiele im Cluster. Der Clusterschwerpunkt\(\theta_k\) ist daher der Durchschnitt der Entfernungen des Beispielschwerpunkts im Cluster. Das hat sich also bewährt.

Da die Schwerpunktpositionen anfangs nach dem Zufallsprinzip ausgewählt werden, können k-Means bei aufeinanderfolgenden Ausführungen erheblich unterschiedliche Ergebnisse liefern. Führen Sie den Befehl „k-means“ mehrmals aus und wählen Sie das Ergebnis mit den besten Qualitätsmesswerten aus, um dieses Problem zu beheben. (Qualitätsmesswerte werden später in diesem Kurs genauer beschrieben.) Sie benötigen eine erweiterte Version von k-means, um bessere Anfangsherdenpositionen auszuwählen.

Test: Verwenden Sie den k-Means-Simulator von Stanford, um K-Means mehrmals auszuführen, um zu sehen, ob Sie unterschiedliche Ergebnisse erhalten.

Wichtige Begriffe:

• Schwerpunkt