Abstract: K-means algorithm is a clustering algorithm used extensively in application.It is very sensitive to initial cluster center.In this paper，the authors compare some classic initialization algorithm and propose a new method for initializing K-means algorithm based on breadth first search.The new method considers both density estimation and distance to select initial cluster center.Analysis shows the cluster centers selected by this method is very close to the desired cluster centers.

摘要： K-means算法是在现实应用中非常广泛的聚类算法，K-means算法对初始中心的选择非常敏感，对已存在的有代表性的初始算法进行了研究，提出了一种基于广度优先搜索的K-means初始化算法。该算法综合考虑了密度与距离因素，选择初始点。分析表明该算法选择的初始点非常接近期望的中心点。