Approximate Backbone Guided Reduction Algorithm for Clustering

Zong Yu; Li Ming-chu; Jiang He

doi:10.3724/SP.J.1146.2008.01663

Volume 31 Issue 12

Dec. 2010

Turn off MathJax

Article Contents

Article Navigation > Journal of Electronics & Information Technology > 2009 > 31(12): 2953-2957

Zong Yu, Li Ming-chu, Jiang He. Approximate Backbone Guided Reduction Algorithm for Clustering[J]. Journal of Electronics & Information Technology, 2009, 31(12): 2953-2957. doi: 10.3724/SP.J.1146.2008.01663

Citation:

Zong Yu, Li Ming-chu, Jiang He. Approximate Backbone Guided Reduction Algorithm for Clustering[J]. Journal of Electronics & Information Technology, 2009, 31(12): 2953-2957. doi: 10.3724/SP.J.1146.2008.01663

Citation:

PDF( 233 KB)

Approximate Backbone Guided Reduction Algorithm for Clustering

doi: 10.3724/SP.J.1146.2008.01663

Received Date: 2008-12-08
Rev Recd Date: 2009-06-29
Publish Date: 2009-12-19

Abstract

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.

FullText(HTML)

References(1)

References

孙吉贵, 刘杰, 赵连宇. 聚类算法研究. 软件学报, 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.

Relative Articles

Supplements(0)

Cited By

Proportional views