• 《机器学习实战》10.K-均值聚类算法

    目录

    利用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个点作为起始质心（经常是随机选择）

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

        对数据集中的每个数据点

            对每个质心

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

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

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

    一般流程：

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

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

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

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

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

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

    1. from numpy import *
    2.  
    3. def loadDataSet(fileName):
    4.     dataMat=[]
    5.     fr=open(fileName)
    6.     for line in fr.readlines():
    7.         curLine=line.strip().split('\t')
    8.         fltLine=list(map(float,curLine))
    9.         dataMat.append(fltLine)
    10.     return dataMat
    11.  
    12. # 计算欧氏距离
    13. def distEclud(vecA,vecB):
    14.     return sqrt(sum(power(vecA-vecB,2)))
    15.  
    16. # 构建一个包含k个随机质心的集合
    17. def randCent(dataSet,k):
    18.     n=shape(dataSet)[1]
    19.     # 初始化矩阵：定义一个k*n的二维全是0的矩阵
    20.     centroids=mat(zeros((k,n)))
    21.     for j in range(n):
    22.         minJ=min(dataSet[:,j])
    23.         rangeJ=float(max(dataSet[:,j])-minJ)
    24.         centroids[:,j]=minJ+rangeJ*random.rand(k,1)
    25.     return centroids

    测试以上函数

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

    得到的输出结果为：

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

    1. # k-均值聚类算法
    2.         # 数据集，簇的个数 距离计算方式 创建初始质心的方式
    3. def kMeans(dataSet,k,distMeas=distEclud,createCent=randCent):
    4.     # 确定数据集中点的个数
    5.     m=shape(dataSet)[0]
    6.     # 创建一个矩阵存放每个点的簇分配结果（簇索引值、误差：当前点到簇质心的距离），后面会使用误差来评价聚类的效果
    7.     clusterAssment=mat(zeros((m,2)))
    8.  
    9.     centroids=createCent(dataSet,k)
    10.     clusterChanged=True
    11.     # 循环直到所有点簇的分配结果不再改变为止
    12.     while clusterChanged:
    13.         clusterChanged=False
    14.         for i in range(m):
    15.             minDist=inf
    16.             minIndex=-1
    17.             for j in range(k):
    18.                 distJI=distMeas(centroids[j,:],dataSet[i,:])
    19.                 if distJI
    20.                     minDist=distJI
    21.                     minIndex=j
    22.             if clusterAssment[i,0]!=minIndex:
    23.                 clusterChanged=True
    24.             clusterAssment[i,:]=minIndex
    25.             minDist**2
    26.         print(centroids)
    27.         for cent in range(k):
    28.             ptsInClust=dataSet[nonzero(clusterAssment[:,0].A==cent)[0]]
    29.             centroids[cent,:]=mean(ptsInClust,axis=0)
    30.             # 质心    点分配结果
    31.     # print(clusterAssment)
    32.     return centroids,clusterAssment
    33.  
    34. import matplotlib.pyplot as plt
    35. # 画图函数
    36. def plotDataKMeans(centroids,clusterAssment):
    37.     numClust,n=shape(centroids)
    38.     fig=plt.figure()
    39.     # 点的类型
    40.     scatterMarkers=['s','o','^','8','p','d','v','h','>','<']
    41.     axprops=dict(xticks=[],yticks=[])
    42.     ax=fig.add_subplot(111)
    43.     for i in range(numClust):
    44.         # nonzero函数得到数组array中非零元素的位置
    45.         ptsInCurrCluster = datMat[nonzero(clusterAssment[:,0].A==i)[0],:]
    46.         markerStyle = scatterMarkers[i % len(scatterMarkers)]
    47.         ax.scatter(ptsInCurrCluster[:,0].flatten().A[0], ptsInCurrCluster[:,1].flatten().A[0], marker=markerStyle, s=90)
    48.     print(centroids)
    49.     ax.scatter(centroids[:,0].flatten().A[0], centroids[:,1].flatten().A[0], marker='+', s=300)
    50.     plt.show()

     测试结果

    1. myCenttroids,clustAssing=kMeans(datMat,4)
    2. # (可视化)
    3. 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最大的簇进行划分，直到簇数目达到用户指定的数目为止。

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

    测试函数：

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

    得到的输出结果为：

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

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

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

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

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

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

    ⑤测试算法：使用biKmeans函数

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

    4.1 Yahoo！PlaceFinder API

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

    4.2 对地理坐标进行聚类

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

     测试函数

    clusterClubs()

    得到的输出结果为：

     

    5 本章小结

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

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

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

  • 相关阅读:
    React源码分析(二)渲染机制
    ChatGPT/GPT4科研技术应用与AI绘图及论文高效写作
    软考高级信息系统项目管理师系列论文九：论信息系统项目的采购管理
    k8s部署手册-v06
    [小项目]手把手教你C语言哈夫曼压缩/解压缩
    第一篇 打开终端的时候处在哪个位置
    Sqlserver存储过程快速上手分享
    蓝桥杯打卡Day5
    如何将枯燥的大数据进行可视化处理？
    基于TI DRV10970驱动直流无刷电机
  • 原文地址：https://blog.csdn.net/weixin_46182244/article/details/128079462