Approximate Backbone Guided Reduction Algorithm for Clustering
Zong Yu①; Li Ming-chu①; Jiang He①②
①School of Software, Dalian University of Technology, Dalian 116621, China; ②The State Key Laboratory of Computer Science, Institute of Software, CAS, Beijing 100190, China
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.
2009, Vol. 31 
