机器学习实战（九）K-均值聚类算法

ゞ浴缸里的玫瑰 2021-10-29 23:22 587阅读 0赞

### 文章目录 ###

*   *  前言：
     *  一、K-均值聚类算法
     *  二、算法分析
     *  三、二分k均值聚类

## 前言： ##

机器学习中有两类的大问题，一个是分类，一个是聚类。

分类是根据一些给定的已知类别标号的样本，训练某种学习机器，使它能够对未知类别的样本进行分类。这属于supervised learning（监督学习）。

聚类指事先并不知道任何样本的类别标号，希望通过某种算法来把一组未知类别的样本划分成若干类别，这在机器学习中被称作 unsupervised learning （无监督学习）。

聚类与分类算法的最大区别在于, 分类的目标类别已知, 而聚类的目标类别是未知的.

本文所要介绍的K-均值聚类算法是无监督学习！

## 一、K-均值聚类算法 ##

**1.简介**  
聚类是一种无监督的学习, 它将相似的对象归到一个簇中, 将不相似对象归到不同簇中.

简单例子：

如下图左所示，从数据点的大致形状可以看出它们大致聚为三个cluster，其中两个紧凑一些，剩下那个松散一些。我们的目的是为这些数据分组，以便能区分出属于不同的簇的数据，如果按照分组给它们标上不同的颜色（如下图右）  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FzMTc4MDkyNTk3MTU_size_16_color_FFFFFF_t_70]

相似这一概念取决于所选择的相似度计算方法.

K-Means 是发现给定数据集的 K 个簇的聚类算法, 之所以称之为 K-均值 是因为它可以发现 K 个不同的簇, 且每个簇的中心采用簇中所含值的均值计算而成.

簇个数 K 是用户指定的, 每一个簇通过其质心（centroid）, 即簇中所有点的中心来描述.

**2.优缺点**

优点: 容易实现  
缺点:可能收敛到局部最小值, 在大规模数据集上收敛较慢  
使用数据类型 : 数值型数据

**3.k-Means术语**

簇: 所有数据点点集合，簇中的对象是相似的。

质心: 簇中所有点的中心（计算所有点的均值而来）.

SSE: Sum of Sqared Error（平方误差和）, SSE 值越小，表示越接近它们的质心. 由于对误差取了平方，因此更加注重那么远离中心的点.

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FzMTc4MDkyNTk3MTU_size_16_color_FFFFFF_t_70 1]  
**4.k-means算法基本思想**

通过迭代寻找k个聚类的一种划分方案，使得用这k个聚类的均值来代表相应各类样本时所得的总体误差最小。

**5.k-means算法的基础**

最小误差平方和准则。

其代价函数是：  
![在这里插入图片描述][20190817165325322.png]  
式中，μc(i)表示第i个聚类的均值。我们希望代价函数最小，直观的来说，各类内的样本越相似，其与该类均值间的误差平方越小，对所有类所得到的误差平方求和，即可验证分为k类时，各聚类是否是最优的。

**6.具体算法描述**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FzMTc4MDkyNTk3MTU_size_16_color_FFFFFF_t_70 2]

下图展示了对n个样本点进行K-means聚类的效果，这里k取2。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FzMTc4MDkyNTk3MTU_size_16_color_FFFFFF_t_70 3]

**7.K-Means算法伪代码**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FzMTc4MDkyNTk3MTU_size_16_color_FFFFFF_t_70 4]  
**8.K-Means 开发流程**

收集数据：使用任意方法
    准备数据：需要数值型数据类计算距离, 也可以将标称型数据映射为二值型数据再用于距离计算
    分析数据：使用任意方法
    训练算法：此步骤不适用于 K-Means 算法
    测试算法：应用聚类算法、观察结果.可以使用量化的误差指标如误差平方和（后面会介绍）来评价算法的结果.
    使用算法：可以用于所希望的任何应用.通常情况下, 簇质心可以代表整个簇的数据来做出决策.

**9.python3代码实现**

*  从文件加载数据集

# 从文本中构建矩阵，加载文本文件，然后处理
    def loadDataSet(fileName):    # 通用函数，用来解析以 tab 键分隔的 floats（浮点数），例如: 1.658985    4.285136
        dataMat = []
        fr = open(fileName)
        for line in fr.readlines():
            curLine = line.strip().split('\t')
            fltLine = map(float,curLine)    # 映射所有的元素为 float（浮点数）类型
            dataMat.append(fltLine)
        return dataMat

