K-means 聚类算法原理

骑猪看日落 2022-05-28 06:45 215阅读 0赞

聚类分析是一个无监督学习 (Unsupervised Learning) 过程, 一般是用来对数据对象按照其特征属性进行分组，经常被应用在客户分群，欺诈检测，图像分析等领域。K-means 应该是最有名并且最经常使用的聚类算法了，其原理比较容易理解，并且聚类效果良好，有着广泛的使用。

和诸多机器学习算法一样，K-means 算法也是一个迭代式的算法，其主要步骤如下:

*  第一步，选择 K 个点作为初始聚类中心。
 *  第二步，计算其余所有点到聚类中心的距离，并把每个点划分到离它最近的聚类中心所在的聚类中去。在这里，衡量距离一般有多个函数可以选择，最常用的是欧几里得距离 (Euclidean Distance), 也叫欧式距离。公式如下：

![Figure xxx. Requires a heading][]

其中 C 代表中心点，X 代表任意一个非中心点。

*  第三步，重新计算每个聚类中所有点的平均值，并将其作为新的聚类中心点。
 *  最后，重复 (二)，(三) 步的过程，直至聚类中心不再发生改变，或者算法达到预定的迭代次数，又或聚类中心的改变小于预先设定的阀值。

在实际应用中，K-means 算法有两个不得不面对并且克服的问题。

1.  聚类个数 K 的选择。K 的选择是一个比较有学问和讲究的步骤，我们会在后文专门描述如何使用 Spark 提供的工具选择 K。
2.  初始聚类中心点的选择。选择不同的聚类中心可能导致聚类结果的差异。

Spark MLlib K-means 算法的实现在初始聚类点的选择上，借鉴了一个叫 K-means||的类 K-means++ 实现。K-means++ 算法在初始点选择上遵循一个基本原则: 初始聚类中心点相互之间的距离应该尽可能的远。基本步骤如下:

*  第一步，从数据集 X 中随机选择一个点作为第一个初始点。
 *  第二步，计算数据集中所有点与最新选择的中心点的距离 D(x)。
 *  第三步，选择下一个中心点，使得![img01.png][]最大。

