K-means聚类算法及python代码实现

K-means聚类算法（事先数据并没有类别之分！所有的数据都是⼀样的）1、概述

K-means算法是集简单和经典于⼀⾝的基于距离的聚类算法

采⽤距离作为相似性的评价指标，即认为两个对象的距离越近，其相似度就越⼤。该算法认为类簇是由距离靠近的对象组成的，因此把得到紧凑且独⽴的簇作为最终⽬标。

2、核⼼思想

通过迭代寻找k个类簇的⼀种划分⽅案，使得⽤这k个类簇的均值来代表相应各类样本时所得的总体误差最⼩。k个聚类具有以下特点：各聚类本⾝尽可能的紧凑，⽽各聚类之间尽可能的分开。 k-means算法的基础是最⼩误差平⽅和准则,其代价函数是：

式中，µc(i)表⽰第i个聚类的均值。

各类簇内的样本越相似，其与该类均值间的误差平⽅越⼩，对所有类所得到的误差平⽅求和，即可验证分为k类时，各聚类是否是最优的。上式的代价函数⽆法⽤解析的⽅法最⼩化，只能有迭代的⽅法。

3、算法步骤图解

下图展⽰了对n个样本点进⾏K-means聚类的效果，这⾥k取2。

4、算法实现步骤

k-means算法是将样本聚类成 k个簇（cluster），其中k是⽤户给定的，其求解过程⾮常直观简单，具体算法描述如下：1) 随机选取 k个聚类质⼼点2) 重复下⾯过程直到收敛 {

对于每⼀个样例 i，计算其应该属于的类：

对于每⼀个类 j，重新计算该类的质⼼：

}

其伪代码如下：

******************************************************************************创建k个点作为初始的质⼼点（随机选择）当任意⼀个点的簇分配结果发⽣改变时 对数据集中的每⼀个数据点 对每⼀个质⼼

计算质⼼与数据点的距离 将数据点分配到距离最近的簇

对每⼀个簇，计算簇中所有点的均值，并将均值作为质⼼********************************************************

5、K-means聚类算法python实战需求：

对给定的数据集进⾏聚类

本案例采⽤⼆维数据集，共80个样本，有4个类。

1 #!/usr/bin/python 2 # coding=utf-8

3 from numpy import * 4 # 加载数据

5 def loadDataSet(fileName): # 解析⽂件，按tab分割字段，得到⼀个浮点数字类型的矩阵 6 dataMat = [] # ⽂件的最后⼀个字段是类别标签 7 fr = open(fileName) 8 for line in fr.readlines():

