# Explainable k-means. Don't be greedy, plant bigger trees!

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

## Key facts

- Cited by 15 papers in the map (data through 14 Oct 2026).
- Builds on 18 of its 35 references that are in the map.
- First posted on arXiv 4 Nov 2021.

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

- [Explainable k-Means and k-Medians Clustering](https://mlsanity.com/paper/2002.12538/) (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)
- [Dimensionality Reduction for k-Means Clustering and Low Rank Approximation](https://mlsanity.com/paper/1410.6801/) (2014)
- [ExKMC: Expanding Explainable k-Means Clustering](https://mlsanity.com/paper/2006.02399/) (2020)
- [The Hardness of Approximation of Euclidean k-means](https://mlsanity.com/paper/1502.03316/) (2015)
- [Improved and Simplified Inapproximability for k-means](https://mlsanity.com/paper/1509.00916/) (2015)
- [On the price of explainability for some clustering problems](https://mlsanity.com/paper/2101.01576/) (2021)
- [Nearly-Tight and Oblivious Algorithms for Explainable Clustering](https://mlsanity.com/paper/2106.16147/) (2021)
- [Near-Optimal Explainable k-Means for All Dimensions](https://mlsanity.com/paper/2106.15566/) (2021)
- [Near-optimal Algorithms for Explainable k-Medians and k-Means](https://mlsanity.com/paper/2107.00798/) (2021)
- [Balancing the Tradeoff Between Clustering Value and Interpretability](https://mlsanity.com/paper/1912.07820/) (2019)
- [Improved Guarantees for k-means++ and k-means++ Parallel](https://mlsanity.com/paper/2010.14487/) (2020)
- [Almost Tight Approximation Algorithms for Explainable Clustering](https://mlsanity.com/paper/2107.00774/) (2021)
- [Interpretable Clustering via Optimal Trees](https://mlsanity.com/paper/1812.00539/) (2018)
- [A Constant-Factor Bi-Criteria Approximation Guarantee for k-means++](https://mlsanity.com/paper/1605.04986/) (2016)
- [A Refined Approximation for Euclidean k-Means](https://mlsanity.com/paper/2107.07358/) (2021)
- [A bi-criteria approximation algorithm for k Means](https://mlsanity.com/paper/1507.04227/) (2015)

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

- [How to Find a Good Explanation for Clustering?](https://mlsanity.com/paper/2112.06580/) (2021)
- [Shallow decision trees for explainable k-means clustering](https://mlsanity.com/paper/2112.14718/) (2021)
- [GLANCE: Global Actions in a Nutshell for Counterfactual Explainability](https://mlsanity.com/paper/2405.18921/) (2024)
- [There is no Accuracy-Interpretability Tradeoff in Reinforcement Learning for Mazes](https://mlsanity.com/paper/2206.04266/) (2022)
- [Kernel KMeans clustering splits for end-to-end unsupervised decision trees](https://mlsanity.com/paper/2402.12232/) (2024)
- [Explainable Graph Spectral Clustering of Text Documents](https://mlsanity.com/paper/2308.00504/) (2023)
- [Explaining Kernel Clustering via Decision Trees](https://mlsanity.com/paper/2402.09881/) (2024)
- [Interpretable Multi-View Clustering](https://mlsanity.com/paper/2405.02644/) (2024)
- [Impossibility of Depth Reduction in Explainable Clustering](https://mlsanity.com/paper/2305.02850/) (2023)
- [Interpretable Sequence Clustering](https://mlsanity.com/paper/2309.01140/) (2023)
- [Dynamic Algorithm for Explainable k-medians Clustering under lp Norm](https://mlsanity.com/paper/2512.01150/) (2025)
- [Data Selection: A General Principle for Building Small Interpretable Models](https://mlsanity.com/paper/2210.03921/) (2022)
- [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)
- [Interpretable Fair Clustering](https://mlsanity.com/paper/2511.21109/) (2025)

## Abstract (arXiv)

We provide a new bi-criteria tildeO(log2 k) competitive algorithm for explainable k-means clustering. Explainable k-means was recently introduced by Dasgupta, Frost, Moshkovitz, and Rashtchian (ICML 2020). It is described by an easy to interpret and understand (threshold) decision tree or diagram. The cost of the explainable k-means clustering equals to the sum of costs of its clusters; and the cost of each cluster equals the sum of squared distances from the points in the cluster to the center of that cluster. The best non bi-criteria algorithm for explainable clustering tildeO(k) competitive, and this bound is tight. Our randomized bi-criteria algorithm constructs a threshold decision tree that partitions the data set into (1+δ)k clusters (where δ∈ (0,1) is a parameter of the algorithm). The cost of this clustering is at most tildeO(1/ δ · log2 k) times the cost of the optimal unconstrained k-means clustering. We show that this bound is almost optimal.