Research map / Learning theory and algorithms / Clustering
Near-Linear Time Approximation Algorithms for k-means with Outliers
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes near-linear-time, aspect-ratio-independent sampling algorithms (Fast-Sampling and Center-Reduction) for k-means with outliers, achieving constant approximations while discarding (1+ϵ)z outliers.
Problem
k-means with outliers: find k centers minimizing clustering cost after discarding up to z outliers, with fast algorithms whose running time does not depend on the aspect ratio and does not require distribution assumptions.
Approach
A two-stage sampling strategy: boost distance-based sampling probabilities by an oversampling factor (estimated without guessing OPT, via fast estimation) so that about (1+ϵ)z points are sampled and inliers constitute a fraction of them, then normalize so an inlier near an optimal center is picked with constant probability; a center-reduction step recovers mistakenly discarded inliers to open exac
Key results
- TIKmeans reduces clustering cost by at least 4.43% on Skin-5 and 21.16% on Shuttle versus the best of RobustKmeans++ and NKmeans.
- On SIFT-5 and SIFT-10, IKmeans cuts running time by at least 50% versus RobustKmeans++ and NKmeans.
- LS++ times out (>24h) on SUSY and SIFT datasets, while the proposed methods finish.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use TIKmeans instead of RobustKmeans++ and NKmeans | k-means with outliers · Skin-5 and Shuttle | Cost: at least 4.43% and 21.16% | Helped |
| Use the proposed algorithms instead of other algorithms | k-means with outliers · 8 datasets in Table 2 | Cost: at least 5% on average | Helped |
| Use IKmeans instead of the state-of-the-art algorithms | k-means with outliers · SIFT-5 and SIFT-10 | Time: at least 50% | Helped |
Limitations
- Theoretical guarantees hold with constant probability and discard (1+ϵ)z outliers rather than exactly z (except under cluster-size assumption).
- Running time still includes a log log n factor and O(k/ϵ) sampling rounds; Center-Reduction adds poly(k,1/ϵ) log(nΔ) term.
- Experiments are on CPU machine with 100 Xeon cores and fixed parameters, with exact z-outlier evaluation based on fixed furthest-point rule.
Experimental setup
Datasets: Skin SUSY Shuttle KDDFULL SIFT
Benchmarks: Skin SUSY Shuttle KDDFULL SIFT
Metrics: clustering cost recall of outliers running time
Baselines: NKmeans RobustKmeans++ LS++ IKmeans (ablation of this paper)
Builds on: k-means++ D2-sampling Robust k-means++ (Deshpande et al., 2020) LS++ local search (Grunau & Rozhoň, 2022) NKmeans (Im et al., 2020) Bhaskara et al. 2019 modified k-means++
Closest papers by meaning
- Fast Algorithms for Distributed k-Clustering with Outliers (ICML 2023 · similarity 0.92)
- Greedy Sampling for Approximate Clustering in the Presence of Outliers (NeurIPS 2019 · similarity 0.91)
- Adapting k-means Algorithms for Outliers (ICML 2022 · similarity 0.91)
- A More Efficient Reduction from Outlier-Aware to Outlier-Free k-Median (AAAI 2026 · similarity 0.90)
- Improved Guarantees for Fully Dynamic $k$-Center Clustering with Outliers in General Metric Spaces (NeurIPS 2024 · similarity 0.88)
- Fully-Scalable Massively Parallel Algorithm for k-center with Outliers (AAAI 2025 · similarity 0.87)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.