聚类是一种无监督的学习，他将相似的对象归到同一个簇中。他有点像自动分类，聚类方法几乎可以应用于所有对象，簇内的对象越相似，聚类效果越好。聚类和分类的最大不同在于，分类的目标事先已知而聚类则不一样。因为其产生的结果与分类相同，而只是类别没有预先定义，聚类有时也被称为无监督分类（unsupervised classification）。聚类分析试图将相似对象归入同一簇，将不相似对象归为不同簇。

簇识别的含义，簇识别给出聚类结果的含义，假定有一些数据，现在将相似数据归到一起，簇识别会告诉我们这些簇到底都是些什。

k-均值聚类算法之所以称之为K-均值是因为它k个不同的簇且每个簇的中心采用簇中所含值的均值计算而成。

K-均值是发现给定数据集的k个簇的算法。簇的个数k是用户给定的，每一个簇通过质心（centroid），即簇中所有点的中心来描述。

k-均值算法的工作流程：首先确定k个初始点作为质心。然后将数据集中的每个点分配到一个簇中，具体来讲为每个点找到距其最近的质心，并将其分配给该质心所对应的簇。这一步完成后，每个簇的质心更新为该簇所有点的平均值。

伪代码表示如下：创建K个点作为起始点的质心（通常随机选择）当任意一个点的簇分配结果发生改变时对数据集中的每一个数据点 对每个质心 计算质心与数据点之间的距离 将数据点分配到距离最近的簇对每一个簇，计算簇中所有点的均值并将均值作为质心

其中需要计算最近距离，可以使用自己熟悉的求距离的算法。

如何确定前期所选的k值（簇的个数）是合适的呢？如何才能知道生成簇比较好呢？由于簇的分配结果矩阵中保存着每个点的误差，即该点到簇质心的距离的平方值。有一只用于度量聚类效果的指标是SSE（sum of Aquared Error误差平方和），SSE值越小表示数据点越接近于他们的质心，聚类效果也越好。

二分K-均值算法

k均值算法存在收敛局部最小值的问题，有人提出另一种称为二分k-均值的算法。该算法首先将所有点作为一个簇，然后将该簇一分为二。之后选择其中一个簇继续进行划分，选择哪一个簇进行划分取决于对其划分是否可以最大程度降低SEE得值。基于SSE的值不断进行划分，知道得到用户指定的簇数目为止。

二分k-均值算法伪代码：将所有点看成一个簇当簇的数目小于k时对于每一个簇计算总误差在给定的簇上面进行k-均值聚类（k=2）计算将该簇一分为二后的总误差选择使得误差最小的那个簇进行划分操作

应用：假如出现这么一种情况，有100个人分别在一块区域，你需要安排出一个合理的方案去接送这些人到某个地方。可以通过聚类的方式，找到几个质心比如说4个质心，你只需要安排4辆车去四个质心的位置去结这些人就行。

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) centroids[:,j] = minJ + rangeJ * random.rand(k,1) return centroidsdef kMeans(dataSet, k, distMeas=distEclud, createCent=randCent): m = shape(dataSet)[0] clusterAssment = mat(zeros((m,2)))#create mat to assign data points #to a centroid, also holds SE of each point centroids = createCent(dataSet, k) clusterChanged = True while clusterChanged: clusterChanged = False for i in range(m):#for each data point assign it to the closest centroid 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):#recalculate centroids ptsInClust = dataSet[nonzero(clusterAssment[:,0].A==cent)[0]]#get all the point in this cluster centroids[cent,:] = mean(ptsInClust, axis=0) #assign centroid to mean return centroids, clusterAssmentdef biKmeans(dataSet,k,distMeas = distEclud): m = shape(dataSet)[0] clusterAssment = mat(zeros((m,2))) centroid0 = mean(dataSet,axis=0).tolist()[0] centList = [centroid0] for j in range(m): clusterAssment[j,1] = distMeas(mat(centroid0),dataSet[j,:])**2 while(len(centList) < k): lowestSSE = inf for i in range(len(centList)): ptsInCurrCluster = dataSet[nonzero(clusterAssment[:,0].A==i)[0],:] centroidMat,splitClustAss = kMeans(ptsInCurrCluster, 2 ,distMeas) sseSpilt = sum(splitClustAss[:,1]) sseNotSplit = sum(clusterAssment[nonzero(clusterAssment[:,0].A != i)[0],1]) print "sseSplit,and notSplit:",sseSpilt,sseNotSplit if (sseSpilt + sseNotSplit) < lowestSSE: bestCentToSplit = i bestNewCents = centroidMat bestClustAss = splitClustAss.copy() lowestSSE = sseSpilt + sseNotSplit bestClustAss[nonzero(bestClustAss[:,0].A == 1)[0],0] = len(centList) bestClustAss[nonzero(bestClustAss[:,0].A == 0)[0],0] = bestCentToSplit print 'the bestCentToSplit is:',bestCentToSplit print 'the len of bestClustAss is:',len(bestClustAss) centList[bestCentToSplit] = bestNewCents[0,:] centList.append(bestNewCents[1,:]) clusterAssment[nonzero(clusterAssment[:,0].A == bestCentToSplit)[0]:] = bestClustAss return mat(centList), clusterAssment