# Explainable k-Means and k-Medians Clustering

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

## Key facts

- Cited by 67 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 28 Feb 2020.

## Built on by (most cited first, 30 of 67)

- [From Shapley Values to Generalized Additive Models and back](https://mlsanity.com/paper/2209.04012/) (2022)
- [Framework for Evaluating Faithfulness of Local Explanations](https://mlsanity.com/paper/2202.00734/) (2022)
- [Explainable Intrusion Detection Systems (X-IDS): A Survey of Current Methods, Challenges, and Opportunities](https://mlsanity.com/paper/2207.06236/) (2022)
- [On the price of explainability for some clustering problems](https://mlsanity.com/paper/2101.01576/) (2021)
- [A Comprehensive Survey on Self-Interpretable Neural Networks](https://mlsanity.com/paper/2501.15638/) (2025)
- [Nearly-Tight and Oblivious Algorithms for Explainable Clustering](https://mlsanity.com/paper/2106.16147/) (2021)
- [Connecting Interpretability and Robustness in Decision Trees through Separation](https://mlsanity.com/paper/2102.07048/) (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 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)
- [Almost Tight Approximation Algorithms for Explainable Clustering](https://mlsanity.com/paper/2107.00774/) (2021)
- [Interpretable Clustering via Multi-Polytope Machines](https://mlsanity.com/paper/2112.05653/) (2021)
- [A Scalable Framework for Evaluating Health Language Models](https://mlsanity.com/paper/2503.23339/) (2025)
- [A Survey on XAI for 5G and Beyond Security: Technical Aspects, Challenges and Research Directions](https://mlsanity.com/paper/2204.12822/) (2022)
- [Fair Wasserstein Coresets](https://mlsanity.com/paper/2311.05436/) (2023)
- [Interpretable Clustering: A Survey](https://mlsanity.com/paper/2409.00743/) (2024)
- [A Theory of Interpretable Approximations](https://mlsanity.com/paper/2406.10529/) (2024)
- [Cluster Explanation via Polyhedral Descriptions](https://mlsanity.com/paper/2210.08798/) (2022)
- [GLANCE: Global Actions in a Nutshell for Counterfactual Explainability](https://mlsanity.com/paper/2405.18921/) (2024)
- [Deep Descriptive Clustering](https://mlsanity.com/paper/2105.11549/) (2021)
- [Text-Guided Image Clustering](https://mlsanity.com/paper/2402.02996/) (2024)
- [There is no Accuracy-Interpretability Tradeoff in Reinforcement Learning for Mazes](https://mlsanity.com/paper/2206.04266/) (2022)
- [The computational complexity of some explainable clustering problems](https://mlsanity.com/paper/2208.09643/) (2022)
- [Kernel KMeans clustering splits for end-to-end unsupervised decision trees](https://mlsanity.com/paper/2402.12232/) (2024)
- [Deep Variational Clustering Framework for Self-labeling of Large-scale Medical Images](https://mlsanity.com/paper/2109.10777/) (2021)
- [A review of clustering models in educational data science towards fairness-aware learning](https://mlsanity.com/paper/2301.03421/) (2023)
- [Optimal Decision Trees For Interpretable Clustering with Constraints (Extended Version)](https://mlsanity.com/paper/2301.12671/) (2023)
- [Joint Debiased Representation Learning and Imbalanced Data Clustering](https://mlsanity.com/paper/2109.05232/) (2021)

## Abstract (arXiv)

Clustering is a popular form of unsupervised learning for geometric data. Unfortunately, many clustering algorithms lead to cluster assignments that are hard to explain, partially because they depend on all the features of the data in a complicated way. To improve interpretability, we consider using a small decision tree to partition a data set into clusters, so that clusters can be characterized in a straightforward manner. We study this problem from a theoretical viewpoint, measuring cluster quality by the k-means and k-medians objectives: Must there exist a tree-induced clustering whose cost is comparable to that of the best unconstrained clustering, and if so, how can it be found? In terms of negative results, we show, first, that popular top-down decision tree algorithms may lead to clusterings with arbitrarily large cost, and second, that any tree-induced clustering must in general incur an Omega(log k) approximation factor compared to the optimal clustering. On the positive side, we design an efficient algorithm that produces explainable clusters using a tree with k leaves. For two means/medians, we show that a single threshold cut suffices to achieve a constant factor approximation, and we give nearly-matching lower bounds. For general k ≥ 2, our algorithm is an O(k) approximation to the optimal k-medians and an O(k2) approximation to the optimal k-means. Prior to our work, no algorithms were known with provable guarantees independent of dimension and input size.