Explainable Clustering Beyond Worst-Case Guarantees
This work addresses the need for more practical and trustworthy explainable clustering methods, offering theoretical improvements for data scientists and practitioners dealing with structured data, though it is incremental as it builds on prior worst-case analyses.
The paper tackles the problem of explainable clustering by analyzing the price of explainability in a statistical mixture model setting, proving that tighter guarantees are possible for well-clustered data and extending results to kernel clustering with improved bounds over worst-case guarantees.
We study the explainable clustering problem first posed by Moshkovitz, Dasgupta, Rashtchian, and Frost (ICML 2020). The goal of explainable clustering is to fit an axis-aligned decision tree with $K$ leaves and minimal clustering cost (where every leaf is a cluster). The fundamental theoretical question in this line of work is the \textit{price of explainability}, defined as the ratio between the clustering cost of the tree and the optimal cost. Numerous papers have provided worst-case guarantees on this quantity. For $K$-medians, it has recently been shown that the worst-case price of explainability is $Θ(\log K)$. While this settles the matter from a data-agnostic point of view, two important questions remain unanswered: Are tighter guarantees possible for well-clustered data? And can we trust decision trees to recover underlying cluster structures? In this paper, we place ourselves in a statistical setting of mixture models to answer both questions. We prove that better guarantees are indeed feasible for well-clustered data. Our algorithm takes as input a mixture model and constructs a tree in data-independent time. We then extend our analysis to kernel clustering, deriving new guarantees that significantly improve over existing worst-case bounds.