Fast and Provably Good Seedings for k-Means
Seeding -the task of finding initial cluster centers -is critical in obtaining highquality clusterings for k-Means. However, k-means++ seeding, the state of the art algorithm, does not scale well to massive datasets as it is inherently sequential and requires k full passes through the data. It was recently shown that Markov chain Monte Carlo sampling can be used to efficiently approximate the seeding step of k-means++. However, this result requires assumptions on the data generating distribution. We propose a simple yet fast seeding algorithm that produces provably good clusterings even without assumptions on the data. Our analysis shows that the algorithm allows for a favourable trade-off between solution quality and computational cost, speeding up k-means++ seeding by up to several orders of magnitude. We validate our theoretical results in extensive experiments on a variety of real-world data sets.
The paper proposed a MCMC approach to approximate the D^2-sampling (k-means++) for finding k centers in clustering, by modifying the proposal distribution of an earlier paper by Banchem 16. The algorithm is able to approximately maintain the O(log k) approximation guarantee to the k-means objective for any dataset (as is k-means++), if their analysis is correct. The running time of the algorithm is linear in the number of data size, but shaves off a factor of k (the number of clusters) comparing to that of k-means++.
Technical quality: I have two doubts regarding the proof of their Lemma 2:  1. The authors argue, in the case of \phi_{C}(X) < \epsilon_1\phi_{c_1}, the claim holds trivially. I don't see how this goes through. First, I don't see why A^{c_1}(C,l) < =\phi_{C}(X). As I understand it, A^{c_1}(C,l) is the expected cost of C while \phi_{C}(X) is the actual cost of C (random quantity). If so, why is the former upper bounded by the latter? Second, even if the relation above holds, I don't see how the statement holds, since then we'll get  A^{c_1}(C,l) < =\phi_{C}(X) < \epsilon_1\phi_{c_1}(X). How does this imply the statement using P^{c_1}(C,l) < 1?  2. I don't see how inequality (8) holds, since I can't see why the equation right above it holds, using the definition of \pi.   Novelty: I think the idea of using MCMC methods to approximate D^2-sampling scheme is great. But since this paper is not the first to propose this approach, and the theoretical analysis seems incremental to that of Banchem 16, I think I should take some points off here.  Potential impact or usefulness: I think this paper could potentially have good impact in large-scale clustering applications, given that k-means++ is widely used together with Lloyd's algorithm for clustering. Although the proposed algorithm still has a linear running time dependence on the data size, I think the fact that they can shave off a factor of k while approximately maintaining the performance guarantee of k-means++ could mean a lot in practice. The proposed algorithm also seems simple enough to be implemented in practice, comparing to other scaled versions of k-means++. In general, I think this research direction worths further exploration.  Clarity and presentation: In terms of highlighting their contribution to previous work, the paper does a good job via both writing and experiments. In terms of the analysis, I think the authors should make more efforts in clarifying definitions and providing For example, the definitions of \phi_{C}(X), A^{c^1}(C,l) and P^{c^1}(C,l) are unclear to me, and seem to be inconsistent from one proof to another. Partly because the definition of C at different stages of the algorithm can change. A^{c^1}(C,l) and P^{c^1}(C,l) became more unclear to me when the authors refer the readers to lines 6-11 of the algorithm; for a moment, I thought "l" denotes the length of the markov chain at an iteration. Maybe the authors can remove this reference. Also, I'd be great if the authors can provide more intuition of their analysis, on a high level.