Research map / Learning theory and algorithms / Clustering
Adapting k-means Algorithms for Outliers
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's title only (no summary yet). Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use penalty-based Local-search++ instead of penalty k-means++ alone | k-means with outliers · kdd and spam | clustering cost: around 12% | Helped |
| Use k-means++ seeding rather than random initialization | Lloyd's algorithm · kdd and spam | clustering cost | Hurt |
| Use k-means++ with penalties rather than Lloyd or ordinary k-means++ | k-means with outliers · kdd and spam | clustering cost: around 40% | Helped |
| Use the distributed or Metropolis variant instead of k-means++ with penalties | k-means with outliers · kdd | clustering cost | No clear effect |
| Use the Metropolis variant instead of k-means++ with penalties | k-means with outliers · spam | clustering cost | Mixed |
| Allow a small excess of outliers and reduce the per-machine computation to polynomial time | Distributed k-means with outliers · coordinator model | local computation time | Helped |
| Use Metropolis-Hastings sampling rather than computing penalty costs for every point | k-means with outliers · general metric query model | running time: \tilde{O}(nk) to \tilde{O}(nk^2/z) | Helped |
Closest papers by meaning
- Near-Linear Time Approximation Algorithms for k-means with Outliers (ICML 2024 · similarity 0.91)
- Fast Algorithms for Distributed k-Clustering with Outliers (ICML 2023 · similarity 0.89)
- Greedy Sampling for Approximate Clustering in the Presence of Outliers (NeurIPS 2019 · similarity 0.88)
- A More Efficient Reduction from Outlier-Aware to Outlier-Free k-Median (AAAI 2026 · similarity 0.88)
- Robust k-means: a Theoretical Revisit (NeurIPS 2016 · similarity 0.88)
- Distributed $k$-Clustering for Data with Heavy Noise (NeurIPS 2018 · 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.