k均值聚类
优点：容易实现。缺点：可能收敛到局部最小值，在大规模数据集上收敛较慢。适用数据类型：数值型数据。
k均值是发现给定数据集的k个簇的算法。簇个数k是用户给定的，每一个簇通过其质心（centroid），即簇中所有点的中心来描述。
k均值算法的工作流程是这样的。首先，随机确定k个初始点作为质心。然后将数据集中的每个点分配到一个簇中，具体来讲，为每个点找距其最近的质心，并将其分配给该质心所对应的簇。这一步完成之后，每个簇的质心更新为该簇所有点的平均值。
上述过程的伪代码表示如下：
创建k个点作为起始质心（经常是随机选择）当任意一个点的簇分配结果发生改变时 对数据集中的每个数据点 对每个质心 计算质心与数据点之间的距离 将数据点分配到距其最近的簇 对每一个簇，计算簇中所有点的均值并将均值作为质心
K均值聚类的一般流程
- 收集数据：使用任意方法。
- 准备数据：需要数值型数据来计算距离，也可以将标称型数据映射为二值型数据再用于距离计算。
- 分析数据：使用任意方法。
- 训练算法：不适用于无监督学习，即无监督学习没有训练过程。
- 测试算法：应用聚类算法、观察结果。可以使用量化的误差指标如误差平方和（后面会介绍）来评价算法的结果。
- 使用算法：可以用于所希望的任何应用。通常情况下，簇质心可以代表整个簇的数据来做出决策。
上面提到“最近”质心的说法，意味着需要进行某种距离计算。读者可以使用所喜欢的任意距离度量方法。数据集上k均值算法的性能会受到所选距离计算方法的影响。下面给出k均值算法的代码实现。首先创建一个名为kMeans.py的文件，然后将下面程序清单中的代码添加到文件中。
程序清单 10-1 k均值聚类支持函数
from numpy import *def loadDataSet(fileName): dataMat = fr = open(fileName) for line in fr.readlines: curLine = line.strip.split(/'t/') fltLine = map(float,curLine) dataMat.append(fltLine) return dataMatdef distEclud(vecA, vecB): return sqrt(sum(power(vecA - vecB, 2)))def randCent(dataSet, k): n = shape(dataSet)[1] centroids = mat(zeros((k,n))) #构建簇质心 for j in range(n): minJ = min(dataSet[:,j]) rangeJ = float(max(dataSet[:,j]) - minJ) entroids[:,j] = minJ + rangeJ * random.rand(k,1) return centroids 程序清单10-1中的代码包含几个k均值算法中要用到的辅助函数。第一个函数loadDataSet和上一章完全相同，它将文本文件导入到一个列表中。文本文件每一行为tab分隔的浮点数。每一个列表会被添加到dataMat中，最后返回dataMat。该返回值是一个包含许多其他列表的列表。这种格式可以很容易将很多值封装到矩阵中。
下一个函数distEclud计算两个向量的欧式距离。这是本章最先使用的距离函数，也可以使用其他距离函数。
最后一个函数是randCent，该函数为给定数据集构建一个包含k个随机质心的集合。随机质心必须要在整个数据集的边界之内，这可以通过找到数据集每一维的最小和最大值来完成。然后生成0到1.0之间的随机数并通过取值范围和最小值，以便确保随机点在数据的边界之内 。接下来看一下这三个函数的实际效果。保存kMeans.py文件，然后在Python提示符下输入：
>>> import kMeans>>> from numpy import * 要从文本文件中构建矩阵，输入下面的命令（第10章的源代码中给出了testSet.txt的内容）：
>>> datMat=mat(kMeans.loadDataSet(/'testSet.txt/')) 读者可以了解一下这个二维矩阵，后面将使用该矩阵来测试完整的k均值算法。下面看看randCent函数是否正常运行。首先，先看一下矩阵中的最大值与最小值：
>>> min(datMat[:,0])matrix([[-5.379713]])>>> min(datMat[:,1])matrix([[-4.232586]])>>> max(datMat[:,1])matrix([[ 5.1904]])>>> max(datMat[:,0])matrix([[ 4.838138]])
然后看看randCent函数能否生成min到max之间的值:
>>> kMeans.randCent(datMat, 2)matrix([[-3.24278889, -0.04213842], [-0.92437171, 3.19524231]]) 从上面的结果可以看到，函数randCent确实会生成min到max之间的值。上述结果表明，这些函数都能够按照预想的方式运行。最后测试一下距离计算方法：
>>> kMeans.distEclud(datMat[0], datMat[1])5.184632816681332 所有支持函数正常运行之后，就可以准备实现完整的k均值算法了。该算法会创建k个质心，然后将每个点分配到最近的质心，再重新计算质心。这个过程重复数次，直到数据点的簇分配结果不再改变为止。打开kMeans.py文件输入下面程序清单中的代码。
程序清单10-2 k均值聚类算法
def kMeans(dataSet, k, distMeas=distEclud, createCent=randCent): m = shape(dataSet)[0] clusterAssment = mat(zeros((m,2))) centroids = createCent(dataSet, k) clusterChanged = True while clusterChanged: clusterChanged = False for i in range(m): minDist = inf; minIndex = -1 for j in range(k): #❶（以下三行）寻找最近的质心 distJI = distMeas(centroids[j,:],dataSet[i,:]) if distJI < minDist: minDist = distJI; minIndex = j if clusterAssment[i,0] != minIndex: clusterChanged = True clusterAssment[i,:] = minIndex,minDist**2 #❷（以下四行）更新质心的位置 print centroids for cent in range(k): ptsInClust = dataSet[nonzero(clusterAssment[:,0].A==cent)[0]] centroids[cent,:] = mean(ptsInClust, axis=0) return centroids, clusterAssment 上述清单给出了k均值算法。kMeans函数接受4个输入参数。只有数据集及簇的数目是必选参数，而用来计算距离和创建初始质心的函数都是可选的。kMeans函数一开始确定数据集中数据点的总数，然后创建一个矩阵来存储每个点的簇分配结果。簇分配结果矩阵clusterAssment包含两列：一列记录簇索引值，第二列存储误差。这里的误差是指当前点到簇质心的距离，后边会使用该误差来评价聚类的效果。
按照上述方式（即计算质心-分配-重新计算）反复迭代，直到所有数据点的簇分配结果不再改变为止。程序中可以创建一个标志变量clusterChanged，如果该值为True，则继续迭代。上述迭代使用while循环来实现。接下来遍历所有数据找到距离每个点最近的质心，这可以通过对每个点遍历所有质心并计算点到每个质心的距离来完成❶。计算距离是使用distMeas参数给出的距离函数，默认距离函数是distEclud，该函数的实现已经在程序清单10-1中给出。如果任一点的簇分配结果发生改变，则更新clusterChanged标志。
最后，遍历所有质心并更新它们的取值❷。具体实现步骤如下：首先通过数组过滤来获得给定簇的所有点；然后计算所有点的均值，选项axis = 0表示沿矩阵的列方向进行均值计算；最后，程序返回所有的类质心与点分配结果。图10-1给出了一个聚类结果的示意图。
图10-1 k均值聚类的结果示意图。图中数据集在三次迭代之后收敛。形状相似的数据点被分到同样的簇中，簇中心使用十字来表示
接下来看看程序清单10-2的运行效果。保存kMeans.py文件后，在Python提示符下输入：
>>> reload(kMeans)<module /'kMeans/' from /'kMeans.pyc/'> 如果没有将前面例子中的datMat数据复制过来，则可以输入下面的命令（记住要导入NumPy）：
>>> datMat=mat(kMeans.loadDataSet(/'testSet.txt/')) 现在就可以对datMat中的数据点进行聚类处理。从图像中可以大概预先知道最后的结果应该有4个簇，所以可以输入如下命令：
>>> myCentroids, clustAssing = kMeans.kMeans(datMat,4)[[-4.06724228 0.21993975] [ 0.73633558 -1.41299247] [-2.59754537 3.15378974] [ 4.49190084 3.46005807]][[-3.62111442 -2.36505947] [ 2.21588922 -2.88365904] [-2.38799628 2.96837672] [ 2.6265299 3.10868015]][[-3.53973889 -2.89384326] [ 2.65077367 -2.79019029] [-2.46154315 2.78737555] [ 2.6265299 3.10868015]] 上面的结果给出了4个质心。可以看到，经过3次迭代之后k均值算法收敛。这4个质心以及原始数据的散点图在图10-1中给出。
到目前为止，关于聚类的一切进展都很顺利，但事情并不总是如此。接下来会讨论k均值算法可能出现的问题及其解决办法。