*  第四部，重复 (二),(三) 步过程，直到 K 个初始点选择完成。
    
    ## MLlib 的 K-means 实现 ##
    
    Spark MLlib 中 K-means 算法的实现类 (KMeans.scala) 具有以下参数，具体如下。
    
    ##### 图 1. MLlib K-means 算法实现类预览 #####
    
    ![图 1. MLlib K-means 算法实现类预览][1. MLlib K-means]
    
    通过下面默认构造函数，我们可以看到这些可调参数具有以下初始值。
    
    ##### 图 2. MLlib K-means 算法参数初始值 #####
    
    ![图 2. MLlib K-means 算法参数初始值][2. MLlib K-means]
    
    参数的含义解释如下：
    
     *  k 表示期望的聚类的个数。
     *  maxInterations 表示方法单次运行最大的迭代次数。
     *  runs 表示算法被运行的次数。K-means 算法不保证能返回全局最优的聚类结果，所以在目标数据集上多次跑 K-means 算法，有助于返回最佳聚类结果。
     *  initializationMode 表示初始聚类中心点的选择方式, 目前支持随机选择或者 K-means||方式。默认是 K-means||。
     *  initializationSteps表示 K-means||方法中的部数。
     *  epsilon 表示 K-means 算法迭代收敛的阀值。
     *  seed 表示集群初始化时的随机种子。
    
    通常应用时，我们都会先调用 KMeans.train 方法对数据集进行聚类训练，这个方法会返回 KMeansModel 类实例，然后我们也可以使用 KMeansModel.predict 方法对新的数据点进行所属聚类的预测，这是非常实用的功能。
    
    KMeans.train 方法有很多重载方法，这里我们选择参数最全的一个展示。
    
    ##### 图 3. KMeans.train 方法预览 #####
    
    ![图 3. KMeans.train 方法预览][3. KMeans.train]
    
    KMeansModel.predict 方法接受不同的参数，可以是向量，或者 RDD，返回是入参所属的聚类的索引号。
    
    ##### 图 4. KMeansModel.predict 方法预览 #####
    
    ![图 4. KMeansModel.predict 方法预览][4. KMeansModel.predict]
    
    ## 如何选择 K ##
    
    前面提到 K 的选择是 K-means 算法的关键，Spark MLlib 在 KMeansModel 类里提供了 computeCost 方法，该方法通过计算所有数据点到其最近的中心点的平方和来评估聚类的效果。一般来说，同样的迭代次数和算法跑的次数，这个值越小代表聚类的效果越好。但是在实际情况下，我们还要考虑到聚类结果的可解释性，不能一味的选择使 computeCost 结果值最小的那个 K。
 *  # K-Means与KNN #
    
    　　　　初学者很容易把K-Means和KNN搞混，两者其实差别还是很大的。
    
    　　　　K-Means是无监督学习的聚类算法，没有样本输出；而KNN是监督学习的分类算法，有对应的类别输出。KNN基本不需要训练，对测试集里面的点，只需要找到在训练集中最近的k个点，用这最近的k个点的类别来决定测试点的类别。而K-Means则有明显的训练过程，找到k个类别的最佳质心，从而决定样本的簇类别。
    
    　　　　当然，两者也有一些相似点，两个算法都包含一个过程，即找出和某一个点最近的点。两者都利用了最近邻(nearest neighbors)的思想。
 *  K-Means小结
    
    　K-Means是个简单实用的聚类算法，这里对K-Means的优缺点做一个总结。
    
    　　　　K-Means的主要优点有：
    
    　　　　1）原理比较简单，实现也是很容易，收敛速度快。
    
    　　　　2）聚类效果较优。
    
    　　　　3）算法的可解释度比较强。
    
    　　　　4）主要需要调参的参数仅仅是簇数k。
    
    　　　　K-Means的主要缺点有：
    
    　　　　1）K值的选取不好把握(改进：可以通过在一开始给定一个适合的数值给k，通过一次K-means算法得到一次聚类中心。对于得到的聚类中心，根据得到的k个聚类的距离情况，合并距离最近的类，因此聚类中心数减小，当将其用于下次聚类时，相应的聚类数目也减小了，最终得到合适数目的聚类数。可以通过一个评判值E来确定聚类数得到一个合适的位置停下来，而不继续合并聚类中心。重复上述循环，直至评判函数收敛为止，最终得到较优聚类数的聚类结果)。
    
    　　　　2）对于不是凸的数据集比较难收敛(改进：基于密度的聚类算法更加适合，比如DESCAN算法)
    
    　　　　3）如果各隐含类别的数据不平衡，比如各隐含类别的数据量严重失衡，或者各隐含类别的方差不同，则聚类效果不佳。
    
    　　　　4） 采用迭代方法，得到的结果只是局部最优。
    
    　　　　5） 对噪音和异常点比较的敏感(改进1：离群点检测的LOF算法，通过去除离群点后再聚类，可以减少离群点和孤立点对于聚类效果的影响；改进2：改成求点的中位数，这种聚类方式即K-Mediods聚类（K中值）)。
    
               6）初始聚类中心的选择(改进1：k-means++;改进2：二分K-means，相关知识详见[这里][Link 1]和[这里][Link 2])。

[Figure xxx. Requires a heading]: /images/20220528/6a4db28851db45ab996227540eefa8e0.png
[img01.png]: /images/20220528/95c30a105295402ab02b9dafcb9e27c8.png
[1. MLlib K-means]: /images/20220528/5caa1fea62da4e26bd2058bb091d5663.png
[2. MLlib K-means]: /images/20220528/cdbb00cce110476d8e48346d44126ef1.png
[3. KMeans.train]: /images/20220528/5c52f69ae6bb408eb8d1241348b906fc.png
[4. KMeansModel.predict]: /images/20220528/2db67024216e4d7786e5c480cc52fc12.png
[Link 1]: http://blog.csdn.net/gamer_gyt/article/details/48949227
[Link 2]: http://blog.csdn.net/zouxy09/article/details/17590137