# Near-Optimal Explainable k-Means for All Dimensions

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

## Key facts

- Cited by 13 papers in the map (data through 14 Oct 2026).
- Builds on 25 of its 63 references that are in the map.
- First posted on arXiv 29 Jun 2021.

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

- [A Unified Approach to Interpreting Model Predictions](https://mlsanity.com/paper/1705.07874/) (2017)
- ["Why Should I Trust You?": Explaining the Predictions of Any Classifier](https://mlsanity.com/paper/1602.04938/) (2016)
- [Interpretable machine learning: definitions, methods, and applications](https://mlsanity.com/paper/1901.04592/) (2019)
- [Fair Algorithms for Clustering](https://mlsanity.com/paper/1901.02393/) (2019)
- [Explaining the Explainer: A First Theoretical Analysis of LIME](https://mlsanity.com/paper/2001.03447/) (2020)
- [Scalable Fair Clustering](https://mlsanity.com/paper/1902.03519/) (2019)
- [Explainable k-Means and k-Medians Clustering](https://mlsanity.com/paper/2002.12538/) (2020)
- [Fair k-Center Clustering for Data Summarization](https://mlsanity.com/paper/1901.08628/) (2019)
- [Individual Fairness for k-Clustering](https://mlsanity.com/paper/2002.06742/) (2020)
- [Better Guarantees for k-Means and Euclidean k-Median by Primal-Dual Algorithms](https://mlsanity.com/paper/1612.07925/) (2016)
- [Performance of Johnson-Lindenstrauss Transform for k-Means and k-Medians Clustering](https://mlsanity.com/paper/1811.03195/) (2018)
- [Coresets for Clustering with Fairness Constraints](https://mlsanity.com/paper/1906.08484/) (2019)
- [From Clustering to Cluster Explanations via Neural Networks](https://mlsanity.com/paper/1906.07633/) (2019)
- [Improved Approximation Algorithms for Individually Fair Clustering](https://mlsanity.com/paper/2106.14043/) (2021)
- [ExKMC: Expanding Explainable k-Means Clustering](https://mlsanity.com/paper/2006.02399/) (2020)
- [Better Algorithms for Individually Fair k-Clustering](https://mlsanity.com/paper/2106.12150/) (2021)
- [The Hardness of Approximation of Euclidean k-means](https://mlsanity.com/paper/1502.03316/) (2015)
- [On the price of explainability for some clustering problems](https://mlsanity.com/paper/2101.01576/) (2021)
- [Local Search Yields a PTAS for k-Means in Doubling Metrics](https://mlsanity.com/paper/1603.08976/) (2016)
- [Balancing the Tradeoff Between Clustering Value and Interpretability](https://mlsanity.com/paper/1912.07820/) (2019)
- [Local search yields approximation schemes for k-means and k-median in Euclidean and minor-free metrics](https://mlsanity.com/paper/1603.09535/) (2016)
- [A Fast Approximation Scheme for Low-Dimensional k-Means](https://mlsanity.com/paper/1708.07381/) (2017)
- [Interpretable Clustering via Optimal Trees](https://mlsanity.com/paper/1812.00539/) (2018)
- [Weight of Evidence as a Basis for Human-Oriented Explanations](https://mlsanity.com/paper/1910.13503/) (2019)
- [Hardness of Approximation of Euclidean k-Median](https://mlsanity.com/paper/2011.04221/) (2020)

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

- [Nearly-Tight and Oblivious Algorithms for Explainable Clustering](https://mlsanity.com/paper/2106.16147/) (2021)
- [How to Find a Good Explanation for Clustering?](https://mlsanity.com/paper/2112.06580/) (2021)
- [Explainable k-means. Don't be greedy, plant bigger trees!](https://mlsanity.com/paper/2111.03193/) (2021)
- [Shallow decision trees for explainable k-means clustering](https://mlsanity.com/paper/2112.14718/) (2021)
- [Near-optimal Algorithms for Explainable k-Medians and k-Means](https://mlsanity.com/paper/2107.00798/) (2021)
- [Almost Tight Approximation Algorithms for Explainable Clustering](https://mlsanity.com/paper/2107.00774/) (2021)
- [Interpretable Clustering: A Survey](https://mlsanity.com/paper/2409.00743/) (2024)
- [The computational complexity of some explainable clustering problems](https://mlsanity.com/paper/2208.09643/) (2022)
- [Explaining Kernel Clustering via Decision Trees](https://mlsanity.com/paper/2402.09881/) (2024)
- [Towards Explainable Clustering: A Constrained Declarative based Approach](https://mlsanity.com/paper/2403.18101/) (2024)
- [Impossibility of Depth Reduction in Explainable Clustering](https://mlsanity.com/paper/2305.02850/) (2023)
- [Explainable Clustering of Mixture Models](https://mlsanity.com/paper/2411.01576/) (2024)
- [SpEx: A Spectral Approach to Explainable Clustering](https://mlsanity.com/paper/2511.00885/) (2025)

## Abstract (arXiv)

Many clustering algorithms are guided by certain cost functions such as the widely-used k-means cost. These algorithms divide data points into clusters with often complicated boundaries, creating difficulties in explaining the clustering decision. In a recent work, Dasgupta, Frost, Moshkovitz, and Rashtchian (ICML 2020) introduced explainable clustering, where the cluster boundaries are axis-parallel hyperplanes and the clustering is obtained by applying a decision tree to the data. The central question here is: how much does the explainability constraint increase the value of the cost function? Given d-dimensional data points, we show an efficient algorithm that finds an explainable clustering whose k-means cost is at most k1 - 2/d,poly(dlog k) times the minimum cost achievable by a clustering without the explainability constraint, assuming k,d≥ 2. Taking the minimum of this bound and the k,polylog (k) bound in independent work by Makarychev-Shan (ICML 2021), Gamlath-Jia-Polak-Svensson (2021), or Esfandiari-Mirrokni-Narayanan (2021), we get an improved bound of k1 - 2/d,polylog(k), which we show is optimal for every choice of k,d≥ 2 up to a poly-logarithmic factor in k. For d = 2 in particular, we show an O(log kloglog k) bound, improving near-exponentially over the previous best bound of O(klog k) by Laber and Murtinho (ICML 2021).