Python实现K-means聚类算法

题记：最近有幸参与了一个机器学习的项目，我的主要工作是帮助进行数据预处理，期间用Python实现了K-means聚类算法，感觉收获很多特此记录下来和大伙儿分享。

一

机器学习项目的主要流程

机器学习项目的主要流程有五步：

1.数据提取

2.数据清洗

3.特征工程

4.训练模型

5.验证模型并优化

之前讲到的PYTHON爬虫可以算是第一步数据提取里面的内容，数据提取的作用就是想方设法获取源数据。获得源数据后，由于源数据里可能包含很多的脏数据，比如房屋面积是零、年龄是负数等等情况，所以需要对源数据进行清洗，使数据变得更加整齐有效。然后开始提取数据信息，也就是我们说的特征工程。特征工程是提升模型强度的关键因素，特征选取的越好，模型效果就越好。然后训练模型，就是找出特征x和标签y之间的函数关系式。最后验证这个函数关系式的效果好不好，并进行优化。

二

聚类算法简介

我这次所做的工作就是第二步数据清洗。需求是这样的：需要将二维坐标系上的点集按距离远近分类，距离近的分成一组。以方便后续算法工程师对各个分组进行特征的提取工作。

为实现目标，常采用的就是K-means聚类算法。K-means聚类算法的思路如下：

1.选择分类数K，也就是我们希望把数据分成K组。一般根据经验来选取，比如衣服就分成S M L三类，或者根据聚类结果和K的函数式，选择让结果最好的那个K值。

2.随机选择每类数据的中心点。中心点的选择对结果影响也很大，如果选取不好就会找到局部最小值，这里一般有两种处理方法：一是多次取平均值，二是采用改进算法。

3.计算数据集中所有点到各个中心点的距离，它们离哪个中心点最近，就把它们划分到哪一类里面去。

4.在每一类中通过求平均值的方法寻找新的中心点

5.循环执行3、4步，直到分类结果收敛为止。（即分类结果不变为止）

三

源数据格式

源数据是一个存放在e盘下的txt文档，其中每一行数据代表点的横坐标和纵坐标，横坐标和纵坐标之间用TAB键分隔，文档有多少行就代表有多个点。如下：

四

Python代码实现

import numpy

def loadDataSet(fileName):

dataMat = []

fr = open(fileName)

for line in fr.readlines():

curLine = line.strip().split('\t') #strip 去除首尾的空格，split以tab作为分隔符分割数据。返回一个list数据

fltLine =[float(i) for i in curLine]

dataMat.append(fltLine)

return dataMat

# 计算两个向量的距离，用的是欧几里得距离

def distEclud(v1, v2):

return numpy.sqrt(numpy.sum(numpy.square(v1 - v2)))

# 构建聚簇中心，取k个(此例中为2)随机质心

def randCent(dataSet, k):

n = shape(dataSet)[1] #等价于dataSet.shape[1]，得到数组的列数。同理，dataSet.shape[0]得到数组的行数。shape函数就是读取矩阵的长度

centroids = mat(zeros((k,n))) # 每个质心有n个坐标值，总共要k个质心

for j in range(n):

minJ = dataSet[:,j].min() #第j列的最小值

maxJ = dataSet[:,j].max() #第j列的最大值

rangeJ = maxJ - minJ

return centroids

#def kMeans(dataSet, k, distMeas=distEclud, createCent=randCent):

def kMeans(dataSet, k):

m = shape(dataSet)[0] #等价于dataSet.shape[0] 第一维的长度，即行数

clusterAssment = mat(zeros((m, 2))) # 用于存放该样本属于哪类及质心距离，第一列是该数据所属中心点，第二列是该数据到中心点的距离

centroids = randCent(dataSet, k)

clusterChanged = True #判断聚类是否已经收敛，当clusterChanged的值为False时已经收敛，跳出While循环。

while clusterChanged:

clusterChanged = False

for i in range(m): # 每个数据点分配到离它最近的质心，range（start,stop,step）用于生成一个整数列表

minDist = inf #inf代表正无穷 -inf代表负无穷

minIndex = -1

for j in range(k):

