机器学习的基石：聚类任务的现状与挑战☆

薛菁菁; 陈慧敏; 孔令怡; 樊欣怡; 聂飞平

doi:10.15978/j.cnki.1673-5668.202401002

科学观察 ›› 2024, Vol. 19 ›› Issue (1) :4-17 DOI: 10.15978/j.cnki.1673-5668.202401002

研究论文

机器学习的基石：聚类任务的现状与挑战^☆

薛菁菁 ¹ ,
陈慧敏 ²^,¹ ,
孔令怡 ¹ ,
樊欣怡 ¹ ,
聂飞平 ¹^,^*

作者信息 +

The Foundation of Machine Learning: Current Status and Challenges in Clustering Tasks

Xue Jingjing ¹ ,
Chen Huimin ²^,¹ ,
Kong Lingyi ¹ ,
Fan Xinyi ¹ ,
Nie Feiping ¹^,^*

Author information +

文章历史 +

摘要

[目的/意义] 随着信息技术的快速发展，各个领域积累的数据呈现出规模大、种类多、结构复杂等特点，这些都为已有的无监督聚类算法提出了严峻挑战。[方法/过程] 该文对近年来提出的各种聚类算法进行了综述。[结果/结论] 根据聚类算法可处理的数据类型不同，聚类算法可分为基于向量表示的聚类算法和基于关系表示的聚类算法；从建模策略的角度，聚类算法可分为基于模型优化的算法以及基于启发式的算法。其中，基于模型优化的算法重点分析了k-means算法以及图割算法的研究现状，并给出了两种算法之间的差别和联系，进而解释了为什么k-means模型只能处理球形数据，而图割模型可以处理非凸数据。基于启发式的算法以密度聚类算法为例展开分析。此外，鉴于无监督聚类算法面临的非凸优化难题，该文还分析讨论了无监督聚类算法的各种优化方法。最后，归纳总结了现有算法与优化方法的主要特点，并指出了现阶段聚类方法存在的问题以及未来的研究方向。

Abstract

[Objective/Significance] With the rapid development of information technology, data accumulated in various fields exhibit characteristics such as large scale, diverse types, and complex structures, posing serious challenges to existing unsupervised clustering algorithms. [Method/Process] This article presents a comprehensive survey of various clustering algorithms proposed in recent years. [Results/Conclusions] Based on the different types of data that clustering algorithms can handle, clustering algorithms are categorized into those relying on vector representation and those on relational representation. From a modeling strategy standpoint, clustering algorithms are further stratified into model optimization-based and heuristic-based approaches. Specifically, model optimization-based algorithms delve into the current research status of the k-means algorithm and the graph-cut algorithm, elucidating their distinctions, connections, and the rationale behind the k-means model’s limitation to handling spherical data, while the graph-cut model can accommodate non-convex data. Heuristic-based algorithms are exemplified by density clustering algorithms, which are thoroughly analyzed in this context. In addition, considering the non-convex optimization challenges faced by unsupervised clustering algorithms, this article also analyzes and discusses various optimization methods for unsupervised clustering algorithms. Finally, it summarizes the main characteristics of existing algorithms and optimization methods, and points out the problems existing in the current clustering methods and future research directions.

Graphical abstract

关键词

数据挖掘 / 无监督学习 / 机器学习 / 聚类分析 / 非凸优化

Key words

data mining / unsupervised learning / machine learning / cluster analysis / non-convex optimization

引用本文

引用格式 ▾

薛菁菁, 陈慧敏, 孔令怡, 樊欣怡, 聂飞平. 机器学习的基石：聚类任务的现状与挑战^☆[J]. 科学观察, 2024, 19(1): 4-17 DOI:10.15978/j.cnki.1673-5668.202401002

Xue Jingjing, Chen Huimin, Kong Lingyi, Fan Xinyi, Nie Feiping. The Foundation of Machine Learning: Current Status and Challenges in Clustering Tasks[J]. Science Focus, 2024, 19(1): 4-17 DOI:10.15978/j.cnki.1673-5668.202401002

登录浏览全文

4963

注册一个新账户忘记密码

1 研究背景

聚类分析^[1,2]作为机器学习和数据挖掘领域的关键研究方向，其目标是将数据集中相似的数据点划为一组，从而揭示数据内在的结构和模式，这些算法在数据分析^[3,4]、图像处理^[5,6]、生物信息学^[7]等多个领域中都具有广泛的应用。随着数据规模的不断增大和应用场景的多样化，聚类算法的研究逐渐演变为一个跨学科的领域，涵盖了计算机科学、数学、统计学等多个领域。

聚类分析的研究背景可以追溯到几十年前。早期，研究者主要着眼于数学统计方法，关注于发展基础的聚类技术，以揭示数据集中的内在结构和模式，例如基于划分的 k-means 算法^[8]。这些算法通过定义距离或相似度度量，将数据点划分为不同的簇。然而，这些方法在处理大规模数据、非凸形状的簇或噪声点时面临一定的挑战。随着对复杂结构数据需求的增加，对数据中复杂关系的理解日益迫切^[9]，因此，研究者们对于层次聚类^[10]、图割算法^[11]、谱聚类^[6]等基于图论的方法表现出了浓厚的兴趣。这些方法的引入是为了更好地处理非线性和不规则分布数据，层次聚类方法通过构建层次结构来描述数据中不同级别的组织关系，图论模型通过挖掘图结构来准确反映数据点之间的关系。这种基于图论的方法不仅使得算法能够更灵活地适应数据的复杂分布，而且能够在聚类过程中更准确地捕捉到数据中的潜在模式和结构。

相比之下，密度聚类^[12]算法可以处理带有噪声和异常值的数据。通过将簇定义为数据点密度较高的区域，密度聚类方法成功地解决了数据集中存在不同密度区域的挑战，从而更准确地捕捉了数据的内在结构。这种算法的独特之处在于它们能够适应不同区域内的密度变化，允许簇在数据集中以自适应的方式形成。此外，密度聚类算法对于噪声数据的处理表现出鲁棒性，能够将这些异常值有效地识别并排除在最终的聚类结果之外，使得聚类过程更加稳健和可靠。近年来，随着深度学习的兴起，研究者们开始探索将神经网络与聚类相结合的方法^[13]，例如深度聚类^[14]和自编码器^[15]。这些方法通过学习数据的低维表征来实现更复杂、更准确的聚类。

总体而言，聚类算法的研究经历了从传统数学统计方法到基于图论、密度和深度学习的多个阶段的演进。尽管关于聚类算法的相关研究已经开展了不少，但由于不同研究所关注的角度不同，研究结果比较分散，缺乏系统性梳理和凝练性总结。鉴于此，本文试图从聚类模型和聚类优化两方面出发，凝练聚类研究的主要成果和进展，进一步剖析当前研究的不足，深入洞察聚类研究存在的深层次问题，并提出未来研究方向。

2 聚类算法研究进展

聚类分析作为机器学习、计算机视觉、数据挖掘等人工智能领域的研究热点，一直以来受到了广泛关注。近年来，有关聚类学习的研究取得了长足发展，本文将其大致分为：聚类算法和优化方法。前者聚焦于构建有效的聚类模型(或一系列启发式规则、策略)使之更适应数据聚类分析任务，后者则致力于发展有效的模型优化方法使得聚类模型能够充分发挥其优点。本文对现有聚类方法从两个角度进行划分，从数据类型角度，可分为基于向量表示的和基于关系表示的聚类模型；从建模策略角度，可分为基于模型优化的聚类方法和基于启发式的聚类方法。另外,本文梳理总结了聚类模型用到的优化方法，主要分为数值型优化方法和启发式智能优化方法。图1展示了本文研究框架图。

