Local Search Methods for k-Means with Outliers
Local Search Methods for k-Means with Outliers
复制标题
DOI：
10.14778/3067421.3067425
复制
发表时间：
2017-03-01
影响因子：
2.5
通讯作者：
Vassilvitskii, Sergei
中科院分区：
文献类型：
--
作者：
Gupta, Shalmoli;Kumar, Ravi;Vassilvitskii, Sergei
研究了存在离群点的k-均值聚类问题。其目标是对一组数据点进行聚类，以最小化分配给同一聚类的点的方差，并且可以自由地忽略可以被标记为异常值的一小部分数据点。带离群点的聚类在数据处理领域得到了广泛的关注，但对于最流行的k-Means对象，实用、高效和可证明是好的算法还是个未知数。我们的工作提出了一个简单的基于局部搜索的带离群点的k-Means聚类算法。我们证明了该算法实现了恒定因子的近似解，并且可以与已知的草图绘制技术相结合来扩展到大数据集。通过对合成数据和大规模真实数据的经验评估，我们证明了该算法在最近提出的启发式方法中占主导地位。
We study the problem of k-means clustering in the presence of outliers. The goal is to cluster a set of data points to minimize the variance of the points assigned to the same cluster, with the freedom of ignoring a small set of data points that can be labeled as outliers. Clustering with outliers has received a lot of attention in the data processing community, but practical, efficient, and provably good algorithms remain unknown for the most popular k-means objective.Our work proposes a simple local search-based algorithm for k-means clustering with outliers. We prove that this algorithm achieves constant-factor approximate solutions and can be combined with known sketching techniques to scale to large data sets. Using empirical evaluation on both synthetic and large-scale real-world data, we demonstrate that the algorithm dominates recently proposed heuristic approaches for the problem.