目录

利用K-均值聚类算法对未标注数据分组

K-均值聚类算法

2 使用后处理来提高聚类性能

3 二分K-均值算法

4 示例：对地图上的点进行聚类

4.1 Yahoo！PlaceFinder API

4.2 对地理坐标进行聚类

5 本章小结

本章涉及到的相关代码和数据

利用K-均值聚类算法对未标注数据分组

本章内容：

①K-均值聚类算法

②对聚类得到的簇进行后处理

③二分K-均值聚类算法

④对地理位置进行聚类

聚类是一种无监督学习，他将类似的对象归到同一个簇中。有点像全自动分类，聚类算法几乎可以应用于所有对象，簇内的对象越相似，聚类的效果就越好。

K-means算法，可以发现k个不同的簇，且每个簇的中心采用簇中所含值的均值计算而成

簇识别：簇识别给出聚类结果的含义，假定有一些数据，现在将相似的数据归到一起，簇识别会告诉我们在这些簇到底都是什么。聚类与分类最大的不同在于，分类的目标事先已知，而聚类则不一样，因为其产生的效果与分类相同，而只是类别没有预先定义，剧烈有时也被称为无监督分类

K-均值聚类算法

优点：容易实现

缺点：可能收敛到局部最小值，在大规模数据集上收敛较慢

适用数据类型：数值型数据

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

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

伪代码如下：

创建k个点作为起始质心（经常是随机选择）

当任意一个点的簇分配结果发生改变时

    对数据集中的每个数据点

        对每个质心

            计算质心与数据点之间的距离

        将数据分配到距其最近的簇

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

一般流程：

①收集数据：适用任意方法

②准备数据：需要数值型数据来计算距离，也可以将标称型数据映射为二值型数据再用于距离计算

③分析数据：适用任意方法

④训练算法：无监督学习没有训练过程

⑤测试算法：应用聚类算法，观察结果。可以使用量化的误差指标如误差平方和来评价算法的结果

⑥使用算法：可以用于所希望的任何应用。通常情况下，簇质心可以代表整个簇来做出决策。

from numpy import *def loadDataSet(fileName):dataMat=[]fr=open(fileName)for line in fr.readlines():curLine=line.strip().split('\t')fltLine=list(map(float,curLine))dataMat.append(fltLine)return dataMat# 计算欧氏距离
def distEclud(vecA,vecB):return sqrt(sum(power(vecA-vecB,2)))# 构建一个包含k个随机质心的集合
def randCent(dataSet,k):n=shape(dataSet)[1]# 初始化矩阵：定义一个k*n的二维全是0的矩阵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 centroids

测试以上函数

datMat=mat(loadDataSet('testSet.txt'))
# 测试计算距离函数
print(distEclud(datMat[0],datMat[1]))
# 测试随机质心函数
randCent(datMat,2)

得到的输出结果为：

可以看出上述函数没有问题，接下来写K-means算法的函数以及对结果进行画图的函数

# 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=Falsefor i in range(m):minDist=infminIndex=-1for j in range(k):distJI=distMeas(centroids[j,:],dataSet[i,:])if distJI','<']axprops=dict(xticks=[],yticks=[])ax=fig.add_subplot(111)for i in range(numClust):# nonzero函数得到数组array中非零元素的位置ptsInCurrCluster = datMat[nonzero(clusterAssment[:,0].A==i)[0],:]markerStyle = scatterMarkers[i % len(scatterMarkers)]ax.scatter(ptsInCurrCluster[:,0].flatten().A[0], ptsInCurrCluster[:,1].flatten().A[0], marker=markerStyle, s=90)print(centroids)ax.scatter(centroids[:,0].flatten().A[0], centroids[:,1].flatten().A[0], marker='+', s=300)plt.show()

 测试结果

myCenttroids,clustAssing=kMeans(datMat,4)
# (可视化)
plotDataKMeans(myCenttroids,clustAssing)

得到的输出结果为：

到目前为止，关于聚类的一切都进展顺利，但是事情并不总是如此

2 使用后处理来提高聚类性能

前面提到，在k-均值聚类中簇的数目k是一个用户预先定义的饿参数，但是k的选择并不一定准确。

考虑到上面的聚类结果，其实点的分配结果并没有那么准确。K-均值算法收敛单聚类效果交叉的原因时，K-均值算法手来能与局部最小值，而非全局最小值。

