# Is Simple Uniform Sampling Effective for Center-Based Clustering with Outliers: When and Why?

arXiv: https://arxiv.org/abs/2103.00558 · HTML: https://mlsanity.com/paper/2103.00558/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 10 of its 55 references that are in the map.
- First posted on arXiv 28 Feb 2021.

## Builds on (most cited first, 10 of 10)

- [Selection via Proxy: Efficient Data Selection for Deep Learning](https://mlsanity.com/paper/1906.11829/) (2019)
- [Constant Approximation for k-Median and k-Means with Outliers via Iterative Rounding](https://mlsanity.com/paper/1711.01323/) (2017)
- [varepsilon-Coresets for Clustering (with Outliers) in Doubling Metrics](https://mlsanity.com/paper/1804.02530/) (2018)
- [Clustering with Outlier Removal](https://mlsanity.com/paper/1801.01899/) (2018)
- [Approximation Schemes for Clustering with Outliers](https://mlsanity.com/paper/1707.04295/) (2017)
- [The Non-Uniform k-Center Problem](https://mlsanity.com/paper/1605.03692/) (2016)
- [Solving k-center Clustering (with Outliers) in MapReduce and Streaming, almost as Accurately as Sequentially](https://mlsanity.com/paper/1802.09205/) (2018)
- [A Practical Algorithm for Distributed Clustering and Outlier Detection](https://mlsanity.com/paper/1805.09495/) (2018)
- [Fast Noise Removal for k-Means Clustering](https://mlsanity.com/paper/2003.02433/) (2020)
- [Layered Sampling for Robust Optimization Problems](https://mlsanity.com/paper/2002.11904/) (2020)

## Built on by (most cited first, 1 of 1)

- [Comparative Analysis of Optimization Strategies for K-means Clustering in Big Data Contexts: A Review](https://mlsanity.com/paper/2310.09819/) (2023)

## Abstract (arXiv)

Real-world datasets often contain outliers, and the presence of outliers can make the clustering problems to be much more challenging. In this paper, we propose a simple uniform sampling framework for solving three representative center-based clustering with outliers problems: k-center/median/means clustering with outliers. Our analysis is fundamentally different from the previous (uniform and non-uniform) sampling based ideas. To explain the effectiveness of uniform sampling in theory, we introduce a measure of "significance" and prove that the performance of our framework depends on the significance degree of the given instance. In particular, the sample size can be independent of the input data size n and the dimensionality d, if we assume the given instance is "significant", which is in fact a fairly reasonable assumption in practice. Due to its simplicity, the uniform sampling approach also enjoys several significant advantages over the non-uniform sampling approaches in practice. To the best of our knowledge, this is the first work that systematically studies the effectiveness of uniform sampling from both theoretical and experimental aspects.