On the price of explainability for some clustering problems

2021/01/05 by Eduardo Sany Laber, Laber, Eduardo, Lucas Murtinho +1 · 2 citations
Computer Science · #Data Mining Algorithms and Applications #Data Structures and Algorithms (cs.DS) #Explainable Artificial Intelligence (XAI) #FOS: Computer and information sciences #Imbalanced Data Classification Techniques #Machine Learning (cs.LG)

paper · pdf · doi:10.48550/arxiv.2101.01576

openalex publication_date 2021/01/05 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

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.

Citations

• On a Method to Measure Supervised Multiclass Model’s Interpretability: Application to Degradation Diagnosis (Short Paper)
• Explainable k-Means and k-Medians Clustering
• ExKMC: Expanding Explainable k-Means Clustering

Cited by

• Dynamic Algorithm for Explainable k-medians Clustering under lp Norm
• SpEx: A Spectral Approach to Explainable Clustering

Related

• The Price of Explainability for Clustering
• Explainable Clustering Beyond Worst-Case Guarantees
• The computational complexity of some explainable clustering problems
• Nearly-Tight and Oblivious Algorithms for Explainable Clustering
• Near-Optimal Explainable k-Means for All Dimensions