# Provable Imbalanced Point Clustering

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 9 of its 35 references that are in the map.
- First posted on arXiv 26 Aug 2024.

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

- [Imbalanced-learn: A Python Toolbox to Tackle the Curse of Imbalanced Datasets in Machine Learning](https://mlsanity.com/paper/1609.06570/) (2016)
- [Turning Big data into tiny data: Constant-size coresets for k-means, PCA and projective clustering](https://mlsanity.com/paper/1807.04518/) (2018)
- [Machine Learning in Python: Main developments and technology trends in data science, machine learning, and artificial intelligence](https://mlsanity.com/paper/2002.04803/) (2020)
- [New Frameworks for Offline and Streaming Coreset Constructions](https://mlsanity.com/paper/1612.00889/) (2016)
- [Training Gaussian Mixture Models at Scale via Coresets](https://mlsanity.com/paper/1703.08110/) (2017)
- [Oversampling for Imbalanced Learning Based on K-Means and SMOTE](https://mlsanity.com/paper/1711.00837/) (2017)
- [Fast Deterministic Selection](https://mlsanity.com/paper/1606.00484/) (2016)
- [Coresets for Gaussian Mixture Models of Any Shape](https://mlsanity.com/paper/1906.04895/) (2019)
- [HiPart: Hierarchical Divisive Clustering Toolbox](https://mlsanity.com/paper/2209.08680/) (2022)

## Abstract (arXiv)

We suggest efficient and provable methods to compute an approximation for imbalanced point clustering, that is, fitting k-centers to a set of points in ℝd, for any d,k≥ 1. To this end, we utilize coresets, which, in the context of the paper, are essentially weighted sets of points in ℝd that approximate the fitting loss for every model in a given set, up to a multiplicative factor of 1±varepsilon. We provide [Section 3 and Section E in the appendix] experiments that show the empirical contribution of our suggested methods for real images (novel and reference), synthetic data, and real-world data. We also propose choice clustering, which by combining clustering algorithms yields better performance than each one separately.