Over the last few years Explainable Clustering has gathered a lot of
attention. Dasgupta et al. [ICML'20] initiated the study of explainable k-means
and k-median clustering problems where the explanation is captured by a
threshold decision tree which partitions the space at each node using axis
parallel hyperplanes. Recently, Laber et al. [Pattern Recognition'23] made a
case to consider the depth of the decision tree as an additional complexity
measure of interest.
In this work, we prove that even when the input points are in the Euclidean
plane, then any depth reduction in the explanation incurs unbounded loss in the
k-means and k-median cost. Formally, we show that there exists a data set X in
the Euclidean plane, for which there is a decision tree of depth k-1 whose
k-means/k-median cost matches the optimal clustering cost of X, but every
decision tree of depth less than k-1 has unbounded cost w.r.t. the optimal cost
of clustering. We extend our results to the k-center objective as well, albeit
with weaker guarantees.

本文研究可解释 K-means 和 K-median 聚类问题，证明了在欧几里得平面上，解释深度降低会导致聚类成本的无界损失，并将其扩展到 K-center 目标。

可解释聚类中深度减少的不可能性

Impossibility of Depth Reduction in Explainable Clustering

We study the problem of explainable clustering in the setting first
formalized by Dasgupta, Frost, Moshkovitz, and Rashtchian (ICML 2020). A
$k$-clustering is said to be explainable if it is given by a decision tree
where each internal node splits data points with a threshold cut in a single
dimension (feature), and each of the $k$ leaves corresponds to a cluster. We
give an algorithm that outputs an explainable clustering that loses at most a
factor of $O(\log^2 k)$ compared to an optimal (not necessarily explainable)
clustering for the $k$-medians objective, and a factor of $O(k \log^2 k)$ for
the $k$-means objective. This improves over the previous best upper bounds of
$O(k)$ and $O(k^2)$, respectively, and nearly matches the previous $\Omega(\log
k)$ lower bound for $k$-medians and our new $\Omega(k)$ lower bound for
$k$-means. The algorithm is remarkably simple. In particular, given an initial
not necessarily explainable clustering in $\mathbb{R}^d$, it is oblivious to
the data points and runs in time $O(dk \log^2 k)$, independent of the number of
data points $n$. Our upper and lower bounds also generalize to objectives given
by higher $\ell_p$-norms.

提出了一个算法，用于在 $k$-medians 目标和 $k$-means 目标下输出可解释的聚类，与最佳聚类最多相差 $O (\log^2 k)$ 和 $O (k\log^2 k)$ 的因子，算法时间为 $O (dk\log^2 k)$ 。

可解释聚类的近乎紧密且无感知算法

Nearly-Tight and Oblivious Algorithms for Explainable Clustering

Many clustering algorithms are guided by certain cost functions such as the
widely-used $k$-means cost. These algorithms divide data points into clusters
with often complicated boundaries, creating difficulties in explaining the
clustering decision. In a recent work, Dasgupta, Frost, Moshkovitz, and
Rashtchian (ICML 2020) introduced explainable clustering, where the cluster
boundaries are axis-parallel hyperplanes and the clustering is obtained by
applying a decision tree to the data. The central question here is: how much
does the explainability constraint increase the value of the cost function?
Given $d$-dimensional data points, we show an efficient algorithm that finds
an explainable clustering whose $k$-means cost is at most $k^{1 -
2/d}\,\mathrm{poly}(d\log k)$ times the minimum cost achievable by a clustering
without the explainability constraint, assuming $k,d\ge 2$. Taking the minimum
of this bound and the $k\,\mathrm{polylog} (k)$ bound in independent work by
Makarychev-Shan (ICML 2021), Gamlath-Jia-Polak-Svensson (2021), or
Esfandiari-Mirrokni-Narayanan (2021), we get an improved bound of $k^{1 -
2/d}\,\mathrm{polylog}(k)$, which we show is optimal for every choice of
$k,d\ge 2$ up to a poly-logarithmic factor in $k$. For $d = 2$ in particular,
we show an $O(\log k\log\log k)$ bound, improving near-exponentially over the
previous best bound of $O(k\log k)$ by Laber and Murtinho (ICML 2021).

介绍了一种可解释性聚类方法，算法通过应用决策树将数据划分为轴平行超平面聚类，使得聚类边界简单，同时保证聚类代价函数的可解释性约束，聚类的代价至多是比不考虑可解释性约束的情况最小代价增加 $k^{1-2/d}$ 倍，与其他方法的代价上界取最小值可得到 $k^{1-2/d} polylog (k)$ 倍，此为 $k,d ≥ 2$ 下的最优代价上界。

高维情况下近似最优的可解释 k 均值算法

Near-Optimal Explainable $k$-Means for All Dimensions

Recent work on explainable clustering allows describing clusters when the
features are interpretable. However, much modern machine learning focuses on
complex data such as images, text, and graphs where deep learning is used but
the raw features of data are not interpretable. This paper explores a novel
setting for performing clustering on complex data while simultaneously
generating explanations using interpretable tags. We propose deep descriptive
clustering that performs sub-symbolic representation learning on complex data
while generating explanations based on symbolic data. We form good clusters by
maximizing the mutual information between empirical distribution on the inputs
and the induced clustering labels for clustering objectives. We generate
explanations by solving an integer linear programming that generates concise
and orthogonal descriptions for each cluster. Finally, we allow the explanation
to inform better clustering by proposing a novel pairwise loss with
self-generated constraints to maximize the clustering and explanation module's
consistency. Experimental results on public data demonstrate that our model
outperforms competitive baselines in clustering performance while offering
high-quality cluster-level explanations.

本文提出了一种新型的复杂数据聚类算法，利用符号数据进行言语解释，通过最大化模块之间的一致性产生更好的聚类效果和高质量的聚类级别解释，实验结果表明，该模型在聚类性能方面优于竞争对手，并提供高质量的聚类级别解释。