Solving k-center Clustering (with Outliers) in MapReduce and Streaming, almost as Accurately as Sequentially
Solving k-center Clustering (with Outliers) in MapReduce and Streaming, almost as Accurately as Sequentially
复制标题
DOI：
10.14778/3317315.3317319
复制
发表时间：
2019-03-01
影响因子：
2.5
通讯作者：
Pucci, Geppino
中科院分区：
文献类型：
--
作者：
Ceccarello, Matteo;Pietracaprina, Andrea;Pucci, Geppino
基于中心的聚类是数据分析的基本原语，对于大型数据集来说变得非常具有挑战性。在本文中，我们关注流行的 k 中心变体，给定来自某个度量空间的一组点 S 和参数 k < 垂直条 S 垂直条，需要识别 S 中 k 中心的子集，从而最小化 S 中任何点与其最近中心的最大距离。为处理噪声数据集而引入的更通用的公式具有另一个参数 z，并允许在计算距中心的最大距离时忽略 S 的最多 z 个点（异常值）。我们针对上述问题的两种表述提出了基于核心集的 2 轮 MapReduce 算法，并针对具有异常值的情况提出了 1 遍 Streaming 算法。对于任何固定的 epsilon > 0，该算法产生的解的近似比仅是与最知名的多项式时间顺序算法可实现的解相比的加法项 epsilon，这一结果大大改进了现有技术。我们的算法相当简单，并且适应数据集的内在复杂性，由度量空间的加倍维度 D 捕获。具体来说，我们的分析表明，对于小（常数）D 的重要情况，这些算法变得非常节省空间。这些理论结果辅以一组对超过十亿点的现实世界和合成数据集的实验，这表明我们的算法在具有出色的可扩展性的同时，可以比现有技术产生更好质量的解决方案，并且它们还可以比现有算法更快地进行顺序实现。
Center-based clustering is a fundamental primitive for data analysis and becomes very challenging for large datasets. In this paper, we focus on the popular k-center variant which, given a set S of points from some metric space and a parameter k < vertical bar S vertical bar, requires to identify a subset of k centers in S minimizing the maximum distance of any point of S from its closest center. A more general formulation, introduced to deal with noisy datasets, features a further parameter z and allows up to z points of S (outliers) to be disregarded when computing the maximum distance from the centers. We present coreset-based 2-round MapReduce algorithms for the above two formulations of the problem, and a 1-pass Streaming algorithm for the case with outliers. For any fixed epsilon > 0, the algorithms yield solutions whose approximation ratios are a mere additive term epsilon away from those achievable by the best known polynomial-time sequential algorithms, a result that substantially improves upon the state of the art. Our algorithms are rather simple and adapt to the intrinsic complexity of the dataset, captured by the doubling dimension D of the metric space. Specifically, our analysis shows that the algorithms become very space-efficient for the important case of small (constant) D. These theoretical results are complemented with a set of experiments on real-world and synthetic datasets of up to over a billion points, which show that our algorithms yield better quality solutions over the state of the art while featuring excellent scalability, and that they also lend themselves to sequential implementations much faster than existing ones.