KMEANS détermine d'abord une position initiale appropriée et répète l'estimation et le calcul de la valeur centrale jusqu'à la convergence.Plus la position initiale est bonne, plus la précision est élevée et moins il y a de répétitions jusqu'à convergence. Il existe deux méthodes d'initialisation, RANDOM et k-means ++. Comme son nom l'indique, RANDOM sélectionne au hasard des échantillons pour le nombre de clusters et les utilise comme positions initiales. Dans k-means ++, le premier point est sélectionné au hasard, mais 2 À partir de la seconde, créez une distribution de probabilité avec D (x) ^ 2 de sorte que plus la distance est longue, plus la probabilité est élevée, et sélectionnez autant d'objets que possible que le nombre de clusters. L'explication ici est très facile à comprendre → https://www.medi-08-data-06.work/entry/kmeans
Comme j'ai pu faire KMEANS avec un micro-ordinateur, il est nécessaire d'effectuer un traitement d'initialisation aussi léger que KMEANS ++ et ne consomme pas de mémoire.
① Calculez la valeur moyenne de toutes les distances entre les valeurs centrales ② Estimer la grappe à laquelle appartient l'échantillon ③ Si la distance de ② est supérieure à la moitié de ① (la distance est considérée comme le diamètre et son rayon), elle est définie comme nouvelle valeur centrale. ④ Si le cluster est mis à jour avec un nouvel échantillon selon ③, passez à ①, sinon passez à ② Répétez ① à ④ pour toutes les données cibles
Le fait que la distance au moment de l'estimation par grappes d'un échantillon soit supérieure à la distance moyenne entre les valeurs centrales signifie que l'échantillon est une nouvelle grappe et que la distribution doit être plus large que la valeur centrale actuelle, donc jusqu'à ce que la distance moyenne entre les valeurs centrales soit élargie. L'idée est de l'élargir. C'est difficile à comprendre, mais je ne peux pas l'expliquer correctement, alors jetez un œil à la source.
iris
| En traitement | Itération moyenne | Distribution d'itération | Bonne réponse moyenne | Bonne dispersion des réponses |
|---|---|---|---|---|
| random | 6.418 | 2.174 | 0.763 | 0.1268 |
| k-means++ | 5.38 | 1.63 | 0.804 | 0.09 |
| Nouvelle méthode | 6.104 | 2.088 | 0.801 | 0.09 |
seeds
| En traitement | Itération moyenne | Distribution d'itération | Bonne réponse moyenne | Bonne dispersion des réponses |
|---|---|---|---|---|
| random | 9.109 | 3.237 | 0.921 | 0.0049 |
| k-means++ | 7.096 | 2.4284 | 0.921 | 0.0051 |
| Nouvelle méthode | 7.368 | 2.56 | 0.921 | 0.0046 |
Bien que ce ne soit pas aussi bon que k-means ++, je pense que le résultat est clairement meilleur que aléatoire, le nombre d'itérations est petit, la précision est élevée et la dispersion est faible, donc la variation du résultat semble faible. Ce serait bien s'il y en avait un peu plus et qu'il y avait un échantillon d'environ 8 grappes, mais il n'y en avait pas de pratique, alors j'ai décidé de tester uniquement l'iris et les graines. À propos, il semble que la méthode soit hautement compatible avec chaque échantillon car elle a une plus grande précision et un nombre réduit d'itérations que le test réel utilisé dans le travail réel. Le code source est affiché ci-dessous.
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
#Calculer la distance moyenne entre les valeurs centrales
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:
#S'il est plus grand que la distance moyenne entre les centres, alors l'échantillon est une nouvelle grappe.
means[predict] = ix
distanceThreshold = KmeansInit_CalcRadiusAverageDistance(means)
else:
#Si elle est égale ou inférieure à la distance moyenne entre les valeurs centrales, il s'agit d'une position raisonnable et la valeur centrale n'est pas mise à jour.
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
c'est tout
Recommended Posts