ExKMC: Expanding Explainable k-Means Clustering

2020/06/03 by Nave Frost, Michal Moshkovitz, Frost, Nave +3 · 6 citations
Computer Science · #Bayesian Modeling and Causal Inference #Computational Geometry (cs.CG) #Data Structures and Algorithms (cs.DS) #Explainable Artificial Intelligence (XAI) #FOS: Computer and information sciences #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Machine Learning and Data Classification

paper · pdf · doi:10.48550/arxiv.2006.02399

openalex publication_date 2020/06/03 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

Despite the popularity of explainable AI, there is limited work on effective methods for unsupervised learning. We study algorithms for k-means clustering, focusing on a trade-off between explainability and accuracy. Following prior work, we use a small decision tree to partition a dataset into k clusters. This enables us to explain each cluster assignment by a short sequence of single-feature thresholds. While larger trees produce more accurate clusterings, they also require more complex explanations. To allow flexibility, we develop a new explainable k-means clustering algorithm, ExKMC, that takes an additional parameter k' ≥ k and outputs a decision tree with k' leaves. We use a new surrogate cost to efficiently expand the tree and to label the leaves with one of k clusters. We prove that as k' increases, the surrogate cost is non-increasing, and hence, we trade explainability for accuracy. Empirically, we validate that ExKMC produces a low cost clustering, outperforming both standard decision tree methods and other algorithms for explainable clustering. Implementation of ExKMC available at https://github.com/navefr/ExKMC.

Citations

• Gradient-based learning applied to document recognition
• Multidimensional binary search trees used for associative searching
• On a Method to Measure Supervised Multiclass Model’s Interpretability: Application to Degradation Diagnosis (Short Paper)
• Explainable k-Means and k-Medians Clustering
• Learning Multiple Layers of Features from Tiny Images

Cited by

• SpEx: A Spectral Approach to Explainable Clustering
• On the price of explainability for some clustering problems
• Near-Optimal Explainable k-Means for All Dimensions
• NetBurst: Event-Centric Forecasting of Bursty, Intermittent Time Series
• Empowering Decision Trees via Shape Function Branching
• Clustering with Tangles: Algorithmic Framework and Theoretical Guarantees

Related

• How to Find a Good Explanation for Clustering?
• Shallow decision trees for explainable k-means clustering
• Nearly-Tight and Oblivious Algorithms for Explainable Clustering
• Explainable k-means. Don't be greedy, plant bigger trees!
• On the price of explainability for some clustering problems