# ExKMC: Expanding Explainable k-Means Clustering

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

## Key facts

- Cited by 31 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 3 Jun 2020.

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

- [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)
- [Connecting Interpretability and Robustness in Decision Trees through Separation](https://mlsanity.com/paper/2102.07048/) (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 Survey on XAI for 5G and Beyond Security: Technical Aspects, Challenges and Research Directions](https://mlsanity.com/paper/2204.12822/) (2022)
- [Interpretable Clustering: A Survey](https://mlsanity.com/paper/2409.00743/) (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)
- [Shapley-based Explainable AI for Clustering Applications in Fault Diagnosis and Prognosis](https://mlsanity.com/paper/2303.14581/) (2023)
- [Algorithm-Agnostic Explainability for Unsupervised Clustering](https://mlsanity.com/paper/2105.08053/) (2021)
- [Kernel KMeans clustering splits for end-to-end unsupervised decision trees](https://mlsanity.com/paper/2402.12232/) (2024)
- [Optimal Decision Trees For Interpretable Clustering with Constraints (Extended Version)](https://mlsanity.com/paper/2301.12671/) (2023)
- [NeurCAM: Interpretable Neural Clustering via Additive Models](https://mlsanity.com/paper/2408.13361/) (2024)
- [KnAC: an approach for enhancing cluster analysis with background knowledge and explanations](https://mlsanity.com/paper/2112.08759/) (2021)
- [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)
- [Interpretable Multi-View Clustering](https://mlsanity.com/paper/2405.02644/) (2024)
- [NetBurst: Event-Centric Forecasting of Bursty, Intermittent Time Series](https://mlsanity.com/paper/2510.22397/) (2025)
- [Explainable Clustering via Exemplars: Complexity and Efficient Approximation Algorithms](https://mlsanity.com/paper/2209.09670/) (2022)
- [Impossibility of Depth Reduction in Explainable Clustering](https://mlsanity.com/paper/2305.02850/) (2023)
- [Fair Clustering: Critique, Caveats, and Future Directions](https://mlsanity.com/paper/2406.15960/) (2024)
- [Explainable Clustering of Mixture Models](https://mlsanity.com/paper/2411.01576/) (2024)
- [Disjunctive and Conjunctive Normal Form Explanations of Clusters Using Auxiliary Information](https://mlsanity.com/paper/2504.20846/) (2025)
- [Empowering Decision Trees via Shape Function Branching](https://mlsanity.com/paper/2510.19040/) (2025)

## Abstract (arXiv)

Despite the popularity of explainable AI, there is limited work on effective methods for unsupervised learning. We study algorithms for k-means clustering, focusing on a trade-off between explainability and accuracy. Following prior work, we use a small decision tree to partition a dataset into k clusters. This enables us to explain each cluster assignment by a short sequence of single-feature thresholds. While larger trees produce more accurate clusterings, they also require more complex explanations. To allow flexibility, we develop a new explainable k-means clustering algorithm, ExKMC, that takes an additional parameter k' ≥ k and outputs a decision tree with k' leaves. We use a new surrogate cost to efficiently expand the tree and to label the leaves with one of k clusters. We prove that as k' increases, the surrogate cost is non-increasing, and hence, we trade explainability for accuracy. Empirically, we validate that ExKMC produces a low cost clustering, outperforming both standard decision tree methods and other algorithms for explainable clustering. Implementation of ExKMC available at https://github.com/navefr/ExKMC.