基于自然邻域图划分的层次聚类算法  

A hierarchical clustering algorithm based on partitioning natural neighborhood graph

作　　者：蔡发鹏 冯骥 杨德刚[1] 陈仲尚 CAI Fapeng;FENG Ji;YANG Degang;CHEN Zhongshang(College of Computer and Information Science,Chongqing Normal University,Chongqing 401331,China)

机构地区：[1]重庆师范大学计算机与信息科学学院,重庆401331

出　　处：《计算机工程与科学》2025年第2期370-380,共11页Computer Engineering & Science

基　　金：重庆市教委科学技术研究计划(KJZD-M202300502,KJQN201800539)。

摘　　要：自然邻域图能自适应地识别不同形状、大小和维度的数据,但在面对密度不均匀且结构复杂的数据时,部分小簇无法被算法正确识别。针对这一问题,提出一种基于自然邻域图划分的层次聚类算法HC-PNNG。HC-PNNG算法首先利用自然邻居关系实现了自然稀疏图的构建,随后利用基于自然稀疏图的图间相似度完成了自然稀疏图的层次化合并,进而实现了更具普适性的层次化聚类结果。在合成数据集和真实数据集上将HC-PNNG与最新的聚类算法进行了对比实验,结果表明该算法明显优于其他聚类算法,验证了HC-PNNG算法的有效性。Natural neighborhood graph can adaptively identify data with different shapes,sizes and dimensions.However,some small clusters cnnot be correctly identified by the algorithm when dealing with data of uneven density and complex structure.To address this issue,a hierarchical clustering algorithm based on natural neighborhood graph partitioning(HC-PNNG)is proposed.The algorithm first constructs a natural sparse graph using the natural neighbor relationship.Subsequently,it completes the hierarchical merging of natural sparse graphs based on the similarity between graphs,thereby achieving more universally applicable hierarchical clustering results.Comparative experiments were conducted on synthetic and real datasets,comparing the proposed algorithm with the latest clustering algorithms.The results demonstrate that the proposed algorithm significantly outperforms other clustering algorithms,verifying its effectiveness.

关 键 词：聚类分析 层次聚类 自然邻域图 图划分 相似度 

分 类 号：TP391[自动化与计算机技术—计算机应用技术]