HC_AB: A new heuristic clustering algorithm based on Approximate Backbone

Yu ZONG, Guandong XU, Ping JIN, Yanchun ZHANG, Enhong CHEN

Research output: Contribution to journalArticlespeer-review

6 Citations (Scopus)


Clustering is an important research area with numerous applications in pattern recognition, machine learning, and data mining. Since the clustering problem on numeric data sets can be formulated as a typical combinatorial optimization problem, many researches have addressed the design of heuristic algorithms for finding sub-optimal solutions in a reasonable period of time. However, most of the heuristic clustering algorithms suffer from the problem of being sensitive to the initialization and do not guarantee the high quality results. Recently, Approximate Backbone (AB), i.e., the commonly shared intersection of several sub-optimal solutions, has been proposed to address the sensitivity problem of initialization. In this paper, we aim to introduce the AB into heuristic clustering to overcome the initialization sensitivity of conventional heuristic clustering algorithms. The main advantage of the proposed method is the capability of restricting the initial search space around the optimal result by defining the AB, and in turn, reducing the impact of initialization on clustering, eventually improving the performance of heuristic clustering. Experiments on synthetic and real world data sets are performed to validate the effectiveness of the proposed approach in comparison to three conventional heuristic clustering algorithms and three other algorithms with improvement on initialization. Copyright © 2011 Elsevier B.V. All rights reserved.

Original languageEnglish
Pages (from-to)857-863
JournalInformation Processing Letters
Issue number17
Early online dateJun 2011
Publication statusPublished - Sept 2011


Zong, Y., Xu, G., Jin, P., Zhang, Y., & Chen, E. (2011). HC_AB: A new heuristic clustering algorithm based on Approximate Backbone, Information Processing Letters, 111(17), 857-863. https://doi.org/10.1016/j.ipl.2011.05.020


Dive into the research topics of 'HC_AB: A new heuristic clustering algorithm based on Approximate Backbone'. Together they form a unique fingerprint.