2.1 从数据类型角度对聚类方法分类

本节从数据类型角度，将聚类模型分为基于向量表示的模型和基于关系表示的模型。

2.1.1 基于向量表示的聚类方法

此类方法将数据点表示为特征向量并对这些向量进行划分，如 k-means 算法^[16]、模糊 c-means 算法^[17]、层次聚类算法^[18]等。图2(a)展示了一个基于向量表示的二维数据集，其中每个数据点被表示为具有两个维度 (x，y) 的特征向量，每个维度对应于数据的一个特征或属性。基于向量表示的聚类方法以此类数据为输入，使用各种距离度量来衡量样本之间的相似性，继而得到聚类结果。以基于原型的 k-means 算法为例,该算法通过找到一组原型（聚类中心）来代表此数据集，并试图通过最小化数据点与聚类中心之间的距离来找到最优的聚类中心，继而得到每个样本的聚类结果。

2.1.2 基于关系表示的聚类方法

此类方法通过构建图结构来准确反映数据点之间的关系，如密度聚类^[19]、图割聚类^[20]等。图2(b)展示了基于关系表示的数据点，该类数据点被视为图的节点，而它们之间的关系则被表示为图的边。这些关系可以是相似性、距离、连接性等度量。基于关系表示的聚类方法以此类数据为输入，使用图论或优化方法，将图分割成不相交的子图，以实现数据的聚类目标。基于关系表示的聚类方法通过图示化展示数据点之间的关系，相对于基于向量表示的聚类方法能够处理非球形数据，后文会给出具体讨论。

2.2 从建模策略角度对聚类方法分类

本节根据聚类方法使用的建模策略的不同，将聚类算法分为基于模型优化的聚类方法和基于启发式的聚类方法。前者通过最大化或最小化定义的概率模型或优化目标函数来实现对数据的有效划分，后者是一类利用启发式策略或规则来优化聚类结果的算法。

2.2.1 基于模型优化的聚类方法

这类方法通过定义目标函数，然后提出优化方法来实现对数据的有效划分，比较经典的方法有 k-means 聚类算法、模糊 c-means 算法、图割算法、高斯混合算法^[21] 等，本节重点介绍 k-means 和图割聚类算法, 并梳理了两者的关系。

(1) k-means 模型

k-means (KM) 作为一种基于向量表示的聚类方法^[16]，根据预定的类别c，通过找到不相交的c个子集来最小化每个点与其所属簇的均值的误差平方和最小，其模型为：

①$ \min _{\mathcal{C}} \sum_{j=1}^{c} \sum_{\mathbf{x}_{i} \in \mathcal{C}_{j}}\left\|\mathbf{x}_{i}-\mathbf{m}_{j}\right\|_{2}^{2}$

其中，$ \mathbf{M} \in \mathbb{R}^{d \times c}$是聚类中心，X_i是$ \mathbf{X} \in \mathbb{R}^{d \times n}$的第 i 列，C_j 是 C的第j个集合，m_j是矩阵 M 的第j列，代表集合 C_j (j = 1, 2，…，c) 的均值。引入指示矩阵 Y 来重新定义k-means 模型：

②$ \begin{array}{l}\min _{\mathrm{Y} \in I n d, \mathrm{M}} \sum_{j=1}^{c} \sum_{i=1}^{n}\left\|\mathbf{x}_{i}-\mathbf{m}_{j}\right\|_{2}^{2} y_{i j} \\\Leftrightarrow \min _{\mathbf{Y} \in I n d, \mathbf{M}}\left\|\mathbf{X}-\mathbf{M Y}^{\mathrm{T}}\right\|_{F}^{2}, \\\end{array}$

其中，$ y_{i j} \in\{0,1\}$是$ \mathbf{Y} \in \mathbb{R}^{n \times c}$的第 (i，j) 个元素。KM 算法利用 Lloyd 算法^[22]来迭代更新指示矩阵 Y 和中心矩阵 M 。

由于 KM 的简单性、高效性及稳定性，KM算法是使用最广泛的聚类算法之一^[23]。然而，它有几个主要缺点：1) 它的性能在很大程度上取决于初始点；2) 在每次迭代中，它必须计算所有数据点与更新的簇均值之间的距离，由此花费更多时间；3) 该优化问题是一个 NP-hard 问题，很容易陷入较差的局部解。因此，许多研究者对这些问题开展了一系列研究：

1)初始化：k-means 算法通常使用随机选择的初始点，这可能导致算法对初始点敏感，产生不稳定的聚类结果^[33]。Fränti 等人^[34]的研究指出，较差的初始化会导致聚类结果陷入较差的局部值，因此，许多研究者集中于改进初始质心的选择^[35,36]。例如，Kant 等人^[37]使用 Atkinson 指数来准确高效地选择初始种子。Arthur等人^[24]提出了k-means++ 算法，其核心思想是确保初始聚类中心之间的距离尽可能远。该算法通过随机选择第一个中心点，然后以概率方式选择后续中心点，以最大化最小距离，从而提高聚类的均匀性。基于此，Bahmani 等人^[38]提出了k-means++ 算法的并行版本。Bachem 等人^[25]利用马尔可夫链蒙特卡洛方法近似k-means++算法，提出了马尔可夫链蒙特卡洛 (K-MC2) 方法。这一方法的优势在于通过引入随机性，能够有效地缓解k-means 算法陷入局部最优解的问题。Cohen-Addad 等人^[26]通过改进 K-MC2，提出了 AFKMC2 算法，与传统的 K-MC2 相比，AFKMC2 在处理大规模数据集时具有更高的效率。此外，AFKMC2 算法还能更好地适应不同分布的数据，提高了聚类的准确性和稳定性。

2)速度：因为k-means 算法在每次迭代时都需要计算所有数据点与更新的中心的距离，导致耗时太久。因此，许多研究者提出改进方案，主要分为：((1))加速近邻搜索^[39]和 kd 树结构法：kd 树方法^[40,41]利用节点来表示大量的数据点，从而减少算法中最近邻查询的数量；((2)) 对输入数据进行取样、降维以及稀疏处理：Newling 等人^[42]在使用距离边界的基础上利用小批量算法加快算法的运行；Cohen 等人^[43]基于一定的误差范围，通过对数据点进行降维处理来近似输入数据；Sinha 等人^[44]通过应用随机矩阵稀疏化来获得稀疏数据矩阵，从而加快算法中矩阵向量的乘法步骤；((3)) 基于距离界限的方法。Elkan 等人^[27]利用三角不等式摒弃了不必要的距离计算；Hamerly 等人^[45]利用三角不等式既可以避免不必要的距离计算，还可以消除 Lloyd 算法中的最内层循环；Yinyang k-means^[29]和 Exp-ns 算法^[30]也是基于界限的方法。另外，Newling 等人^[46]通过加速以图搜索为结构的 CLARANS 算法^[47]来加速算法过程；Xia 等人^[28]引入球簇以及邻近簇搜索的概念，使得算法不依赖于任何界限就可以减少距离计算的数量。

3) 优化：k-means 由于使用 Lloy 优化方法，对初始化过于敏感，可能陷入较差的局部解。因此，为了获得更鲁棒更优的解，Nie 等人利用CD 和 IRW 方法^[31,32]，把更新多变量问题转换成更新少变量问题。表1展示了部分算法。

(2) 图割模型

