Stable Initialization Scheme for K-Means Clustering

Though K-means is very popular for general clustering, its performance, which generally converges to numerous local minima, depends highly on initial cluster centers. In this paper a novel initialization scheme to select initial cluster centers for K-means clustering is proposed. This algorithm is based on reverse nearest neighbor (RNN) search which retrieves all points in a given data set whose nearest neighbor is a given query point. The initial cluster centers computed using this methodology are found to be very close to the desired cluster centers for iterative cluster-ing algorithms. This procedure is applicable to clustering algo-rithms for continuous data. The application of the proposed algo-rithm to K-means clustering algorithm is demonstrated. An ex-periment is carried out on several popular datasets and the results show the advantages of the proposed method.