一种用于度量剧烈效果的指标是SSE（误差平方和）。SSE值越小表示数据集越接近于他们的质心，聚类效果也越好。因为误差取了平方，因此更加中重视那些远离中心的点。一种可以肯定可以降低SSE值的方法是增加簇的个数，但这违背了聚类的目标，聚类的目标是保持粗数目不变的情况下提高簇的质量。

我们可以对生成的簇进行后处理，一种方法是将具有最大SSE值的簇划分为两个簇，具体实现时可以将最大粗包含的点过滤出来并在这些点上运行K-均值聚类算法，其中k设为2为了保持簇总数不变，可以将某两个簇进行合并。

有两种可以量化的方法：合并最近的质心或者合并两个使得SSE增幅最小的质心。第一种思路通过计算所有质心之间的距离，然后合并距离最近的两个点来实现。第二种方法需要合并两个簇然后计算总SSE值。必须在所有可能的两个簇上重复上述处理过程，直到找到最佳的两个簇为止。

3 二分K-均值算法

为了歌赋上述问题，一种二分K-均值算法：该算法首先将所有点作为一个簇，然后将该簇一分为二。之后选择其中一个簇继续进行划分，选择哪一个簇进行划分取决于对其划分是否可以最大程度降低SSE的值。上述基于SSE的划分过程不断重复，直到得到用户的满意为止。

伪代码：

将所有点看成一个簇

当簇的数目小于k时

    对每一个簇

        计算总误差

        在给定的簇上面进行K-均值聚类（k=2）

        计算将该簇一分为二后的总误差

    选择使得误差最小的那个簇进行划分操作

另一种做法是选择SSE最大的簇进行划分，直到簇数目达到用户指定的数目为止。

def bikmeans(dataSet, k, distMeas=distEclud):"""二分K-均值聚类算法:param dataSet:数据集:param k:质心数量:param distMeas:距离计算方法，默认欧氏距离distEclud():return:"""numSamples = dataSet.shape[0]  # 获得数据集的样本数# 创建一个初始簇clusterAssment = mat(zeros((numSamples, 2)))  # 初始化一个元素值0的(numSamples,2)矩阵centroid0 = mean(dataSet, axis=0).tolist()[0]  # 列表中的第一个列表元素：即全部数据每个属性centList = [centroid0]  # 当前聚类列表为将数据集聚为一类for j in range(numSamples):  # 遍历每个数据集样本clusterAssment[j, 1] = (distMeas(mat(centroid0), dataSet[j, :])) ** 2  # 计算当前聚为一类时各个数据点距离质心的平方距离# 循环，直至二分k-均值达到k类为止while len(centList) < k:  lowestSSE = inf  # 将当前最小平方误差置为正无穷for i in range(len(centList)):  # 遍历当前每个聚类# 通过数组过滤筛选出属于第i类的数据集合ptsInCurrCluster = dataSet[nonzero(clusterAssment[:, 0].A == i)[0], :]# 对该类利用二分k-均值算法进行划分，返回划分后结果，及误差centroidMat, splitClusAss = kMeans(ptsInCurrCluster, 2, distMeas)sseSplit = sum(splitClusAss[:, 1])  # 计算该类划分后两个类的误差平方和# 计算数据集中不属于该类的数据的误差平方和sseNotSplit = sum(clusterAssment[nonzero(clusterAssment[:, 0].A != i)[0], 1])print("sseSplit,and notSplit:", sseSplit, sseNotSplit)if (sseSplit + sseNotSplit) < lowestSSE:  # 划分第i类后总误差小于当前最小总误差bestCentToSplit = i  # 第i类作为本次划分类bestNewCents = centroidMat  # 第i类划分后得到的两个质心向量bestClustAss = splitClusAss.copy()  # 复制第i类中数据点的聚类结果即误差值lowestSSE = sseSplit + sseNotSplit  # 将划分第i类后的总误差作为当前最小误差# 数组过滤筛选出本次2-均值聚类划分后类编号为1数据点，将这些数据点类编号变为当前类个数+1，作为新的一个聚类bestClustAss[nonzero(bestClustAss[:, 0].A == 1)[0], 0] = len(centList)# 同理，将划分数据集中类编号为0的数据点的类编号仍置为被划分的类编号，使类编号连续不出现空缺bestClustAss[nonzero(bestClustAss[:, 0].A == 0)[0], 0] = bestCentToSplitprint("the bestCentToSplit is：", bestCentToSplit)print("the len of bestClustAss is :", len(bestClustAss))centList[bestCentToSplit] = bestNewCents[0, :].tolist()[0]  # 更新质心列表中的变化后的质心向量centList.append(bestNewCents[1, :].tolist()[0])  # 添加新的类的质心向量# 更新clusterAssment列表中参与2-均值聚类数据点变化后的分类编号，及数据该类的误差平方clusterAssment[nonzero(clusterAssment[:, 0].A == bestCentToSplit)[0], :] = bestClustAssreturn mat(centList), clusterAssment

