带信息反馈的凝聚层次聚类算法  

Hierarchical agglomerative clustering with information feedback

作　　者：李春忠[1,2] 徐宗本[1,2] 乔琛[1,2] 

机构地区：[1]西安交通大学信息与系统科学研究所,西安710049 [2]西安交通大学智能网络与网络安全教育部重点实验室,西安710049

出　　处：《中国科学：信息科学》2012年第6期730-742,共13页Scientia Sinica(Informationis)

基　　金：国家重点基础研究计划(批准号:2007CB311002);国家自然科学基金(批准号:60975036)资助项目

摘　　要：本文针对传统的基于相似性的层次聚类算法存在的两个问题(相似性度量中方向信息的丢失和算法的适应能力弱)提出了一种带有信息反馈的凝聚层次聚类算法.首先将无法预知的复杂数据结构描述成3个基本的结构特征单元,并对其进行建模构建一种相似性度量定义的泛型和一种凝聚的层次聚类算法.在凝聚的层次聚类算法中加入类信息的反馈机制,并在不同阶段对相似性定义的泛型进行具体化,充分利用数据点对之间的方向信息和距离信息进行聚类.该聚类算法主要有两大优势:(i)算法的适应能力较强,不需要假设的前提下可以处理无法预知的复杂数据结构;(ii)算法对噪声具有较强的鲁棒性,在不需要对数据集进行预处理的情况下能够在聚类的过程中识别噪声点或者噪声类.从人工数据和真实数据的试验结果可以看出新算法的优越性能.The paper proposes an hierarchical agglomerative clustering with information feedback, aiming to solve the problems （the absence of direction information in similarity measurement and relatively poor adaptability） in traditional hierarchical clustering algorithms based on similarity. In the algorithm, the unpredictable complicated data structure is described with three basic structural feature units, and then it is modeled to construct a general framework of similarity measurement and agglomerative hierarchical clustering algorithm. The algorithm adds information feedback into the agglomerative hierarchical clustering, and specifies similarity measurement according to different stages, so as to make full use of the direction and distance information between pairs of points in clustering. The advantages of the algorithm are as follows： （i） the powerful adaptability allows the algorithm to process complicated data sets without any priors or assumption; （ii） the powerful robustness to noises permits the algorithm to recognize noises without any pretreatment of the data set. The superiority of the algorithm is proved by the application on synthetic and real data sets.

关 键 词：层次聚类 信息反馈 流形 结构近邻 自顶向下 方向一致相似性 

分 类 号：TP311.13[自动化与计算机技术—计算机软件与理论]