Recently, due to an increasing interest for transparency in artificial
intelligence, several methods of explainable machine learning have been
developed with the simultaneous goal of accuracy and interpretability by
humans. In this paper, we study a recent framework of explainable clustering
first suggested by Dasgupta et al.~\cite{dasgupta2020explainable}.
Specifically, we focus on the $k$-means and $k$-medians problems and provide
nearly tight upper and lower bounds.
First, we provide an $O(\log k \log \log k)$-approximation algorithm for
explainable $k$-medians, improving on the best known algorithm of
$O(k)$~\cite{dasgupta2020explainable} and nearly matching the known
$\Omega(\log k)$ lower bound~\cite{dasgupta2020explainable}. In addition, in
low-dimensional spaces $d \ll \log k$, we show that our algorithm also provides
an $O(d \log^2 d)$-approximate solution for explainable $k$-medians. This
improves over the best known bound of $O(d \log k)$ for low
dimensions~\cite{laber2021explainable}, and is a constant for constant
dimensional spaces. To complement this, we show a nearly matching $\Omega(d)$
lower bound. Next, we study the $k$-means problem in this context and provide
an $O(k \log k)$-approximation algorithm for explainable $k$-means, improving
over the $O(k^2)$ bound of Dasgupta et al. and the $O(d k \log k)$ bound of
\cite{laber2021explainable}. To complement this we provide an almost tight
$\Omega(k)$ lower bound, improving over the $\Omega(\log k)$ lower bound of
Dasgupta et al. Given an approximate solution to the classic $k$-means and
$k$-medians, our algorithm for $k$-medians runs in time $O(kd \log^2 k )$ and
our algorithm for $k$-means runs in time $ O(k^2 d)$.

本文研究了一个最近提出的可解释聚类框架，专注于 k-medians 和 k-means 问题，并提供了近似算法和上下界。

可解释聚类的近似最紧算法

Almost Tight Approximation Algorithms for Explainable Clustering

Clustering is a popular form of unsupervised learning for geometric data.
Unfortunately, many clustering algorithms lead to cluster assignments that are
hard to explain, partially because they depend on all the features of the data
in a complicated way. To improve interpretability, we consider using a small
decision tree to partition a data set into clusters, so that clusters can be
characterized in a straightforward manner. We study this problem from a
theoretical viewpoint, measuring cluster quality by the $k$-means and
$k$-medians objectives: Must there exist a tree-induced clustering whose cost
is comparable to that of the best unconstrained clustering, and if so, how can
it be found? In terms of negative results, we show, first, that popular
top-down decision tree algorithms may lead to clusterings with arbitrarily
large cost, and second, that any tree-induced clustering must in general incur
an $\Omega(\log k)$ approximation factor compared to the optimal clustering. On
the positive side, we design an efficient algorithm that produces explainable
clusters using a tree with $k$ leaves. For two means/medians, we show that a
single threshold cut suffices to achieve a constant factor approximation, and
we give nearly-matching lower bounds. For general $k \geq 2$, our algorithm is
an $O(k)$ approximation to the optimal $k$-medians and an $O(k^2)$
approximation to the optimal $k$-means. Prior to our work, no algorithms were
known with provable guarantees independent of dimension and input size.

本文提出了一种使用决策树对数据集进行聚类的算法，并探讨了该方法对 k-means 和 k-medians 目标函数的适用性。作者证明了常见的自顶向下决策树算法可能会导致成本任意大的聚类结果，但设计了一种有效的方法使用具有 k 个叶子的树生成可解释的聚类，并对于两个中心点的情况，仅需要一个阈值切割即可实现常数近似。