对于构建的无向图$ \mathcal{G}(\mathcal{V}, E, \mathbf{W})$,$\mathcal{V}$是一组节点，每个节点代表一个数据点，E是一组连接相邻节点的边，$\mathbf{W} \in \mathbb{R}^{n \times n}$是衡量边强度的无向加权邻接矩阵。对这 n 个数据点进行聚类相当于将$\mathcal{V}$划分为c个不相交的子集 $\mathcal{V}_{1}, \mathcal{V}_{2}, \cdots, \mathcal{V}_{c}$。图割模型的统一框架如下：

③$\min \sum_{l=1}^{c} \frac{\operatorname{cut}\left(\mathcal{V}_{l}, \overline{\mathcal{V}}_{l}\right)}{\sigma\left(\mathcal{V}_{l}\right)}=\min \sum_{l=1}^{c} \frac{\mathbf{y}_{l}^{\mathrm{T}} \mathbf{L y}_{l}}{\sigma\left(\mathcal{V}_{l}\right)},$

其中，$\overline{\mathcal{V}}_{l}$是$\mathcal{G}$中子集$\mathcal{V}_{l}$的补集，$\sigma\left(\mathcal{V}_{l}\right)$为正则项。$\mathbf{L}=\mathbf{D}-\mathbf{W}$是拉普拉斯矩阵，对角阵 D 为度矩阵，其第 i 个对角元为 $d_{i}=\sum_{g} w_{i g}$。

最小割模型最初由 Wu 等人^[11]提出，即当上述模型的正则项 $\sigma\left(\mathcal{V}_{l}\right)=1$ 时所展示的模型。然而，他们发现最小割模型的思想可能导致形成极小簇，即将数据集中的小型孤立节点归为一类。为了克服这一问题，Hagen 等人^[62]引入了类规模平衡项 $\sigma\left(\mathcal{V}_{l}\right)=\left|\mathcal{V}_{l}\right|=\mathbf{y}_{l}^{\mathrm{T}} \mathbf{y}_{l}$，限制每个子图中的样本个数，并提出了比值切割模型 (Ratio Cut，RCut)。该模型旨在最小化子图间的相似性同时最大化子图内点的个数，从而避免最小割模型产生的极小簇。与此同时，Shi等人^[63]通过最大化子图内点的度之和并引入正则项 $\operatorname{vol}\left(\mathcal{V}_{l}\right)=\sum_{\mathbf{v}_{i} \in \mathcal{V}_{l}} \sum_{g} w_{i g}=\mathbf{y}_{l}^{\mathrm{T}} \mathbf{D} \mathbf{y}_{l}$来限制每个子图内点的度，并提出了归一化切割模型(Normalized Cut，NCut)。该模型旨在最小化子图间的相似性同时最大化子图内点的度之和，从而避免最小割模型产生极小簇。上述 RCut 和NCut 模型分别为：

④$\left\{\begin{array}{l}\min _{\mathbf{Y} \in I n d} \operatorname{Tr}\left(\left(\mathbf{Y}^{\mathrm{T}} \mathbf{Y}\right)^{-1} \mathbf{Y}^{\mathrm{T}} \mathbf{L} \mathbf{Y}\right) \\\min _{\mathbf{Y} \in I n d} \operatorname{Tr}\left(\left(\mathbf{Y}^{\mathrm{T}} \mathbf{D} \mathbf{Y}\right)^{-1} \mathbf{Y}^{\mathrm{T}} \mathbf{L} \mathbf{Y}\right)\end{array}\right.$

进一步, 问题④可以写为:

⑤$\left\{\begin{array}{l}\min _{\mathbf{F}=\mathrm{Y}\left(\mathbf{Y}^{\mathrm{T}} \mathbf{Y}\right)^{-\frac{1}{2}}, \mathrm{Y} \in I n d, \mathbf{F}^{\mathrm{T}} \mathbf{F}=\mathrm{I}} \operatorname{Tr}\left(\mathbf{F}^{\mathrm{T}} \mathbf{L F}\right), \\\min _{\mathbf{F}=\mathrm{Y}\left(\mathbf{Y}^{\mathrm{T}} \mathbf{D Y}\right)^{-\frac{1}{2}}, \mathrm{Y} \in I n d, \mathbf{F}^{\mathrm{T}} \mathbf{D F}=\mathrm{I}} \operatorname{Tr}\left(\mathbf{F}^{\mathrm{T}} \mathbf{L F}\right).\end{array}\right.$

图割模型涉及的数学优化问题是 NP-hard的。考虑到矩阵 F 的约束条件，为了求解该模型，通常会将加权离散矩阵 F 松弛为连续矩阵,即保留其正交约束，但放弃其离散约束。因此，松弛后的图割模型具有统一的表示形式：

⑥$\min _{\mathbf{H}^{\mathrm{T}} \mathbf{H}=\mathrm{I}} \operatorname{Tr}\left(\mathbf{H}^{\mathrm{T}} \mathbf{A} \mathbf{H}\right),$

问题⑥通过两步法求解：对A进行特征值分解 (Eigenvalue Decomposition，EVD) 得到 H，然后对 H进行 k-means 或谱旋转得到离散结果。图割模型可以处理任意分布的数据类型，因此受到了广泛关注。然而，其自身缺点限制了其发展和应用，主要有：1) 时间复杂度高；2) 需要放缩-离散两步求解策略。因此，许多研究者对这些问题开展了一系列研究：

1)速度：对于输入的加权无向图，基于两步策略的图割模型需要对拉普拉斯矩阵进行特征值分解，其时间复杂度为 O(n³)，最快为 O(dn²),其运行时间对于大规模数据而言难以承担，并且需要更多的存储内存。针对这个问题，许多学者采取了采样法和锚点法，通过在小矩阵实施分解来代替在大矩阵上实施 EVD，使得模型在保持精度的同时，加快算法的运行速率。

采样法^[64]适用于图中的边子集或节点子集,前者使用谱稀疏化^[65]来近似图拉普拉斯算子,后者将原始的相似图简化为一个具有较低维度的图。Nyström 方法^[48,66,67]是一种寻找图拉普拉斯矩阵的近似 EVD 技术，通过计算子矩阵的 EVD 来近似原矩阵的 EVD。此外，KASP 和RASP^[49]也是快速的近似方法，它们从特征空间采样数据，并在小矩阵上实现 EVD。

此外，锚点法通过采样代表点来构造样本与代表点之间的相似性得到锚点图，通过对锚点图进行奇异值分解 (Singular Value Decomposition，SVD) 代替对原图进行 EVD，把时间复杂度从 O(n²) 降低为 O(n)。其中，FSC^[50]和LSC^[51]使用不同的锚点生成策略获得锚点图，SNC^[52]使用改进的谱旋转技术来得到聚类结果，FRWL^[53]使用随机游走策略来提升聚类性能。

2) 优化：图割模型是一个 NP-hard 问题，很难求解，以上各种图割方法都是通过放缩-离散两步策略对图割模型进行求解。由此，可能会使得解偏离直接求解原始问题的解，导致次优解，并且特征值分解以及奇异值分解也会耗费大量的时间。基于此，Li 等人^[68]通过引入秩约束条件学习一个具有 c个连通分量的邻接矩阵来直接求解 RCut，但其时间复杂度较高。因此，研究者们针对大图和锚点图都提出了优化算法。

DNC^[54]通过引入辅助变量而非采用松弛方法，来直接优化图割模型，但其计算复杂度为O(n²)，仍不适合处理大规模数据。为了解决这一问题，下列方法都通过加速策略将时间复杂度降低至 O(n)。FINC^[55]引入辅助变量并交替更新指示矩阵来加速 DNC，并且，相对于 DNC，FINC 的正则化参数是通过有效的方法调整的。Nie 等人提出了 Fast-CD^[56]，该方法无需任何辅助变量即可更新指示矩阵。除了针对传统的Ncut 模型外，SBMC^[57]引入平衡正则化项来避免平凡解，通过 ALM 方法直接求解具有离散约束的优化问题。进一步，为了在聚类过程中自动学习平衡参数，提出了一种新的图割模型 EBMC^[58]，以自动产生平衡划分并避免平凡解。