*  计算两个向量的欧氏距离

# 计算两个向量的欧式距离（可根据场景选择）
    def distEclud(vecA, vecB):
        return sqrt(sum(power(vecA - vecB, 2))) # la.norm(vecA-vecB)

*  构建一个包含 K 个随机质心的集合

# 为给定数据集构建一个包含 k 个随机质心的集合。随机质心必须要在整个数据集的边界之内，这可以通过找到数据集每一维的最小和最大值来完成。然后生成 0~1.0 之间的随机数并通过取值范围和最小值，以便确保随机点在数据的边界之内。
    def randCent(dataSet, k):
        n = shape(dataSet)[1] # 列的数量
        centroids = mat(zeros((k,n))) # 创建k个质心矩阵
        for j in range(n): # 创建随机簇质心，并且在每一维的边界内
            minJ = min(dataSet[:,j])    # 最小值
            rangeJ = float(max(dataSet[:,j]) - minJ)    # 范围 = 最大值 - 最小值
            centroids[:,j] = mat(minJ + rangeJ * random.rand(k,1))    # 随机生成
        return centroids

*  K-Means 聚类算法

# k-means 聚类算法
    # 该算法会创建k个质心，然后将每个点分配到最近的质心，再重新计算质心。
    # 这个过程重复数次，直到数据点的簇分配结果不再改变位置。
    # 运行结果（多次运行结果可能会不一样，可以试试，原因为随机质心的影响，但总的结果是对的， 因为数据足够相似，也可能会陷入局部最小值）
    def kMeans(dataSet, k, distMeas=distEclud, createCent=randCent):
        m = shape(dataSet)[0]    # 行数
        clusterAssment = mat(zeros((m, 2)))    # 创建一个与 dataSet 行数一样，但是有两列的矩阵，用来保存簇分配结果
        centroids = createCent(dataSet, k)    # 创建质心，随机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（最小距离）还小，更新 minDist（最小距离）和最小质心的 index（索引）
                        minDist = distJI; minIndex = j
                if clusterAssment[i, 0] != minIndex:    # 簇分配结果改变
                    clusterChanged = True    # 簇改变
                    clusterAssment[i, :] = minIndex,minDist**2    # 更新簇分配结果为最小质心的 index（索引），minDist（最小距离）的平方
            print centroids
            for cent in range(k): # 更新质心
                ptsInClust = dataSet[nonzero(clusterAssment[:, 0].A==cent)[0]] # 获取该簇中的所有点
                centroids[cent,:] = mean(ptsInClust, axis=0) # 将质心修改为簇中所有点的平均值，mean 就是求平均值的
        return centroids, clusterAssment

*  测试代码

datMaat = mat(loadDataSet('testSet.txt'))
    myCentroids, clustAssing = kMeans(datMat, 4)

*  使用matplotlib绘出数据点

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FzMTc4MDkyNTk3MTU_size_16_color_FFFFFF_t_70 5]

## 二、算法分析 ##

**k-means算法比较简单，但也有几个比较大的缺点：**

**1.k值的选择**

k值的选择是用户指定的，不同的k得到的结果会有挺大的不同，如下图所示，左边是k=3的结果，这个就太稀疏了，蓝色的那个簇其实是可以再划分成两个簇的。而右图是k=5的结果，可以看到红色菱形和蓝色菱形这两个簇应该是可以合并成一个簇的：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FzMTc4MDkyNTk3MTU_size_16_color_FFFFFF_t_70 6]  
**2.对k个初始质心的选择比较敏感，** 容易陷入局部最小值。例如，我们上面的算法运行的时候，有可能会得到不同的结果，如下面这两种情况。K-means也是收敛了，只是收敛到了局部最小值：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FzMTc4MDkyNTk3MTU_size_16_color_FFFFFF_t_70 7]  
**3.存在局限性**  
如下面这种非球状的数据分布就搞不定了：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FzMTc4MDkyNTk3MTU_size_16_color_FFFFFF_t_70 8]  
**4.数据库比较大的时候，收敛会比较慢。**

