阅读 139

k-means聚类算法 && k-means++聚类算法

     0/K-means聚类算法:一种无监督学习算法

     1/概述
         K-means聚类算法是基于距离的聚类算法。它采用距离大小作为相似性的评价指标,即认为两个数据点的距离越近,其相似度就越大。该算法认为簇是由距离靠近的数据点组成的,因此把得到紧凑且独立的簇作为最终目标。

     2/算法核心思想
         K-means聚类算法是一种迭代求解的聚类分析算法,其步骤是随机选取K个数据点作为初始聚类中心,然后计算其他每个数据点与各个初始聚类中心的距离,把每个数据点分配给距离它最近的初始聚类中心。初始聚类中心以及分配给它们的数据点就构成一个簇。每分配一个数据点,聚类的聚类中心会根据聚类中现有的对象被重新计算。这个过程将不断重复直到满足某个终止条件。终止条件可以是没有(或最小数目)对象被重新分配给不同的聚类,没有(或最小数目)聚类中心再发生变化,误差平方和局部最小。

     3/算法实现步骤
         1、首先确定一个k值,即我们希望将数据集合聚合成几类
         2、从数据集合中随机选择k个数据点作为初始聚类中心
         3、对数据集和中的每一个点,计算其与每一个初始聚类中心的距离(如欧式距离),离哪个初始聚类中心近,就划分到那个初始聚类中心所属的簇。
         4、把所有数据归好簇之后,一共有k个簇。然后重新计算每个簇的中心。
         5、如果新计算出来的中心和原来的中心之间的距离小于某一个设置的阈值(表示重新计算的质心的位置变化不大,趋于稳定,或者说收敛),我们可以认为聚类已经达到期望的结果,算法终止。
         6、如果新质心和原质心距离变化很大,需要迭代3~5步骤。

     4/算法步骤图解
复制代码

         <1> 上图a表达了初始的数据集合,假设k=2,此时还没有分类,全都是一种颜色
         <2> 在图b中,我们随机选择了两个初始聚类中心,即图中的红色质心和蓝色质心
         <3> 分别计算数据集合中所有数据点到初始聚类中心的距离,并标记每个数据点的类别为和该样本距离最小的聚类中心的类别,经过计算数据点和红色质心和蓝色质心的距离,我们得到了所有数据点的第一轮迭代后的类别,如图c所示
         <4> 此时我们对我们当前标记为红色和蓝色的点分别求其新的质心,如图d所示,新的红色质心和蓝色质心的位置已经发生了变动
         <5> 图e和图f重复了我们在图c和图d的过程,即将所有点的类别标记为距离最近的质心的类别并求新的质心。
         <6> 最终我们得到的两个类别如图f。
         

     5/K-means术语:
         簇:所有数据的点集合,簇中的对象是相似的。
         质心:簇中所有点的中心(计算所有点的中心而来)
    
     6/K-means算法优缺点
         优点:
             1、原理比较简单,实现也是很容易,收敛速度快。
             2、当每个簇是密集的,而簇与簇之间区别明显时, 它的效果较好。
             3、需要调节的参数少,主要需要调参的参数仅仅是簇数k。
         缺点:
             1、K值需要预先给定,很多情况下K值的估计是非常困难的。
             2、K-Means算法对初始选取的质心点是敏感的,不同的随机种子点得到的聚类结果完全不同,对结果影响很大。
             3、对噪音和异常点比较的敏感。用来检测异常值。
             
     ###########################################################################################################################
     ###########################################################################################################################
     K-means++算法:
     由于k-means算法的分类结果会受到初始点的选取而有所区别,因此有提出这种算法的改进: K-means++
     算法步骤:
     其实这个算法也只是对初始点的选择有改进而已,其他步骤都和k-means算法一样。
     初始质心选取的基本思路就是:
             初始的聚类中心之间的相互距离要尽可能的远
             假设已经选取了n个初始聚类中心(n<K),则在选取第n+1个聚类中心时,距离当前n个聚类中心越远的点会有更高的概率被选为第n+1个聚类中心
     
     算法描述如下:
         步骤一:
             随机选取一个样本作为第一个聚类中心c1
         步骤二:
             计算每个样本与当前已有类聚中心最短距离(即与最近一个聚类中心的距离),用D(x)表示,这个值越大,表示被选取作为聚类中心的概率较越大
         步骤三:重复步骤二,直到选出k个初始聚类中心。

     ###########################################################################################################################
     ###########################################################################################################################
     k-means聚类算法有2个难点
             <1> 确定k值的大小
复制代码

             <2> 如何选择k个初始聚类中心
复制代码

     ################################################################################################
     ################################################################################################
复制代码
关注下面的标签,发现更多相似文章
评论