A Practical Algorithm for Distributed Clustering and Outlier Detection *
We study the classic k-means/median clustering, which are fundamental problems in unsupervised learning, in the setting where data are partitioned across multiple sites, and where we are allowed to discard a small portion of the data by labeling them as outliers. We propose a simple approach based on constructing small summary for the original dataset. The proposed method is time and communication efficient, has good approximation guarantees, and can identify the global outliers effectively. To the best of our knowledge, this is the first practical algorithm with theoretical guarantees for distributed clustering with outliers. Our experiments on both real and synthetic data have demonstrated the clear superiority of our algorithm against all the baseline algorithms in almost all metrics.
The paper considers the problem of computing a weighted summary for the k-means problem with outliers, in order to use this summary in a distributed setting.  The algorithm is a variation of an approximation algorithm by Mettu and Plaxton (without outliers). The idea is: Iteratively, sample points, assign every point to its closest sample point, and then cut out a ball with the closest points around every sample point. The points that are "cut out" are then represented by their closest sample point and deleted. This is repeated until there are only very few points left. The adaptation considered in the paper for the outlier case is that the algorithm is stopped earlier, namely, when there are only 8*t points left (t being the number of outliers). These are then represented by themselves. The final coreset size is O(k log n + t), where the log n-term stems from the fact that in every round, log n points are sampled, and the t is from the last 8t points which are added to the summary. The algorithm is slightly improved for the case that t is much larger than k, which seems like a reasonable assumption.  The paper experimentally compares the resulting algorithm to using k-means++ to construct a summary (k-means++ sampling, used to find O(k+t) samples, can also be used to get a O(1)-summary for k-means with outliers), and to kmeans||, again a k-means algorithm run with k'=O(k+t). The summaries are then clustered by using k-means-- to obtain a final solution (for all three approaches).   Question: What does the sentence "ball-grow outperforms k-means++ and k-means|| in almost all metrics" mean? I do not find the entry where it does not outperform the others.  My evaluation of this paper is two-fold. While in my opinion there are a couple of issues with the theoretical presentation of this work, the experiments look very good. I particularly like the evaluation with respect to actual outlier recognition. Still, for me there is a question mark on how this compares to adaptations of better k-means streaming algorithms (see below). Thus, I pick my initial vote to be weak accept.  (+) The experimental results look great. The loss is smaller, but in particular, the outlier detection works much better. I like how the data set was constructed; this makes sense and gives a reasonable test case. I assume that "rand" was included to prove that there is need for a better method; rand is a really bad method for this and does indeed perform badly. But also k-means++ performs surprisingly bad.  (-) The related work section does not cover works on coresets for k-means and streaming k-means algorithms, which would set this paper's contribution into perspective. (see below). (-) Comparison with coreset-based algorithms: A coreset for k-means is a weighted summary which approximates the cost of any possible solution within a factor of epsilon. It can thus be used to compute a PTAS (for constant k or d), and also to compute O(1)-approximations. For k-means it is possible to construct a coreset of size O(k*d*eps^(-4)), see [1], the size for k-median is even lower. And coresets have one additional benefit: Since the error can be made arbitrarily small, it is possible to embedd them into a merge-and-reduce framework, which transforms them into streaming algorithms. These are then very fast and do not need random access any more!  The construction in this paper, however, needs random access. While uniform sampling is easy and requires no extra computation (compared to, e.g., the sampling in k-means++, which needs a lot of precomputation), it needs time and in particular random access to cut out the balls around all sampled points. And, since the guarantee here is only O(1), merge and reduce will not compute a very good summary.  (-) Comparison to streaming k-means algorithms: There are two types of these algorithms. First, there are coreset-inspired streaming algorithms. These are not mentioned in the paper at all. Second, there are streaming algorithms that are inspired by online facility location algorithms. Most relevant here is probably [2]. These methods are typically faster and need a size around O(k log n), but only provide a O(1) guarantee, like this paper. So for me, a natural question would be whether those methods could be extended to outliers. Again, the advantage of that would be that there is no need for random access. (-) It would be nice to have some justification for the choice of k-means--, which, as far as I can see, has no guarantee at all. Since there is the paper [3] which apparently implemented a constant factor approximation for k-means with outliers, one wonders if that would give more stable / informative information. I gather that k-means-- is probably a fair bit faster, yet it is unclear to me how high the variance of this algorithm is. For standard k-means, classical Lloyd is much more unreliable than k-means++, and I believe that k-means-- is simply a Lloyd variant for k-means with outliers?  [1] Feldman, Langberg: A Unified Framework for Approximating and Clustering Data, STOC 2011, https://arxiv.org/abs/1106.1379  [2] Shindler, Wong, Meyerson: Fast and Accurate k-means For Large Datasets, NIPS 2011, www-bcf.usc.edu/~shindler/papers/FastKMeans_nips11.pdf.  [3] Gupta, Kumar, Lu, Moseley, Vassilvitskii: Local Search Methods for k-Means with Outliers, PVLDB 2017.  Edit after author feedback: The response is convincing to me. I still think that comparing to (non-outlier) work on coresets and streaming sets this paper into perspective, but I understand the points that are risen in the feedback. I thus increase my score to 7.