实例簇驱动的图结构聚类参数计算算法

作     者：宗传玉 宪超 夏秀峰 ZONG Chuanyu;XIAN Chao;XIA Xiufeng

作者机构：沈阳航空航天大学计算机学院沈阳110136 

出 版 物：《计算机应用》 (journal of Computer Applications)

年 卷 期：2023年第43卷第2期

页      面：398-406页

学科分类：08[工学] 081203[工学-计算机应用技术] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

基　　金：国家自然科学基金资助项目(61802268)。 

主　　题：图结构聚类 实例簇 参数计算 节点划分 最优参数 

摘      要：pSCAN算法的聚类结果受密度约束参数和相似度阈值参数的影响,如果用户提供的聚类参数得到的聚类结果无法满足需求,那么用户可以通过实例簇表达自己的聚类需求。针对实例簇表达聚类查询需求的问题,提出一种实例簇驱动的图结构聚类参数计算算法PART及其改进算法ImPART。首先,分析两个聚类参数对聚类结果的影响,并提取实例簇的相关子图;其次,对相关子图进行分析得到密度约束参数的可行区间,并根据当前密度约束参数和节点之间的结构相似度将实例簇内节点划分为核心节点和非核心节点;最后,依据节点划分结果计算出当前密度约束参数对应的最优相似度阈值参数,并在相关子图上对得到的参数进行验证和优化,直到得到满足实例簇需求的聚类参数。在真实数据集上的实验结果表明,所提算法能够为用户实例簇返回一组有效参数,且所提改进算法ImPART的运行时间比PART缩短了20%以上,能够快速有效地为用户返回满足实例簇要求的最优聚类参数。