Explainable Clustering of Mixture Models

Maximilian Fleissner, Maedeh Zarvandi, Debarghya Ghoshdastidar
Proceedings of the 42nd Conference on Uncertainty in Artificial Intelligence, PMLR 337:1585-1603, 2026.

Abstract

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 \textit{price 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.

Cite this Paper

BibTeX
@InProceedings{pmlr-v337-fleissner26a, title = {Explainable Clustering of Mixture Models}, author = {Fleissner, Maximilian and Zarvandi, Maedeh and Ghoshdastidar, Debarghya}, booktitle = {Proceedings of the 42nd Conference on Uncertainty in Artificial Intelligence}, pages = {1585--1603}, year = {2026}, editor = {Perković, Emilija and Malinsky, Daniel}, volume = {337}, series = {Proceedings of Machine Learning Research}, month = {17--21 Aug}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/v337/main/assets/fleissner26a/fleissner26a.pdf}, url = {https://proceedings.mlr.press/v337/fleissner26a.html}, abstract = {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 \textit{price 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.} }
Endnote
%0 Conference Paper %T Explainable Clustering of Mixture Models %A Maximilian Fleissner %A Maedeh Zarvandi %A Debarghya Ghoshdastidar %B Proceedings of the 42nd Conference on Uncertainty in Artificial Intelligence %C Proceedings of Machine Learning Research %D 2026 %E Emilija Perković %E Daniel Malinsky %F pmlr-v337-fleissner26a %I PMLR %P 1585--1603 %U https://proceedings.mlr.press/v337/fleissner26a.html %V 337 %X 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 \textit{price 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.
APA
Fleissner, M., Zarvandi, M. & Ghoshdastidar, D.. (2026). Explainable Clustering of Mixture Models. Proceedings of the 42nd Conference on Uncertainty in Artificial Intelligence, in Proceedings of Machine Learning Research 337:1585-1603 Available from https://proceedings.mlr.press/v337/fleissner26a.html.

Related Material