# On the price of explainability for some clustering problems

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

## Key facts

- Cited by 21 papers in the map (data through 14 Oct 2026).
- Builds on 7 of its 36 references that are in the map.
- First posted on arXiv 5 Jan 2021.

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

- [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)
- [Explainable k-Means and k-Medians Clustering](https://mlsanity.com/paper/2002.12538/) (2020)
- [Born-Again Tree Ensembles](https://mlsanity.com/paper/2003.11132/) (2020)
- [ExKMC: Expanding Explainable k-Means Clustering](https://mlsanity.com/paper/2006.02399/) (2020)
- [Balancing the Tradeoff Between Clustering Value and Interpretability](https://mlsanity.com/paper/1912.07820/) (2019)
- [Computationally Efficient Feature Significance and Importance for Machine Learning Models](https://mlsanity.com/paper/1905.09849/) (2019)

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

- [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: A Survey](https://mlsanity.com/paper/2409.00743/) (2024)
- [GLANCE: Global Actions in a Nutshell for Counterfactual Explainability](https://mlsanity.com/paper/2405.18921/) (2024)
- [Learning to Generate Fair Clusters from Demonstrations](https://mlsanity.com/paper/2102.03977/) (2021)
- [The computational complexity of some explainable clustering problems](https://mlsanity.com/paper/2208.09643/) (2022)
- [XClusters: Explainability-first Clustering](https://mlsanity.com/paper/2209.10956/) (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)
- [The Computational Complexity of Concise Hypersphere Classification](https://mlsanity.com/paper/2312.07103/) (2023)
- [Dynamic Algorithm for Explainable k-medians Clustering under lp Norm](https://mlsanity.com/paper/2512.01150/) (2025)
- [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)
- [Neural-Symbolic Integration with Evolvable Policies](https://mlsanity.com/paper/2601.04799/) (2026)

## Abstract (arXiv)

The price of explainability for a clustering task can be defined as the unavoidable loss,in terms of the objective function, if we force the final partition to be explainable. Here, we study this price for the following clustering problems: k-means, k-medians, k-centers and maximum-spacing. We provide upper and lower bounds for a natural model where explainability is achieved via decision trees. For the k-means and k-medians problems our upper bounds improve those obtained by [Moshkovitz et. al, ICML 20] for low dimensions. Another contribution is a simple and efficient algorithm for building explainable clusterings for the k-means problem. We provide empirical evidence that its performance is better than the current state of the art for decision-tree based explainable clustering.