# Shallow decision trees for explainable k-means clustering

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

## Key facts

- Cited by 15 papers in the map (data through 14 Oct 2026).
- Builds on 16 of its 40 references that are in the map.
- First posted on arXiv 29 Dec 2021.

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

- [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)
- [OpenML: networked science in machine learning](https://mlsanity.com/paper/1407.7722/) (2014)
- [A Survey on the Explainability of Supervised Machine Learning](https://mlsanity.com/paper/2011.07876/) (2020)
- [Explainable k-Means and k-Medians Clustering](https://mlsanity.com/paper/2002.12538/) (2020)
- [From Clustering to Cluster Explanations via Neural Networks](https://mlsanity.com/paper/1906.07633/) (2019)
- [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)
- [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)
- [Explainable k-means. Don't be greedy, plant bigger trees!](https://mlsanity.com/paper/2111.03193/) (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)
- [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)

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

- [Interpretable Clustering: A Survey](https://mlsanity.com/paper/2409.00743/) (2024)
- [Accurate Explanation Model for Image Classifiers using Class Association Embedding](https://mlsanity.com/paper/2406.07961/) (2024)
- [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)
- [Counterfactual Explanations for k-means and Gaussian Clustering](https://mlsanity.com/paper/2501.10234/) (2025)
- [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)
- [Using Decision Trees for Interpretable Supervised Clustering](https://mlsanity.com/paper/2307.08104/) (2023)
- [Data Selection: A General Principle for Building Small Interpretable Models](https://mlsanity.com/paper/2210.03921/) (2022)
- [XAI for Self-supervised Clustering of Wireless Spectrum Activity](https://mlsanity.com/paper/2305.10060/) (2023)
- [Topological Quality of Subsets via Persistence Matching Diagrams](https://mlsanity.com/paper/2306.02411/) (2023)
- [Massively-Parallel Heat Map Sorting and Applications To Explainable Clustering](https://mlsanity.com/paper/2309.07486/) (2023)
- [SpEx: A Spectral Approach to Explainable Clustering](https://mlsanity.com/paper/2511.00885/) (2025)
- [Collapse-Free Prototype Readout Layer for Transformer Encoders](https://mlsanity.com/paper/2604.03850/) (2026)

## Abstract (arXiv)

A number of recent works have employed decision trees for the construction of explainable partitions that aim to minimize the k-means cost function. These works, however, largely ignore metrics related to the depths of the leaves in the resulting tree, which is perhaps surprising considering how the explainability of a decision tree depends on these depths. To fill this gap in the literature, we propose an efficient algorithm that takes into account these metrics. In experiments on 16 datasets, our algorithm yields better results than decision-tree clustering algorithms such as the ones presented in citedasgupta2020explainable, citefrost2020exkmc, citelaber2021price and citeDBLP:conf/icml/MakarychevS21, typically achieving lower or equivalent costs with considerably shallower trees. We also show, through a simple adaptation of existing techniques, that the problem of building explainable partitions induced by binary trees for the k-means cost function does not admit an (1+ε)-approximation in polynomial time unless P=NP, which justifies the quest for approximation algorithms and/or heuristics.