“机器学习实战”刻意练习——聚类问题：K均值聚类

朱雀 2023-06-23 16:20 33阅读 0赞

# 一、概述 #

**聚类**是一种无监督的学习，它将相似的对象归到同一个簇中。

聚类方法几乎可以应用于所有对象，簇内的对象**越相似**，聚类的效果越好。

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

在介绍K-均值算法之前，先讨论一下**簇识别（cluster identification）**。  
簇识别给出**聚类结果的含义**。  
假定有一些数据，现在将相似数据归到一起，簇识别会告诉我们这些簇到底都是些什么。

聚类与分类的最大不同在于，分类的目标事先已知，而聚类则不一样。  
因为其产生的结果与分类相同，而只是**类别没有预先定义**，聚类有时也被称为**无监督分类（unsupervisedclassification**）。

聚类分析试图将相似对象归入同一簇，将不相似对象归到不同簇。  
**相似**这一概念取决于所选择的相似度计算方法。到底使用哪种相似度计算方法取决于具体应用。

*  优缺点  
    优点：容易实现。  
    缺点：可能收敛到局部最小值，在大规模数据集上收敛较慢。
 *  适用数据类型  
    数值型数据
 *  K-均值聚类的一般流程  
    (1) 收集数据：使用任意方法。  
    (2) 准备数据：需要数值型数据来计算距离，也可以将**标称型数据映射为二值型数据**再用于距离计算。  
    (3) 分析数据：使用任意方法。  
    (4) 训练算法：不适用于无监督学习，即**无监督学习没有训练过程**。  
    (5) 测试算法：应用聚类算法、观察结果。可以使用量化的误差指标如**误差平方和**来评价算法的结果。  
    (6) 使用算法：可以用于所希望的任何应用。通常情况下，**簇质心**可以代表整个簇的数据来做出决策。

# 二、基本概念 #

## 1.K-均值聚类算法 ##

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

K-均值算法的工作流程伪代码如下：

创建k个点作为起始质心（经常是随机选择）
    当任意一个点的簇分配结果发生改变时
    	对数据集中的每个数据点
    		对每个质心
    			计算质心与数据点之间的距离
    	将数据点分配到距其最近的簇
    对每一个簇，计算簇中所有点的均值并将均值作为质心

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

在 kMeans 的函数测试中，可能偶尔会陷入局部最小值（局部最优的结果，但不是全局最优的结果），如下图：  
![在这里插入图片描述][format_png]  
出现这个问题有很多原因，可能是k值取的不合适，可能是距离函数不合适，可能是最初随机选取的质心靠的太近，也可能是数据本身分布的问题。

为了解决这个问题，我们可以对生成的簇进行后处理，一种方法是将具有**最大SSE值的簇划分成两个簇**。具体实现时可以将最大簇包含的点过滤出来并在这些点上运行K-均值算法，令k设为2。

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

为了保持簇总数不变，可以将某两个簇进行合并。从上图中很明显就可以看出，应该将上图下部两个出错的簇质心进行合并。那么问题来了，我们可以很容易对二维数据上的聚类进行可视化， 但是如果遇到40维的数据应该如何去做？

有两种可以量化的办法：

1.  合并最近的质心，通过计算所有质心之间的距离， 然后合并距离最近的两个点来实现。
2.  合并两个使得SSE增幅最小的质心，需要合并两个簇然后计算总SSE值。必须在所有可能的两个簇上重复上述处理过程，直到找到合并最佳的两个簇为止。

## 3.二分 K-Means 聚类算法 ##

为克服K-均值算法收敛于局部最小值的问题，有人提出了另一个称为二分K-均值（bisecting K-means）的算法。该算法首先将所有点作为一个簇，然后将该簇一分为二。之后选择其中一个簇继续进行划分，选择哪一个簇进行划分取决于对其划分是否可以最大程度降低SSE的值。上述基于SSE的划分过程不断重复，直到得到用户指定的簇数目为止。

二分 K-Means 聚类算法伪代码如下：

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

另一种做法是选择 SSE 最大的簇进行划分，直到簇数目达到用户指定的数目位置。 接下来主要介绍该做法的python2代码实现