同样，对于锚点图方法，FNC^[54]通过引入辅助变量，直接优化基于锚点的图割模型，无需使用 SVD，具有较低的计算复杂度。为了更高效地优化模型，Nie 等人提出了 FDBC^[20]，只需要使用 CD 更新一个变量。此外，GCSED^[59]引入正则化参数，来同时进行谱嵌入和谱旋转。对于大规模平衡图割模型，Labin^[60]引了锚点图来扩展SBMC，使之适用于大规模数据；DBSC^[61]引了平衡正则化项，以获得锚点图问题的平衡聚类和离散解。表2展示了部分算法。

(3) 讨论

将 k-means 模型写成矩阵形式：

⑦$\min _{\mathbf{Y} \in I n d, \mathbf{M}} \operatorname{Tr}\left(\left(\mathbf{X}-\mathbf{M} \mathbf{Y}^{\mathrm{T}}\right)\left(\mathbf{X}-\mathbf{M} \mathbf{Y}^{\mathrm{T}}\right)^{\mathrm{T}}\right),$

通过对M求导并将导数设为零，得到$\mathbf{M}=\mathbf{X Y}\left(\mathbf{Y}^{\mathrm{T}} \mathbf{Y}\right)^{-1}$，将其带入 k-means 模型中，得到只有一个变量 Y 的模型：

⑧$\max _{\mathbf{Y} \in \operatorname{Ind}} \operatorname{Tr}\left(\left(\mathbf{Y}^{\mathrm{T}} \mathbf{Y}\right)^{-1} \mathbf{Y}^{\mathrm{T}} \mathbf{X}^{\mathrm{T}} \mathbf{X} \mathbf{Y}\right).$

根据拉普拉斯矩阵定义，图割模型的最小化问题可以转化为最大化问题，这里不再赘述。因此，k-means和图割模型的统一框架为：

⑨$\max _{\mathbf{Y} \in \text { Ind }} \operatorname{Tr}\left(\left(\mathbf{Y}^{\mathrm{T}} \mathbf{D} \mathbf{Y}\right)^{-1} \mathbf{Y}^{\mathrm{T}} \mathbf{K Y}\right),$

当 K = X^TX 且 D = I 时, 模型 ⑨ 为 k-means模型；当 K = W 时, 模型 ⑨ 为 Ncut 模型；当K = W 且 D = I 时,模型 ⑨ 为 RCut 模型。

众所周知，k-means 模型只能处理球形分布数据，而图割模型可以处理非凸数据。因为从另一个角度考虑, k-means 优化问题等价于：

⑩$\min _{\mathcal{C}_{1}, \mathcal{C}_{2}, \cdots, \mathcal{C}_{c}} \sum_{k=1}^{c} \frac{1}{\left|\mathcal{C}_{k}\right|} \sum_{x_{i}, x_{j} \in \mathcal{C}_{k}} d_{i j}^{2}$

d_ij 表示 x_i 和 x_j 之间的欧氏距离。当 D = I 时,图割优化问题等价于为：

⑪$\max _{\mathcal{C}_{1}, \mathcal{C}_{2}, \cdots, \mathcal{C}_{c}} \sum_{k=1}^{c} \frac{1}{\left|\mathcal{C}_{k}\right|} \sum_{x_{i}, x_{j} \in \mathcal{C}_{k}} w_{i j}$

其中, k-means 是通过最小化距离获得结果，图割模型是通过最大化相似性获得结果。而非凸数据中会存在同属于一类的数据点对距离比较远的情况, 此时, k-means 算法不会将它们分成一类, 而图割聚类算法最大化局部相似性。因此，后者可以捕捉到局部信息，能够更好地处理非凸数据。

2.2.2 基于启发式的聚类方法

基于启发式的聚类方法通常基于简单的规则或启发式策略来优化聚类结果, 不需要定义目标函数, 易于理解和实现, 能更灵活地适应各种类型和结构的数据。比较经典的方法有密度聚类算法^[19]、层次聚类算法^[18] 等。层次聚类算法包括: 凝聚式和分裂式聚类, 凝聚式聚类先将每个数据点作为一个独立的类, 然后通过合并最接近的类来构建层次结构, 直到所有数据点最终形成一个大的类。分裂式与凝聚式相反, 它先将整个数据集作为一个类, 然后通过分裂来构建层次结构, 直到每个数据点成为一个单独的类。本节重点介绍密度聚类算法。

密度聚类是一种启发式聚类方法，它通过在搜索空间中使用启发式技术来快速找到聚类的有效解决方案。其核心思想是将数据集中的样本划分为高密度区域和低密度区域，从而形成簇。常见的密度聚类算法 DBSCAN^[69]通过定义样本邻域内的最小样本数和邻域半径，将高密度区域内的样本归为同一簇，而低密度区域的样本被视为噪声。但是，密度聚类算法面临的一些挑战和缺点，限制了其在实际应用中的效果。首先，这些算法通常对参数敏感，需要调整邻域半径和最小样本数等参数，而这在实际场景中往往需要领域专业知识或者反复试验。其次，密度聚类对密度变化敏感，难以适应密度变化较大的区域，且对高维数据和非凸形状的簇不够鲁棒。

为了克服这些问题，研究者们提出了一系列改进方法。OPTICS^[70]引入自适应参数选择策略，以减轻对用户指定参数的依赖。Mcinnes 等人^[79]引入层次结构来更好地捕捉不同密度区域,提高对密度变化的适应性。对于高维数据，一些算法通过特征选择和降维等技术来缓解维度灾难问题^[80,81]。此外，DENCLUE^[71] 和 OPTICS 致力于使密度聚类算法更具适应性，能够处理更复杂的簇形状，并减弱对簇形状的敏感性。这些改进方法的引入使得密度聚类算法在更广泛的场景应用中能够更稳健、更灵活地应对不同类型的数据。虽然 DBSCAN可以重建任意形状的集群，然而，其高复杂度使其不适合大规模数据集。因此，DSets-DBSCAN^[72]将 DSets^[82] 与 DBSCAN集成，有效减少了时间消耗。KNNBLOCK DBSCAN^[73] 通过考虑每个样本与其前 k 个最近邻样本的相似性和连通性，减少了时间复杂度以及存储成本。

此外，如何为 DBSCAN 建立一个全局最优的密度连通性阈值至关重要，特别是在处理包含重叠聚类的数据集时。DPC^[74] 对密度峰的初始搜索可以有效区分高度重叠的集群，使得 DPC 具有广泛的应用。然而，与 DBSCAN 类似, DPC 由于其高复杂性而限制了其对大规模问题的适用性。因此，FastDPeak^[75]、DenPEHC^[76]、FHC-LDP^[77]、Fast LDP-MST^[78] 等使用不同的策略来加速 KNN 搜索或使用 k-means 算法来增强 DPC 的可扩展性。表3展示了部分算法。

2.3 模型优化

上一节从基于模型优化和启发式角度对聚类方法进行了分类介绍，其中，基于模型优化的方法因其简单、解释性强成为主流方法。它通过构建聚类模型并设计优化方法来获得聚类结果，这两步对于聚类方法来说同样重要。由于聚类算法中构建的模型通常涉及非凸优化问题，如何设计更好的优化方法，使得该模型发挥其最大的聚类潜力值得关注。并且，随着机器学习模型的复杂程度不断增加，聚类模型的优化在机器学习中起到越来越关键的作用。

