提出可解释聚类新算法，对结构清晰数据实现更优性能。
Explainable Clustering Beyond Worst-Case Guarantees
- 基于混合模型构造独立于数据的轴对齐决策树
- 在良好聚类数据下实现优于最坏情况的聚类代价比
- 适用于需要可解释性且数据结构清晰的场景
我们研究了Moshkovitz等人（ICML 2020）提出的可解释聚类问题。目标是用含K个叶节点的轴对齐决策树拟合最小聚类代价（每个叶节点对应一个簇）。该领域核心理论问题是“可解释性代价”，即树形聚类代价与最优代价之比。已有研究给出了最坏情况下的界：对K-均值问题，该代价比为Θ(log K)。尽管从数据无关视角已解决此问题，但仍有两个关键问题未回答：对结构良好数据能否获得更紧的界？能否信任决策树恢复真实聚类结构？本文在混合模型的统计设定下回答这两个问题。我们证明，在良好聚类数据下确实可获得更优保证。所提算法输入混合模型，在数据无关时间内构造决策树，并将分析扩展至核聚类，得到显著优于现有最坏情况界的新结果。
原文摘要 · Abstract (English)
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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。