# 三、代码实现 #

## 1.K-均值聚类算法 ##

先给出数据集分布：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25hbmFzaGlfRg_size_16_color_FFFFFF_t_70]

import numpy as np
    import matplotlib.pyplot as plt
    
    def loadDataSet(fileName): 
        """ 加载数据集 - - - - fileName - 文件路径 """
        dataMat = []
        fr = open(fileName)
        for line in fr.readlines():
            curLine = line.strip().split('\t')
            #映射所有的元素为 float（浮点数）类型
            fltLine = list(map(float,curLine))    
            dataMat.append(fltLine)
        return np.mat(dataMat)
    
    def distEclud(vecA, vecB):
        """ 计算两个向量的欧式距离 - - - - vecA - 向量A vecB - 向量B """
        return np.sqrt(np.sum(np.power(vecA - vecB, 2)))
    
    def randCent(dataSet, k):
        """ 构建一个包含 k 个随机质心的集合 - - - - dataSet - 数据集 k - 簇的数目 """
        # 列的数量，即数据的特征个数
        n = np.shape(dataSet)[1]
        # 创建k个质心矩阵
        centroids = np.mat(np.zeros((k,n))) 
        # 在每一维的边界内创建随机簇质心
        for j in range(n): 
            minJ = min(dataSet[:,j])
            # 范围 = 最大值 - 最小值
            rangeJ = float(max(dataSet[:,j]) - minJ)
            centroids[:,j] = np.mat(minJ + rangeJ * np.random.rand(k,1))
        return centroids
    
    def kMeans(dataSet, k, distMeas=distEclud, createCent=randCent):
        """ K-Means 聚类算法 - - - - dataSet - 数据集 k - 簇的数目 distMeas - 计算距离函数 createCent - 创建初始质心函数 """
        m = np.shape(dataSet)[0]
        # 一列记录簇索引值，一列存储误差(误差是指当前点到簇质心的距离)
        clusterAssment = np.mat(np.zeros((m, 2))) 
        centroids = createCent(dataSet, k)
        # 记录簇改变
        clusterChanged = True
        while clusterChanged:
            clusterChanged = False
            # 循环每一个数据点并分配到最近的质心中去
            for i in range(m):    
                minDist = np.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[np.nonzero(clusterAssment[:, 0].A==cent)[0]] 
                # 将质心修改为簇中所有点的平均值，mean 就是求平均值的
                centroids[cent,:] = np.mean(ptsInClust, axis=0) 
        return centroids, clusterAssment
    
    def showData(dataMat,centroids,clust,k):
        """ 数据可视化 - - - - dataMat - 数据矩阵 centroids - 质心 clust - 簇分配结果 k - 簇的个数 """
        data = np.array(dataMat)
        datanum=len(data)
        for i in range(k):
            cluster=[]
            for j in range(datanum):
                if clust[j,0]==i:
                    cluster.append(data[j])
            plt.scatter(np.transpose(cluster)[0], np.transpose(cluster)[1])
        cen=np.array(centroids)   
        plt.scatter(np.transpose(cen)[0], np.transpose(cen)[1],marker='+')
        plt.show()
    
    def testKMeans(k,filep):
        """ 测试k-means 聚类算法 - - - - k - 簇的个数 filep - 文件路径 """
        dataMat = np.mat(loadDataSet(filep))
        myCentroids, clustAssing = kMeans(dataMat,k)
        showData(dataMat,myCentroids,clustAssing,k)
    
    if __name__ == "__main__":
        filepath='10.KMeans/testSet.txt'
        testKMeans(4,filepath)

结果：

