K-Medoids for K-Means Seeding
We show experimentally that the algorithm clarans of Ng and Han (1994) finds better K-medoids solutions than the Voronoi iteration algorithm of Hastie et al. (2001). This finding, along with the similarity between the Voronoi iteration algorithm and Lloyd's K-means algorithm, motivates us to use clarans as a K-means initializer. We show that clarans outperforms other algorithms on 23/23 datasets with a mean decrease over k-means-++ (Arthur and Vassilvitskii, 2007) of 30% for initialization mean squared error (MSE) and 3% for final MSE. We introduce algorithmic improvements to clarans which improve its complexity and runtime, making it a viable initialization scheme for large datasets.
The authors propose to use a particular version of the K-medoids algorithm (clarans - that uses iterative swaps to identify the medoids) for initializing k-means and claim that this improves the final clustering quality. The authors have also tested their claims with multiple datasets, and demonstrated their performance improvements. They have also published code that will be made open after the review process.
Comments:
1. The paper is easy to read and follow, and the authors have done a good job placing their work in context. I appreciate the fact that the optimizations are presented in a very accessible manner in Section 4. As the authors claim, open source code is an important contribution.
2. The authors should consider the following work for inclusion in their discussions and/or comparisons:
Bahmani, Bahman, et al. "Scalable k-means++." Proceedings of the VLDB Endowment 5.7 (2012): 622-633.
3. While the authors have compared actual run times of different algorithms in Section 5, can they also provide some idea of the theoretical complexity (whenever possible)?
4. Related to previous comment: how much impact would the actual implementation have on the runtimes, particularly given that the “bf” algorithm uses BLAS routines and hence can be implicitly parallelizing matrix operations. Is there any other place in the implementations where parallel processing is done?
5. Please number the data sets in Table 3 to make it easy to compare with table 4.
6. In column 1(km++) of Table 4, why is it that km++ does not run unto 90 iterations always given that TL was based on this time?
7.  In 5.2, the claim that “clarans often finds a globally minimal initialization” seems a bit too speculative. If the authors want to claim this they must run many many rounds at least in a few datasets, and show that the performance cannot get better by much.