《Neurocomputing》：Density-increment and cut-edge optimized clustering via minimum spanning forest
编辑推荐：
针对传统图聚类方法连接性差和局部结构保留不足的问题，提出基于最小生成森林（MSF）的分合聚类算法SMMSF。通过迭代生成α个MST构建MSF，增强对局部和全局结构的表征；分裂阶段利用密度增量峰值识别高密度区域，加速深度优先搜索实现高效聚类；合并阶段采用包含切点和切边的改进距离度，分两阶段优化聚类结果。实验表明该算法在多种数据集上显著优于现有方法，尤其适应高维、异构和非均匀噪声场景。
作者：翟浩宇、杨杰、郭汉涛、王斌、马岩
上海师范大学信息、机械与电气工程学院，中国上海200234
摘要
基于图的聚类方法因其能够模拟复杂数据结构并揭示内在关系而受到广泛关注。然而，传统方法（如k最近邻图和最小生成树（MST）通常存在连通性差的问题，无法准确保留局部结构，从而限制了聚类性能。为了解决这些问题，本文提出了一种基于最小生成森林（MSF）的新聚类算法，该算法采用多阶段分割-合并策略。首先，通过迭代生成和合并α个MST来构建MSF，从而更稳健地表示局部和全局结构。在分割阶段，沿着密度增量最大的路径进行遍历，确保簇围绕密度增量峰值形成，同时保持结构一致性。合并阶段包括两个步骤：（1）初始合并步骤，将空间相邻的小簇组合在一起；（2）基于新的簇间距离度量的精细合并过程，该度量考虑了割点和割边，实现了自适应和拓扑感知的合并策略。在合成数据和UCI真实数据集上的广泛实验表明，所提出的方法始终优于现有的基于图的聚类方法，在具有不同密度、形状和噪声水平的数据集中表现出更强的鲁棒性。
引言
聚类分析的目标是以一种方式对数据进行分类，即在同一簇内的数据点之间最大化相似性，同时最小化不同簇之间数据点之间的相似性。聚类在模式识别、图像分析和生物信息学等多个领域得到了广泛应用[1]、[2]、[3]。一些常用的经典聚类算法，如k-means[4]、层次聚类[5]和DBSCAN[6]，因其简单性和易于实现而受到青睐[7]。然而，这些算法可能并不适用于所有场景，因为它们的性能会因特定数据集而异。
近年来，基于图的聚类方法因其在建模数据关系方面的灵活性而受到广泛研究。本节回顾了现有基于图的聚类方法中的密度定义和分割-合并策略，强调了它们的优点和缺点，为所提出的方法奠定了基础。
