聚类与K-Means

本文介绍无监督学习中最基础的一种K-Means，全文共2300字，简单易懂，估计阅读时间8分钟。

在传统的数据挖掘领域中，聚类是其中最常见的方法。其种类层出不穷，有基于层次,密度,网格以及原型的聚类方法，还有核聚类，谱聚类等等。在同一聚类方法中也会针对数据集或者是算法本身的缺点引申出各种各样的升级的算法版本，所以聚类方法保罗万象，我们只能管中窥豹，逐个探索，最后由点串面，达到对聚类的总体认识。今天ARGO主要为大家介绍的是其中最著名也是最浅显易懂的一种：K-Means，本文的内容包括：

聚类方法的类别

K-Means的原理

K-Means的例子

算法的优缺点及其改进方法

一 聚类方法的类别

如前文所述，聚类方法有很多不同的种类。聚类方法是机器学习算法中出现最多，更新最快的一个领域。对传统的聚类方法进行归类，可以认为其一般可以归为四类：原型，密度，层次和网格聚类。

原型聚类

prototyped-based clustering，西瓜书说，"此类算法假设聚类结构能通过一组原型刻画”，也就是在一个簇cluster中，找到该簇的一个原型，将这个原型作为该簇的代表。需要预测的数据与这些原型作比较，从而判断出需要预测的数据属于哪些簇。

原型聚类在聚类算法中最为常见，这篇文章要介绍的K-means就属于这一种类。此外，学习向量量化（Learning Vector Quantization，LVQ）使用了带标签的数据进行有监督来辅助聚类，寻找一组原型向量，也是原型聚类中的典型算法。

在原型聚类中，高斯混合模型（Mixture-of-Gaussian）聚类则与K-Means 和 LVQ所使用的原型截然不同，它试图建立一种概率模型作为原型，因此很多学者直接将其划分成另外一类，基于概率聚类方法。高斯混合模型也是聚类中广泛应用的一种，ARGO将在之后的学习中给读者们再详细介绍。

密度聚类

density-based clustering，此类算法通常假定所有同类的样本是密度接近而且连接同等紧密的。密度聚类算法考虑样本类别的连接性问题时，从样本密度角度出发。针对不规则的聚类图形，此类算法应用比较广泛。DBSCAN(Density-Based Spatial Clustering of Applications with Noise) 是著名的密度聚类算法，其聚类过程如下图所示。其特点之一是不用提前指定簇类别数量，而且能迅速找到噪音点。

针对DBSCAN算法对于其密度搜索参数固定的缺点，OPTICS算法是其升级优化版本。

层次聚类

hierarchical clustering，层次聚类试图自下而上的以不同的层次对数据集进行分类，从而从下而上形成不同的层次类型的树形结构。层次聚类通常被看做成一棵树，其中最小的簇合并在一起创建下一个较高层次的簇，这一层次的簇再合并在一起就创建了再下一层次的簇。通过这样的过程，就可以生成一棵完整的树来完成聚类。AGNES是层次聚类中的典型算法。

图片来源：sigai，https://zhuanlan.zhihu.com/p/43651469

网格聚类

基于划分和层次聚类方法都无法发现非凸面形状的簇，真正能有效发现任意形状簇的算法是基于密度的算法，但基于密度的算法一般时间复杂度较高，1996年到2000年间，研究数据挖掘的学者们提出了大量基于网格的聚类算法，网格方法可以有效减少算法的计算复杂度，且同样对密度参数敏感。

引用自 https://cloud.tencent.com/developer/article/1005263

网格划分方法最核心的概念是将数据集从空间上划分成网格，然后将网格内的数据统计信息计算得到其密度信息，根据各个网格的密度信息再将高密度单元连接成簇。网格聚类方法跟密度聚类相似，但是效率要比密度聚类法方法高很多。STING，CLIQUE和WaveCluster 都是其中比较典型的算法。

其他聚类方法

基于图的聚类方法。这种方法与基于网格划分的方法类似，但是通过构造的是以样本边界为边和顶点的图形来划分簇的方法。典型代表是谱聚类方法。

模糊聚类方法。这种基于模糊数学的分类方法，分析该样本同时属于几类的概率，它的核心理念是事物并非非黑即白，而是存在着几种都属于的可能性。这种方法其实跟原型聚类本质上接近，因此概率聚类方法的典型代表FCM又被认为是划分聚类方式。

同时，针对不同聚类的具体算法的不同缺点，又有相应的改进算法，所以聚类算法远而观之，又多又杂。故而我们从K-Means一具体算法入手，开始和读者们一起探索聚类算法之路。

二 K-Means的原理

原型聚类的一般方法

依前文所述，K-Means算法属于原型聚类或很多博客上所写的划分聚类。这种聚类算法是根据给定的n个对象的数据集，预先构建k个簇的方法。每个划分即为一个簇，并且k每个对象必须属于而且只能属于一个簇。该方法一般是先给出一个初始的划分，然后用迭代重定位技术，不断地改进划分的结果。这种聚类算法涉及3个要点：

选择某种距离计算方法作为对象的相似度度量

定义某个准则函数用于评价聚类质量

初始质心的选择以及迭代方法

K-Means 流程

K-Means 算法是一种无监督学习算法，该算法的目的就是要给指定的对象分簇，簇的数目由k指定。这个算法基于一定的度量标准，迭代地将每个对象分配到k个簇中的一个。该算法的相似性度量是基于距离计算的，目前有多种计算距离的方法，不过最典型的就是欧几里得距离。欧几里得距离计算两点间的距离的计算公式如下：

其中，n表示特征数。

算法的流程很简单，具体如下：

1)随机地确定k个初始点作为质心。

2) 然后将数据集中的每个点分配到一个簇中，具体来讲，为每个点找距离其最近的质心，并将其分配给该质心所对应的簇。