9 curLine = line.strip().split('\')

10 fltLine = map(float, curLine) # 将每个元素转成float类型11 dataMat.append(fltLine)12 return dataMat13

14 # 计算欧⼏⾥得距离

15 def distEclud(vecA, vecB):

16 return sqrt(sum(power(vecA - vecB, 2))) # 求两个向量之间的距离17

18 # 构建聚簇中⼼，取k个(此例中为4)随机质⼼19 def randCent(dataSet, k):20 n = shape(dataSet)[1]

21 centroids = mat(zeros((k,n))) # 每个质⼼有n个坐标值，总共要k个质⼼22 for j in range(n):

23 minJ = min(dataSet[:,j])24 maxJ = max(dataSet[:,j])25 rangeJ = float(maxJ - minJ)

26 centroids[:,j] = minJ + rangeJ * random.rand(k, 1)27 return centroids28

29 # k-means 聚类算法

30 def kMeans(dataSet, k, distMeans =distEclud, createCent = randCent):31 m = shape(dataSet)[0]

32 clusterAssment = mat(zeros((m,2))) # ⽤于存放该样本属于哪类及质⼼距离

33 # clusterAssment第⼀列存放该数据所属的中⼼点，第⼆列是该数据到中⼼点的距离34 centroids = createCent(dataSet, k)

35 clusterChanged = True # ⽤来判断聚类是否已经收敛36 while clusterChanged:

37 clusterChanged = False;

38 for i in range(m): # 把每⼀个数据点划分到离它最近的中⼼点39 minDist = inf; minIndex = -1;40 for j in range(k):

41 distJI = distMeans(centroids[j,:], dataSet[i,:])42 if distJI < minDist:

43 minDist = distJI; minIndex = j # 如果第i个数据点到第j个中⼼点更近，则将i归属为j

44 if clusterAssment[i,0] != minIndex: clusterChanged = True; # 如果分配发⽣变化，则需要继续迭代45 clusterAssment[i,:] = minIndex,minDist**2 # 并将第i个数据点的分配情况存⼊字典46 print centroids

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

48 ptsInClust = dataSet[nonzero(clusterAssment[:,0].A == cent)[0]] # 去第⼀列等于cent的所有列49 centroids[cent,:] = mean(ptsInClust, axis = 0) # 算出这些数据的中⼼点50 return centroids, clusterAssment

51 # --------------------测试----------------------------------------------------52 # ⽤测试数据及测试kmeans算法

53 datMat = mat(loadDataSet('testSet.txt'))

54 myCentroids,clustAssing = kMeans(datMat,4)55 print myCentroids56 print clustAssing

运⾏结果：

6、K-means算法补充

K-means算法的缺点及改进⽅法

（1）k值的选择是⽤户指定的，不同的k得到的结果会有挺⼤的不同，如下图所⽰，左边是k=3的结果，这个就太稀疏了，蓝⾊的那个簇其实是可以再划分成两个簇的。⽽右图是k=5的结果，可以看到红⾊菱形和蓝⾊菱形这两个簇应该是可以合并成⼀个簇的：改进：

对k的选择可以先⽤⼀些算法分析数据的分布，如重⼼和密度等，然后选择合适的k

（2）对k个初始质⼼的选择⽐较敏感，容易陷⼊局部最⼩值。例如，我们上⾯的算法运⾏的时候，有可能会得到不同的结果，如下⾯这两种情况。K-means也是收敛了，只是收敛到了局部最⼩值：改进：

有⼈提出了另⼀个成为⼆分k均值（bisecting k-means）算法，它对初始的k个质⼼的选择就不太敏感

（3）存在局限性，如下⾯这种⾮球状的数据分布就搞不定了：

（4）数据集⽐较⼤的时候，收敛会⽐较慢。

上班了，⼯作繁忙，很少看博客了，不能及时给各位数据集，很抱歉，现在决定放在博客⾥⾯，⼤家复制下去使⽤即可：testSet.txt

1.6585 4.285136-3.453687 3.4243214.838138 -1.151539

-5.379713 -3.3621040.9725 2.924086-3.567919 1.5316110.450614 -3.302219-3.487105 -1.7244322.668759 1.594842-3.1585 3.1911373.165506 -3.999838-2.786837 -3.0993544.208187 2.984927-2.123337 2.9433660.704199 -0.479481-0.392370 -3.9637042.831667 1.574018-0.790153 3.3431442.943496 -3.357075-3.195883 -2.2839262.3345 2.875106-1.786345 2.5542482.190101 -1.906020-3.403367 -2.7782881.778124 3.880832-1.688346 2.2302672.592976 -2.054368-4.007257 -3.2070662.257734 3.3875-2.679011 0.7851190.939512 -4.023563-3.674424 -2.2610842.046259 2.735279-3.1470 1.7802694.3726 -0.822248-2.579316 -3.4975761.8034 5.190400-0.798747 2.1855882.836520 -2.658556-3.837877 -3.2538152.096701 3.886007-2.709034 2.9238873.367037 -3.1847-2.121479 -4.2325862.329546 3.1797-3.284816 3.2730993.091414 -3.815232-3.762093 -2.4321913.542056 2.778832-1.736822 4.2410412.127073 -2.983680-4.323818 -3.9381163.792121 5.135768-4.7873 3.3585472.624081 -3.260715-4.009299 -2.9781152.493525 1.963710-2.513661 2.21621.8375 -3.176309-3.171184 -3.5724522.4220 2.4128-2.562539 2.8844383.491078 -3.947487-2.565729 -2.0121143.332948 3.983102-1.616805 3.5731882.280615 -2.559444-2.651229 -3.1031982.321395 3.154987-1.685703 2.9396973.031012 -3.620252-4.599622 -2.1858294.196223 1.126677-2.133863 3.09368.6682 -2.562705-2.793241 -2.1497062.884105 3.043438-2.9677 2.84869.479332 -1.7772-4.905566 -2.911070