Explainable Clustering of Mixture Models

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.

Machine Learning (cs.LG)

arXiv:2411.01576 [cs.LG]

(or arXiv:2411.01576v3 [cs.LG] for this version)

https://doi.org/10.48550/arXiv.2411.01576 Focus to learn more arXiv-issued DOI via DataCite

arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website.

Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them.

Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs.