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.