优化方法可分为数值优化方法和智能优化方法。智能优化方法依靠对目标函数的采样，基于现实世界机理来制定搜索策略，通过设计相应的编码方式、适值函数和停止准则等相关内容以获得满足条件的解。而数值优化方法则通过优化损失函数来实现任务的最佳性能，旨在为模型提供一种数值计算的框架, 用于寻找到模型的局部或全局最优解。

2.3.1 数值优化方法

由于多数机器学习模型都是非凸优化问题，其中可能存在着许多局部解，寻找到全局最优解几乎是不可能的任务，且模型易受初始值影响从而陷入较差的局部解。因此，选择合适的优化方法对于成功训练和优化机器学习模型至关重要。根据聚类模型的求解问题有无约束条件，可将优化问题分为无约束问题以及有约束问题，无约束优化问题相对简单，因为在求解这样的问题时无需考虑可行域，可直接在函数上沿着搜索方向来寻找优化目标。根据搜索方向的不同，无约束优化方法主要有梯度下降方法、牛顿法等。而在约束优化问题中，待求解变量受到一系列约束条件的限制，如标签矩阵的约束为每行中只有一个非零元素 1，隶属度矩阵的约束为非负且行和为 1。求解有约束的优化问题的方法有投影梯度法、坐标下降法 (Coordinate Descent，CD) ^[31]、增广拉格朗日乘子法 (Augmented Lagrangian multiplier，ALM) ^[57]、交替方向乘子法 (Alternating DirectionMethod of Multipliers，ADMM) ^[31]、迭代重复加权法 (Iteratively Re-Weighted，IRW)^[17]等。不同的优化方法具有不同的特点和适用范围，没有一种优化算法适用于所有的优化问题。

聚类模型中常见的具有离散约束的优化问题通过指示矩阵的约束限制使得模型可以直接得到聚类结果，但是，这类问题是一个 NP-hard 问题，无法在多项式时间内找到正确解。例如，对于具有离散条件约束的 k-means 聚类模型，针对 Lloyd 算法对初始化敏感，易陷入较差的局部解，而且迭代过程中可能出现空类的问题，Nie等人^[33]通过减少中间变量，利用 ADMM 来交替优化，其显示出更快的收敛速度。进一步， Nie 等人^[32]将 k-means 模型转化为只有标签矩阵的优化问题，并利用 CD 求解，中间变量的舍弃使得模型对初始化不敏感，可以获得更好的解。Chen等人^[83]提出一个框架来进行 k-means 和谱旋转的联合优化，并通过 CD 对标签矩阵进行逐行更新。对于基于离散约束的图割模型的优化，2.2.1节已有详细介绍，这里不再赘述。

此外，对于具有模糊约束的聚类模型，Chen 等人^[84]提出一种新的模糊聚类算法，并通过ALM 来求解有约束的模糊隶属度矩阵，利用 IRW 求解协方差矩阵，以及使用牛顿法求解中心矩阵。同样，Xue 等人^[17]利用 IRW 求解模糊 c-means 算法。Nie 等人^[85]最近通过实验分析对CD、投影梯度法、IRW 三种优化方法进行了比较，发现在保持同样复杂度的基础上，CD 能够获得最高的聚类性能，这也将为未来开展聚类工作的研究和优化方法制定产生一定的影响。

2.3.2 智能优化方法

数值优化方法依赖于数学模型和数值计算，通过对目标函数进行数值计算和优化来搜索最优解。而智能优化方法受到人类智能、生物群体社会性或自然现象规律的启发，采用启发式规则或模仿自然过程来寻找可行解。这些算法具有一定的全局优化能力、通用性强且适合并行处理，已应用于图像分割^[86]、旅行商问题^[87]以及股票价格预测^[88]等领域。这些智能优化方法包括：模拟退火算法 (Simulated Annealing，SA) ^[89]和禁忌搜索算法 (Tabu Search，TS) ^[90]；基于群体仿真的进化算法，如遗传算法 (Genetic Algorithm，GA) ^[91]、差分进化算法^[92]；基于群体仿真的群智能算法，如蚁群算法^[93]、粒子群算法^[94]以及布谷鸟算法^[95]。

这些方法已成功应用于优化聚类模型，如，Selim 等人^[96]利用 SA 对 k-means 模型进行优化；Muritiba 等人^[97]利用 TS 算法求解容量中心聚类问题；Di Martino 等人^[98]利用 GA 算法提出了一种新的量子启发遗传算法；Cura^[99]利用粒子群优化算法解决传统聚类模型； Hu 等人^[100]在k-means 算法的迭代过程中利用布谷鸟算法的莱维飞行机制搜索新的位置，避免 k-means 算法过早陷入局部最优解。

3 科学问题与展望

经过数十年的长足发展和探索，无监督聚类方法已经在聚类算法以及优化方法上全面发展，并取得了显著成果。但聚类算法作为机器学习研究以及数据处理的基础方向之一，其研究随着现代数据产生的特点而发展，很多开放性的问题仍有待进一步探索。本节根据现实数据的特点以及发展趋势对聚类算法的研究热点方向进行展望，具体可以概括为以下几个方面。

(1)无监督单视角聚类

随着互联网的迅猛发展，智能终端种类的攀升和技术的不断进步，真实世界中产生的数据从样本数量、数据维数、类别数量三个维度呈现出大规模的趋势。1) 大规模数据聚类问题：传统聚类方法对数据进行分析时需要的时间和存储成本与样本数量成幂次关系，因而在样本数量变多时难以快速或正常执行，聚类方法如何轻松处理大规模数据成为其能否在信息爆炸时代被广泛应用的关键。许多方法基于锚点策略提出了改进的聚类模型，但如何确定合适的锚点数量以及如何选择具有代表性和丰富信息的锚点是一个重要问题。在深度学习中许多包括 MiniBatch聚类、并行聚类、分布式聚类等改进策略使大规模聚类问题得到了一定的缓解，但在研究中仍存在模型选择和参数调节的问题。2) 大维度数据聚类问题：在文本挖掘、推荐系统、基因分析等领域中，需要被分析的数据往往是高维且稀疏的，传统聚类方法对其进行分析会出现所有样本的相似性都较低的情况，从而导致聚类效果不佳。因此，对高维数据进行准确分析是值得关注的研究方向。数据预处理、降维算法以及子空间学习等方法已经从各个角度对这个问题进行缓解，未来可能仍需研究如何分辨噪声和异常值，以及如何剔除不正常样本带来的影响。3) 大类别数据聚类问题：相对于大数据和大维度聚类问题，大类别聚类任务很少被重视。数据类别大会导致数据类间差异性弱，进而增加了数据分析的难度。因此，如何处理大类别数据来同时保证聚类精度和效率值得研究。此外，多数机器学习模型都是非凸优化问题，存在许多局部解，因此，设计合适的优化方法来发挥模型的聚类潜力值得进一步研究。

(2)多模态数据的融合 (多模态聚类)

伴随着信息采集手段的丰富发展，数据往往可以在多种角度下被表示。如何充分挖掘和利用多个数据源下的一致性和差异化信息，补足单一数据源下的信息不充分问题，是物互联时代下聚类算法的重要研究方向。另外，在实际应用中，数据往往存在各种不确定性和噪声，如何从不完整的数据视角中进行聚类分析，发现隐藏在数据中的模式和结构，具有重要研究意义。多视角聚类方法在如何捕捉多模态数据的一致性和不完整视角补全问题上已经提出了建设性的改进。未来可能需要专注于如何更好地挖掘多个模态间信息的一致性关系并避免某些视角中的异常值影响。此外，对于多个视角中数据的顺序对齐也是在未来需要考虑的问题。

