算法原理
原理很簡(jiǎn)單，我就不細(xì)說(shuō)了（如果這還看不懂，建議補(bǔ)一下數(shù)學(xué)知識(shí)），直接參考周志華老師的《機(jī)器學(xué)習(xí)》俏蛮，上面也把算法的實(shí)現(xiàn)過(guò)程總結(jié)了。
算法流程分析
下面先看一下算法的流程上遥，分析搏屑、理解每一個(gè)步驟才能正確寫(xiě)出程序。
算法過(guò)程第3行：初始化聚類(lèi)結(jié)果的存儲(chǔ)變量
算法過(guò)程第5行：計(jì)算m個(gè)樣本分別到k個(gè)均值向量的距離辣恋，dji表示第j個(gè)樣本到第i個(gè)均值向量的距離。（注意：這個(gè)步驟要計(jì)算第j個(gè)樣本分別到i = 1,2,...,k個(gè)均值向量的距離）
算法過(guò)程第6行：從第5行的結(jié)果中模软，選出第j個(gè)樣本到各個(gè)均值向量的最小距離伟骨，確定該樣本的簇標(biāo)記。
算法過(guò)程第7行：將第j個(gè)樣本按照簇標(biāo)記放入到存儲(chǔ)變量C對(duì)應(yīng)的位置燃异。
算法過(guò)程第4~8行則是根據(jù)樣本到均值向量的距離携狭，將樣本分別劃分到距離均值向量最小的那標(biāo)記下，實(shí)現(xiàn)了樣本根據(jù)圍繞均值向量的緊密程度劃分到不同的類(lèi)中特铝。
算法過(guò)程第9~16行：重新計(jì)算C中每個(gè)簇類(lèi)下樣本的均值向量暑中，然后與原均值向量進(jìn)行比較壹瘟，如果重新計(jì)算后的均值向量與原均值向量不相等鲫剿，則更新均值向量，否則不更新稻轨。
最后如果所有的均值向量都不需要更新灵莲，則算法結(jié)束，這個(gè)時(shí)候算法已經(jīng)收斂了殴俱。
完整的實(shí)現(xiàn)代碼
import numpy as np
from numpy import *
import matplotlib.pyplot as plt
import math
#計(jì)算兩個(gè)向量之間的距離
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均值聚類(lèi)算法
#輸入數(shù)據(jù)：X是輸入的訓(xùn)練數(shù)據(jù)矩陣政冻，每一列是一簇
#輸入數(shù)據(jù)：K是要分的類(lèi)數(shù)量
#返回?cái)?shù)據(jù)：分好類(lèi)的列表
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
#隨機(jī)選取三個(gè)值作為均值向量
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)
測(cè)試數(shù)據(jù)
本文的測(cè)試數(shù)據(jù)與周志華老師的《機(jī)器學(xué)習(xí)》這本書(shū)上的一致枚抵，初始化參數(shù)也是一樣的。
測(cè)試數(shù)據(jù)：
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
書(shū)上的測(cè)試數(shù)據(jù)
#隨機(jī)選取三個(gè)值作為均值向量
miu[0, :] = X[5, :]
miu[1, :] = X[11, :]
miu[2, :] = X[26, :]
書(shū)上的初始化參數(shù)：
