Fast Distributed k-Center Clustering with Outliers on Massive Data

Gustavo Malkomes, Matt J. Kusner, Wenlin Chen, Kilian Q. Weinberger, Benjamin MoseleyNeurIPS 2015 · OpenReview

TL;DR

This paper introduces two highly efficient, two-round MapReduce algorithms for $k$-center clustering: one for standard datasets and a novel variant for datasets containing outliers. Both algorithms provide constant-factor approximation guarantees and achieve massive speedups—up to 677x—while maintaining clustering quality nearly identical to their sequential counterparts.

The Challenge of Scale and Noise in Clustering

Clustering is a cornerstone of machine learning, used for everything from document grouping to targeted advertising. The $k$-center problem specifically aims to find $k$ points (centers) such that the maximum distance from any data point to its nearest center is minimized.

However, modern practitioners face two major hurdles:

  1. Scale: As datasets grow to millions or billions of points, sequential algorithms become too slow and exceed the memory limits of a single machine.
  2. Noise: Standard $k$-center clustering is extremely sensitive to outliers. A single noisy point far from the rest of the data can "pull" a center away from a dense cluster, ruining the result.

While distributed frameworks like MapReduce are the standard for "Big Data," existing distributed $k$-center algorithms often lack theoretical guarantees or perform poorly when data is missing due to sampling. This paper fills that gap by providing distributed algorithms that are both theoretically sound and practically fast.

A Two-Round MapReduce Approach

The authors propose two primary algorithms designed for the MapReduce framework, which operates in discrete "rounds" of parallel computation and data shuffling.

GREEDY-MR (For Standard $k$-Center)

  • Round 1: Data is partitioned across $m$ machines. Each machine independently runs a sequential greedy algorithm to find $k$ local centers.
  • Round 2: All local centers (totaling $m \times k$ points) are sent to a single machine, which runs the greedy algorithm again to select the final $k$ global centers.
  • The Innovation: The authors prove this simple approach is a 4-approximation algorithm, providing a theoretical explanation for why this intuitive method works so well in practice.

OUTLIERS-MR (For $k$-Center with Outliers)

Handling outliers is significantly harder because the algorithm must decide which $z$ points to ignore while simultaneously picking centers. This is the paper's most significant contribution.

  • Round 1: Each machine finds $k+z$ local centers. Crucially, it also calculates a weight for each center, representing how many original data points that center "covers."
  • Round 2: These weighted "proxy" points are sent to a central machine. The authors developed a new CLUSTER subroutine that uses these weights to distinguish between dense clusters and sparse outliers.
  • The Innovation: They prove this achieves an O(1)-approximation (specifically a 13-approximation), marking the first such result for distributed $k$-center with outliers.

Key Insights

  • Weighted Proxies are Powerful: Instead of sending all data to one machine (which is impossible) or relying on random samples (which is inaccurate), sending a small set of weighted centers acts as a highly effective "summary" of the data distribution.
  • The "Guessing" Strategy: The outlier algorithm relies on a parameter $G$, which is a "guess" of the optimal radius. By performing a parallel binary search for $G$, the algorithm can find the optimal clustering threshold efficiently.

Key Results

The authors evaluated their methods on seven diverse real-world datasets, ranging from small biomedical datasets to an 11-million-point physics dataset (Higgs).

Empirical comparison of distributed algorithms against sequential and random baselines.
  • Quality Preservation: As shown in the results above, the distributed versions (GREEDY-MR and OUTLIERS-MR) produced objective values nearly identical to the sequential versions across varying numbers of clusters, outliers, and machines. They also significantly outperformed "naive" distributed baselines like random sampling.
  • Massive Speedups: On the Census dataset, the distributed outlier algorithm was 677x faster than the sequential version. This is largely because the distributed version avoids the need to compute a massive, memory-intensive distance matrix.
  • Extreme Scalability: The OUTLIERS-MR algorithm successfully clustered the 11-million-point Higgs dataset in less than 15 minutes, a task that would be computationally prohibitive for standard sequential approaches.

Limitations and Future Work

While the theoretical bound for the outlier algorithm is a 13-approximation—a breakthrough for distributed outlier clustering—it is theoretically "looser" than the sequential 3-approximation. Future work could aim to tighten this bound.

Additionally, the algorithm requires the number of outliers $z$ to be specified upfront. In some real-world scenarios, $z$ might be unknown, requiring further heuristics to estimate. However, the authors suggest that the "weighted proxy" approach used here could potentially be adapted for other clustering objectives, such as $k$-median or $k$-means with outliers, opening exciting new avenues for distributed machine learning.

Summary updated

Abstract

Clustering large data is a fundamental problem with a vast number of applications. Due to the increasing size of data, practitioners interested in clustering have turned to distributed computation methods. In this work, we consider the widely used k-center clustering problem and its variant used to handle noisy data, k-center with outliers. In the noise-free setting we demonstrate how a previously-proposed distributed method is actually an O(1)-approximation algorithm, which accurately explains its strong empirical performance. Additionally, in the noisy setting, we develop a novel distributed algorithm that is also an O(1)-approximation. These algorithms are highly parallel and lend themselves to virtually any distributed computing framework. We compare both empirically against the best known noisy sequential clustering methods and show that both distributed algorithms are consistently close to their sequential versions. The algorithms are all one can hope for in distributed settings: they are fast, memory efficient and they match their sequential counterparts.
BibTeX
@inproceedings{malkomes2015fast,
  author = {Gustavo Malkomes and Matt J. Kusner and Wenlin Chen and Kilian Q. Weinberger and Benjamin Moseley},
  title = {{Fast Distributed k-Center Clustering with Outliers on Massive Data}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2015},
  url = {https://openreview.net/forum?id=S1b9gDWdZS},
}
Figure