[[ 0.08495263 -3.1470703 ]
     [ 1.79128272 -3.49504779]
     [ 0.97056461  0.12167986]
     [ 2.8122667  -2.14469345]]
    [[-3.19984738 -2.96423548]
     [ 2.58639411 -3.57601678]
     [ 0.09765693  2.86443007]
     [ 3.51402856 -2.07382678]]
    [[-3.38237045 -2.9473363 ]
     [ 2.44798442 -3.43588358]
     [-0.02298687  2.99472915]
     [ 3.431003   -1.363668  ]]
    [[-3.53973889 -2.89384326]
     [ 2.2728545  -3.41806164]
     [-0.09810934  3.03211629]
     [ 3.43046378 -0.893382  ]]
    [[-3.53973889 -2.89384326]
     [ 2.28769    -3.23832819]
     [-0.29458614  3.07335139]
     [ 3.66311589  0.05552433]]
    [[-3.53973889 -2.89384326]
     [ 2.42776071 -3.19858565]
     [-0.70059397  3.13642319]
     [ 3.34275475  1.111461  ]]
    [[-3.53973889 -2.89384326]
     [ 2.54173689 -3.11892933]
     [-1.6334182   3.03655888]
     [ 3.00278739  2.19743744]]
    [[-3.53973889 -2.89384326]
     [ 2.65077367 -2.79019029]
     [-2.46154315  2.78737555]
     [ 2.6265299   3.10868015]]

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25hbmFzaGlfRg_size_16_color_FFFFFF_t_70 1]  
可以看到，经过8次迭代之后K-均值算法收敛。

## 3.二分 K-Means 聚类算法 ##

def biKMeans(dataSet, k, distMeas=distEclud):
        """ 二分 KMeans 聚类算法 - - - - dataSet - 数据集 k - 簇的数目 distMeas - 计算距离函数 """
        m = np.shape(dataSet)[0]
        # 保存每个数据点的簇分配结果和平方误差
        clusterAssment = np.mat(np.zeros((m,2))) 
        # 质心初始化为所有数据点的均值
        centroid0 = np.mean(dataSet, axis=0).tolist()[0] 
        # 存放质心
        centList =[centroid0] 
        # 计算所有数据点到初始质心的距离平方误差
        for j in range(m): 
            clusterAssment[j,1] = distMeas(np.mat(centroid0), dataSet[j,:])**2
        # 当质心数量小于 k 时，二分迭代
        while (len(centList) < k): 
            lowestSSE = np.inf
            for i in range(len(centList)): 
                # 获取当前簇 i 下的所有数据点，进行二分 kMeans 处理
                ptsInCurrCluster = dataSet[np.nonzero(clusterAssment[:,0].A==i)[0],:] 
                centroidMat, splitClustAss = kMeans(ptsInCurrCluster, 2, distMeas)
                # 将二分 kMeans 结果中的平方和的距离进行求和
                sseSplit = np.sum(splitClustAss[:,1]) 
                # 将未参与二分 kMeans 分配结果中的平方和的距离进行求和
                sseNotSplit = np.sum(clusterAssment[np.nonzero(clusterAssment[:,0].A!=i)[0],1]) 
                print ("sseSplit, and notSplit: ",sseSplit,sseNotSplit)
                #若总误差和小于最小误差和，记录
                if (sseSplit + sseNotSplit) < lowestSSE: 
                    bestCentToSplit = i
                    bestNewCents = centroidMat
                    bestClustAss = splitClustAss.copy()
                    lowestSSE = sseSplit + sseNotSplit
            # 找出最好的簇分配结果 
            bestClustAss[np.nonzero(bestClustAss[:,0].A == 1)[0],0] = len(centList) 
            bestClustAss[np.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]) 
            # 重新分配最好簇下的数据（质心）以及SSE
            clusterAssment[np.nonzero(clusterAssment[:,0].A == bestCentToSplit)[0],:]= bestClustAss 
        return np.mat(centList), clusterAssment
    
    def testbiKMeans(k,filep):
        """ 测试二分 KMeans 聚类算法 - - - - k - 簇的个数 filep - 文件路径 """
        dataMat = np.mat(loadDataSet(filep))
        myCentroids, clustAssing = biKMeans(dataMat,k)
        showData(dataMat,myCentroids,clustAssing,k)
    
    if __name__ == "__main__":
        #1.测试k-means 聚类算法
        """ filepath='10.KMeans/testSet.txt' testKMeans(4,filepath) """
        #2.测试二分 KMeans 聚类算法
        filepath='10.KMeans/testSet2.txt'
        testbiKMeans(3,filepath)

