融合转移概率矩阵的多阶最近邻图聚类算法

作者：徐童童; 解滨^*; 张春昊; 张喜梅

来源：计算机应用, 2023, 1-16.

• 共享近邻
• 趋密性
• 转移概率
• 多阶最近邻
• 分层聚类

聚类根据样本之间的相似性，将数据集划分为多个类簇。现有的大多数聚类方法都存在两个挑战：一方面，在定义样本间相似性时往往没有考虑到样本的空间分布结构，无法构建稳定的相似度矩阵；另一方面，图聚类构造的样本图结构过于复杂，计算成本较高。为解决这两个问题，提出融合转移概率矩阵的多阶最近邻图聚类算法(MNNGC)。首先，该算法综合样本的近邻关系和空间分布结构，将共享近邻定义的相似度进行趋密性加权，得到节点间的趋密性亲和矩阵。其次，利用节点间多阶概率转移，预测非邻接点的关联程度，并通过融合多阶转移概率矩阵得到稳定的节点间亲和矩阵。接着，为进一步增强图局部结构，重新构建节点的多阶最近邻图，并对多阶最近邻图的局部结构分层聚类，最后优化了边缘点分配策略。定位实验结果表明，MNNGC算法在合成数据集上的准确率（Acc）均优于其他对比算法，且在8个UCI数据集上的Acc为最大值。其中在Compound数据集上，MNNGC算法的Acc、调整互信息(AMI)、调整兰德指数(ARI)和FM指数(FMI)相较于基于局部密度峰和图割思想的聚类算法(LDP-SC)分别提高38.6%,27.2%,45.4%和35.1%。可见MNNGC算法能够有效提升聚类性能。

• 单位
  河北师范大学