Fast Noise Removal for kMeans Clustering
[edit]
Proceedings of the Twenty Third International Conference on Artificial Intelligence and Statistics, PMLR 108:456466, 2020.
Abstract
This paper considers kmeans clustering in the presence of noise. It is known that kmeans clustering is highly sensitive to noise, and thus noise should be removed to obtain a quality solution. A popular formulation of this problem is called kmeans clustering with outliers. The goal of kmeans clustering with outliers is to discard up to a specified number z of points as noise/outliers and then find a kmeans solution on the remaining data. The problem has received significant attention, yet current algorithms with theoretical guarantees suffer from either high running time or inherent loss in the solution quality. The main contribution of this paper is twofold. Firstly, we develop a simple greedy algorithm that has provably strong worst case guarantees. The greedy algorithm adds a simple preprocessing step to remove noise, which can be combined with any kmeans clustering algorithm. This algorithm gives the first pseudoapproximationpreserving reduction from kmeans with outliers to kmeans without outliers. Secondly, we show how to construct a coreset of size O(k log n). When combined with our greedy algorithm, we obtain a scalable, near linear time algorithm. The theoretical contributions are verified experimentally by demonstrating that the algorithm quickly removes noise and obtains a highquality clustering.
Related Material


