《机器学习实战》10.K-均值聚类算法
目录
本章涉及到的相关代码和数据
利用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=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)
# 质心 点分配结果
# print(clusterAssment)
return centroids,clusterAssment
import matplotlib.pyplot as plt
# 画图函数
def plotDataKMeans(centroids,clusterAssment):
numClust,n=shape(centroids)
fig=plt.figure()
# 点的类型
scatterMarkers=['s','o','^','8','p','d','v','h','>','<']
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] = bestCentToSplit
print("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], :] = bestClustAss
return 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.0
import 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个簇创建成功为止，效果更好。