# Explaining Kernel Clustering via Decision Trees

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 19 of its 35 references that are in the map.
- First posted on arXiv 15 Feb 2024.

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

- [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)
- [Counterfactual Explanations without Opening the Black Box: Automated Decisions and the GDPR](https://mlsanity.com/paper/1711.00399/) (2017)
- [A Survey on Explainable Artificial Intelligence (XAI): Towards Medical XAI](https://mlsanity.com/paper/1907.07374/) (2019)
- [Explainable k-Means and k-Medians Clustering](https://mlsanity.com/paper/2002.12538/) (2020)
- [On the Safety of Machine Learning: Cyber-Physical Systems, Decision Sciences, and Data Products](https://mlsanity.com/paper/1610.01256/) (2016)
- [ExKMC: Expanding Explainable k-Means Clustering](https://mlsanity.com/paper/2006.02399/) (2020)
- [RKHS-SHAP: Shapley Values for Kernel Methods](https://mlsanity.com/paper/2110.09167/) (2021)
- [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)
- [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)
- [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)
- [Cluster Explanation via Polyhedral Descriptions](https://mlsanity.com/paper/2210.08798/) (2022)
- [Random Cuts are Optimal for Explainable k-Medians](https://mlsanity.com/paper/2304.09113/) (2023)
- [Solving Interpretable Kernel Dimension Reduction](https://mlsanity.com/paper/1909.03093/) (2019)
- [Impossibility of Depth Reduction in Explainable Clustering](https://mlsanity.com/paper/2305.02850/) (2023)

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

- [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)

## Abstract (arXiv)

Despite the growing popularity of explainable and interpretable machine learning, there is still surprisingly limited work on inherently interpretable clustering methods. Recently, there has been a surge of interest in explaining the classic k-means algorithm, leading to efficient algorithms that approximate k-means clusters using axis-aligned decision trees. However, interpretable variants of k-means have limited applicability in practice, where more flexible clustering methods are often needed to obtain useful partitions of the data. In this work, we investigate interpretable kernel clustering, and propose algorithms that construct decision trees to approximate the partitions induced by kernel k-means, a nonlinear extension of k-means. We further build on previous work on explainable k-means and demonstrate how a suitable choice of features allows preserving interpretability without sacrificing approximation guarantees on the interpretable model.