聚类算法综合综述

A Comprehensive Survey of Clustering Algorithms

聚类算法综合综述

https://aagyapalkaur.github.io/survey.pdf

摘要

数据分析被用作现代科学研究中的一种常见方法，它跨越了通信科学、计算机科学和生物学科学。聚类，作为数据分析的基本组成部分，发挥着重要作用。一方面，随着信息增长和学科交叉，许多用于聚类分析的工具已经被创建出来。另一方面，由于信息的复杂性，每种聚类算法都有其自身的优势和弱点。在这篇综述论文中，我们从聚类的定义开始，将聚类过程中涉及的基本要素，如距离或相似度测量和评价指标，纳入考虑，并从两个视角分析聚类算法，即传统算法和现代算法。所有讨论的聚类算法将在附录表22中进行详细比较和全面展示。

关键词 聚类 · 聚类算法 · 聚类分析 · 综述 · 无监督学习

1 引言

聚类，被认为是无监督学习中最重要的一个问题，处理未知区域中的数据结构划分，并且是进一步学习的基础。然而，聚类的完整定义并没有达成一致，一个经典的定义描述如下[1]：

(1) 在同一聚类中的实例，必须尽可能相似；
(2) 在不同聚类中的实例，必须尽可能不同；
(3) 对于相似性和不相似性的测量必须清晰并且具有实际意义；

聚类的标准过程可以分为以下几个步骤[2]：

(1) 特征提取和选择：从原始数据集中提取并选择最具代表性的特征；
(2) 聚类算法设计：根据问题的特点设计聚类算法；
(3) 结果评估：评估聚类结果并判断算法的有效性；
(4) 结果解释：对聚类结果给出实际的解释；

在本文的剩余部分，常见的相似度和距离测量将在第2节中介绍，聚类结果的评价指标将在第3节中列出，传统聚类算法和现代聚类算法将分别在第4节和第5节中被系统地分析，最终结论将在第6节中得出。

2 距离和相似度

距离（不相似度）和相似度是构建聚类算法的基础。至于定量数据特征，距离更适合用来识别数据之间的关系。而相似度在处理定性数据特征时更受青睐[2]。

定量数据特征常用的距离函数总结在表1中。

定性数据特征常用的相似度函数总结在表2中。

3 评价指标

评价指标的主要目的是检验算法的有效性。根据测试数据是否在构建聚类算法的过程中，评价指标可以分为两类，即内部评价指标和外部评价指标。

内部评价利用内部数据来检验算法的有效性。然而，当两个算法的基于内部评价指标的得分不相等时，它不能绝对地判断哪个算法更好[5]。有三种常用的内部指标，总结在表3中。

外部评价，被称为测试方法的黄金标准，利用外部数据来检验算法的有效性。然而，最近结果表明外部评价并不完全正确[6]。有六种常用的外部评价指标，总结在表4中。

在接下来的章节中，特别是在时间复杂度分析中，n代表总对象/数据点的数量，k代表聚类簇的数量，s代表样本对象/数据点的数量，t代表迭代次数。

4 传统聚类算法

传统聚类算法可以分为9个类别，主要包含26种常用算法，总结在表5中。

4.1 基于划分的聚类算法

这类聚类算法的基本思想是将数据点的中心视为相应聚类簇的中心。K-means [7] 和 K-medoids [8] 是这类聚类算法中最著名的两种。K-means 的核心思想是通过迭代计算来更新由数据点中心表示的聚类簇中心，并且迭代过程将持续进行，直到满足某些收敛标准。K-medoids 是 K-means 的一种改进，用于处理离散数据，它将最接近数据点中心的数据点作为相应聚类簇的代表。典型的基于划分的聚类算法还包括 PAM [9]、CLARA [10]、CLARANS [11]。
关于这类聚类算法的更多信息，您可以参考 [12–14]。
分析：

(1) 时间复杂度（表6）：
(2) 优点：通常具有相对较低的时间复杂度和较高的计算效率；
(3) 缺点：不适用于非凸数据，对异常值相对敏感，容易陷入局部最优，需要预先设定聚类簇的数量，并且聚类结果对聚类簇的数量敏感。；
(4) AP算法 [15]，将在基于亲和传播的聚类算法章节中讨论，也可以被视为这类聚类算法之一。

