KMEANS ermittelt zunächst eine geeignete Anfangsposition und wiederholt die Schätzung und Berechnung des Mittelwerts bis zur Konvergenz. Je besser die Anfangsposition, desto höher die Genauigkeit und desto weniger Wiederholungen bis zur Konvergenz. Es gibt zwei Initialisierungsmethoden, RANDOM und k-means ++. Wie der Name schon sagt, wählt RANDOM zufällig Stichproben für die Anzahl der Cluster aus und verwendet sie als Anfangspositionen. In k-means ++ wird der erste Punkt zufällig ausgewählt, aber 2 Erstellen Sie ab dem zweiten eine Wahrscheinlichkeitsverteilung mit D (x) ^ 2, sodass die Wahrscheinlichkeit umso höher ist, je länger der Abstand ist, und wählen Sie so viele Objekte wie möglich aus, wie viele Cluster es gibt. Die Erklärung hier ist sehr leicht zu verstehen → https://www.medi-08-data-06.work/entry/kmeans
Da ich KMEANS mit einem Mikrocomputer ausführen konnte, muss eine Initialisierungsverarbeitung durchgeführt werden, die so leicht wie KMEANS ++ ist und keinen Speicher belegt.
① Berechnen Sie den Durchschnittswert aller Abstände zwischen den Mittelwerten ② Schätzen Sie den Cluster, zu dem die Stichprobe gehört ③ Wenn der Abstand von ② größer als die Hälfte von ① ist (der Abstand wird als Durchmesser und Radius betrachtet), wird er als neuer Mittelwert festgelegt. ④ Wenn der Cluster mit einem neuen Beispiel gemäß ③ aktualisiert wird, gehen Sie zu ①, andernfalls zu ② Wiederholen Sie ① bis ④ für alle Zieldaten
Die Tatsache, dass der Abstand zum Zeitpunkt der Clusterschätzung einer Stichprobe größer ist als der Abstandsdurchschnitt zwischen den Mittelwerten, bedeutet, dass die Stichprobe ein neuer Cluster ist und die Verteilung breiter als der aktuelle Mittelwert sein muss, bis sich der Abstandsmittelwert zwischen den Mittelwerten vergrößert. Die Idee ist, es zu erweitern. Es ist schwer zu verstehen, aber ich kann es nicht gut erklären, also schauen Sie sich bitte die Quelle an.
iris
| wird bearbeitet | Iterationsdurchschnitt | Iterationsverteilung | Richtiger Antwortdurchschnitt | Richtige Antwortstreuung |
|---|---|---|---|---|
| random | 6.418 | 2.174 | 0.763 | 0.1268 |
| k-means++ | 5.38 | 1.63 | 0.804 | 0.09 |
| Neue Methode | 6.104 | 2.088 | 0.801 | 0.09 |
seeds
| wird bearbeitet | Iterationsdurchschnitt | Iterationsverteilung | Richtiger Antwortdurchschnitt | Richtige Antwortstreuung |
|---|---|---|---|---|
| random | 9.109 | 3.237 | 0.921 | 0.0049 |
| k-means++ | 7.096 | 2.4284 | 0.921 | 0.0051 |
| Neue Methode | 7.368 | 2.56 | 0.921 | 0.0046 |
Obwohl es nicht so gut war wie k-means ++, denke ich, dass das Ergebnis deutlich besser als zufällig ist, die Anzahl der Iterationen gering ist, die Genauigkeit hoch ist und die Streuung gering ist, sodass das Ergebnis weniger variabel zu sein scheint. Es wäre schön, wenn es etwas mehr gäbe und es eine Stichprobe von ungefähr 8 Clustern gäbe, aber es gab keine geeignete, also entschied ich mich, nur Iris und Samen zu testen. Übrigens scheint die Methode mit jeder Probe sehr gut kompatibel zu sein, da sie eine höhere Genauigkeit und eine geringere Anzahl von Iterationen aufweist als der tatsächliche Test, der in der eigentlichen Arbeit verwendet wird. Der Quellcode ist unten angegeben.
def Kmeans_Predict(means, x):
distances = []
for m in means:
distances.append(np.linalg.norm(m - x))
predict = np.argmin(distances)
return distances[predict], predict
#Berechnen Sie den durchschnittlichen Abstand zwischen den Mittelwerten
def KmeansInit_CalcRadiusAverageDistance(means):
length = len(means)
avrDistance = 0
cnt = 0
for i in range(length):
for j in range(i):
if j == i: continue
avrDistance += np.linalg.norm(means[i] - means[j])
cnt += 1
return (avrDistance / cnt/ 2)
def KmeansInit_FarawayCentroids(n_clusters, x):
means = np.zeros((n_clusters, x.shape[1]))
distanceThreshold = 0
for cnt in range(1):
for ix in x:
distance, predict = Kmeans_Predict(means, ix)
if distance > distanceThreshold:
#Wenn es größer als der durchschnittliche Abstand zwischen den Zentren ist, ist die Stichprobe ein neuer Cluster.
means[predict] = ix
distanceThreshold = KmeansInit_CalcRadiusAverageDistance(means)
else:
#Wenn es gleich oder kleiner als der durchschnittliche Abstand zwischen den Mittelwerten ist, ist dies eine vernünftige Position und der Mittelwert wird nicht aktualisiert.
pass
return means
import math
import numpy as np
import sklearn.cluster
import sklearn.preprocessing
import sys
def Kmeans_Predict(means, x):
distances = []
for m in means:
distances.append(np.linalg.norm(m - x))
predict = np.argmin(distances)
return distances[predict], predict
def KmeansInit_CalcRadiusAverageDistance(means):
length = len(means)
avrDistance = 0
cnt = 0
for i in range(length):
for j in range(i):
if j == i: continue
avrDistance += np.linalg.norm(means[i] - means[j])
cnt += 1
return (avrDistance / cnt/ 2)
def KmeansInit_FarawayCentroids(n_clusters, x):
means = np.zeros((n_clusters, x.shape[1]))
distanceThreshold = 0
for cnt in range(1):
for ix in x:
distance, predict = Kmeans_Predict(means, ix)
if distance > distanceThreshold:
means[predict] = ix
distanceThreshold = KmeansInit_CalcRadiusAverageDistance(means)
return means
def loadIris():
data = np.loadtxt("./iris_dataset.txt", delimiter="\t", dtype=str)
length = len(data)
x = data[:,0:4].astype(np.float)
names = data[:,4]
nameList = np.unique(data[:,4])
y = np.zeros(length)
for i, name in enumerate(nameList):
y[names == name] = i
return x, y
def loadSeeds():
data = np.loadtxt("./seeds_dataset.txt", delimiter="\t", dtype=str)
length = len(data)
x = data[:,0:7].astype(np.float)
y = data[:,7].astype(float)
return x, y
def KmeansModel(init, n_clusters):
return sklearn.cluster.KMeans(
n_clusters=n_clusters,
init=init,
n_init=1,
max_iter=100,
tol=1e-5,
verbose=3
)
def CalcAccuracy(y, predicts):
answers = np.unique(y)
clusters = np.sort(np.unique(predicts))
accuracy = []
ignoreCluster = []
for ans in answers:
pred = predicts[y == ans]
total = []
totalClusters = []
for c in clusters:
if c in ignoreCluster:
continue
total.append(np.sum(pred == c))
totalClusters.append(c)
maxIdx = np.argmax(total)
ignoreCluster.append(totalClusters[maxIdx])
acc = total[maxIdx] / len(pred)
accuracy.append(acc)
return accuracy
def KmeansTestSub(init, n_clusters, x, y):
model = KmeansModel(init, n_clusters)
model.fit(x)
predicts = model.predict(x)
accuracy = CalcAccuracy(y, predicts)
return [model.n_iter_, np.mean(accuracy)] + list(accuracy)
def shuffleData(x, y):
idxs = np.arange(len(x))
np.random.shuffle(idxs)
x, y = x[idxs], y[idxs]
return x, y
def KmeansTest(dataset, n_clusters, prefix="", test_count=1000):
x, y = dataset
scaler = sklearn.preprocessing.StandardScaler()
scaler.fit(x)
x = scaler.transform(x)
# farway
report = []
for i in range(test_count):
x, y = shuffleData(x, y)
init = KmeansInit_FarawayCentroids(n_clusters, x)
rep = KmeansTestSub(init, n_clusters, x, y)
report.append(rep)
report = np.vstack([report, np.mean(report, axis=0)])
report = np.vstack([report, np.std(report, axis=0)])
np.savetxt("./{}report_farway.txt".format(prefix), report, delimiter="\t")
# random
report = []
for i in range(test_count):
rep = KmeansTestSub("random", n_clusters, x, y)
report.append(rep)
report = np.vstack([report, np.mean(report, axis=0)])
report = np.vstack([report, np.std(report, axis=0)])
np.savetxt("./{}report_random.txt".format(prefix), report, delimiter="\t")
# k-means++
report = []
for i in range(test_count):
rep = KmeansTestSub("k-means++", n_clusters, x, y)
report.append(rep)
report = np.vstack([report, np.mean(report, axis=0)])
report = np.vstack([report, np.std(report, axis=0)])
np.savetxt("./{}report_kmeansPP.txt".format(prefix), report, delimiter="\t")
def run():
KmeansTest(loadIris(), prefix="iris_", n_clusters=3)
KmeansTest(loadSeeds(), prefix="seeds_", n_clusters=3)
if __name__ == "__main__":
run()
# python kmeans_test.py
das ist alles
Recommended Posts