A Practical Algorithm for Distributed Clustering and Outlier Detection
A Practical Algorithm for Distributed Clustering and Outlier Detection
复制标题
DOI：
--
复制
发表时间：
2018-05
期刊：
影响因子：
--
通讯作者：
Jiecao Chen;Erfan Sadeqi Azer;Qin Zhang
中科院分区：
文献类型：
--
作者：
Jiecao Chen;Erfan Sadeqi Azer;Qin Zhang
我们研究了经典的$ k $ - $ -MEAN/中位数聚类，它们是无监督学习的基本问题，在各个站点分配数据的环境中，我们可以通过将它们标记为异常值来丢弃一小部分数据。我们提出了一种基于原始数据集构造小摘要的简单方法。提出的方法是时间和沟通效率，具有良好的近似保证，并且可以有效地识别全球异常值。据我们所知，这是第一种实用算法，具有与异常值分布式聚类的理论保证。我们对真实数据和合成数据的实验证明了我们算法与几乎所有指标中所有基线算法的明显优势。
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.