4.2 基于层次的聚类算法

这类聚类算法的基本思想是构建数据之间的层次关系以便进行聚类 [16]。假设一开始每个数据点代表一个单独的聚类簇，然后，将最相邻的两个聚类簇合并为一个新的聚类簇，直到只剩下一个聚类簇。或者，一个相反的过程。这类聚类的典型算法包括 BIRCH [17]、CURE [18]、ROCK [19]、Chameleon [20]。BIRCH 通过构建聚类的特征树，即 CF 树来实现聚类结果，其中一个节点代表一个子聚类簇。当新的数据点到来时，CF 树将动态生长。CURE，适用于大规模聚类，采用随机采样技术分别对样本进行聚类，并最终整合结果。ROCK 是 CURE 的改进，用于处理枚举类型的数据，它考虑了聚类簇周围数据对相似度的影响。Chameleon，首先基于最近邻图将原始数据划分为较小规模的聚类簇，然后基于凝聚算法将小规模的聚类簇合并为更大规模的聚类簇，直到满足条件。
关于这类聚类算法的更多信息，您可以参考 [21,22]。
分析：
(1) 时间复杂度（表7）：
(2) 优点：适用于具有任意形状和任意类型属性的数据集，容易检测到聚类簇之间的层次关系，并且通常具有相对较高的可扩展性；
(3) 缺点：通常时间复杂度相对较高，需要预先设定聚类簇的数量。

4.3 基于模糊理论的聚类算法

这类聚类算法的基本思想是将隶属标签的离散值 {0, 1} 改变为连续区间 [0, 1]，以便更合理地描述对象之间的隶属关系。这类聚类的典型算法包括 FCM [23–25]、FCS [26] 和 MM [27]。FCM 的核心思想是通过优化目标函数来获得每个数据点对每个聚类簇的隶属度。FCS 不同于传统的模糊聚类算法，它将多维超球体作为每个聚类簇的原型，从而使用基于超球体的距离函数进行聚类。MM，基于山峰函数，用于寻找聚类簇的中心。
关于这类聚类算法的更多信息，您可以参考 [28–30]。

分析：

1. 时间复杂度（表8）：

2. FCS的时间复杂度很高，因为算法中涉及了核；

3. 优点：更真实地给出隶属概率，聚类准确率相对较高；

4. 缺点：通常可扩展性相对较低，容易陷入局部最优，聚类结果对初始参数值敏感，并且需要预先设定聚类簇的数量。

4.4 基于分布的聚类算法

其基本思想是，如果原始数据中存在几种分布，那么由相同分布生成的数据属于同一个聚类簇。典型的算法是 DBCLASD [31] 和 GMM [32]。DBCLASD 的核心思想是，它是一种动态增量算法，即如果一个聚类簇与其最近数据点之间的距离满足期望距离的分布（该分布是由该聚类簇的现有数据点生成的），那么该最近数据点应该属于这个聚类簇。GMM 的核心思想是，GMM 由几个高斯分布组成，原始数据由这些高斯分布生成，服从相同独立高斯分布的数据被认为属于同一个聚类簇。
关于这类聚类算法的更多信息，您可以参考 [33,34]。
分析：
(1) 时间复杂度（表9）：
(2) 优点：更真实地给出隶属概率，通过改变分布、聚类簇数量等具有相对较高的可扩展性，并且得到发展完善的统计科学的支持；
(3) 缺点：前提不完全正确，涉及许多对聚类结果有强烈影响的参数，并且时间复杂度相对较高。

4.5 基于密度的聚类算法

这类聚类算法的基本思想是，位于数据空间高密度区域的数据被认为属于同一个聚类簇 [35]。典型的包括 DBSCAN [36]、OPTICS [37] 和 Mean-shift [38]。DBSCAN 是最著名的基于密度的聚类算法，它直接源自这类聚类算法的基本思想。OPTICS 是 DBSCAN 的一种改进，它克服了 DBSCAN 对两个参数敏感的缺点，即邻域的半径和邻域内点的最小数量。在 Mean-shift 的过程中，首先计算当前数据点的偏移均值，然后基于当前数据点和偏移量找出下一个数据点，最后，迭代将持续进行，直到满足某些标准。
关于这类聚类算法的更多信息，您可以参考 [39–42]。
分析：

