Abstract: Due to the inherent initial clustering center sensitivity of K-means algorithm,it exists problems including result instability and being easy to fall into local optimum．The current improvement schemes can reduce the number of iteration and obtain an approximate global optimal solution when deal with noise-free data sets．But for noisy data sets,it would be easy to fall into local optimum,and the clustering result is lower than traditional K-means algorithm．Based on the algorithm that can find initial clustering centers according to the farthest spatial distance,the paper proposed a novel algorithm to select initial centers based on spatial distance difference．The main idea of the algorithm is calculating the sum distances between non-clustering center and all selected centers,then sort them．Choose the point which is the closer to the given centers as the new selected cluster center．Experimental results show that under the quite condition of iteration,when deal with noise-free data sets,the clustering accuracy of the proposed algorithm is improved about 1%．For noisy data sets,the classified accuracy is above 90%.

Key words: K-means algorithm,Initial centroid,Spatial distance difference,Noisy data