mlsanityData to 7 Oct 2026

On the price of explainability for some clustering problems

arXiv 2101.01576 ↗First posted 5 Jan 2021cs.LG cs.DScited by 21

Not on the map. Why?

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.

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

Builds on

7 of 36 references.

References · 7

  1. 2017A Unified Approach to Interpreting Model Predictionscited by 6,488
  2. 2016"Why Should I Trust You?": Explaining the Predictions of Any Classifiercited by 5,040
  3. 2020Explainable k-Means and k-Medians Clusteringcited by 67
  4. 2020Born-Again Tree Ensemblescited by 38
  5. 2020ExKMC: Expanding Explainable k-Means Clusteringcited by 31
  6. 2019Balancing the Tradeoff Between Clustering Value and Interpretabilitycited by 11
  7. 2019Computationally Efficient Feature Significance and Importance for Machine Learning Modelscited by 2

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 9; 2022: 2; 2023: 2; 2024: 5; 2025: 2; 2026: 1.

21 papers.

Sort:

  1. 2021Nearly-Tight and Oblivious Algorithms for Explainable Clusteringcited by 17
  2. 2021Connecting Interpretability and Robustness in Decision Trees through Separationcited by 16
  3. 2021How to Find a Good Explanation for Clustering?cited by 16
  4. 2021Explainable k-means. Don't be greedy, plant bigger trees!cited by 15
  5. 2021Shallow decision trees for explainable k-means clusteringcited by 15
  6. 2021Near-Optimal Explainable k-Means for All Dimensionscited by 13
  7. 2021Near-optimal Algorithms for Explainable k-Medians and k-Meanscited by 13
  8. 2021Almost Tight Approximation Algorithms for Explainable Clusteringcited by 12
  9. 2024Interpretable Clustering: A Surveycited by 8
  10. 2024GLANCE: Global Actions in a Nutshell for Counterfactual Explainabilitycited by 6
  11. 2021Learning to Generate Fair Clusters from Demonstrationscited by 4
  12. 2022The computational complexity of some explainable clustering problemscited by 4
9 more
  1. 2022XClusters: Explainability-first Clusteringcited by 2
  2. 2024Explaining Kernel Clustering via Decision Treescited by 2
  3. 2024Towards Explainable Clustering: A Constrained Declarative based Approachcited by 2
  4. 2023Impossibility of Depth Reduction in Explainable Clusteringcited by 1
  5. 2023The Computational Complexity of Concise Hypersphere Classificationcited by 1
  6. 2024Explainable Clustering of Mixture Modelscited by 0
  7. 2025SpEx: A Spectral Approach to Explainable Clusteringcited by 0
  8. 2025Dynamic Algorithm for Explainable k-medians Clustering under lp Normcited by 0
  9. 2026Neural-Symbolic Integration with Evolvable Policiescited by 0