(1) 时间复杂度（表10）：
(2) Mean-shift 的时间复杂度很高，因为算法中涉及了核；
(3) 优点：聚类效率高，适用于任意形状的数据；
(4) 缺点：当数据空间的密度不均匀时，会导致聚类结果质量低下，当数据量大时需要大尺寸的内存，并且聚类结果对参数高度敏感；
(5) DENCLUE 算法 [43]，将在面向大规模数据的聚类算法章节中讨论，也可以被视为这类聚类算法之一。

4.6 基于图论的聚类算法

根据这类聚类算法，聚类是在图上实现的，其中节点被视为数据点，边被视为数据点之间的关系。这类聚类的典型算法是 CLICK [44] 和基于 MST 的聚类 [45]。CLICK 的核心思想是通过迭代对图进行最小权重划分，以便生成聚类簇。从数据图生成最小生成树是基于 MST 的聚类算法进行聚类分析的关键步骤。
关于这类聚类算法的更多详细信息，您可以参考 [1,20,46–49]。

分析：

(1) 时间复杂度（表11）：
其中 v 代表顶点的数量，e 代表边的数量，f(v, e) 代表计算最小割的时间复杂度；
(2) 优点：聚类效率高，聚类结果准确率高；
(3) 缺点：时间复杂度随着图复杂度的增加而急剧增加；
(4) SM算法 [50] 和 NJW算法 [51]，将在基于谱图理论的聚类算法章节中讨论，也可以被视为这类聚类算法之一。

4.7 基于网格的聚类算法

这类聚类算法的基本思想是将原始数据空间改变为具有确定大小的网格结构以进行聚类。这类聚类的典型算法是 STING [52] 和 CLIQUE [53]。STING 的核心思想（可用于并行处理）是通过构建层次结构将数据空间划分为许多矩形单元，并且不同结构层级内的数据分别进行聚类。CLIQUE 利用了基于网格的聚类算法和基于密度的聚类算法的优势。
关于这类聚类算法的更多详细信息，您可以参考 [41,54–57]。
分析：
(1) 时间复杂度（表12）：
(2) 优点：时间复杂度低，可扩展性高，适用于并行处理和增量更新；
(3) 缺点：聚类结果对粒度（网格大小）敏感，高计算效率是以降低聚类簇质量和降低聚类准确率为代价的；
(4) Wavecluster 算法 [54]，将在面向空间数据的聚类算法章节中讨论，也可以被视为这类聚类算法之一。

4.8 基于分形理论的聚类算法

分形代表一种几何体，它可以被分成几个部分，这些部分与整体共享一些共同特征 [58]。这类聚类的典型算法是 FC [59]，其核心思想是聚类簇中任何内部数据的变化对分形维数的内在质量没有任何影响。
关于这类聚类算法的更多详细信息，您可以参考 [60–63]。
分析：
(1) FC 的时间复杂度是 O(n)；
(2) 优点：聚类效率高，可扩展性高，有效处理异常值，并且适用于任意形状和高维的数据；
(3) 缺点：前提不完全正确，聚类结果对参数敏感。

4.9 基于模型的聚类算法

其基本思想是为每个聚类簇选择一个特定的模型，并找到该模型的最佳拟合。基于模型的聚类算法主要有两种，一种基于统计学习方法，另一种基于神经网络学习方法。
基于统计学习方法的典型算法是 COBWEB [64] 和 GMM [32]。COBWEB 的核心思想是基于一些启发式标准构建分类树，以便在每个属性的概率分布独立的假设下实现层次聚类。基于神经网络学习方法的典型算法是 SOM [65] 和 ART [66–69]。SOM 的核心思想是在输入数据中存在拓扑结构的假设下，构建从高维输入空间到低维输出空间的降维映射。ART 的核心思想，一种增量算法，是当当前神经元不够时，动态生成一个新神经元来匹配新模式以创建一个新聚类簇。GMM 已在基于分布的聚类算法章节中讨论过。
关于这类聚类算法的更多详细信息，您可以参考 [70–75]。

分析：

