k- Means-MIND: An Efficient Alternative to Repetitive k-Means Runs

The problem of local minimum in k-means clustering, is commonly addressed by running the algorithm repeatedly in order to choose the best run. Although effective, the approach is computationally expensive. In this paper, we observe that the approach is effectively a comparison among different initializations. Thus, if there is a way to compare these initializations ab initio, there will be no need for repeated clustering. We propose such a technique in this paper. Specifically, we choose the initialization with the largest minimum inter-center distance (MIND), as the `best' one. In other words, our technique is a general approach to improving existing seeding techniques. We demonstrate the concept with MIND-optimized versions of two standard algorithms: k-means and k-means++. Experiments show that in addition to drastic efficiency gain when compared to repetitive k-means, our approach improves the accuracy of the standard versions of these algorithms.