K-means-Lite++: The combined advantage of sampling and seeding

The k-means-lite algorithm was recently introduced to address the poor scalability of the popular k-means algorithm. This paper modifies k-means-lite by applying D2 sampling, the state-of-the-art seeding technique employed by k-means++, to each sample in the former. K-means-lite estimates its final centroids by applying standard k-means to the combination of all centroids obtained from initial application of k-means to a few (say, five) samples. Although k-means-lite achieves drastic efficiency gain, the five-sample implementation trades off some of the standard algorithm's accuracy. One way to improve its accuracy is to increase the number of samples. But it may be difficult to determine a priori what performance level is attainable, or the number of samples required to attain such performance. These would vary per problem. In this paper, we show experimentally that without increasing the sample size or number of samples in k-means-lite, our modified algorithm, named k-means-lite++, addresses this problem and is even more accurate than the standard k-means. For the cases tested, k-means-lite++ matches the accuracy of k-means++, which is widely considered the state-of-the-art k-means algorithm. The extra cost of sample seeding is compensated for by faster convergence. So, although drastically more accurate, k-means-lite++ has efficiency that is comparable to k-means-lite's. Thus, the proposed algorithm may also be viewed as a solution to scalability issues associated with k-means++'s sequential sampling.