(1) 时间复杂度（表13）：
(2) COBWEB 的时间复杂度通常较低，这取决于算法中涉及的分布；
(3) SOM 的时间复杂度通常较高，这取决于算法中涉及的层构建；
(4) ART 的时间复杂度通常中等，这取决于 ART 的类型和算法中涉及的层构建；
(5) 优点：多样且发展完善的模型提供了充分描述数据的手段，并且每个模型都有自己的特殊特征，这可能在某些特定领域带来一些显著优势；
(6) 缺点：通常时间复杂度相对较高，前提不完全正确，并且聚类结果对所选模型的参数敏感。

5 现代聚类算法

现代聚类算法可以分为10个类别，主要包含45种常用算法，总结在表14中。

5.1 基于核的聚类算法

这类聚类算法的基本思想是通过非线性映射将输入空间中的数据变换到高维特征空间以进行聚类分析。这类聚类的典型算法包括核 K-means [76]、核 SOM [77]、核 FCM [78]、SVC [79]、MMC [80] 和 MKC [81]。核 K-means、核 SOM 和核 FCM 的基本思想是利用核方法和原始聚类算法的优势，通过非线性核函数将原始数据变换到高维特征空间，以便执行原始聚类算法。SVC 的核心思想是找到能够覆盖高维特征空间中所有数据点的最小半径球体，然后将该球体映射回原始数据空间以形成等值线，即聚类簇的边界，覆盖数据，并且封闭等值线内的数据应属于同一个聚类簇。MMC 试图找到具有最大间隔的超平面以进行聚类，并且它可以被推广用于多标签聚类问题。MKC，作为 MMC 的改进，试图基于多个核找到最佳超平面以进行聚类。MMC 和 MKC 在一定程度上共享计算的局限性。
关于这类聚类算法的更多详细信息，您可以参考 [82–84]。
分析：
(1) 时间复杂度（表15）：

(2) 这类聚类算法的时间复杂度通常很高，因为算法中涉及了核；
(3) 优点：更容易在高维特征空间中进行聚类，适用于任意形状的数据，能够分析噪声并分离重叠的聚类簇，并且不需要具有关于数据拓扑的先验知识；
(4) 缺点：聚类结果对核的类型及其参数敏感，时间复杂度高，并且不适用于大规模数据。

5.2 基于集成的聚类算法

基于集成的聚类算法也称为集成聚类，其核心思想是通过特定方法生成一组初始聚类结果，并通过整合初始聚类结果得到最终聚类结果。主要有4种方法可以得到这组初始聚类结果，如下：
(1) 对于同一数据集，采用具有不同参数或不同初始条件的相同算法 [85]；
(2) 对于同一数据集，采用不同的算法 [86]；
(3) 对于子集，分别进行聚类 [86]；
(4) 对于同一数据集，基于不同的核在不同特征空间中进行聚类 [87]。

初始聚类结果通过共识函数的方式进行整合。共识函数可以分为以下9个类别，总结在表16中：

关于这类聚类算法的更多详细信息，您可以参考 [95]。
分析：
(1) 这类算法的时间复杂度基于算法中涉及的特定方法和算法；
(2) 优点：鲁棒，可扩展，能够并行，并且利用所涉及算法的优势；
(3) 缺点：对初始聚类结果之间的差异理解不足，共识函数的设计存在缺陷。

5.3 基于群体智能的聚类算法

这类聚类算法的基本思想是模拟生物种群的变化过程。典型算法包括4个主要类别：基于 ACO 的 [96,97]、基于 PSO 的 [97,98]、基于 SFLA 的 [99] 和基于 ABC 的 [100]。LF [101] 的核心思想，作为基于 ACO 的典型算法，是首先将数据随机分布在二维网格上，然后基于蚂蚁的决策选择或不选择数据进行进一步操作，并且这个过程迭代进行，直到获得令人满意的聚类结果。基于 PSO 的算法将数据点视为一个粒子。粒子的初始聚类簇首先由其他聚类算法获得，然后粒子的聚类簇基于聚类簇的中心以及每个粒子的位置和速度持续更新，直到获得令人满意的聚类结果。基于 SFLA 的算法的核心思想是模拟青蛙的信息交互，并利用局部搜索和全局信息交互。基于 ABC 的算法的核心思想是模拟蜂群中三种类型蜜蜂的觅食行为，其职责是确定食物源，并利用局部信息和全局信息的交换进行聚类。
关于这类聚类算法的更多详细信息，您可以参考 [102–104]。
分析：
(1) 时间复杂度（表17）：

