# Explainable Clustering of Mixture Models

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 15 of its 27 references that are in the map.
- First posted on arXiv 3 Nov 2024.

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

- [Kernel Mean Embedding of Distributions: A Review and Beyond](https://mlsanity.com/paper/1605.09522/) (2016)
- [Explainable k-Means and k-Medians Clustering](https://mlsanity.com/paper/2002.12538/) (2020)
- [ExKMC: Expanding Explainable k-Means Clustering](https://mlsanity.com/paper/2006.02399/) (2020)
- [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)
- [Identifiability of Nonparametric Mixture Models and Bayes Optimal Clustering](https://mlsanity.com/paper/1802.04397/) (2018)
- [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)
- [Recovery Guarantees for Kernel-based Clustering under Non-parametric Mixture Models](https://mlsanity.com/paper/2110.09476/) (2021)
- [Random Cuts are Optimal for Explainable k-Medians](https://mlsanity.com/paper/2304.09113/) (2023)
- [The Price of Explainability for Clustering](https://mlsanity.com/paper/2304.09743/) (2023)
- [Kernel KMeans clustering splits for end-to-end unsupervised decision trees](https://mlsanity.com/paper/2402.12232/) (2024)
- [Explaining Kernel Clustering via Decision Trees](https://mlsanity.com/paper/2402.09881/) (2024)

## Abstract (arXiv)

The explainable clustering problem was first posed by Moshkovitz et al. (ICML 2020) and studies how well an axis-aligned decision tree with K leaves can approximate a given clustering. The performance of the tree is measured via the textitprice of explainability, defined as the ratio between the clustering cost of the tree (where every leaf is a cluster) and the optimal cost. Several recent works have given worst-case characterizations of the price of explainability for different cost functions. However, these guarantees are data-agnostic and therefore notoriously pessimistic in practical clustering settings. In this paper, we study explainable clustering from the point of view of mixture models, which allows us to give the first data-dependent bounds on the price of explainability. First, we focus on K-medians clustering of mixture models with subexponential tails. We propose an algorithm that leverages information about the distribution of the data to find better cuts, and prove new upper and lower bounds. Second, we extend our algorithm and the theoretical guarantees it provides to kernel clustering, thereby refining the existing worst-case analysis.