结果：

[[-3.14742611 -3.12648867]
     [-4.43243513  4.42896576]]
    [[-0.32150057 -2.62473743]
     [-0.06953469  3.29844341]]
    [[-0.45965615 -2.7782156 ]
     [-0.00675605  3.22710297]]
    sseSplit, and notSplit:  1216.4437240993682 0.0
    the bestCentToSplit is:  0
    the len of bestClustAss is:  60
    [[-1.50786484 -3.48728639]
     [-1.31476755 -2.92558692]]
    [[-0.60498967 -3.775502  ]
     [-0.43400906 -2.60222388]]
    [[ 0.124341   -3.594312  ]
     [-0.77411615 -2.33877908]]
    [[ 0.34658275 -3.48379675]
     [-0.99714875 -2.30782817]]
    [[ 0.35496167 -3.36033556]
     [-1.12616164 -2.30193564]]
    sseSplit, and notSplit:  23.82180447123951 1216.4437240993682
    [[-1.45823624  4.48218902]
     [-3.14911701  1.49929085]]
    [[ 0.94818419  3.40211065]
     [-3.29599467  2.62429878]]
    [[ 2.76275171  3.12704005]
     [-3.06779095  3.33769884]]
    [[ 2.93386365  3.12782785]
     [-2.94737575  3.3263781 ]]
    sseSplit, and notSplit:  60.59976828718332 0.0
    the bestCentToSplit is:  1
    the len of bestClustAss is:  40

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25hbmFzaGlfRg_size_16_color_FFFFFF_t_70 2]

# 四、小结 #

1.  聚类是一种**无监督**的学习方法。所谓无监督学习是指事先并不知道要寻找的内容，即没有目标变量。
2.  聚类将数据点归到多个簇中，其中相似数据点处于同一簇，而不相似数据点处于不同簇中。
3.  聚类中可以使用多种不同的方法来计算相似度。  
    一种广泛使用的聚类算法是**K-均值算法**，其中k是用户指定的要创建的簇的数目。
4.  K-均值聚类算法以k个随机质心开始。算法会计算每个点到质心的距离。每个点会被分配到距其最近的簇质心，然后紧接着基于新分配到簇的点更新簇质心。以上过程重复数次，直到簇质心不再改变。这个简单的算法非常有效但是也**容易受到初始簇质心的影响**。
5.  为了获得更好的聚类效果，可以使用另一种称为**二分K-均值**的聚类算法。  
    二分K-均值算法首先将所有点作为一个簇，然后使用K均值算法（k = 2）对其划分。下一次迭代时，选择有最大误差的簇进行划分。该过程重复直到k个簇创建成功为止。二分K-均值的聚类效果要好于K-均值算法。

[format_png]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9jYW1vLmdpdGh1YnVzZXJjb250ZW50LmNvbS81NDQxZjIwYTg3MGI5Yzc0NTRmOGYxZDFhYTA2OTNkNzhjMmI3MmNiLzY4NzQ3NDcwM2EyZjJmNjQ2MTc0NjEyZTYxNzA2MTYzNjg2NTYzNmUyZTZmNzI2NzJmNjk2ZDY3MmY0MTY5NGM2NTYxNzI2ZTY5NmU2NzJmNmQ2YzJmMzEzMDJlNGI0ZDY1NjE2ZTczMmY2MTcwNjE2MzY4NjU2MzZlMmQ2YjZkNjU2MTZlNzMyZDcwNjE3Mjc0Njk2MTZjMmQ2MjY1NzM3NDJkNzI2NTczNzU2Yzc0MmQzMTJlNmE3MDY3?x-oss-process=image/format,png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25hbmFzaGlfRg_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20191220220228146.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25hbmFzaGlfRg==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25hbmFzaGlfRg_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20191221093906668.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25hbmFzaGlfRg==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25hbmFzaGlfRg_size_16_color_FFFFFF_t_70 2]: https://img-blog.csdnimg.cn/20191221095746568.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25hbmFzaGlfRg==,size_16,color_FFFFFF,t_70