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

Approximate Backbone Guided Reduction Algorithm for Clustering

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

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.