Research map / Learning theory and algorithms / Clustering
Robust k-means: a Theoretical Revisit
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 a biased proximal map (convex f_lambda, e.g. l1 penalty / Huber Moreau envelope) instead of unbiased | robust k-means · theoretical breakdown analysis | finite-sample breakdown point: breakdown point 1/n (one outlier suffices) | Hurt |
| Use an unbiased (non-convex, e.g. l0-type) proximal map satisfying P(x)=x for large |x| | robust k-means · theoretical breakdown analysis | universal breakdown point: breakdown point 2/n instead of 1/n | Helped |
| Restrict to well-structured (rho1,rho2)-balanced datasets with well-separated inlier balls and suitable lambda | robust k-means · theoretical restricted robustness analysis | effect of outliers on grouping of inliers | Helped |
| Empirical comparison of robust k-means vs trimmed k-means on mixture of 10 Gaussians with mild/heavy outliers | robust k-means · synthetic 10-Gaussian mixture with 150 outliers | accuracy, center error, outlier detection rates | No clear effect |
| Well-clustered two-sphere dataset with heavy contamination (50% outliers) | robust k-means · two spherical clusters, 150 outliers in [-6,6]^10 | clustering performance | Helped |
Closest papers by meaning
- Clustering What Matters: Optimal Approximation for Clustering with Outliers (AAAI 2023 · similarity 0.89)
- The Complexity of k-Means Clustering when Little is Known (ICML 2022 · similarity 0.88)
- Near-Linear Time Approximation Algorithms for k-means with Outliers (ICML 2024 · similarity 0.88)
- A Practical Algorithm for Distributed Clustering and Outlier Detection (NeurIPS 2018 · similarity 0.88)
- On Robustness of Kernel Clustering (NeurIPS 2016 · similarity 0.88)
- Adapting k-means Algorithms for Outliers (ICML 2022 · similarity 0.88)
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.