k means algorithm

k-means-Algorithmus

Dies ist eine Python-Implementierung des K-Means-Algorithmus einschließlich der Ellbogenmethode und der Silhouette-Methode zur Auswahl des optimalen K

K-means ist ein beliebter Clustering-Algorithmus, der zur Partitionierung von Daten in K-Cluster verwendet wird. Es funktioniert, indem es jeden Datenpunkt iterativ dem nächstgelegenen Cluster-Schwerpunkt zuordnet und dann den Schwerpunkt jedes Clusters basierend auf den ihm zugewiesenen Datenpunkten neu berechnet. Der Vorgang wird bis zur Konvergenz wiederholt.

Algorithmus

• Wählen Sie zufällig K anfängliche Clusterschwerpunkte aus den Datenpunkten aus.
• Ordnen Sie jeden Datenpunkt dem nächstgelegenen Clusterschwerpunkt zu.
• Berechnen Sie den Schwerpunkt jedes Clusters basierend auf den ihm zugewiesenen Datenpunkten neu.
• Wiederholen Sie die Schritte 2-3 bis zur Konvergenz (dh wenn sich die Clusterzuweisungen nicht mehr ändern).

Zielfunktion

Das Ziel von k-means besteht darin, die Summe der quadrierten Abstände zwischen jedem Datenpunkt und seinem zugewiesenen Clusterschwerpunkt zu minimieren. Die Zielfunktion kann wie folgt geschrieben werden: $$J = sum_{j=1}^K sum_{i=1}^N||x_i^j - mu_j||^2$$ Wo $x_i^j$ ist der i-th Datenpunkt innerhalb von Cluster j , μj ist der Schwerpunkt von Cluster j und N ist die Gesamtzahl der Datenpunkte.

Ellenbogenmethode

Die Elbow-Methode ist eine Heuristik zur Bestimmung der optimalen Anzahl von Clustern beim K-Means-Clustering. Die Methode zeichnet die Summe der quadrierten Abstände zwischen jeder Beobachtung und ihrem zugewiesenen Schwerpunkt als Funktion der Anzahl der Cluster auf. Der „Ellenbogen“-Punkt im Diagramm gibt die Anzahl der Cluster an, bei denen das Hinzufügen zusätzlicher Cluster nicht zu einer signifikanten Verringerung der Summe der quadrierten Abstände führt.

Die Elbow-Methode kann in den folgenden Schritten zusammengefasst werden:

• Führen Sie K-Means-Clustering für einen Bereich von k-Werten aus
• Berechnen Sie die Summe der quadrierten Abstände für jeden k-Wert
• Stellen Sie die Summe der quadrierten Abstände als Funktion von k dar
• Identifizieren Sie den „Ellenbogen“-Punkt auf dem Diagramm

Silhouette-Methode

Die Silhouette-Methode ist eine weitere Heuristik zur Bestimmung der optimalen Anzahl von Clustern beim K-Means-Clustering. Die Methode misst die Qualität der Clusterzuordnung jeder Beobachtung durch Berechnung ihres Silhouettenkoeffizienten. Der Silhouettenkoeffizient reicht von -1 bis 1, wobei ein Wert von 1 angibt, dass die Beobachtung gut geclustert ist, und ein Wert von -1 angibt, dass die Beobachtung falsch klassifiziert ist. Die Formel zur Berechnung des Silhouettenkoeffizienten für einen Datenpunkt i lautet: $$s(i) = frac{(b(i) - a(i))}{max(a(i), b(i))}$$ Dabei ist a(i) der durchschnittliche Abstand zwischen i und allen anderen Datenpunkten in seinem Cluster und b(i) der minimale durchschnittliche Abstand zwischen i und allen anderen Clustern (dh dem Cluster mit dem nächstnächsten Schwerpunkt). Der Silhouette-Koeffizient für das gesamte Clustering ist der Durchschnitt der Silhouette-Koeffizienten für alle Datenpunkte.

Die Silhouette-Methode kann in den folgenden Schritten zusammengefasst werden:

• Führen Sie K-Means-Clustering für einen Bereich von k-Werten aus
• Berechnen Sie für jede Beobachtung den Silhouettenkoeffizienten
• Berechnen Sie den durchschnittlichen Silhouettenkoeffizienten für jeden k-Wert
• Stellen Sie den durchschnittlichen Silhouettenkoeffizienten als Funktion von k dar
• Identifizieren Sie den k-Wert mit dem höchsten durchschnittlichen Silhouettenkoeffizienten