distJI = distEclud(numpy.array(centroids[j, :]), numpy.array(dataSet[i, :])) #求第j行的中心点到第i行的数据之间的距离

if distJI

minDist = distJI;

minIndex = j

if clusterAssment[i, 0] != minIndex:

clusterChanged = True

clusterAssment[i, :] = minIndex, minDist ** 2 # x**y 返回x的y次幂 x//y 取x除以y的整数部分

print(centroids)

for cent in range(k): #重新计算中心点

ptsInClust = dataSet[nonzero(clusterAssment[:, 0].A == cent)[0]] # 筛选出第一列等于cent的所有数据，即找到属于这个聚类的所有数据点。 nonzero函数是numpy中用于得到数组array中非零元素的位置（数组索引）的函数

centroids[cent, :] = mean(ptsInClust, axis=0) # mean是求平均值的函数，

# numpy.mean(a, axis, dtype, out，keepdims ) axis 不设置值，对 m*n 个数求均值，返回一个实数

#axis = 0：压缩行，对各列求均值，返回 1* n 矩阵 axis =1 ：压缩列，对各行求均值，返回 m *1 矩阵

return centroids, clusterAssment

def show(dataSet, k, centroids, clusterAssment): #绘图展示，这块还没看

from matplotlib import pyplot as plt

numSamples, dim = dataSet.shape

mark = ['or', 'ob', 'og', 'ok', '^r', '+r', 'sr', 'dr', '

for i in range(numSamples): #画样本点，属于同一中心的用一种标记

markIndex = int(clusterAssment[i, 0])

plt.plot(dataSet[i, 0], dataSet[i, 1], mark[markIndex])

mark = ['Dr', 'Db', 'Dg', 'Dk', '^b', '+b', 'sb', 'db', '

for i in range(k): #画中心点

plt.plot(centroids[i, 0], centroids[i, 1], mark[i], markersize=12)

plt.show()

def main():

dataMat =mat(loadDataSet('E:/test.txt')) #mat转换成矩阵操作

myCentroids, clustAssing = kMeans(dataMat, 2) #函数返回一个元组，元组的括号可以省略

# print(myCentroids)

show(dataMat, 2, myCentroids, clustAssing)

if __name__ == '__main__':

main()

*代码要点精讲*

main（）函数：这是程序的起点，它先对用loadDataSet函数对源数据做加载，再要用kMeans（）做聚类，最后用show（）将聚类结果以图表形式展示出来。

loadDataSet（）函数：用来加载源数据，先用open函数打开源文件，然后逐行读取源文件的内容，每行内容用TAB作为分隔符，每行内容形成一个列表，附加到dataMat中，最后返回一个对象是列表的列表dataMat。比如这里的txt数据形成一个10*2的矩阵给了dataMat。

kMeans()函数：分类结果存放在clusterAssment中，中心点存放在centroids中，当标志位clusterChanged为false时，表示聚类结束。While循环表示每次聚类，一次WHILE里有双重for循环，表示每次聚类时，都要计算所有数据点到中心点的距离，数据到哪个中心点距离最短，就划分到哪类里面去。划分完毕后重新计算中心点。

Show（）函数：用于聚类结果的展示。导入matplotlib库，应用其中的plot函数绘图，先绘制样本点再绘制中心点。属于同一中心点的样本点用同种标记。

五

聚类结果

从图中我们可以看到十个样本点被分成了两类。红色的是一类，蓝色的是一类，这个结果符合我们最初的预期。当数据量加大的时候，也有同样的效果，这里就不赘述了。

六

后记

曾经作为测试小白的我有很长一段时间也认为测试不需要懂代码，特别是功能测试只需要懂业务，然后会跑用例就够了。但是当真正遇到一些稍微高大上一点的项目的时候，才知道测试光懂业务还远远不够，知其然还要知其所以然，才能更好地把控软件产品质量。通过这次"兼职"数据处理工程师，在我明白这个聚类算法的逻辑后，才能思考怎么测试才能更好了把控产品质量，比如说采用大数据量、采用一些垃圾数据做干扰、采用让它收敛到局部最小的K值等等。。

测试路上没有最好，只有更好。与各位同仁共勉！

选自《51测试天地》第五十二期电子杂志