聚类分析算法概述及其适用性比较

印晓天 湛高峰

摘 要：聚类算法作为大数据与人工智能领域重要的分析工具，受到了学术界的高度关注与广泛研究。本文从算法设计思想的角度对现今主要的聚类算法进行了归纳总结。具体来讲，针对中心聚类法、层次聚类法、密度聚类法、谱聚类法以及一些其他聚类算法分析了各自算法及其思想的优缺点与适用性，对算法的实际应用建立指导性作用。

关键词：聚类分析 算法 适用性

中图分类号：TP311 文献标识码：A 文章编号：1672-3791（2018）11（c）-0230-03

聚类分析作为机器学习的重要分析手段，是当前大数据时代下的热点研究领域之一。在过去数十年间，产生了大量的聚类分析算法。本文对目前主流的聚类算法进行归纳总结，并对各自的优缺点和适用性进行比较分析。

通俗来讲，聚类算法的目标是将具有共性的样本归为同一类型，而将没有或者少有共性的样本归为不同类型。数学上对于共性的度量常用样本之间的距离来衡量，而如何定义距离则需要根据实际情况具体分析。因此，聚类算法的目标是得到一系列内部联系相对紧密、外部联系相对稀疏的样本集合（又称为类簇）。聚类算法按实现方式，主要可以分为中心聚类、层次聚类、密度聚类、谱聚类等。下面就以上各类型聚类算法逐一介绍。由于本文着重分类介绍算法的思想，旨在分析各类算法的优缺点及其适用性，所以在介绍的时候不会拘泥于参数细节，而强调执行过程是如何体现算法思想的。具体的算法实现过程可参考相应文献。

1 中心聚类法

中心聚类法是一类极为常见聚类算法。它以找各类簇的中心为基本任务，将离某中心最近那些点归为该中心所代表的类簇。中心聚类的代表性算法是K-means[1-2]。K-means算法的执行是一个迭代的过程，以正整数K作为超参数，在每轮次更新K个类簇的中心。具体来说，给定空间中样本点集合作为输入，初始时算法以某种方式选定K个空间中的点作为K个类簇的初始中心点，这种选取方式可以是随机的，也可以是根据输入样本的特征先验选取。在每轮迭代的过程中，对每一个输入样本，计算他们到各个中心的距离，将其归入距离最近的中心所代表的类簇中，这将得到一个样本的类别划分。然后对每一个聚类计算其新的中心，计算方式通常是取类簇中各自样本集合的平均值，作为下一次迭代的中心。迭代直到每个类簇的中心相较于上一轮迭代的中心都仅产生足够小的位移为止。

K-means算法的优点是计算简单，迭代收敛速度快，尤其适合欧式空间中按向量和欧式距离定义的样本聚类。但是其缺点也很明显，最大的缺点是需要事先选定一个超参数K。一般在样本数目很大的应用中，对于类别数目没有先验知识时，这个参数不好估计，通常需要对各种给定的值进行试探。其次，K-means算法找到的类簇中心由于类簇中样本分布不定的原因，可能落在样本分布稀疏的地方，导致与直观上的聚类中心不符。为了克服这个问题，

人们提出在每次更新各类簇中心点的时候限制其在样本点上选取，这就是K-medoids算法[3]。此外，还有高斯混合模型聚类，可以视为K-means算法的扩展，它假设类簇的各维度服从高斯分布，从而保证类簇中心的稠密性与类簇的凸性。另一个问题是K-means算法得到的类簇之间是刚性划分，没有重叠或软性隶属关系，这在某些应用场景中是与事实不合的（之后我们会看到，这也是大部分聚类算法的通病）。为此，人们提出模糊（Fuzzy）c-means聚类算法[4-5]，即设定在各类簇边缘的样本点可以依一定概率属于多个类簇，概率值大小反映样本对于该类别的隶属程度。

2 层次聚类法

层次聚类法是另一类极为常见聚类算法。它的思想是通过逐层次的划分方式将样本点分成若干类簇的集合。层次聚类法一般把样本及其之间的距离建模成带权图，其中包含顶点、边以及边的权重等参数。通常启发式地有两种层次划分方式，即自顶向下的分裂法和自底向上的凝聚法。分裂法从初始将所有样本视为同一类开始，通过某种规则将当前的每一个类簇拆分成两个，直到每个类簇达到终止条件为止。而凝聚法则相反，它从初始将每一个样本都视为不同类别，也是通过某种规则将当前的类簇两两合并成，直到每个类簇达到终止条件为止。