(2) 这类算法的时间复杂度很高，主要是因为迭代次数多；
(3) 优点：具有克服容易陷入局部最优并获得全局最优特性的算法，易于理解算法；
(4) 缺点：可扩展性低，运行效率低，不适用于高维或大规模数据。

5.4 基于量子理论的聚类算法

基于量子理论的聚类算法被称为量子聚类，其基本思想是通过研究粒子在能量场中的分布规律来研究样本数据在尺度空间中的分布规律。这类典型算法包括 QC [105,106] 和 DQC [107]。QC（量子聚类）的核心思想，适用于高维数据，是通过使用迭代梯度下降算法，利用薛定谔方程获得每个对象的势能，将具有低势能的对象视为聚类簇的中心，并通过定义的距离函数将对象放入不同的聚类簇中。DQC，作为 QC 的一种改进，采用基于时间的薛定谔方程，以便动态地研究原始数据集的变化和量子势能函数的结构。
关于这类聚类算法的更多详细信息，您可以参考 [108–110]。
分析：
(1) 时间复杂度（表18）：

(2) QC 的时间复杂度很高，因为求解薛定谔方程的过程和大量的迭代；
(3) DQC 的时间复杂度，与 DQ 相比更实用，由于求解薛定谔方程的过程而处于中等水平；
(4) 优点：这类算法涉及的参数数量少，基于样本数据的潜在信息确定聚类簇的中心；
(5) 缺点：聚类结果对算法的参数敏感，算法模型不能完全描述数据的变化规律。

5.5 基于谱图理论的聚类算法

这类聚类算法的基本思想是将对象视为顶点，将对象之间的相似度视为加权边，以便将聚类问题转化为图划分问题。关键在于找到一种图划分方法，使得不同组之间的连接权重尽可能小，而同一组内各边之间的连接总权重尽可能高 [111]。这类聚类的典型算法主要可以分为两类，递归谱和多路谱，这两类的典型算法分别是 SM [50] 和 NJW [51]。SM 的核心思想，通常用于图像分割，是基于特征向量，通过启发式方法最小化归一化割。而 NJW 在由拉普拉斯矩阵的 k 个最大特征值对应的特征向量构成的特征空间中进行聚类分析。
关于这类聚类算法的更多详细信息，您可以参考 [51,84,112–114]。
分析：
(1) 时间复杂度（表19）：

(2) SM 的时间复杂度很高，因为求出特征向量的过程和算法中涉及的启发式方法；
(3) NJW 的时间复杂度很高，因为求出特征向量的过程；
(4) 优点：适用于具有任意形状和高维的数据集，收敛于全局最优，只需要相似度矩阵作为输入，并且对异常值不敏感；
(5) 缺点：聚类结果对缩放参数敏感，时间复杂度相对较高，相似度矩阵的构建不明确，特征向量的选择未优化，并且需要预先设定聚类簇的数量。

5.6 基于亲和传播的聚类算法

AP（亲和传播聚类）是一种重要的算法，于2007年在《Science》上被提出。AP的核心思想是将所有数据点视为潜在的聚类中心，并将两个数据点之间欧几里得距离的负值作为亲和度。因此，一个数据点对其他数据点的亲和度总和越大，该数据点成为聚类中心的可能性就越高。AP算法采取贪婪策略，在每次迭代中最大化聚类网络全局函数的值 [15]。
关于这类聚类算法的更多详细信息，您可以参考 [115–117]。
分析：
(1) AP的时间复杂度是O(n^2*logn)；
(2) 优点：算法思想简单清晰，对异常值不敏感，并且不需要预先设定聚类簇的数量；
(3) 缺点：时间复杂度高，不适用于非常大规模的数据集，并且聚类结果对AP算法中涉及的参数敏感。

5.7 基于密度和距离的聚类算法

DD（基于密度和距离的聚类）是2014年在《Science》上提出的另一种重要聚类算法 [118]，其核心思想新颖。DD的主要特点是对于聚类中心的描述，如下所示：
(1) 具有高局部密度：在特定范围内，聚类中心附近的数据点数量必须足够大；
(2) 远离其他具有高局部密度的数据点：聚类中心必须远离其他可能成为聚类中心的数据点。

