基于径向搜索的图聚类方法(RSGC)：一种针对多峰复杂数据的高效聚类框架

本文提出了一种创新的基于径向搜索的图聚类方法（Radial Search-Based Graph Clustering, RSGC），通过径向搜索分配（RSA）算法实现相似图的初始分区，生成具有单峰特性的子图结构，并基于跨簇边重要性设计子图相似性度量。该方法有效解决了传统谱聚类忽略局部结构、密度峰值聚类（DPC）在多峰数据中失效等问题，在合成数据集和单细胞RNA测序（scRNA-seq）等真实数据中展现出优越性能。

　　

Highlight

• 设计了一种相似图分区框架RSGC，能够通过子图划分与合并有效检测多峰数据中任意形状和密度的簇

• 提出径向搜索分配（RSA）方法，利用相似图局部结构信息快速识别中心节点，并通过径向搜索过程高效分配非中心节点

• 基于跨簇边重要性假设设计子图相似性度量，可靠评估子图间关联性

• 在具有任意形状/密度的合成数据集及scRNA-seq真实数据中验证了方法的普适性

The proposed RSGC method

本节详细阐述了RSGC方法的聚类策略。在介绍使用的连接度量后，重点讨论了子图生成与合并的核心步骤：

1. 1.

   子图生成阶段采用RSA方法，通过计算节点局部密度和平均路径权重，将相似图划分为多个具有单峰特性的子图

2. 2.

   子图合并阶段创新性地提出基于跨簇边权重的相似性度量公式：

   Sim(S_i,S_j)=∑_e∈Ecross(w(e)×I(e))

   其中w(e)表示边权重，I(e)为边重要性指标

Experiments

实验部分展示了RSGC在三大场景的验证：

1. 1.

   合成数据集测试：在具有多峰分布、高维流形等复杂结构的数据中，RSGC的调整兰德指数（ARI）较谱聚类提升12.7%

2. 2.

   真实数据集应用：在UCI标准数据集上，F1-score平均提高9.3%

3. 3.

   scRNA-seq分析：成功识别出稀有的循环肿瘤细胞亚群，证实方法对高维噪声数据的鲁棒性

Conclusion

RSGC通过径向搜索过程实现了相似图的精准分区，其创新性体现在：

1. 1.

   RSA方法生成的子图保持良好单峰结构，为后续合并奠定基础

2. 2.

   跨簇边权重度量有效捕捉子图间潜在关联

3. 3.

   整个框架无需预设簇数，在复杂生物医学数据中展现出独特优势