An Approximate Algorithm for k-Means Problem Based on Input Points

The k-means clustering is one of the most popular schemes for discovering clusters in data. Its aim is to minimize the mean squared distance from each data to its nearest center. A lot of variants of Lloyd´s heuristic have been studied. Unfortunately, many research results haven´t given any approximate ratio. In this paper, an algorithm is presented which can obtain the optimal clustering with the ration of at most 2. The main idea of this algorithm is that k points are selected by means of a very simple, randomized seeding technique and then the local search is implemented to improve the accuracy. Some examples are selected to verify our algorithm and got better results both the speed and accuracy than the former methods. The main algorithmic contribution is that the input points are used as the candidate sets to obtain the optimal clustering with a constant ratio by means of local search technique and one method of selecting initial points.