(3)不同聚类算法的融合 (集成聚类)

通过前文的介绍已知，不同的聚类方法有其适宜的不同数据类型，且同一种聚类算法在不同的参数取值、优化方法下也有不同的性能表现。通过使用不同的基础聚类器，可以从同一数据集中发现不同的结构，或者通过调整同一基础聚类器的不同参数设置来提高聚类分析的泛化能力和鲁棒性。这是探索复杂数据结构、提供稳定和高质量聚类结果的一个重要途径，因此，集成聚类具有极大的研究价值和意义。

(4)深度学习与聚类的融合 (深度聚类)

随着深度学习的兴起，深度图聚类技术不断取得突破。基于深度神经网络的深度聚类方法旨在将聚类目标与深度表示学习统一起来，利用深度神经网络强大的拟
合能力，并结合深度学习的非线性运算能力和传统聚类分析的可解释性，对数据集中的基本结构信息进行挖掘。图神经网络的引入丰富了深度聚类方法的工具箱，通过对图数据进行建模和表示学习，更好地捕捉图数据中的拓扑结构和节点之间的关系，提高聚类的准确性和鲁棒性，对于社交网络、生物信息学和推荐系统等领域的图数据聚类具有重要意义。因此，结合深度学习来提升聚类效果已成为新的研究趋势。

(5)其他

1)半监督聚类：尽管传统的聚类分析任务已经取得了显著的成果，但现实聚类任务往往能够获得一些额外的监督信息，而无监督聚类方法不能利用这些监督信息。半监督聚类则可以对先验的标签或者约束条件进行利用和学习，提升聚类方法性能的上限。现有半监督聚类方法中的研究难点为约束信息的违反问题，即如何在迭代中保证成对约束中的必连条件和勿连条件被满足，以充分挖掘和利用先验知识中隐含的数据结构信息。2) 模糊聚类：与传统的硬聚类不同，模糊聚类允许数据点属于多个簇，而不是严格地分配到一个确定的簇中。在模糊聚类中，每个数据点都被赋予一个隶属度 (或隶属度向量)，这种柔性分配对噪声和异常值更具有容忍性，可以提供更丰富的信息。3) 鲁棒聚类：真实数据的产生和采集过程中往往会掺杂进噪声或产生异常数据，这些信息将干扰传统聚类方法的分析过程，导致聚类效果的下降。鲁棒聚类针对此种情况展开研究，通过识别数据中的离群点，弱化甚至消除异常数据带来的影响，以提升算法对数据中异常值的鲁棒性。

4 结语

本文从数据类型和建模策略角度分别对无监督聚类方法进行了归纳和梳理，并对基于模型优化的聚类算法梳理了相关优化方法。尽管取得了一些进展，但随着数据规模的不断增大和应用场景的多样化，聚类算法在处理复杂任务时仍面临着挑战，无法高效刻画数据的本质聚类结构。因此，在未来的研究中，我们希望聚类算法能够高效处理任意分布数据并且能够扩展到更多场景任务中。解决这些问题需要综合运用数学、计算机科学、统计学等多学科的知识，借助新兴技术如深度学习、量子计算等，不断推动聚类算法的发展。

参考文献

原文顺序 | 出版日期 | 本文引用

[1]	Diday E, Simon J C. Clustering analysis. Digital Pattern Recognition[M]. Berlin, Heidelberg: Springer, 1976, 47-94.

[2]	王骏, 王士同, 邓赵红. 聚类分析研究中的若干问题[J]. 控制与决策, 2012, 27(3): 321-328.

[3]	(Wang J, Wang S T, Deng Z H. Survey on challenges in clustering analysis research[J]. Control and Decision, 2012, 27(3): 321-328.)

[4]	Wang X Y, Du Y X, Yang S, et al. RetCCL: Clustering-guided contrastive learning for whole-slide image retrieval[J]. Medical Image Analysis, 2023, 83: 102645.

[5]	Chen M S, Han J W, Yu P S. Data mining: An overview from a database perspective[J]. IEEE Transactions on Knowledge and Data Engineering, 1996, 8(6): 866-883.

[6]	Ji X, Vedaldi A, Henriques J. Invariant information clustering for unsupervised image classification and segmentation[C]. In Proceedings of the IEEE International Conference on Computer Vision. October 27-November 2, 2019. Seoul, Korea (South). IEEE, 2019, 9865-9874.

[7]	Bianchi F M, Grattarola D, Alippi C. Spectral clustering with graph neural networks for graph pooling[C]. Proceedings of the 37th International Conference on Machine Learning. ACM, 2020, 874-883.

[8]	Karim M R, Beyan O, Zappa A, et al. Deep learning-based clustering approaches for bioinformatics[J]. Briefings in Bioinformatics, 2021, 22(1): 393-415.

[9]	Ikotun A M, Ezugwu A E, Abualigah L, et al. K-means clustering algorithms: A comprehensive review, variants analysis, and advances in the era of big data[J]. Information Sciences, 2023, 622: 178-210.

[10]	赵兴旺. 大规模复杂数据聚类算法研究[D]. 太原: 山西大学, 2019.

[11]	(Zhao X W. Research on clustering algorithms for large-scale complex data[D]. Taiyuan: Shanxi University, 2019.)

[12]	Moseley B, Wang J R. Approximation bounds for hierarchical clustering: Average linkage, bisecting k-means, and local search[J]. Journal of Machine Learning Research, 2023, 24(1): 1-36.