k-means老早就出现在江湖了。所以以上的这些不足也被世人的目光敏锐的捕捉到，并融入世人的智慧进行了某种程度上的改良。例如问题（1）对k的选择可以先用一些算法分析数据的分布，如重心和密度等，然后选择合适的k。而对问题（2），有人提出了另一个成为二分k均值（bisecting k-means）算法，它**对初始的k个质心的选择就不太敏感**。

## 三、二分k均值聚类 ##

二分k均值聚类算法就是解决：k均值聚类算法对初始k个质心点的选取比较敏感问题。

**1.二分k均值（bisecting k-means）算法的主要思想是：**

首先将所有点作为一个簇，然后将该簇一分为二。之后选择能最大程度降低聚类代价函数（也就是误差平方和）的簇划分为两个簇。以此进行下去，直到簇的数目等于用户给定的数目k为止。

以上隐含着一个**原则**是：因为聚类的误差平方和能够衡量聚类性能，该值越小表示数据点月接近于它们的质心，聚类效果就越好。所以我们就需要对误差平方和最大的簇进行再一次的划分，因为误差平方和越大，表示该簇聚类越不好，越有可能是多个簇被当成一个簇了，所以我们首先需要对这个簇进行划分。

**2.二分k均值算法的伪代码如下：**

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FzMTc4MDkyNTk3MTU_size_16_color_FFFFFF_t_70 9]

**3.python代码实现**

#distMeas为距离计算函数
    def biKmeans(dataSet, k, distMeas=distEclud):
        m = shape(dataSet)[0]
        #(m,2)维矩阵,第一列保存样本所属簇,第二列保存样本到簇中心的距离
        clusterAssment = mat(zeros((m,2)))
        #取数据集特征均值作为初始簇中心
        centroid0 = mean(dataSet, axis=0).tolist()[0]
        #centList保存簇中心数组,初始化为一个簇中心
        #create a list with one centroid,转化成二维list
        centList =[centroid0]
        #calc initial Error
        for j in range(m):
            clusterAssment[j,1] = distMeas(mat(centroid0), dataSet[j,:])**2
        #迭代，直到簇中心集合长度达到k,也就是不断地分割，划分簇的数量达到所想要划分的簇 数，则停止迭代
        while (len(centList) < k):
        #初始化最小误差
            lowestSSE = inf
            #迭代簇中心集合，找出找出分簇后总误差最小的那个簇进行分解
            for i in range(len(centList)):
                #get the data points currently in cluster i
                #获取属于i簇的数据集样本
                ptsInCurrCluster = dataSet[nonzero(clusterAssment[:,0].A==i)[0],:]
                #对该簇进行k均值聚类
                centroidMat, splitClustAss = kMeans(ptsInCurrCluster, 2, distMeas)
                #获取该簇分类后的误差和
                sseSplit = sum(splitClustAss[:,1])#compare the SSE to the currrent minimum
                #获取不属于该簇的样本集合的误差和，注意矩阵过滤中用的是!=i
                sseNotSplit = sum(clusterAssment[nonzero(clusterAssment[:,0].A!=i)[0],1])
                #打印该簇分类后的误差和和不属于该簇的样本集合的误差和
                print("sseSplit, and notSplit: ",sseSplit,sseNotSplit)
                #两误差和相加即为分簇后整个样本集合的误差和,找出簇中心集合中能让分簇后误差和最小的簇中心，保存最佳簇中心(bestCentToSplit),最佳分簇中心集合(bestNewCents),以及分簇数据集中样本对应簇中心及距离集合(bestClustAss),最小误差(lowestSSE)
                if (sseSplit + sseNotSplit) < lowestSSE:
                    bestCentToSplit = i
                    bestNewCents = centroidMat
                    bestClustAss = splitClustAss.copy()
                    lowestSSE = sseSplit + sseNotSplit
            #更新用K-means获取的簇中心集合，将簇中心换为len(centList)和bestCentToSplit,以便之后调整clusterAssment(总样本集对应簇中心与和簇中心距离的矩阵)时一一对应
            bestClustAss[nonzero(bestClustAss[:,0].A == 1)[0],0] = len(centList) #change 1 to 3,4, or whatever
            bestClustAss[nonzero(bestClustAss[:,0].A == 0)[0],0] = bestCentToSplit
            print('the bestCentToSplit is: ',bestCentToSplit)
            print('the len of bestClustAss is: ', len(bestClustAss))
            #更新簇中心集合,注意与bestClustAss矩阵是一一对应的
            centList[bestCentToSplit] = bestNewCents[0,:].tolist()[0]#replace a centroid with two best centroids 
            centList.append(bestNewCents[1,:].tolist()[0])
            #reassign new clusters, and SSE
            clusterAssment[nonzero(clusterAssment[:,0].A == bestCentToSplit)[0],:]= bestClustAss
        return mat(centList), clusterAssment

