K-means clustering

K-means clustering的Python实现
交流群不相识的朋友突然问我怎么手写K-means…于是腾出时间简单写下。

Overview

k-平均算法源于信号处理中的一种向量量化方法,现在则更多地作为一种聚类分析方法流行于数据挖掘领域。k-平均聚类的目的是:把 n {\displaystyle n} n个点(可以是样本的一次观察或一个实例)划分到k个聚类中,使得每个点都属于离他最近的均值(此即聚类中心)对应的聚类,以之作为聚类的标准。这个问题将归结为一个把数据空间划分为Voronoi cells的问题。[wiki]

Theory

关于算法的步骤也是参考的WIKI,原理比较简单,不再重复叙述。

Code

这里的实现有几个需要改进的地方,这里放在前面指出。

  • [ ] 采用了循环,而不是向量化,矩阵化的运算
  • [ ] 收敛的判断,并没有按照分类是否恒定不变来判断收敛与否,而是以,所有质点新一次迭代前后空间距离的微小变化[自定义阀值]作为收敛的标准。[这里纯属个人想法,不知道是否有原则的错误0.0]

    2017.03.01补充
    今天再次搜索K-means算法,看到集智百科的关于次算法的介绍。恰好正是按照这种方法来判断算法的收敛。
    叙述是这样的

    可以看到下面算法收敛的判断准则就是质心的微小变化。[所以目前看来这样还是靠谱的0.0]
    但是呢,有些不太同意简介的开头:
    ++ “K-means算法是很典型的基于距离的聚类算法,采用距离作为相似性的评价指标,即认为两个对象的距离越近,其相似度就越大。该算法认为簇是由距离靠近的对象组成的,因此把得到紧凑且独立的簇作为最终目标。”++
    这里还是参考WIK的说法:
    ++“分配(Assignment):将每个观测分配到聚类中,使得组内平方和(WCSS)达到最小。因为这一平方和就是平方后的欧氏距离,所以很直观地把观测分配到离它最近得均值点即可 [8] 。(数学上,这意味依照由这些均值点生成的Voronoi图来划分上述观测)。”++

这里测试的data来自于那位朋友的题目,比较简单,见代码。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104



import random
import numpy as np
import matplotlib.pyplot as plt

# 获取数据
def getdata():
x = np.array([[i] for i in range(1, 101)])
y = np.array([[i] for i in range(51, 151)])
data = np.hstack((x, y))
return data

# 获取两点间的距离
def getdis(px, py):
dims = len(px)
# dist = np.sqrt(((px[0]-py[0])**2)+(px[1]-py[1])**2)
dist = np.sqrt(np.sum(((px[i] - py[i]) ** 2) for i in range(dims)))
return dist

# 用于首次随机获取质点
def getrandmeans(data, n):
means = []
for i in range(n):
x0 = random.choice(data)
means.append(x0)
print('Random: ', means)
return means

# 递归,重复计算所属类别,至收敛
def getclass(data, means):
classx = {}
for k in range(len(means)):
classx[str(k)] = []

for i in range(len(data)):
p0 = data[i]
dists = []
for k in range(len(means)):
dist = getdis(p0, means[k])
dists.append(dist)
maxdist = max(dists)
class_p0 = [i for i, j in enumerate(dists) if j==maxdist ][0]
classx[str(class_p0)].append(p0)


# print(means)
newmeans = getnewmeans(classx)
# 这里我们并未按照所属类别是否收敛,而后所得质心各维度的距离是否足够小
dists_of_means = getdis(np.sort(means, 0), np.sort(newmeans, 0))
print('alculating...')
if sum(dists_of_means > 0.001) == 0:
print('complete!')
print('求得的最优质点为: ', means)
print('各维度的距离为: ', dists_of_means)
print('最终聚类结果为: ', classx)
return classx

newclassx = getclass(data, newmeans)

return newclassx

def getnewmeans(classx):
classes = list(classx.keys())
means = [0 for i in range(len(classx))]
for class0 in classes:
if len(classx[class0]) != 0:
points = np.vstack(classx[class0])
x = np.mean(points[:, 0])
y = np.mean(points[:, 1])
means[int(class0)] = np.array([x, y])
else:
print('WARNING: 极大可能存在一个多余的质点!')
means[int(class0)] = np.array([0, 0])

return means

def plotdata(classx):
plt.figure()
classes = classx.keys()
color = ['ro', 'bo']
for class0 in range(len(classes)):
points = np.vstack(classx[str(class0)])
# print(points)
plt.plot(points[:, 0], points[:, 1], color[class0])
# print('=========================')
plt.show()

if __name__=='__main__':

data = getdata()
#print(data)
dist = getdis(data[0], data[1])
#print(dist)
means = getrandmeans(data, 2)
#print(means)

# print(classx)
classx = getclass(data, means)
plotdata(classx)



输出:

Random: [array([ 85, 135]), array([ 92, 142])]
alculating…
alculating…
alculating…
alculating…
alculating…
alculating…
alculating…
alculating…
complete!
求得的最优质点为: [array([ 75.5, 125.5]), array([ 25.5, 75.5])]
各维度的距离为: [ 0. 0.]
最终聚类结果为: {‘1’: [array([ 51, 101]), array([ 52, 102]), array([ 53, 103]), array([ 54, 104]),array([ 55, 105]), … , array([46, 96]), array([47, 97]), array([48, 98]), array([49, 99]), array([ 50, 100])]}

Supplement

关于上面的实现,开始时发现,每次运行作出来的图竟然不一样…调试发现时递归那里的问题。
就是关于return的问题,这里内部的return只是起到终止递归的作用,返回的是外面的return。抽象出来,类似下面这种

后面有时间会再针对上面的问题进行改进。

Reference

WIKI
StackOverflow
CodingLabs

击蒙御寇