Algorithm for the k-means clustering based on minimum cluster size
Daming Zhu · Journal of Communications · 2010
For the k-means clustering subproblem that the size of each cluster must meet at least some given value,three randomized approximate algorithms were presented.The first algorithm was an expected 2-approximation randomized algorithm.Before given the algorithm,a subset that includes at least one point of each optimal cluster was first drawn at random.The second randomized algorithm was the (1+e) approximation algorithm.The probability of getting the successful result was proved to be at least 3/2k+2.At last,by means of sampling technique,a local search randomized algorithm was also proposed.