Local Search Algorithm for K-Means Clustering Based on Minimum Sub-Cluster Size
Shouqiang Wang, Xiaomei Wang · 2009
i cC dp c ∈ 。 Abstract: This paper presented a randomized local search algorithm for one of the k-means clustering subproblems which requests that each cluster must has at least some points. It is proved that An expected 2-approximation randomized algorithm could be obtained if k centers come from different optimal subsets. A sample set that includes at least one point of each optimal sub-cluster is given in this paper. By means of sample technique, an improved local search algorithm was also proposed in this paper. The new algorithm running time is O(nk 3 dlog(n)log(k)/α), which has better performance than the initial algorithm both in the running time and solution.