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

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