mlsanityData to 7 Oct 2026

Explainable k-means. Don't be greedy, plant bigger trees!

arXiv 2111.03193 ↗First posted 4 Nov 2021cs.LG cs.DScited by 15

Not on the map. Why?

Abstract (arXiv)

We provide a new bi-criteria tildeO(log2 k) competitive algorithm for explainable k-means clustering. Explainable k-means was recently introduced by Dasgupta, Frost, Moshkovitz, and Rashtchian (ICML 2020). It is described by an easy to interpret and understand (threshold) decision tree or diagram. The cost of the explainable k-means clustering equals to the sum of costs of its clusters; and the cost of each cluster equals the sum of squared distances from the points in the cluster to the center of that cluster. The best non bi-criteria algorithm for explainable clustering tildeO(k) competitive, and this bound is tight. Our randomized bi-criteria algorithm constructs a threshold decision tree that partitions the data set into (1+δ)k clusters (where δ∈ (0,1) is a parameter of the algorithm). The cost of this clustering is at most tildeO(1/ δ · log2 k) times the cost of the optimal unconstrained k-means clustering. We show that this bound is almost optimal.

Key facts. Cited by 15 papers in the map (data through 7 Oct 2026). Builds on 18 of its 35 references that are in the map. First posted on arXiv 4 Nov 2021.

Builds on

18 of 35 references.

References · 18

  1. 2020Explainable k-Means and k-Medians Clusteringcited by 67
  2. 2016Better Guarantees for k-Means and Euclidean k-Median by Primal-Dual Algorithmscited by 54
  3. 2018Performance of Johnson-Lindenstrauss Transform for k-Means and k-Medians Clusteringcited by 53
  4. 2014Dimensionality Reduction for k-Means Clustering and Low Rank Approximationcited by 48
  5. 2020ExKMC: Expanding Explainable k-Means Clusteringcited by 31
  6. 2015The Hardness of Approximation of Euclidean k-meanscited by 25
  7. 2015Improved and Simplified Inapproximability for k-meanscited by 22
  8. 2021On the price of explainability for some clustering problemscited by 21
  9. 2021Nearly-Tight and Oblivious Algorithms for Explainable Clusteringcited by 17
  10. 2021Near-Optimal Explainable k-Means for All Dimensionscited by 13
  11. 2021Near-optimal Algorithms for Explainable k-Medians and k-Meanscited by 13
  12. 2020Improved Guarantees for k-means++ and k-means++ Parallelcited by 12
6 more
  1. 2021Almost Tight Approximation Algorithms for Explainable Clusteringcited by 12
  2. 2019Balancing the Tradeoff Between Clustering Value and Interpretabilitycited by 11
  3. 2018Interpretable Clustering via Optimal Treescited by 10
  4. 2016A Constant-Factor Bi-Criteria Approximation Guarantee for k-means++cited by 8
  5. 2021A Refined Approximation for Euclidean k-Meanscited by 7
  6. 2015A bi-criteria approximation algorithm for k Meanscited by 4

Built on by

Cited by year

Citing papers per year: 2021: 2; 2022: 2; 2023: 3; 2024: 5; 2025: 3.

15 papers.

Sort:

  1. 2021How to Find a Good Explanation for Clustering?cited by 16
  2. 2021Shallow decision trees for explainable k-means clusteringcited by 15
  3. 2024GLANCE: Global Actions in a Nutshell for Counterfactual Explainabilitycited by 6
  4. 2022There is no Accuracy-Interpretability Tradeoff in Reinforcement Learning for Mazescited by 4
  5. 2024Kernel KMeans clustering splits for end-to-end unsupervised decision treescited by 4
  6. 2023Explainable Graph Spectral Clustering of Text Documentscited by 2
  7. 2024Explaining Kernel Clustering via Decision Treescited by 2
  8. 2024Interpretable Multi-View Clusteringcited by 2
  9. 2023Impossibility of Depth Reduction in Explainable Clusteringcited by 1
  10. 2023Interpretable Sequence Clusteringcited by 1
  11. 2022Data Selection: A General Principle for Building Small Interpretable Modelscited by 0
  12. 2024Explainable Clustering of Mixture Modelscited by 0
3 more
  1. 2025SpEx: A Spectral Approach to Explainable Clusteringcited by 0
  2. 2025Interpretable Fair Clusteringcited by 0
  3. 2025Dynamic Algorithm for Explainable k-medians Clustering under lp Normcited by 0