[PYTHON] Verstehe k-means ++
Einführung
Ich habe zuvor Artikel über k-means gepostet. Da k-means ein Problem der Abhängigkeit von Anfangswerten hat, wurde ein Algorithmus namens k-means ++ entwickelt, um es zu überwinden. Dieses Mal habe ich zusammengefasst, was ich über k-means ++ gelernt habe.
Referenz
Um k-means ++ zu verstehen, habe ich mich auf Folgendes bezogen.
- Einführung in maschinelles Lernen für die Sprachverarbeitung (Natural Language Processing Series) Daiya Takamura (Autorin), Manabu Okumura (betreut) Herausgeber, Corona
- Essenz des maschinellen Lernens Koichi Kato (Autor) Herausgeber; SB Creative Co., Ltd.
- k-means ++ method-Wikipedia
Über k-means ++
Überprüfung der k-Mittel
Übersicht über k-means
k-means ist ein Algorithmus, der die Daten zuerst in geeignete Cluster unterteilt und dann die Daten so anpasst, dass sie unter Verwendung des Durchschnitts der Cluster gut aufgeteilt werden. Es wird als k-Mittelwert-Methode (k-Punkt-Mittelungsmethode) bezeichnet, da es sich um einen Algorithmus handelt, der k Cluster mit beliebiger Bezeichnung erzeugt.
k-bedeutet Algorithmus
Insbesondere folgt k-means dem folgenden Prozess.
- Ordnen Sie jedem Punkt $ x_ {i} $ zufällig Cluster zu
- Berechnen Sie den Schwerpunkt für die jedem Cluster zugewiesenen Punkte
- Berechnen Sie für jeden Punkt den oben berechneten Abstand vom Schwerpunkt und weisen Sie ihn dem Cluster mit dem nächstgelegenen Abstand neu zu.
- Wiederholen Sie die Schritte 2 und 3, bis der zugewiesene Cluster unverändert bleibt.
Probleme mit k-Mitteln
** Da k-means zu Beginn Cluster zufällig zuweist, kann sein Anfangswert zu einer Clusterbildung führen, die alles andere als optimal ist. Außerdem dauert es sehr lange, bis das Ergebnis abhängig vom Anfangswert konvergiert. ** **.
k-means++
Übersicht über k-means ++
k-means ++ ist ein Algorithmus, der darauf abzielt, das obige Anfangswertabhängigkeitsproblem zu überwinden. ** k-means ++ basiert auf der Idee, dass die Zentren der anfänglichen Cluster voneinander getrennt werden sollten **, und die anfängliche Clusterzuweisung wird wahrscheinlich entsprechend dem Abstand zwischen Datenpunkten zugewiesen. Ich werde.
k-bedeutet ++ Algorithmus
- Wählen Sie zufällig einen Punkt aus jedem Punkt $ x_ {i} $ aus und verwenden Sie ihn als Mittelpunkt des Clusters.
- Berechnen Sie für jeden Punkt $ x_ {i} $ den Abstand $ D (x) $ vom vorhandenen Clusterzentrum zum nächsten Clusterzentrum.
- Wählen Sie zufällig neue Clusterzentren mit der gewichteten Wahrscheinlichkeitsverteilung $ \ frac {D (x) ^ 2} {\ sum_ {} D (x) ^ 2} $ für jeden Punkt $ x_ {i} $ aus
- Wiederholen Sie die Schritte 2 und 3, bis k Cluster-Zentren ausgewählt werden können.
Wie oben erwähnt, versuchen wir, das Anfangswertabhängigkeitsproblem zu lösen, indem wir den anfänglichen Clustermittelpunkt basierend auf dem Abstand zwischen den Datenpunkten probabilistisch bestimmen. ** **.
Implementiere k-means ++
Implementierung von k-means ++ ohne Verwendung einer Bibliothek
Das Folgende ist eine Implementierung der k-means-Methode ohne Verwendung einer Bibliothek. Basierend auf dem in Essence of Machine Learning beschriebenen k-means-Code habe ich ihn selbst geändert, als ich zu k-means ++ gewechselt habe. Ich bin.
import numpy as np
class KMeans_pp:
def __init__(self, n_clusters, max_iter = 1000, random_seed = 0):
self.n_clusters = n_clusters
self.max_iter = max_iter
self.random_state = np.random.RandomState(random_seed)
def fit(self, X):
#Bestimmen Sie zufällig den ersten Clusterpunkt
tmp = np.random.choice(np.array(range(X.shape[0])))
first_cluster = X[tmp]
first_cluster = first_cluster[np.newaxis,:]
#Berechnen Sie das Quadrat des Abstands zwischen dem ersten Clusterpunkt und den anderen Datenpunkten und dividieren Sie jeden durch seine Summe
p = ((X - first_cluster)**2).sum(axis = 1) / ((X - first_cluster)**2).sum()
r = np.random.choice(np.array(range(X.shape[0])), size = 1, replace = False, p = p)
first_cluster = np.r_[first_cluster ,X[r]]
#Wenn die Anzahl der zu teilenden Cluster 3 oder mehr beträgt
if self.n_clusters >= 3:
#Wiederholen Sie diesen Vorgang, bis Sie die angegebene Anzahl von Clusterpunkten angeben können
while first_cluster.shape[0] < self.n_clusters:
#Berechnen Sie das Quadrat der Entfernung zwischen jedem Clusterpunkt und jedem Datenpunkt
dist_f = ((X[:, :, np.newaxis] - first_cluster.T[np.newaxis, :, :])**2).sum(axis = 1)
#Welcher Clusterpunkt ist Ihnen am nächsten?
f_argmin = dist_f.argmin(axis = 1)
#Ableitung des Quadrats der Entfernung zwischen dem nächsten Clusterpunkt und jedem Datenpunkt
for i in range(dist_f.shape[1]):
dist_f.T[i][f_argmin != i] = 0
#Leiten Sie wahrscheinlich neue Clusterpunkte ab
pp = dist_f.sum(axis = 1) / dist_f.sum()
rr = np.random.choice(np.array(range(X.shape[0])), size = 1, replace = False, p = pp)
#Fügen Sie neue Clusterpunkte als Anfangswerte hinzu
first_cluster = np.r_[first_cluster ,X[rr]]
#Machen Sie die erste Beschriftung
dist = (((X[:, :, np.newaxis] - first_cluster.T[np.newaxis, :, :]) ** 2).sum(axis = 1))
self.labels_ = dist.argmin(axis = 1)
labels_prev = np.zeros(X.shape[0])
count = 0
self.cluster_centers_ = np.zeros((self.n_clusters, X.shape[1]))
#Endet, wenn sich der Cluster, zu dem jeder Datenpunkt gehört, nicht ändert oder eine bestimmte Anzahl von Wiederholungen überschreitet
while (not (self.labels_ == labels_prev).all() and count < self.max_iter):
#Berechnen Sie den Schwerpunkt jedes Clusters zu diesem Zeitpunkt
for i in range(self.n_clusters):
XX = X[self.labels_ == i, :]
self.cluster_centers_[i, :] = XX.mean(axis = 0)
#Runden Sie den Abstand zwischen jedem Datenpunkt und dem Schwerpunkt jedes Clusters ab
dist = ((X[:, :, np.newaxis] - self.cluster_centers_.T[np.newaxis, :, :]) ** 2).sum(axis = 1)
#Denken Sie an die vorherige Clusterbezeichnung. Wenn sich das vorherige Label und das Label nicht ändern, wird das Programm beendet.
labels_prev = self.labels_
#Weisen Sie als Ergebnis der Neuberechnung die Bezeichnung des Clusters zu, der der Entfernung am nächsten liegt
self.labels_ = dist.argmin(axis = 1)
count += 1
self.count = count
def predict(self, X):
dist = ((X[:, :, np.newaxis] - self.cluster_centers_.T[np.newaxis, :, :]) ** 2).sum(axis = 1)
labels = dist.argmin(axis = 1)
return labels
Überprüfung
Das Folgende ist eine Überprüfung, ob Clustering mit diesem Algorithmus wirklich möglich ist.
import matplotlib.pyplot as plt
#Erstellen Sie einen geeigneten Datensatz
np.random.seed(0)
points1 = np.random.randn(80, 2)
points2 = np.random.randn(80, 2) + np.array([4,0])
points3 = np.random.randn(80, 2) + np.array([5,8])
points = np.r_[points1, points2, points3]
np.random.shuffle(points)
#Erstellen Sie ein Modell, das in drei Cluster unterteilt werden soll
model = KMeans_pp(3)
model.fit(points)
print(model.labels_)
Dann sieht die Ausgabe so aus. Sie können sehen, dass die Beschriftungen den drei hervorragend zugeordnet sind.
[2 1 0 2 1 1 0 1 2 0 1 1 0 1 0 0 1 1 0 2 0 1 2 0 1 2 0 2 1 2 1 1 1 0 1 0 1
2 2 1 1 1 1 2 0 1 1 1 0 2 1 0 2 1 0 1 0 2 2 2 2 2 1 0 1 0 0 1 1 1 1 1 0 1
0 0 0 2 1 0 2 0 1 1 0 1 2 0 2 2 2 0 0 0 2 0 0 0 2 0 2 1 1 1 1 1 0 1 2 1 2
0 1 2 2 1 2 0 2 2 2 0 0 2 0 2 1 2 2 0 1 2 1 2 2 2 1 0 2 1 1 2 0 0 0 2 1 1
1 0 0 0 1 1 2 0 1 0 0 0 2 0 0 0 0 0 2 2 1 2 0 2 2 0 1 2 2 2 2 1 0 2 1 2 2
0 2 0 0 0 2 0 1 2 0 0 0 1 1 1 1 2 2 0 2 2 2 0 0 1 1 2 2 0 1 1 2 1 2 2 0 2
1 2 0 2 1 2 0 0 2 2 0 2 0 2 1 2 2 0]
Lassen Sie uns dies mit matplotlib veranschaulichen.
markers = ["+", "*", "o", '+']
color = ['r', 'b', 'g', 'k']
for i in range(4):
p = points[model.labels_ == i, :]
plt.scatter(p[:, 0], p[:, 1], marker = markers[i], color = color[i])
plt.show()
Hier ist die Ausgabe. Sie können sehen, dass das Clustering problemlos abgeschlossen ist.
Versuchen Sie außerdem, die Anzahl der Versuche auszugeben, bis das Clustering konvergiert.
print(model.count)
4
Diesmal betrug die Anzahl der Versuche bis zur Konvergenz von k-means ++ vier. In ähnlicher Weise war das Ergebnis dreimal, wenn die Anzahl der Versuche mit gewöhnlichen k-Mitteln gezählt wurde. Ursprünglich soll k-means ++ weniger Zeit für die Konvergenz benötigen, daher möchte ich dies selbst überprüfen.
Next Ich möchte das Clustering durch gemischte Normalverteilung und das Clustering durch den EM-Algorithmus herausfordern.