k-均值聚类

电玩女神 2022-06-01 02:27 252阅读 0赞

聚类是一种无监督的学习，它将相似的对象归到同一个簇中，簇内的对象越相似，聚类的效果越好。聚类与分类的最大不同在于，分类的目标事先已知，而聚类则不一样，是数据一种“自主”分类，属于无监督学习的范畴。

聚类在这里要解决的2大问题是：

1怎么分？ 2分到哪里去？

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

通过这个定义可以解答我们上面的问题：

1怎么分？根据距离分，质心是中心，它将是这一簇的中心点。

2分到哪里去？所有数据点分到离它最近的质心那一簇去。

虽然思路慢慢明确了，但是现在摆在我们面前的最后一个难题也就是我们直接面临的第一个困难：如何初始化质心？

围绕着质心的初始化，将K-均值聚类拆分为随机K-均值聚类算法和二分K-均值算法。

先看随机K-均值算法：

随机的由来在于初始的K个质心是随机给定然后慢慢优化的，有点随便找个点先干起来的意思。虽然随机，但并不代表没有原则，需要将质心限制在数据范围之内。

Python代码：

#为给定数据集构建一个包含k个随机质心的集合。
    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)
            #确保质心要在数据边界之内
            #rand函数，生成k行1列的随机矩阵
            centroids[:,j] = minJ + rangeJ*random.rand(k,1)
        return centroids

有了原始的K个随机质心，后面就要不断的循环去优化这些质心，在优化之前准备好2个辅助函数，数据集加载和距离计算：

def loadDataSet (fileName) :
        numFeat = len(open(fileName).readline().split('\t'))
        dataMat = []
        fr = open(fileName)
        for line in fr.readlines() :
            lineArray = []
            oneLine = line.strip().split('\t')
            for i in range(numFeat) :
                lineArray.append(float(oneLine[i]))
            dataMat.append(lineArray)
        return dataMat
    
    #计算A与B的欧式距离
    def distEclud(vecA, vecB) :
        return sqrt(sum(power(vecA-vecB,2)))

下面开始优化质心，

优化的步骤是求所有数据距离当前质心的距离，将其先做一次聚类，然后将每一簇的平均值作为新的质心，不断循环，直到不再有簇的变化。

代码如下：

#第一步初始化质心
    #第二步跟数据分簇
    #第三步更新质心再递归
    #当分簇结果不再更改时，返回结果
    def kMeans(dataSet, k, distMeas=distEclud, createCent=randCent) :
        #数据行数m
        m = shape(dataSet)[0]
        #簇分配结果
        clusterAssment = mat(zeros((m,2)))
        #随机获取k个质心
        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
                #第0列存储簇索引值，第1列存储误差，使用该误差来评价聚类的效果
                clusterAssment[i,:] = minIndex,minDist**2
            #print(centroids)
            #遍历现有的质心，重新计算质心
            for cent in range(k) :
                #取所有的簇索引为cent的dataSet的第一列组成新的一维纵列矩阵
                ptsInClust = dataSet[nonzero(clusterAssment[:,0].A==cent)[0]]
                #取上路矩阵的均值，更新质心
                centroids[cent,:] = mean(ptsInClust, axis=0)
        return centroids, clusterAssment

利用matplotlib.pyplot来验证数据集（https://github.com/yejingtao/forblog/blob/master/MachineLearning/trainingSet/clustering/testSet.txt）聚类的效果：

![20180117181007431][]

从效果图中感觉还可以。

现在我们换一个数据集（https://github.com/yejingtao/forblog/blob/master/MachineLearning/trainingSet/clustering/testSet2.txt），将其分为3个簇，大部分情况下都可以达到理想效果，如图：

![20180117181121470][]

但是有10%左右的概率会产生如下分类结果：

![20180117181137107][]

这是由初始质心的随机性导致的，随机导致了效果的不稳定性，于是更稳定的算法产生了，

二分k-均值算法。

二分K均值之所以稳定，是由于初始质心不再是随机生成K个，而是基于全部数据的平均值先生成一个质心，然后基于最优的方法分裂成2个质心，然后再对现有的2个判断下哪个簇的误差较大，将其再分裂成2个。如此n+1+1+1每次优化分裂一个簇，直到达到k个簇结束优化。

误差的判断利用误差平方和SSE：

![20180117181231727][]

Python代码如下：