3) 将每个簇的质心更新为该簇所有点的平均值，这也是该算法名称中Mean的由来。

4) 如果质心不再变化或者说变化很小或者到达一定的迭代次数，退出循环，否则返回到第2)步。

一般来说，让质心不再发生变化，也就是找到最优解是非常困难的。但是我们可以让质心在之后的迭代过程中变化很小，也就是达到收敛。在K-Means算法中，收敛的衡量标准是用的是误差平方和，如果每轮迭代后的计算结果开始收敛则认为分簇开始收敛。同时，误差平方和也是聚类性能的衡量指标。

K-Means算法简单易懂，接着我们用一个例子来说明这个算法的执行过程，加深读者对这种算法的理解。

三 K-Means的例子

使用的数据来自http://sci2s.ugr.es/keel/dataset.php?cod=1293

这是96个篮球运动员的5项技术统计数据，部分数据如下图所示：

每条有5个特征，这里只取用3个特征：每分钟助攻数、运动员身高和每分钟得分数，来对运动员进行聚类，看看能不能通过这三类特征给运动员在球场上分配一个合适的位置，如控卫，大前锋，中锋等。在未聚类时，用这三类特征构建三维点图如下：

聚成k=5类的散点图像（就像上面提到的，每次算法开始的时候质心的选择是随机的，所以每次的聚类结果是不同的，不一定可以得到想要的结果）：

就直观来看，身高对聚类结果的影响是最大的，可能是身高数据的量级和其他两项相比差距比较大，后续可以对身高数据做点标准化处理。 这也跟实际情况匹配，身高确实对一个篮球运动员的位置分配影响非常大。图中绿色的那些点，个子很高，得分效率可以，助攻不行，比较适合打中锋。紫色那些点，个子比较高，得分效率最好，助攻也可以，可以打小前锋或分卫；深蓝色那些点，个子一般，得分一般，助攻效率很高，最适合打控卫。其他两类没有明显特征，可能是没有固定位置。

四 算法的优缺点及其改进方法

K-Means算法也同其他的机器学习算法一样，有优点也有缺陷。其优点明显，迭代次数少，速度快，简单高效。当簇的分布接近高斯分布时，其聚类表现结果最佳。其缺点也一样突出：

用欧几里得公式计算距离求均值，对于连续特征比较方便，但是有限类型特征的则求均值没有意义。

需要预先设定k值，这个预先设定的值往往让人头疼不已。

质心的选择是随机给点，却是聚类是否准确很重要的依赖，其结果很有可能收敛于局部最优，靠天吃饭效果明显。

聚类效果还取决于数据集的分布，不能处理非球形簇、不同尺寸和不同密度的簇（如开始提到的笑脸数据分布）。

模型对于噪音点非常敏感，错误样本导致模型产生较大的偏差。

所以，针对这些缺点，各种优化算法应运而生。

K-Medoids 聚类

K-Medoids 以名字来看，其对K-Mean的mean做了些文章，其算法本身也确实如此，将质心是求簇所有点的均值变成了求簇中所有点的类中位数点，K-Medoids将从当前 cluster 中选取这样一个类中位数点，这个点到其他所有（当前 cluster 中的）点的距离之和最小——作为中心点。也就解决了对于非连续特征计算均值无意义的问题，将所有的质心限制在已有的空间之内。

但随之而来的问题是，这种计算又加剧了其计算成本，提高了算法的时间复杂度和空间复杂度。

二分K-Means(bisecting K-Means)

这种算法是为了克服K-Means算法收敛于局部最小值的问题。该算法首先将所有点作为一个簇，之后选择能最大限度降低聚类代价函数（误差平方和）的簇，将该簇划分为两个簇，一分为二。每次切分后，不停迭代计算，直至簇的数目等于用户给定的数目k为止,类似于决策树中寻找分裂点的计算模式。算法如下：

1) 将所有数据点看成一个簇

2) 当簇数目小于k时:

对每一个簇

计算总误差

在给定的簇上面进行k=2的k-均值聚类

计算将该簇一分为二后的总误差（误差平方和）

选择使得误差最小的那个簇进行划分操作

二分K均值可以收敛到最优，这是其最大的优点。但与此同时，也有计算负担加重的问题。

核K-Means（Kernel K-means Clustering）

ARGO在之前讲

SVM理解(一)

时，已经提出核方法这一概念。其主要目标是为了引入核函数对数据集进行空间变化，从而使数据集在高维空间中符合凸数据集的结构，从而线性可分。

核方法主要是对数据集进行变换，从而在很多的算法中应用广泛，在K-Means中也有极大的用武之地，正好可以用来解决K-Means的一个极大的局限，只能用于球形簇数据集的问题。

五 总结

K-Means是广大聚类算法中最为人所知的一种，其简单易懂程度与机器学习的另一算法KNN相当。聚类算法是一种无监督学习方法，在数据探索、知识挖掘和数据预处理方面有着广泛的应用，其算法版本之多，更新之快令人目不暇接。ARGO将在以后的文章中，逐步展开对于聚类的介绍，从而将机器学习的整个有监督，无监督学习的整体知识框架搭建完全。

好资料：

深入浅出聚类算法：https://zhuanlan.zhihu.com/p/43651469

六大聚类算法快速了解：https://www.plob.org/article/12370.html

FCM聚类介绍：https://www.cnblogs.com/sddai/p/6259553.html

基于网格的机器学习：https://cloud.tencent.com/developer/article/1005263

好了，聚类的K-Means算法介绍完了。谢谢大家过去半年里对ARGO的持续关心，在新的一年，ARGO将跟读者朋友们一起学习，一起进步，一起开创新天地。

参考文档：

西瓜书，统计机器学习