层次聚类法的拆分或者合并规则通常是基于某种特定的指标。分裂法中类型拆分的依据常用的是平衡割（Balanced Cut）。平衡割指的是移除之后能将图分割成大小或体积相差不多的兩个子图的边的集合，分裂法中找的是权重之和最小的平衡割。之所以要求两个子图大小或体积相对平衡，是为了防止计算过程中出现仅仅为了达到数学上的极小值，而在图中的一个小局部进行切分的情况，而这样零散的小局部聚类通常不能很好地反映样本的共性，且过于细小的切分通常也不是我们需要的聚类方式。当然，解决这一问题还有其他的指标，如稀疏割（Sparsest Cut）等。

凝聚法中通常有一个目标函数，算法在每轮次凝聚的过程中贪心地选取使得目标函数值优化最多的两个类型的样本集合进行合并，直到目标函数无法继续优化或者达到其他终止条件为止。这个目标函数是定义在全样本及其聚类划分上的，它的大小从某种直观上反映了该样本划分定义的聚类的质量。目前使用最为广泛、最有代表性的目标函数是模块性（Modularity），它反映的是在该划分下的聚类程度与保持顶点度数不变的随机连边的聚类程度之间的差距。这一正向差距越大，表明该划分的聚类效果越好。近年来有学者提出了图的结构熵（Structural Entropy）的概念，从图中随机游走编码极小化的角度定义了图的K-维结构熵，并设计了基于二维结构熵极小化的凝聚聚类算法。

分裂法聚类的优点在于其算法过程完全是基于人们对聚类方式的直观理解，思路清晰明确，因此效果一般较好，并且算法的递归过程天然地给出了样本的层次聚类划分，将样本类型之间的距离以及样本类型的更高层次聚类关系都展示了出来。但是缺点是计算过程缓慢，因为每轮迭代均要在当前子问题中求全局的划分方式，且不论找最小平衡割的计算困难性，单是子问题的递归次数就已经与样本规模成正比。而找最小平衡割的问题本身是困难的，有效时间内只能找到近似解。另一个问题是，分裂法的算法终止条件需要人为设定，即到底划分到多细就（才）能满足需要。这样的条件需要对样本有一定的先验，或者取不同的参数进行多次尝试。

凝聚法聚类的优点在于执行速度快，贪心凝聚的迭代过程中，目标函数的增量无论模块性还是二维结构熵均能局部计算，因此以堆作为辅助的数据结构，这两种算法均能在几乎线性时间内完成。与分裂法相比，凝聚法的另一个优势是它的目标函数清晰，所以终止条件明确且具有可解释性。它的缺点是由于样本的局部微观结构导致初始时样本的聚类方式比较任意，并且之后的算法执行过程中聚在同一类簇中的样本无法再分开，从而就有可能造成最终的结果虽然使得目标函数值较优，但是与真实的聚类方式差距较大。当然，为了克服这一缺点，可以增加一些在贪心迭代过程中的样本迁移策略来纠正初始时的错误。

3 密度聚类法

密度聚类法将内部连续稠密的样本子集视为同一类型，代表性算法是DBSCAN（Density-Based Spatial Clustering of Applications with Noise）。DBSCAN算法首先将所有样本点区分为核心点和非核心点，其中核心点指半径r以内样本点数目大于k的那些点，这里r，k均为参数。如果两个核心点的距离不超过r，则称之为直接密度可达。经过多次直接密度可达的核心点称为密度可达。一个极大的密度可达的核心点子集并上其中各核心点半径r以内的非核心点，即构成一个类簇。可以看到，DBSCAN算法得到的各类簇之间的核心点集不交，但非核心点集可能相交，并且还可能存在某些非核心点其r半径内不包含任何核心点，这被视为噪声。因此，DBSCAN算法允许类簇有重叠，也允许某些点不从属于任何类簇，是其他大多数聚类算法所不具备的优势。而DBSCAN算法的缺点是它用一个统一的尺度r和k来衡量所有类簇，很多时候这样是不合适的。因此，人们提出了改进版本OPTICS（Ordering Points To Identify the Clustering Structure）算法，将半径r设为灵活的参数，由算法自身来调节，但思想上与DBSCAN是统一的。