测试函数：

datMat2=mat(loadDataSet("testSet.txt"))
# print(datMat2)
centList,myNewAssments=kMeans(datMat2,4)
plotDataKMeans(centList,myNewAssments)

得到的输出结果为：

4 示例：对地图上的点进行聚类

示例：对于地理数据应用的二分K-均值算法

①收集数据：使用Yahoo！ PlaceFinder API收集数据，这里因为API已经不能用，我们直接读取txt文本

②准备数据：只保留经纬度信息

③分析数据：使用matplotlib来构建一个二维数据图，其中包含簇与地图

④训练算法：无监督学习不用训练算法

⑤测试算法：使用biKmeans函数

⑥使用算法：最后的输出是包含簇及簇中心的地图

4.1 Yahoo！PlaceFinder API

书中所提到的API已经不能在使用，我们直接使用已经提供的places.txt文件

4.2 对地理坐标进行聚类

# 球面距离计算
def distSLC(vecA,vecB):a=sin(vecA[0,1]*pi/180)*sin(vecB[0,1]*pi/180)b=cos(vecA[0,1]*pi/180)*cos(vecB[0,1]*pi/180)*cos(pi*(vecB[0,0]-vecA[0,0])/180)# 反三角函数中的反余弦return arccos(a+b)*6371.0import matplotlib.pyplot as plt
def clusterClubs(numClust=5):datList=[]# 打开文本文件for line in open('places.txt').readlines():lineArr=line.split('\t')# 文本文件的第五列和第四列为坐标datList.append([float(lineArr[4]),float(lineArr[3])])datMat=mat(datList)# 进行聚类：距离计算公式利用球面计算公式myCentroids,clustAssing=bikmeans(datMat,numClust,distMeas=distSLC)# 画图fig=plt.figure()# rect=[0.1,0.1,0.8,0.8]rect=[1,1,1,1]scatterMarkers=['s','o','^','8','p','d','v','h','>','<']axprops=dict(xticks=[],yticks=[])ax0=fig.add_axes(rect,label='ax0',**axprops)imgP=plt.imread("Portland.png")ax0.imshow(imgP)ax1=fig.add_axes(rect,label='ax1',frameon=False)for i in range(numClust):# nonzero函数得到数组array中非零元素的位置ptsInCurrCluster = datMat[nonzero(clustAssing[:,0].A==i)[0],:]markerStyle = scatterMarkers[i % len(scatterMarkers)]ax1.scatter(ptsInCurrCluster[:,0].flatten().A[0], ptsInCurrCluster[:,1].flatten().A[0], marker=markerStyle, s=50)# print(centroids)ax1.scatter(myCentroids[:,0].flatten().A[0], myCentroids[:,1].flatten().A[0], marker='+', s=200)plt.show()

 测试函数

clusterClubs()

得到的输出结果为：

5 本章小结

聚类是一种无监督学习。所谓无监督就是事先并不知道要寻找的内容，即没有目标变量。聚类将数据点归到多个簇中，其中相似数据点处于同一簇，而不相似数据点处于不同簇中。聚类中可以使用多种不同方法来计算相似度

一种广泛使用的聚类算法是K-均值算法。其中k是用户指定的要创建的簇的数目。K-均值聚类算法以k个随机质心开始，算法会计算每个点到质心的距离。每个点被分配到距其最近的簇质心，然后紧接着基于新分配到簇的点更新质心。以上过程重复数次，直到簇质心不再改变。这种简单的算法非常有效但是也容易受到初始簇质心的影响。

为了获得更好的效果，可以使用另一种二分K-均值的聚类算法。二分K-均值算法首先将所有点作为一个簇，然后使用K-均值算法（k=2）对其划分。下一次迭代时，选择有最大误差的簇进行划分。该过程重复直到k个簇创建成功为止，效果更好。