Abstract: K-means is one of classical heuristic clustering algorithm，which is sensitive to initialization and may not produce ideal optimal results.In recent years，the backbone（the shared common parts of all optimal solutions） has attracted many interests in heuristic algorithm design，due to its impact on improving the performance of heuristic algorithms.In this paper，a backbone initialization K-means（BK-means） algorithm is proposed.The main idea is to find out the backbone cluster which is the intersection of several local suboptimal solutions obtained by run K-means algorithm several times，then generate a backbone initialization and new search space.Finally，K-means is run again on the new search space with the backbone initialization.Experiments on 15 synthesis and 4 real datasets show that BK-means has significant effects for improving the quality of clustering.

Key words: clustering, K-means algorithm, heuristic algorithm, backbone initialization

摘要： K-means是典型的启发式聚类算法，容易受到初始解的影响而无法获得高质量的聚类结果。骨架是近年来启发式算法设计的研究热点，它是指所有全局最优解中相同的部分，对于提高启发式算法性能具有重要意义。给出的骨架初始解K-means算法（BK-means）的基本思想是：首先利用K-means算法得到一组局部最优解（聚类结果），通过对局部最优解求交得到骨架簇。利用骨架簇构造骨架初始解及新的搜索空间。最后以骨架初始解引导K-means算法在新的搜索空间中搜索聚类结果。在15组仿真数据集和4组实际数据集上的实验结果表明，BK-means算法具有获得高内聚、高分离的聚类结果能力。

关键词: 聚类, K-means算法, 启发式算法, 骨架初始解