算法原理
原理很简单，我就不细说了（如果这还看不懂，建议补一下数学知识），直接参考周志华老师的《机器学习》，上面也把算法的实现过程总结了。
算法原理.PNG
算法流程分析
下面先看一下算法的流程，分析、理解每一个步骤才能正确写出程序。
算法的流程.PNG
算法过程第3行：初始化聚类结果的存储变量
算法过程第5行：计算m个样本分别到k个均值向量的距离，dji表示第j个样本到第i个均值向量的距离。（注意：这个步骤要计算第j个样本分别到i = 1,2,...,k个均值向量的距离）
算法过程第6行：从第5行的结果中，选出第j个样本到各个均值向量的最小距离，确定该样本的簇标记。
算法过程第7行：将第j个样本按照簇标记放入到存储变量C对应的位置。
算法过程第4~8行则是根据样本到均值向量的距离，将样本分别划分到距离均值向量最小的那标记下，实现了样本根据围绕均值向量的紧密程度划分到不同的类中。
算法过程第9~16行：重新计算C中每个簇类下样本的均值向量，然后与原均值向量进行比较，如果重新计算后的均值向量与原均值向量不相等，则更新均值向量，否则不更新。
最后如果所有的均值向量都不需要更新，则算法结束，这个时候算法已经收敛了。
完整的实现代码
import numpy as np
from numpy import *
import matplotlib.pyplot as plt
import math
#计算两个向量之间的距离
def get_dist(X1, X2):
N = shape(X1)[1]
dist = 0
for u in range(N):
dist += abs(float(X1[0, u] - X2[0, u])) ** 2
return sqrt(dist)
def mat_compare(x1, x2):
n = shape(x1)[1]
equal = True
for i in range(n):
if(x1[0, i] != x2[0, i]):
equal = False
return equal
#k均值聚类算法
#输入数据：X是输入的训练数据矩阵，每一列是一簇
#输入数据：K是要分的类数量
#返回数据：分好类的列表
def k_means(X_arr, K, iterator_counts):
X = mat(X_arr)
m,n = shape(X)
miu = mat(zeros((K, n)))
update_flag_mat = mat(zeros((1, K)))
C = []
cnt = 0
#随机选取三个值作为均值向量
miu[0, :] = X[5, :]
miu[1, :] = X[11, :]
miu[2, :] = X[26, :]
lamda = mat(zeros((m, 1)))
for i in range(K):
C.append([[0.0, 0.0]])
while(True):
d = mat(zeros((m, K)))
for j in range(m):
for k in range(K):
d[j, k] = get_dist(X[j, :], miu[k, :])
lamda[j, 0] = argmin(d[j, :])
mat_data = []
for i in range(n):
mat_data.append(float(X[j, i]))
index = int(lamda[j, 0])
(C[index]).append([float(X[j, 0]), float(X[j, 1])])
if(update_flag_mat[0, index] == 0):
update_flag_mat[0, index] = 1
del C[index][0]
update_flag = False
for i in range(K):
new_miu = mat(zeros((1, K)))
Ci = mat(array(C[i]))
new_miu = mean(Ci, axis = 0)
if(mat_compare(new_miu, miu[i, :]) == False):
update_flag = True
for j in range(n):
miu[i, j] = new_miu[0, j]
cnt += 1
if(cnt >= iterator_counts):
break
if(update_flag == False):
print("cnt = ", cnt)
#break
else:
C.clear()
update_flag_mat[0, :] = 0
for i in range(K):
C.append([[0.0, 0.0]])
return C
def load_data_set(file_name):
X = []
fd = open(file_name)
for line in fd.readlines():
line_data = line.strip().split()
X.append([float(line_data[0]), float(line_data[1])])
return np.array(X)
def show_experiment_plot(C):
D = mat(array(C[0]))
plt.plot(D[:, 0], D[:, 1], "or")
D = mat(array(C[1]))
plt.plot(D[:, 0], D[:, 1], "ob")
D = mat(array(C[2]))
plt.plot(D[:, 0], D[:, 1], "og")
plt.xlabel("X1")
plt.ylabel("X2")
plt.show()
if __name__ == "__main__":
X = load_data_set("data_set.txt")
C = k_means(X, 3, 6)
print(C[0])
print("-----------------------")
print(C[1])
print("-----------------------")
print(C[2])
print("-----------------------")
print(len(C))
show_experiment_plot(C)
测试数据
本文的测试数据与周志华老师的《机器学习》这本书上的一致，初始化参数也是一样的。
测试数据：
0.697 0.460
0.774 0.376
0.634 0.264
0.608 0.318
0.556 0.215
0.403 0.237
0.481 0.149
0.437 0.211
0.666 0.091
0.243 0.267
0.245 0.057
0.343 0.099
0.639 0.161
0.657 0.198
0.360 0.370
0.593 0.042
0.719 0.103
0.359 0.188
0.339 0.241
0.282 0.257
0.748 0.232
0.714 0.346
0.483 0.312
0.478 0.437
0.525 0.369
0.751 0.489
0.532 0.472
0.473 0.376
0.725 0.445
0.446 0.459
书上的测试数据
测试数据.PNG
#随机选取三个值作为均值向量
miu[0, :] = X[5, :]
miu[1, :] = X[11, :]
miu[2, :] = X[26, :]
书上的初始化参数：
初始化参数.PNG
实验结果1.PNG
实验结果2.PNG
书上实验结果.PNG
