近似骨架导向的归约聚类算法  

Approximate Backbone Guided Reduction Algorithm for Clustering

作　　者：宗瑜[1] 李明楚[1] 江贺[1,2] 

机构地区：[1]大连理工大学软件学院,大连116621 [2]中国科学院软件研究所计算机科学国家重点实验室,北京100190

出　　处：《电子与信息学报》2009年第12期2953-2957,共5页Journal of Electronics & Information Technology

基　　金：国家自然科学基金(60805024);教育部博士点基金(20070141020)资助课题

摘　　要：该文针对聚类问题上缺乏骨架研究成果的现状,分析了聚类问题的近似骨架特征,设计并实现了近似骨架导向的归约聚类算法。该算法的基本思想是:首先利用现有的启发式聚类算法得到同一聚类实例的多个局部最优解,通过对局部最优解求交得到近似骨架,将近似骨架固定得到规模更小的搜索空间,最后在新空间上求解。在26个仿真数据集和3个实际数据集上的实验结果表明,骨架理论对提高聚类质量、降低初始解影响及加快算法收敛速度等方面均十分有效。In this paper, the characteristic of approximate backbone is analyzed and an Approximate Backbone guided Reduction Algorithm for Clustering （ABRAC） is proposed. ABRAC works as follows： firstly, multiple local optimal solutions are obtained by an existing heuristic clustering algorithm; then, the approximate backbone is generated by intersection of local optimal solutions; afterwards, the search space can be dramatically reduced by fixing the approximate backbone; finally, this reduced search space can be efficiently searched to find high quality solutions. Extensively wide experiments on 26 synthetic and 3 real-life data sets demonstrate that the backbone has significantly effects for improving the quality of clustering, reducing the impact of initial solution, and speeding up the convergence rate.

关 键 词：聚类问题 NP-难解 启发式算法 近似骨架 

分 类 号：TP181[自动化与计算机技术—控制理论与控制工程]