In this paper, we study the problem of {\em $k$-center clustering with outliers}. The problem has many important applications in real world, but the presence of outliers can significantly increase the computational complexity. Though a number of methods have been developed in the past decades, it is still quite challenging to design quality guaranteed algorithm with low complexity for this problem. Our idea is inspired by the greedy method, Gonzalez's algorithm, that was developed for solving the ordinary $k$-center clustering problem. Based on some novel observations, we show that a simple randomized version of this greedy strategy actually can handle outliers efficiently. We further show that this randomized greedy approach also yields small coreset for the problem in doubling metrics (even if the doubling dimension is not given), which can greatly reduce the computational complexity. Moreover, together with the partial clustering framework proposed in arXiv:1703.01539 , we prove that our coreset method can be applied to distributed data with a low communication complexity. The experimental results suggest that our algorithms can achieve near optimal solutions and yield lower complexities comparing with the existing methods.
翻译:在本文中,我们研究了 $ $ 美元 中心集聚与外部线 的问题。 这个问题在现实世界中有许多重要的应用, 但外部线的存在会大大增加计算的复杂性。 尽管在过去几十年中开发了一些方法, 但设计质量保障算法的难度仍然很大。 我们的想法来自贪婪的方法, Gonzalez 的算法, 这个方法是为了解决普通的 $ 中心集聚问题而开发的。 根据一些新颖的观察, 我们显示, 这个贪婪战略的简单随机化版本实际上可以有效地处理外部线。 我们进一步显示, 这种随机化的贪婪方法 也为加倍指标( 即使没有给出加倍的维度 ) 中的问题提供了小的核心, 这可以大大降低计算的复杂性。 此外, 再加上在 arXiv: 1703. 01539 中提出的部分集成框架, 我们证明我们的核心集成方法可以应用在传播数据时使用低通信复杂性。 实验结果表明, 我们的算法可以实现接近最佳的解决方案, 并且比现有方法的复杂程度更低。