[13]	Wu Z, Leahy R. An optimal graph theoretic approach to data clustering: Theory and its application to image segmentation[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 1993, 15(11): 1101-1113.

[14]	Kriegel H P, Kröger P, Sander J, et al. Density-based clustering[J]. WIREs Data Mining and Knowledge Discovery, 2011, 1(3): 231-240.

[15]	Tsitsulin A, Palowitch J, Perozzi B, et al. Graph clustering with graph neural networks[J]. Journal of Machine Learning Research, 2023, 24(127): 1-21.

[16]	Liu Y, Yang X H, Zhou S H, et al. Hard sample aware network for contrastive deep graph clustering[C]. Proceedings of the AAAI Conference on Artificial Intelligence, 2023, 37(7): 8914-8922.

[17]	Wang H B, Yao M Z, Jiang G Q, et al. Graph-collaborated auto-encoder hashing for multiview binary clustering[J]. IEEE Transactions on Neural Networks and Learning Systems, 2023.

[18]	Hartigan J A, Wong M A. Algorithm AS 136: A k-means clustering algorithm[J]. Journal of the Royal Statistical Society, 1979, 28(1): 100-108.

[19]	Xue J J, Nie F P, Wang R, et al. Iteratively reweighted algorithm for fuzzy c-means[J]. IEEE Transactions on Fuzzy Systems, 2022, 30(10): 4310-4321.

[20]	Murtagh F, Contreras P. Algorithms for hierarchical clustering: an overview[J]. WIREs Data Mining and Knowledge Discovery, 2012, 2(1): 86-97.

[21]	Cheng D F, Xu R H, Zhang B, et al. Fast density estimation for density-based clustering methods[J]. Neurocomputing, 2023, 532: 170-182.

[22]	Nie F P, Xue J J, Wang R, et al. Fast clustering by directly solving bipartite graph clustering problem[J]. IEEE Transactions on Neural Networks and Learning Systems, 2022.

[23]	Ban Z H, Liu J G, Cao L. Superpixel segmentation using gaussian mixture model[J]. IEEE Transactions on Image Processing, 2018, 27(8): 4105-4117.

[24]	Lloyd S. Least squares quantization in PCM[J]. IEEE Transactions on Information Theory, 1982, 28(2): 129-137.

[25]	Wu X D, Kumar V, Ross Quinlan J, et al. Top 10 algorithms in data mining[J]. Knowledge and Information Systems, 2008, 14(1): 1-37.

[26]	Arthur D, Vassilvitskii S. k-means++: The advantages of careful seeding[C]. In Proceedings of the ACM-SIAM Symposium on Discrete Algorithms, 2006, 1027-1035.

[27]	Bachem O, Lucic M, Hassani H, et al. Fast and provably good seedings for k-means[C]. In Proceedings of the International Conference on Neural Information Processing System, 2016, 55-63.

[28]	Vincent Cohen-Addad, Silvio Lattanzi, Ashkan Norouzi-Fard, et al. Fast and accurate k-means++ via rejection sampling[C]. In Proceedings of the International Conference on Neural Information Processing System, 2020, 16235-16245.

[29]	Elkan C. Using the triangle inequality to accelerate k-means[C]. In Proceedings of the International Conference on Machine Learning, 2003, 147-153.

[30]	Xia S Y, Peng D W, Meng D Y, et al. A fast adaptive k-means with no bounds[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2020.

[31]	Ding Y F, Zhao Y, Shen X P, et al. Yinyang k-means: A drop-in replacement of the classic k-means with consistent speedup[C]. In International Conference on Machine Learning, PMLR, 2015, 579-587.

[32]	Newling J, Fleuret F. Fast k-means with accurate bounds[C]. In International Conference on Machine Learning, PMLR, 2016, 936-944.

[33]	Nie F P, Xue J J, Wu D Y, et al. Coordinate descent method for k k-means[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2021, 44(5): 2371-2385.

[34]	Nie F P, Li Z H, Wang R, et al. An effective and efficient algorithm for k-means clustering with new formulation[J]. IEEE Transactions on Knowledge and Data Engineering, 2022, 35(4): 3433-3443.

[35]	Ahmed M, Seraj R, Islam S M S. The k-means algorithm: A comprehensive survey and performance evaluation[J]. Electronics, 2020, 9(8): 1295.

[36]	Fränti P, Sieranoja S. How much can k-means be improved by using better initialization and repeats?[J]. Pattern Recognition, 2019, 93: 95-112.

[37]	Bachem O, Lucic M, Hassani S H, et al. Approximate k-means++ in sublinear time[C]. In Proceedings of the AAAI Conference on Artificial Intelligence, 2016, 1459-1467.

[38]	Bachem O, Lucic M, Krause A. Distributed and provably good seedings for k-means in constant rounds[C]. In Proceedings of the International Conference on Machine Learning, 2017, 292-300.

[39]	Kant S, Ahmad Ansari I. An improved K means clustering with Atkinson index to classify liver patient dataset[J]. International Journal of System Assurance Engineering and Management, 2016, 7: 222-228.

[40]	Bahmani B, Moseley B, Vattani A, et al. Scalable k-means++[J]. Proceedings of the VLDB Endowment, 2012, 5(7): 622-633.

[41]	Orchard M T. A fast nearest-neighbor search algorithm. In Acoustics, Speech, and Signal Processing, IEEE International Conference on[C]. IEEE Computer Society, 1991,2297-2298.

[42]	Kanungo T, Mount D M, Netanyahu N S, et al. An efficient k-means clustering algorithm: Analysis and implementation[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2002, 24(7): 881-892.

[43]	Pelleg D, Moore A. Accelerating exact k-means algorithms with geometric reasoning[C]. In Proceedings of the Fifth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 1999, 277-281.

[44]	Newling J, Fleuret F. Nested mini-batch k-means[C]. In Proceedings of the International Conference on Neural Information Processing System, 2016, 1352-1360.

[45]	Cohen M B, Elder S, Musco C, et al. Dimensionality reduction for k-means clustering and low rank approximation[C]. In Proceedings of the ACM Symposium on Theory of Computing, 2015, 163-172.

[46]	Sinha K. K-means clustering using random matrix sparsification[C]. In Proceedings of the International Conference on Machine Learning, 2018, 4684-4692.

[47]	Hamerly G. Making k-means even faster[C]. In Proceedings of the SIAM International Conference on Data Mining, 2010, 130-140.

[48]	Newling J, Fleuret F. K-medoids for k-means seeding[J]. Advances in Neural Information Processing Systems, 2017, 30,.

[49]	Ng R T, Han J W. CLARANS: A method for clustering objects for spatial data mining[J]. IEEE Transactions on Knowledge and Data Engineering, 2002, 14(5): 1003-1016.

[50]	Fowlkes C, Belongie S, Chung F, et al. Spectral grouping using the nyström method[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2004, 26(2): 214-225.

[51]	Yan D H, Huang L, Jordan M I. Fast approximate spectral clustering[C]. In Proceedings of the 15th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 2009, 907-916.

[52]	Zhu W, Nie F P, Li X L. Fast spectral clustering with efficient large graph construction[C]. In 2017 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), IEEE, 2017, 2492-2496.

[53]	Cai D, Chen X L. Large scale spectral clustering via landmark-based sparse representation[J]. IEEE Transactions on Cybernetics, 2014, 45(8): 1669-1680.

[54]	Chen X J, Nie F P, Huang J Z X, et al. Scalable normalized cut with improved spectral rotation[C]. In IJCAI, 2017, 1518-1524.

[55]	Wang C L, Nie F P, Wang R, et al. Revisiting fast spectral clustering with anchor graph[C]. In ICASSP 2020-2020 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), IEEE, 2020, 3902-3906.

[56]	Chen X J, Hong W J, Nie F P, et al. Spectral clustering of large-scale data by directly solving normalized cut[C]. In Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, 2018, 1206-1215.

[57]	Chen X J, Xiao Z C, Nie F P, et al. Finc: An efficient and effective optimization method for normalized cut[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2022.

[58]	Nie F P, Lu J T, Wu D Y, et al. A novel normalized-cut solver with nearest neighbor hierarchical initialization[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2023.

[59]	Chen X J, Haung J Z, Nie F P, et al. A self-balanced min-cut algorithm for image clustering[C]. In Proceedings of the IEEE International Conference on Computer Vision, 2017, 2061-2069.

[60]	Chen X J, Hong W J, Nie F P, et al. Enhanced balanced min cut[J]. International Journal of Computer Vision, 2020, 128:1982-1995.

[61]	Wang Z, Li Z Q, Wang R, et al. Large graph clustering with simultaneous spectral embedding and discretization[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2020, 43(12): 4426-4440.

[62]	Chen X J, Chen R J, Wu Q Y, et al. Labin: Balanced min cut for large-scale data[J]. IEEE Transactions on Neural Networks and Learning Systems, 2019, 31(3): 725-736.

[63]	Wang R, Chen H M, Lu Y H, et al. Discrete and balanced spectral clustering with scalability[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2023.

[64]	Hagen L, Kahng A B. New spectral methods for ratio cut partitioning and clustering[J]. IEEE Transactions on Computer-aided Design of Integrated Circuits and Systems, 1992, 11(9): 1074-1085.

[65]	Shi J B, Malik J. Normalized cuts and image segmentation[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2000, 22(8): 888-905.

[66]	Tremblay N, Loukas A. Approximating spectral clustering via sampling: a review[J]. Sampling Techniques for Supervised or Unsupervised Tasks, 2020, 129-183.

[67]	Spielman D A, Teng S H. Spectral sparsification of graphs[J]. SIAM Journal on Computing, 2011, 40(4): 981-1025.

[68]	Gittens A, Mahoney M W. Revisiting the nyström method for improved large-scale machine learning[C]. In International Conference on Machine Learning, PMLR, 2013, 567-575.

[69]	Bouneffouf D, Birol I. Sampling with minimum sum of squared similarities for nyström-based large scale spectral clustering[C]. In IJCAI, 2015, 2313-2319.

[70]	Li J, Nie F P, Li X L. Directly solving the original ratiocut problem for effective data clustering[C]. In Proceedings of the IEEE International Conference on Acoustics, Speech and Signal Processing, 2018, 2306-2310.

[71]	Ester M, Kriegel H P, Sander J, et al. A density-based algorithm for discovering clusters in large spatial databases with noise[C]. In KDD, 1996, 96: 226-231.

[72]	Ankerst M, Breunig M M, Kriegel H P, et al. Optics: Ordering points to identify the clustering structure[J]. ACM Sigmod Record, 1999, 28(2): 49-60.

[73]	McInnes L, Healy J, Astels S. hdbscan: Hierarchical density based clustering[J]. The Journal of Open Source Software, 2017, 2(11): 205.

[74]	Hinneburg A, Gabriel H H. DENCLUE 2.0: Fast clustering based on kernel density estimation[C]. In International Symposium on Intelligent Data Analysis, Springer, 2007, 70-80.

[75]	Hou J, Gao H J, Li X L. DSets-DBSCAN: A parameter-free clustering algorithm[J]. IEEE Transactions on Image Processing, 2016, 25(7): 3182-3193.

[76]	Chen Y W, Zhou L D, Pei S W, et al. KNN-BLOCK DBSCAN: Fast clustering for large-scale data[J]. IEEE Transactions on Systems, Man, and Cybernetics: Systems, 2019, 51(6): 3939-3953.

[77]	Rodriguez A, Laio A. Clustering by fast search and find of density peaks[J]. Science, 2014, 344(6191): 1492-1496.

[78]	Chen Y W, Hu X L, Fan W T, et al. Fast density peak clustering for large scale data based on KNN[J]. Knowledge-Based Systems, 2020, 187: 104824.

[79]	Xu J, Wang G Y, Deng W H. DenPEHC: Density peak based efficient hierarchical clustering[J]. Information Sciences, 2016, 373: 200-218.

[80]	Guan J Y, Li S, He X X, et al. Fast hierarchical clustering of local density peaks via an association degree transfer method[J]. Neurocomputing, 2021, 455: 401-418.

[81]	Qiu T, Li Y J. Fast LDP-MST: An efficient density-peak-based clustering method for large-size datasets[J]. IEEE Transactions on Knowledge and Data Engineering, 2022, 35(5): 4767-4780.

[82]	Shi J L, Luo Z G. A novel clustering approach based on the manifold structure of gene expression data[C]. In 2010 4th International Conference on Bioinformatics and Biomedical Engineering, IEEE, 2010, 1-4.

[83]	Song Y, Gu Y, Zhang R, et al. Brepartition: Optimized high-dimensional kNN search with bregman distances[J]. IEEE Transactions on Knowledge and Data Engineering, 2020, 34(3): 1053-1065.

[84]	Pavan M, Pelillo M. Dominant sets and pairwise clustering[J]. IEEE transactions on pattern analysis and machine intelligence, 2006, 29(1): 167-172.

[85]	Chen J W, Xie S Y, Jiang H Y, et al. A novel k-means framework via constrained relaxation and spectral rotation[J]. IEEE Transactions on Neural Networks and Learning Systems, 2023.

[86]	Chen Q, Yu W Z, Zhao X W, et al. Rooted mahalanobis distance based gustafson-kessel fuzzy c-means[J]. Information Sciences, 2023, 644: 118878.

[87]	Nie F P, Xue J J, Yu W Z, et al. Fast clustering with anchor guidance[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2023.

[88]	Chakraborty S, Mali K. Fuzzy modified cuckoo search for biomedical image segmentation[J]. Knowledge and Information Systems, 2022, 64(4): 1121-1160.

[89]	Zhang Z C, Yang J L. A discrete cuckoo search algorithm for traveling salesman problem and its application in cutting path optimization[J]. Computers and Industrial Engineering, 2022, 169: 108157.

[90]	Guo Y Q, Guo J F, Sun B Z, et al. A new decomposition ensemble model for stock price forecasting based on system clustering and particle swarm optimization[J]. Applied Soft Computing, 2022, 130: 109726.

[91]	Bertsimas D, Tsitsiklis J. Simulated annealing[J]. Statistical Science, 1993, 8(1): 10-15.

[92]	Glover F. Tabu search: A tutorial[J]. Interfaces, 1990, 20(4): 74-94.

[93]	Maulik U, Bandyopadhyay S. Genetic algorithm-based clustering technique[J]. Pattern Recognition, 2000, 33(9): 1455-1465.

[94]	贺兴时, 孟炎辉, 田梦男, 等. 基于多策略组合的改进差分进化算法[J]. 纺织高校基础科学学报, 2023, 36: 80-88.

[95]	(He X S, Meng Y H, Tian M N, et al. Improved differential evolution algorithm with multi-strategies[J]. Basic Sciences Journal of Textile Universities, 2023, 36(4): 80-88.)

[96]	贺兴时, 陈慧园. 基于避障寻优改进蚁群算法的机器人路径规划[J/OL]. 西安工程大学学报, 2024, 38(2): 1-9.

[97]	(He X S, Chen H Y. Robot path planning based on obstacle avoidance optimization and improved ant colony algorithm[J/OL]. Journal of Xi’an Polytechnic University, 2024, 38(2): 1-9.)

[98]	蒋大锐, 徐胜超. 基于改进 pso-means 算法的大数据聚类处理方法[J/OL]. 吉林大学学报 (信息科学版), 1-8. https://doi.org/10.19292/j.cnki.jdxxp.20231128.002.

[99]	Jiang D R, Xu S C. Large data clustering processing method based on improved PSO means clustering algorithm[[J/OL]]. Journal of Jilin University (Information Science Edition, 1-8. https://doi.org/10.19292/j.cnki.jdxxp.20231128.002)

[100]

顾佳鑫, 贺兴时, 刘青. 改进的布谷鸟搜索算法对支持向量机参数[J]. 西安工程大学学报, 2022, 36: 110-118.

[101]

(Gu J X, He X S, Liu Q. Parameter optimization of support vector machine based on improved cuckoo search algorithm[J]. Journal of Xi’an Polytechnic University, 2022, 36(2): 110-118.)

[102]

Selim S Z, Alsultan K. A simulated annealing algorithm for the clustering problem[J]. Pattern Recognition, 1991, 24(10): 1003-1008.

[103]

Muritiba A E F, Gomes M J N, de Souza M F, et al. Path-relinking with tabu search for the capacitated centered clustering problem[J]. Expert Systems with Applications, 2022, 116766.

[104]

Di Martino F, Sessa S. A novel quantum inspired genetic algorithm to initialize cluster centers in fuzzy c-means[J]. Expert Systems with Applications, 2022, 191: 116340.

[105]

Cura T. A particle swarm optimization approach to clustering[J]. Expert Systems with Applications, 2012, 39(1): 1582-1588.

[106]

Hu H Z, Liu J X, Zhang X P, et al. An effective and adaptable k-means algorithm for cluster analysis[J]. Pattern Recognition, 2023, 139: 109404.

基金资助

☆国家自然科学基金(62176212)

PDF (18008KB)

858

访问

被引

详细

导航

Published
2024-02-15
Online Date
2024-03-20

摘要