# How to Find a Good Explanation for Clustering?

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

## Key facts

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

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

- [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)
- [Axiomatic Attribution for Deep Networks](https://mlsanity.com/paper/1703.01365/) (2017)
- [Learning Important Features Through Propagating Activation Differences](https://mlsanity.com/paper/1704.02685/) (2017)
- [The Mythos of Model Interpretability](https://mlsanity.com/paper/1606.03490/) (2016)
- [Supersparse Linear Integer Models for Optimized Medical Scoring Systems](https://mlsanity.com/paper/1502.04269/) (2015)
- [Explainable k-Means and k-Medians Clustering](https://mlsanity.com/paper/2002.12538/) (2020)
- [Falling Rule Lists](https://mlsanity.com/paper/1411.5899/) (2014)
- [Interpretability and Explainability: A Machine Learning Zoo Mini-tour](https://mlsanity.com/paper/2012.01805/) (2020)
- [DeepPINK: reproducible feature selection in deep neural networks](https://mlsanity.com/paper/1809.01185/) (2018)
- [Sparse-Input Neural Networks for High-dimensional Nonparametric Regression and Classification](https://mlsanity.com/paper/1711.07592/) (2017)
- [Constant Approximation for k-Median and k-Means with Outliers via Iterative Rounding](https://mlsanity.com/paper/1711.01323/) (2017)
- [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)
- [Almost Tight Approximation Algorithms for Explainable Clustering](https://mlsanity.com/paper/2107.00774/) (2021)
- [Approximation Schemes for Clustering with Outliers](https://mlsanity.com/paper/1707.04295/) (2017)
- [The Non-Uniform k-Center Problem](https://mlsanity.com/paper/1605.03692/) (2016)
- [A Lottery Model for Center-type Problems With Outliers](https://mlsanity.com/paper/1710.00287/) (2017)

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

- [Interpretable Clustering: A Survey](https://mlsanity.com/paper/2409.00743/) (2024)
- [The computational complexity of some explainable clustering problems](https://mlsanity.com/paper/2208.09643/) (2022)
- [A review of clustering models in educational data science towards fairness-aware learning](https://mlsanity.com/paper/2301.03421/) (2023)
- [XClusters: Explainability-first Clustering](https://mlsanity.com/paper/2209.10956/) (2022)
- [Explainable Graph Spectral Clustering of Text Documents](https://mlsanity.com/paper/2308.00504/) (2023)
- [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)
- [Impossibility of Depth Reduction in Explainable Clustering](https://mlsanity.com/paper/2305.02850/) (2023)
- [Interpretable Sequence Clustering](https://mlsanity.com/paper/2309.01140/) (2023)
- [Explaining Clustering of Ecological Momentary Assessment Data Through Temporal and Feature Attention](https://mlsanity.com/paper/2405.04854/) (2024)
- [Dynamic Algorithm for Explainable k-medians Clustering under lp Norm](https://mlsanity.com/paper/2512.01150/) (2025)
- [Explainable Evidential Clustering](https://mlsanity.com/paper/2507.12192/) (2025)
- [SpEx: A Spectral Approach to Explainable Clustering](https://mlsanity.com/paper/2511.00885/) (2025)
- [ExDBSCAN: Explaining DBSCAN with Counterfactual Reasoning -- Additional Material](https://mlsanity.com/paper/2605.30225/) (2026)
- [Central Description Length (CDL) Clustering Validation Index](https://mlsanity.com/paper/2606.05230/) (2026)
- [Beyond Feature Importance: A Comparative Analysis of Pattern Detection Methods in Cluster Interpretation](https://mlsanity.com/paper/2608.05880/) (2026)

## Abstract (arXiv)

k-means and k-median clustering are powerful unsupervised machine learning techniques. However, due to complicated dependences on all the features, it is challenging to interpret the resulting cluster assignments. Moshkovitz, Dasgupta, Rashtchian, and Frost [ICML 2020] proposed an elegant model of explainable k-means and k-median clustering. In this model, a decision tree with k leaves provides a straightforward characterization of the data set into clusters. We study two natural algorithmic questions about explainable clustering. (1) For a given clustering, how to find the "best explanation" by using a decision tree with k leaves? (2) For a given set of points, how to find a decision tree with k leaves minimizing the k-means/median objective of the resulting explainable clustering? To address the first question, we introduce a new model of explainable clustering. Our model, inspired by the notion of outliers in robust statistics, is the following. We are seeking a small number of points (outliers) whose removal makes the existing clustering well-explainable. For addressing the second question, we initiate the study of the model of Moshkovitz et al. from the perspective of multivariate complexity. Our rigorous algorithmic analysis sheds some light on the influence of parameters like the input size, dimension of the data, the number of outliers, the number of clusters, and the approximation ratio, on the computational complexity of explainable clustering.