|
|
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.
|
Received: 08 December 2008
|
|
Corresponding Authors:
Jiang He
|
|
|
|
|
|
|