#二次K-均值聚类算法
    def biKmeans(dataSet, k, distMeans=distEclud) :
        m = shape(dataSet)[0]
        #每个点的簇分配结果及平方误差
        clusterAssment = mat(zeros((m,2)))
        #对dataSet按列求均值，然后压平成一个1*n数组，取第一行数据
        centroids0 = mean(dataSet, axis=0).tolist()[0]
        #初始化一个质心，为所有数据所有向量均值的那个点
        centList = [centroids0]
        for j in range(m) :
            #初始化误差
            clusterAssment[j,1] = distMeans(mat(centroids0),dataSet[j,:])**2
        while (len(centList)< k) :
            lowestSSE = inf
            for i in range(len(centList)) :
                #ptsInCurrCluster存储的是属于簇i的所有数据集
                ptsInCurrCluster = dataSet[nonzero(clusterAssment[:,0].A==i)[0],:]
                #将这些内容拆分为2个簇
                centroidMat, splitClustAss = kMeans(ptsInCurrCluster,2,distMeans)
                #拆分后的误差和
                sseSplit = sum(splitClustAss[:,1])
                #不属于簇i的误差之和
                sseNotSplit = sum(clusterAssment[nonzero(clusterAssment[:,0].A!=i)[0],1])
                print('sseSplit : %f, sseNotSplit : %f' %(sseSplit,sseNotSplit))
                if (sseSplit+sseNotSplit)<lowestSSE :
                    #如果拆分后能优化，更新整套内容
                    bestCentToSplit = i
                    bestNewCents = centroidMat
                    bestClustAss = splitClustAss.copy()
                    lowestSSE = sseSplit + sseNotSplit
            #bestClustAss是一拆二的，所以里面第0列代表属于某个簇，只有0和1两个值
            #bestClustAss中属于1的，是新扩展出来的簇，在现有簇中+1为编号
            # bestClustAss中属于0的，还以当前列祖i为编号
            #这两行代码顺序不能颠倒，可以试试看
            bestClustAss[nonzero(bestClustAss[:, 0].A == 1)[0], 0] = len(centList)
            bestClustAss[nonzero(bestClustAss[:, 0].A == 0)[0], 0] = bestCentToSplit
            #与bestClustAss处理类似，在原位置更新质心，并在最后添加新质心
            centList[bestCentToSplit] = bestNewCents[0,:].tolist()[0]
            centList.append(bestNewCents[1,:].tolist()[0])
            #更新误差
            clusterAssment[nonzero(clusterAssment[:,0].A==bestCentToSplit)[0],:]=bestClustAss
        return mat(centList), clusterAssment

结果是稳定的，每次都可以达到我么的预期，例如我要分7簇，效果如下：

![20180117181331409][]

机器学习实践中最后给了一个案例介绍聚类的一个应用场景，小伙伴们要出去游玩，选择了几个地方，想打车到几个地方的中心点后步行前往，给出最优路线。

采用二分K-均值法本身不难，我却被其中另一个问题给考倒了，因为获得的地点是经纬度坐标，如何求地球妈妈球面积上坐标之间的距离？

[https://www.cnblogs.com/softfair/p/distance\_of\_two\_latitude\_and\_longitude\_points.html][https_www.cnblogs.com_softfair_p_distance_of_two_latitude_and_longitude_points.html]

这个小伙伴讲的很透彻了，基本是就是利用平面的问题去求解立体的问题，原理图如下：

![20180117181420601][]

代码中需要添加一个求坐标距离的辅助函数：

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)
        #地球半径6371.0KM
        return arccos(a+b)*6371.0

利用二分K-均值求质心，然后将结果展示到地图上：

def clusterClubs(numClust=5):
        import matplotlib
        import matplotlib.pyplot as plt
        datList = []
        for line in open('C:\\2017\\提高\\机器学习\\训练样本\\clustering\\places.txt').readlines():
            lineArr = line.split('\t')
            datList.append([float(lineArr[4]), float(lineArr[3])])
        datMat = mat(datList)
        myCentroids, clustAssing = biKmeans(datMat, numClust, distMeans=distSLC)
    
        fig = plt.figure()
        rect=[0.1,0.1,0.8,0.8]
        scatterMarkers = ['s','o','^','8','p','d','v','h','>','<']
        axprops = dict(xticks=[], yticks=[])
        ax0=fig.add_axes(rect,label='ax0',**axprops)
        imgP = plt.imread('C:\\2017\\提高\\机器学习\\训练样本\\clustering\\Portland.png')
        ax0.imshow(imgP)
        ax1=fig.add_axes(rect, label='ax1', frameon=False)
        for i in range(numClust):
            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=90)
        ax1.scatter(myCentroids[:,0].flatten().A[0],myCentroids[:,1].flatten().A[0],marker='+',s=300)
        plt.show()

效果如下：

![20180117181556367][]

地图底图在git上：https://github.com/yejingtao/forblog/blob/master/MachineLearning/trainingSet/clustering/Portland.png

坐标在git上：https://github.com/yejingtao/forblog/blob/master/MachineLearning/trainingSet/clustering/places.txt

[20180117181007431]: /images/20220601/15e1419107ad4e9a83b2516b914acd0f.png
[20180117181121470]: /images/20220601/08a164a15c494e1886a8728c6f3b6ef5.png
[20180117181137107]: /images/20220601/402e6d4e8cff493fb1505714da017095.png
[20180117181231727]: /images/20220601/dab707d2a3c54eb58952dc7d6e3c03aa.png
[20180117181331409]: /images/20220601/f31561fdd78e46a6a6d15c80dca4fbf3.png
[https_www.cnblogs.com_softfair_p_distance_of_two_latitude_and_longitude_points.html]: https://www.cnblogs.com/softfair/p/distance_of_two_latitude_and_longitude_points.html
[20180117181420601]: /images/20220601/25b5c6c1054745ce84ca21a7018690c9.png
[20180117181556367]: /images/20220601/e36731bb67894afda156d1488eb4434f.png