另一个基于密度的聚类算法是团渗透（Clique Percolation）算法。团是图论中的经典概念，一个大小为k的团就是指k个点的完全图。团渗透算法主要针对的是无向图中的聚类问题。它以一个正整数k作为参数，首先找到图中所有的极大团（即不存在更大的团以该团作为子集），然后当两个极大团的交集大小为至少k-1时将两个极大团合并，视为同一类簇。算法执行过程中是从一个极大团出发找与其交集大于等于k-1的“邻居”团，如同液体的渗透蔓延，故而得名。以团作为类簇组成的基本元素在某些应用中是十分合理的，比如社交网络，但k的取值不宜过大，通常取3或4即可，否则对类簇稠密度要求太高，不易找到合理的类簇。不难发现，团渗透算法也能找到重叠类簇。但是其缺点是对于类簇内部密度要求较高，且只能适用于图的聚类，应用场景有很大的局限性。

4 谱聚类法

谱聚类（Spectral Clustering）是一种针对图聚类的基于谱图理论的聚类算法。它将图中的每个顶点先用代数方法向量化，然后调用其他经典的聚类算法对向量样本聚类。虽然算法执行步骤是代数的，但其直观基于最小化各类簇的扩张性（expansion）。一个点集扩张性是指该点集向外联系的边的数目比上自身的大小，因此这是一个既考虑向外联系的紧密程度又同时考虑类簇自身大小的数学量。算法执行过程首先计算图的拉普拉斯矩阵的最小的k个特征值，这个k的设定需要根据特征值的分布，使得拉普拉斯矩阵的主要特征向量被指使出来。之后将这k个特征值对应的长度为n（n为顶点数目）的特征向量按各顶点分量构成k维向量并归一化，再用其他聚类算法对这n个向量样本进行聚类。谱聚类算法的优点是它可以处理联系非常稀疏的样本，并且它给出了一个对高维数据进行降维的方法。但缺点是由于涉及矩阵运算求特征值和特征向量，计算复杂度较高，且需要一个处理向量聚类的算法做辅助。

5 其他聚类方法

还有其他一些聚类方法没有被归入以上4种，如标签传播聚类法、神经网络聚类法等。标签传播（Label Propagation）算法运用了随机游走的思想，用当前顶点的标签去预测下一步其邻居的标签。算法初始时可以有一些标注好的顶点，其标签代表其所属的真实类型，而其他顶点可随机赋予标签。算法迭代执行的每一步都视为每个顶点以随机游走的方式将标签传给其邻居，因此需计算每个顶点获得其邻居标签的概率，但实现的时候只需计算矩阵与向量的乘法即可。然后除已标注顶点外，其他顶点获得概率最大的那个标签，多个概率最大标签之间任意选取即可。算法执行至所有顶点标签不再发生改变为止。可以看出，距离越近的两个顶点之间越容易获得共同的标签。标签传播算法的优点是简洁直观，计算速度快，虽然在某些极端情况下算法不收敛，但实际问题中很难遇到这种情况。由于算法允许一些标注样本的存在，所以标签传播也是一种简单高效的半监督算法。其缺点也很明显，由于初始对于非标注顶点的标签是随机赋予的，这使得算法结果差异很大，影响准确性。另外还有一类基于特定神经网络模型的聚类算法，自组织映射（Self Organizing Maps）神经网络算法。由于神经网络的原理解释仍是目前学术界的一大难题，所以这里所用的思想還并不明确，需要进一步探究，我们在此也不详述。

6 结语

本文总结了目前常用的聚类算法，并按算法思想分类，阐述了基于其思想的算法实现过程，分析了优缺点与适用性。总体来说，没有任何一个算法可以适用于所有的需求，需要根据实际应用场景选择最适合的聚类算法。

参考文献

[1] S. P. Lloyd. Least square quantization in PCM[A].Bell Telephone Laboratories Paper，Published much later in IEEE Transactions on Information Theory[C].1982：129-137.

[2] E. W. Forgy. Cluster analysis of multivariate data： efficiency versus interpretability of classifications[J]. Biometrics，1965（2）：768-769.

[3] L. Kaufman and P.J. Rousseeuw. Clustering by means of medoids[A].In Statistical Data Analysis Based on the L1-Norm and Related Methods[C].North-Holland，1987：405-416.

[4] J. C. Dunn. A Fuzzy Relative of the ISODATA Process and Its Use in Detecting Compact Well-Separated Clusters[J].Journal of Cybernetics，1973（3）：32-57.

[5] J. C. Bezdek. Pattern Recognition with Fuzzy Objective Function Algorithms[Z]. ISBN 0-306-40671-3，1981.