python实现k-means分类算法

准备实现一些算法,顺带复习numpy,因此将比较简单的k-means算法用python实现一次。

k-means算法

upload successful

准备数据集

首先,考虑数据集来源。懒得去找数据,因此直接用scikit的dataset模块随机生成一组聚类数据。既然要生成聚类数据,用make_blobs是再好不过了。sklearn.dataset.make_blobs文档

为了直观地展示数据,用matplotlib来进行数据可视化。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
import numpy as np
from sklearn.datasets import make_blobs
import matplotlib.pyplot as plt

def generateDataAndShow():
plt.figure(figsize=(8,5))
plt.title("Dataset", fontsize='small')
datas, class_info = make_blobs(n_samples=200 ,n_features=2, centers=3)
plt.scatter(datas[:, 0], datas[:, 1], marker='o', c=class_info)
plt.show()
return datas

if __name__=='__main__':
data = generateDataAndShow()

可以得到一个有三个聚类,共200个点的数据集。如图所示

upload successful

且每次运行都会生成不同的数据。

此时,得到200对坐标数据以及相应的分类数据。仅将坐标数据拿出来进行计算。

算法实现

1、随机生成3个点,作为初始聚类中心。为了减少计算量,所以将3个点生成在所有点的值域中。此时data的数据结构是Float[][],第一重数组为一个点,第二重数组为点的两个坐标。因此需要用到numpy的amax函数与amin函数:

1
[x_max, y_max], [x_min, y_min] = np.amax(data,axis=0),np.amin(data,axis=0)

使用numpy.random的rand生成一组点:

1
2
3
centers = np.random.rand(3,2)
centers[0:,0] = (x_max-x_min)*centers[0:,0]+x_min
centers[0:,1] = (y_max-y_min)*centers[0:,1]+y_min

这样就得到了在值域内的3个随机点。

2、计算距离。二维平面内两个点的距离公式为

\[d=\sqrt{(x_1-x_2)^2+(y_1-y_2)^2}\]

因此可以计算出每个点分别到三个聚类中心的距离:

1
2
3
4
5
6
7
def distance(data, dots):
rs = []
for d in data:
rs.append([])
for dot in dots:
rs[-1].append(((d[0]-dot[0])**2+(d[1]-dot[1])**2)**0.5)
return rs

3、分组。根据计算得到的各个点距离聚类中心的距离,可以判断这个点是属于哪一个聚类的。

1
2
def classify(dis):
return [i.index(min(i)) for i in dis]

返回一个分类索引数组。这个时候也可以用plt将此时的分类打印出来,和最开始的正确聚类对比一下:

upload successful
upload successful

考虑一种特殊情况:只分出两个聚类。这时候将无法继续计算下去,应当重新随机生成中心。

4、移动聚类中心。根据随机得到的初始聚类,重新计算每个聚类的质心作为其新的聚类中心。

1
2
3
4
5
def calCenters(data, clazz):
clz = [[] for i in range(3)]
for index,dot in enumerate(data):
clz[clazz[index]].append(dot)
return [sum(x)/len(x) for x in clz]

得到了新的聚类中心

5、循环上述步骤,直到收敛。

1
2
3
4
5
6
while True:
new_centers = calCenters(data, clazz)
if equal(new_centers,centers):break
else:
centers = new_centers
clazz = classify(distance(data,centers))

收敛条件是聚类中心点不再变化。

最终代码:https://github.com/lsvih/algorithm-practice/blob/master/k-means/k-means.py (_src=undefined)

结果

生成的聚类:

upload successful

k-means运行后的聚类:

upload successful

可以看到分类算法运行良好。