*  测试代码

datMat3 = mat(loadDataSet('testSet2.txt'))
    centList, myNewAssments = biKmeans(datMat3, 3)
    print(centList)

*  绘制图表，更好的理解。

xArr = datMat3[:,0].flatten().A[0]
    yArr = datMat3[:,1].flatten().A[0]
    xArr1 = centList[:,0].flatten().A[0]
    yArr1 = centList[:,1].flatten().A[0]
    
    #paint为笔者自己写的绘图函数
    # print(xArr,yArr,xArr1,yArr1) 
    
    def paint(xArr,yArr,xArr1,yArr1):
        fig = plt.figure()
        ax = fig.add_subplot(111)
        ax.scatter(xArr,yArr,c='blue')
        ax.scatter(xArr1,yArr1,c='red')
        plt.show()
    
    paint(xArr,yArr,xArr1,yArr1)

*  结果图：

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FzMTc4MDkyNTk3MTU_size_16_color_FFFFFF_t_70 10]

参考资料：  
\[1\]《统计学习方法》李航著

\[2\]《机器学习实战》Peter Harrington著

\[3\] [机器学习算法与Python实践之（五）k均值聚类（k-means）][Python_k_k-means]

\[4\][【机器学习实战】第10章 K-Means（K-均值）聚类算法][10_ K-Means_K-]

\[5\] [基本Kmeans算法介绍及其实现][Kmeans]

\[6\] [k-means+python︱scikit-learn中的KMeans聚类实现( + MiniBatchKMeans)][k-means_python_scikit-learn_KMeans_ _ MiniBatchKMeans]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FzMTc4MDkyNTk3MTU_size_16_color_FFFFFF_t_70]: /images/20211029/599550ff101748be9c27e0e0c8a8f0e3.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FzMTc4MDkyNTk3MTU_size_16_color_FFFFFF_t_70 1]: /images/20211029/05c0ec02080e46708fa1b2897b3de639.png
[20190817165325322.png]: /images/20211029/7b30f81a7039498ebfa254beb5ace940.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FzMTc4MDkyNTk3MTU_size_16_color_FFFFFF_t_70 2]: /images/20211029/4664a8b004294d0fa6ebf27828af0b6b.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FzMTc4MDkyNTk3MTU_size_16_color_FFFFFF_t_70 3]: /images/20211029/770942c1eae24e2d885f08d7320d3fc7.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FzMTc4MDkyNTk3MTU_size_16_color_FFFFFF_t_70 4]: /images/20211029/ee26dbf5f7b7439b829a55b3288d40fe.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FzMTc4MDkyNTk3MTU_size_16_color_FFFFFF_t_70 5]: /images/20211029/a08e824772f742c8ad098c736b9a4a11.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FzMTc4MDkyNTk3MTU_size_16_color_FFFFFF_t_70 6]: /images/20211029/628860a3eb5d4dae8bb2496c25a8edba.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FzMTc4MDkyNTk3MTU_size_16_color_FFFFFF_t_70 7]: /images/20211029/251e35ae8add46a1b45de0ad7c1181ef.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FzMTc4MDkyNTk3MTU_size_16_color_FFFFFF_t_70 8]: /images/20211029/d145850fa01b4b3b9114a5261004aced.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FzMTc4MDkyNTk3MTU_size_16_color_FFFFFF_t_70 9]: /images/20211029/d399324d30294f8ca38d741d10541a87.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FzMTc4MDkyNTk3MTU_size_16_color_FFFFFF_t_70 10]: /images/20211029/229def077ff34f96b3d176494274ba62.png
[Python_k_k-means]: https://blog.csdn.net/zouxy09/article/details/17589329?utm_source=app
[10_ K-Means_K-]: https://www.jianshu.com/p/8f11d6cd6b30
[Kmeans]: https://blog.csdn.net/qll125596718/article/details/8243404
[k-means_python_scikit-learn_KMeans_ _ MiniBatchKMeans]: https://blog.csdn.net/sinat_26917383/article/details/70240628