最大上升角图

该图通过最大化上升角自动连接点，以在簇内形成稠密边、簇间形成稀疏边，从而合理平衡簇间连接性与簇内非连接性。

Guan, Junyi · 李胜 · 何熊熊 · 陈佳佳 · Zhao, Yangyang · Zhang, Yuxuan

IEEE Transactions on Knowledge and Data Engineering 2024

技术优势

自动平衡簇内外连接

通过连接每个点的最近高密度邻居和最大上升角邻居，Y-graph 不依赖任何形状假设即可在簇内形成稠密连接、在簇间形成稀疏连接。

快速找到簇边界

得益于 Y-graph 的高稀疏性和合理的边权重，Ncut-Y 算法能快速定位并切断低密度边界，无需扫描整个图。

适用于任意形状和维度

Y-graph 的连接规则只依赖点的密度和角度，不依赖数据的几何形状或特征空间维度，因此对复杂形状和高维数据同样有效。

应用场景

• 聚类分析：用 Y-graph 替换传统 kNN 或 ε-邻域图，提高聚类质量。
• 复杂数据聚类：可直接处理任意形状和高维数据，无需预先设定簇形状。
• 数据挖掘：为下游挖掘任务提供更准确的簇结构，减少噪声边干扰。
• 无监督分割：利用图割自动确定分割边界，无需标签或人工设定阈值。