DD的核心思想是基于距离函数，首先计算出每个数据点的局部密度以及每个数据点与其他具有更高局部密度的数据点之间的最短距离，以便构建决策图，然后基于决策图选择聚类中心，最后将剩余的数据点放入最近的具有更高局部密度的聚类簇中。
分析：
(1) DD的时间复杂度是O(n^2)；
(2) 优点：算法思想简单清晰，适用于具有任意形状的数据集并且对异常值不敏感；
(3) 缺点：时间复杂度相对较高，基于决策图选择聚类中心的主观性相对较强，并且聚类结果对DD算法中涉及的参数敏感。

5.8 面向空间数据的聚类算法

空间数据指的是同时具有时间和空间两个维度的数据，具有规模大、速度快和信息复杂的特点。这类聚类的典型算法包括 DBSCAN [36]、STING [52]、Wavecluster [54] 和 CLARANS [11]。Wavecluster 的核心思想，可用于并行处理，是通过对原始数据应用小波变换，在新的特征空间中进行聚类。而 CLARANS 的核心思想是基于 CLARA [10] 进行采样，并通过 PAM [9] 进行聚类。DBSCAN 已在基于密度的聚类算法章节中讨论过，STING 已在基于网格的聚类算法章节中讨论过。
关于这类聚类算法的更多详细信息，您可以参考 [119–122]，ST-DBSCAN [123]。
时间复杂度（表20）：

5.9 面向数据流的聚类算法

数据流具有基于序列到达、规模大和读取频率有限的特点。这类聚类的典型算法包括 STREAM [124]、CluStream [125]、HPStream [126]、DenStream [127]，后三者是增量算法。STREAM，基于分治的思想，按照数据到达的顺序依次处理数据，以便构建层次聚类结构。CluStream，主要处理 STREAM 仅静态描述原始数据的缺点，将数据视为动态变化的过程。因此 CluStream 不仅能对请求给出及时响应，还能通过在线和离线计算出微聚类簇，从而给出不同时间粒度的聚类结果。HPStream，作为 CluStream 的改进，考虑了数据影响力随时间的衰减，并且更适用于高维数据的聚类。DenStream，采用了基于密度的聚类算法的核心思想，适用于非凸数据集，并且与本节中上述算法相比，能够高效地处理异常值。
关于这类聚类算法的更多详细信息，您可以参考 [128–131]，D-Stream [41,132]。
时间复杂度（表21）：

CluStream、HPStream 和 DenStream 的时间复杂度涉及在线和离线过程。

5.10 面向大规模数据的聚类算法

大数据具有4个V的特征，即体量大、多样性丰富、速度快和真实性存疑 [133]。大数据聚类的主要基本思想可以概括为以下4个类别：
(1) 采样聚类 [10,18]；
(2) 数据合并聚类 [17,134]；
(3) 降维聚类 [135,136]；
(4) 并行聚类 [114,137–139]；

这类聚类的典型算法是 K-means [7]、BIRCH [17]、CLARA [10]、CURE [18]、DBSCAN [36]、DENCLUE [43]、Wavecluster [54] 和 FC [59]。
关于这类聚类算法的更多详细信息，您可以参考 [2,13,140,141]。
DENCLUE 的时间复杂度是 O(nlogn)，K-means、BIRCH、CLARA、CURE、DBSCAN、Wavecluster 和 FC 的复杂度已在其他章节中描述过。

6 结论

本文从聚类的定义和典型流程开始，列出了奠定聚类基础的常用距离（不相似度）函数、相似度函数和评价指标，并从两个视角分析了聚类算法，即包含9个类别26种算法的传统算法，以及包含10个类别45种算法的现代算法。所有讨论的聚类算法的详细而全面的比较总结在附录表22中。

本文的主要目的是介绍每种常用聚类算法的基本和核心思想，指明每一种算法的来源，并分析每一种算法的优缺点。由于信息的多样性、研究领域的交叉以及现代计算机技术的发展，很难呈现所有聚类算法的完整列表。因此，选择了19个类别具有高实用价值且研究充分的常用聚类算法，并详细讨论了每个类别中一个或多个典型算法，以便给读者提供一个关于重要数据分析方法——聚类的系统而清晰的视图。

原文链接：https://aagyapalkaur.github.io/survey.pdf