《Information Sciences》：TscEcs: Two-stage clustering using edge-cutting and statistics based on proximity graphs
编辑推荐：
摘要本文提出了一种基于近邻图的两阶段聚类算法，称为TscEcs（基于边切割和统计的两阶段聚类）。该方法首先使用Delaunay三角剖分和Gabriel图来表示空间数据，然后通过结合几何特征和稳健统计特征的局部和全局切割策略修剪长边。在图划分之后，从连通分量形成簇，并使用基于分
摘要
本文提出了一种基于近邻图的两阶段聚类算法，称为TscEcs（基于边切割和统计的两阶段聚类）。该方法首先使用Delaunay三角剖分和Gabriel图来表示空间数据，然后通过结合几何特征和稳健统计特征的局部和全局切割策略修剪长边。在图划分之后，从连通分量形成簇，并使用基于分量大小的肘部法识别异常值。在合成数据集和真实世界数据集上的实验结果表明，TscEcs能够有效检测任意形状、不同密度和大小不平衡的簇，同时与DBSCAN、OPTICS和HDBSCAN等传统方法相比，所需的输入参数更少，在多个外部聚类准则上取得了具有竞争力或更优的性能。
引言
近年来，聚类分析在空间数据挖掘中的知识发现自动化过程中发挥了重要作用[1,2]。已经开发了许多空间聚类算法来揭示隐含信息并对相关空间对象进行分组。一个好的聚类算法满足两个主要要求：高簇内相似性和低簇间相似性。最大化的簇内（同一簇内）相似性导致同一簇内的数据点之间距离较小，从而产生一种称为同质性的特性。相反，最小化的簇间（不同簇间）相似性通过推远不同簇中的数据点来增加它们之间的距离，从而产生一种称为分离性的特性。
在本文中，我们提出了一种基于近邻图的空间聚类算法。它能够对复杂形状进行自动聚类。此外，它还允许感兴趣的用户通过为特定应用设置参数来调整聚类过程。为了表征数据，首先基于数据点构建一个无向图，表示顶点之间的空间相似性。然后算法通过移除全局长边将图划分为子图。接下来，根据子图的内部边长和稳健统计特征修剪局部长边。最后，根据子图的连通性将数据点分配到最终簇中。
本文其余部分分为四节。第2节简要介绍了近邻图的建立和一些现有的聚类方法。第3节描述了所提出的算法。第4节展示了实验结果，并在第5节得出结论。
章节摘要
文献综述
近邻图建立了一种几何结构，其中两个空间对象满足某些几何要求时通过一条边连接[3]。这样的图通常由高效算法计算，可以作为相似矩阵的表示，例如Delaunay三角剖分（DT）[4]和Gabriel图（GG）[5]。使用近邻图的关键优势在于它能够动态定义邻域，无需固定的距离阈值。
方法论
所提出的算法是基于近邻图的基于边切割和统计的两阶段聚类算法（TscEcs）。图1展示了所提出算法的框图。
首先，使用近邻图表示数据的空间结构。随后，根据图的结构性、几何和统计特征修剪全局和局部长边。最后，系统地检查所有顶点，将其适当分配到簇中或识别为
结果
在本节中，我们报告了所提出的算法TscEcs的比较研究。我们使用各种合成数据集和真实世界数据集验证了该算法。为了比较这些数据集结果的质量，我们使用了外部聚类准则。我们对七个公开可用的数据集进行了一些实验，即Chameleon（t8.8k）数据集[12]、UCI（Heart-Statlog、New-Thyroid）数据集[13]、Aggregation[14]、Compound[15]、D31[16]、neck-touch-data[9]。详细信息见
结论和未来工作
在本文中，我们提出了一种基于近邻图的利用边切割和统计的两阶段聚类方法。所提出的方法运行如下。首先，通过近邻图捕获数据的空间结构。随后，根据图的结构性、几何和统计特征修剪全局和局部长边。最后，系统地评估每个顶点，将其分配到簇中或标记为异常值。实验结果表明
资金支持
本研究得到重庆市教育委员会科技研究项目支持（项目编号：KJQN202203910、KJQN202603914）。
数据和材料可用性
本研究使用的图像数据集可在线获取。
CRediT作者贡献声明
徐富平：写作 – 审阅与编辑，写作 – 原稿撰写，形式分析。徐岚奇：可视化，验证，数据整理。
Fuping Xu|Lanqi Xu
