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

宗瑜; 李明楚; 江贺

doi:10.3724/SP.J.1146.2008.01663

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

doi: 10.3724/SP.J.1146.2008.01663

基金项目:

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

计量
- 文章访问数: 3102
- HTML全文浏览量: 78
- PDF下载量: 898
- 被引次数: 0
出版历程
- 收稿日期: 2008-12-08
- 修回日期: 2009-06-29
- 刊出日期: 2009-12-19

Approximate Backbone Guided Reduction Algorithm for Clustering

摘要

摘要: 该文针对聚类问题上缺乏骨架研究成果的现状，分析了聚类问题的近似骨架特征，设计并实现了近似骨架导向的归约聚类算法。该算法的基本思想是：首先利用现有的启发式聚类算法得到同一聚类实例的多个局部最优解，通过对局部最优解求交得到近似骨架，将近似骨架固定得到规模更小的搜索空间，最后在新空间上求解。在26个仿真数据集和3个实际数据集上的实验结果表明，骨架理论对提高聚类质量、降低初始解影响及加快算法收敛速度等方面均十分有效。
- 聚类问题; NP-难解; 启发式算法; 近似骨架
Abstract: 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.

HTML全文

参考文献(1)

孙吉贵, 刘杰, 赵连宇. 聚类算法研究. 软件学报, 2008, 19(1):48-61.Sun J G, Liu J, and Zhao L Y. Clustering algorithms research.Journal of Software, 2008, 19(1): 48-61.[2]Drinesa P, Frieze A, and Kannan R, et al.. Clustering largegraphs via the singular value decomposition [J]. MachineLearning, 2004, 56(1-3): 9-33.[3]Jain A K and Dubes R C. Algorithms for Clustering Data [M].Prentice Hall, Englewood Cliffs, New Jersey, 1998: 10-89.[4]David A and Sergei V. k-means++: the advantages of carefulseeding[C]. SODA 2007, New Orleans France, 2007:1027-1035.[5]Amir A and Lipoka D. A K-mean clustering algorithm formixed numeric and categorical data [J]. Data and KnowledgeEngineering, 2007, 63(2): 503-527.[6]江贺, 张宪超, 陈国良. 图的二分问题唯一全局最优解实例与骨架计算复杂性[J]. 科学通报, 2007, 52(17): 2077-2081.Jiang H, Zhang X C, and Chen G L. Exclusive optimalsolution instance and backbone computation complexity ofgraph bi-partition problem. Chinese Science Bulletin, 2007,52(17): 2077-2081.[7]江贺, 张宪超, 陈国良, 李明楚. 二次分配问题的骨架分析与算法设计[J]. 中国科学E 辑, 2008, 38(2): 209-222 .Jiang H, Zhang X C, Chen G L, and Li M C. Backboneanalysis and algorithm design for the quadratic assignmentproblem. Science in China Series E: Information Sciences,2008, 28(2): 209-222.[8]Valnir F J. Backbone guided dynamic local search forpropositional satisfiability[C]. Proceeding of 9thInternational Symposium on Artificial Intelligence andMathematics (AI Math-06). Florida America, 2006:100-108.[9]Zhang W X. Configuration landscape analysis and backboneguided local search: Part I: Satisifiability and maximumsatisfiability [J].Artificial Intelligence.2004, 158(1):1-26[10]He J, Tan A H, and Tan C L, et al.. On quantitativeevaluation of clustering systems[C]. Information Retrievaland Clustering. Kluwer Academic Publishers, ISBN1-4020-7682-7, 2003.[11]He J, Lan M, and Tan C L, et al.. Initialization of clusterrefinement algorithms: a review and comparative study[C].Proceedings of International Joint Conference on NeuralNetworks (IJCNN). Budapest Hungary, 2004: 297-302.

施引文献

资源附件(0)

访问统计