The computational complexity of some explainable clustering problems

Let ${\cal X}$ be a finite set of points in $\mathbb{R}^{d}$. We say that a decision tree is standard if each internal node $v$ is associated with a test (cut), specified by a coordinate $i_{v}\in[d]$ and a real value $\theta_{v}$, that partitions the points in ${\cal X}$ that reach $v$ into two sets: those having the coordinate $i_{v}$ smaller than or equal to $\theta_{v}$ and those having it larger than $\theta_{v}$. The leaves of a standard decision tree induce a partition of $\mathbb{R}^{d}$ into axis-aligned boxes and, naturally, a partition of ${\cal X}$ into clusters.

Let $k\geq 2$ be an integer. The clustering problems considered here consist of finding a partition of ${\cal X}$ into $k$ groups, among those that can be induced by a standard decision tree with $k$ leaves, that optimizes a given objective function. For the $k$-means, $k$-medians and $k$-centers cost functions, in addition to the partition, a representative $\mu(C)\in\mathbb{R}^{d}$ for each group $C$ must also be output.

For the $k$-means problem the objective (cost function) to be minimized is the Sum of the Squared Euclidean Distances (SSED) between each point $\mathbf{x}\in{\cal X}$ and the representative of the cluster where $\mathbf{x}$ lies. Mathematically, the cost (SSED) of a partition ${\cal C}=(C_{1},\ldots,C_{k})$ for ${\cal X}$ is given by

For the $k$-medians problem the cost of a partition ${\cal C}=(C_{1},\ldots,C_{k})$ is given by

The $k$-centers problem is also a minimization problem; its cost function for a partition ${\cal C}=(C_{1},\ldots,C_{k})$ is given by

Let $dist:{\cal X}\times{\cal X}\mapsto\mathbb{R}^{+}$ be a distance function. The meximum-spacing problem consists of finding a partition with at least $k$ groups that has maximum spacing, where the spacing $sp({\cal C})$ of a partition ${\cal C}$ is defined as

In contrast to the other criteria, the spacing is an inter-clustering criterion.

We note that an optimal solution of the unrestricted version of any of these problems, in which the decision tree constraint is not enforced, might be a partition that is hard to explain in terms of the input features. Thus, the motivation for using standard decision trees.

For the sake of simplicity, throughout of this text, by explainable clustering we mean a clustering that is obtained via decision trees.

In Section 2, we first show that the problem of building a partition via decision trees that minimizes the $k$-means cost function does not admit an $(1+\epsilon)$-approximation in polynomial time, for some $\epsilon>0$, unless $P=NP$. Then, we show that analogous results hold for both the $k$-median and $k$-centers cost functions. Our results for both the $k$-means and $k$-medians are stronger than the NP-Hardness result established recently by [9] and they formally help to justify the quest for approximation algorithms and/or heuristics for these cost functions.

In Section 3 we propose a polynomial time algorithm that produces an explainable clustering of maximum spacing. As far as we know, this is the first efficient method that produces optimal explainable clustering with respect to some well studied metric.

Our research is inspired by the recent work of [2], where the problem of building explainable clusterings, via standard decision trees, for both the $k$-means and the $k$-medians cost functions are studied. This paper proposes algorithms with provable approximation bounds for building explainable clusterings. In addition, it investigates the price of explainability for these cost functions, which is the unavoidable gap between the cost of the optimal explainable and the optimal unconstrained clustering. Among their results, they showed that the price of explainability for the $k$-means and $k$-median are respectively $O(k^{2})$ and $O(k)$.

Their results were refined/improved by a series of recent papers [4, 5, 7, 8, 6]. Currently, the best upper bound for the $k$-medians is $O(\log k\log\log k)$ [5, 7] while for the $k$-means is $O(k\log k)$ [7]. The study of bounds that depend on the dimension $d$ was initiated in [4], where the authors present an $O(d\log k)$ upper bound for the $k$-medians and an $O(dk\log k)$ upper bound for the $k$-means. These bounds were improved to $O(d\log^{2}d)$ for the $k$-medians [7] and $O(k^{1-2/d}poly(d,\log k))$ [6] for the $k$-means.

The price of explainability was also investigated for other cost functions. In [4], Laber and Murtinho considered the $k$-centers and maximum-spacing cost functions. In [5], Makarychev and Shan considered the $k$-medoids problem ($k$-median with $\ell_{2}$ objective). Finally, in [8], Gamlath et. al addressed $\ell_{p}^{p}$ objectives.

The aforementioned papers, except [4] which also presents experiments, are mainly theoretical. However, there are also a number of papers that propose algorithms (without theoretical guarantees) for building explainable clustering, among them we cite [10, 11, 3].

The computational complexity of building explainable clustering via decision trees for both the $k$-means and the $k$-medians problems is studied in [9]. It is shown that both problems admit polynomial time algorithms when either $k$ or $d$ is constant and they are NP-Complete for arbitrary $k$ and $d$. In addition, they show that an optimal explainable clustering cannot be found in $f(k)\cdot|{\cal X}|^{o(k)}$ time for any computable function $f(\textperiodcentered)$, unless Exponential Time Hypothesis (ETH) fails.

When we turn to standard (non-explainable) clustering, the problems of optimizing the $k$-means, $k$-medians and $k$-centers cost functions are APX-Hard [12, 13, 14] and all of them admit polynomial time algorithms with constant approximation [15, 16, 17]. With regards to the spacing cost function, the single-link algorithm, a very popular algorithm to build hierarchical clustering, produces a partition with maximum spacing [18, Chapter 4].

We start by recalling some basic definitions and facts that are useful for studying the hardness of optimization problems (see, e.g., [19, chapter 29]).

Given a minimization problem $\mathbb{A}$ and a parameter $\epsilon>0$ we define the $\epsilon$-Gap-$\mathbb{A}$ problem as the problem of deciding for an instance $I$ of $\mathbb{A}$ and a parameter $k$ whether: (i) $I$ admits a solution of value at most $k$; or (ii) every solution of $I$ have value at least $(1+\epsilon)k.$ In such a gap decision problem it is tacitly assumed that the instances are either of type (i) or of type (ii).

We will use the following definition of a gap-preserving reduction.

We will now specialize the above definitions for restricted variants of the problem of finding a minimum vertex cover in a graph and for our clustering problems.

The $\epsilon$-Gap-MinVC-3B-TF (gap) decision problem has a similar definition, the only differences is that, in addition of being triangle-free, the graphs are required to be 3-bounded, that is, all of its vertexes have degree at most 3.

The NP-Hardness of $\epsilon$-Gap-MinVC-B-TF and $\epsilon$-Gap-MinVC-3B-TF were established in [13] and [20], respectively.

The $\eta$-Gap-Explainable-kmedians and $\eta$-Gap-Explainable-kcenters decision problems are analogously defined.

To prove the hardness for the $k$-means we use a gap-preserving reduction from the $\epsilon$-Gap-MinVC-B-TF decision problem. To handle both the $k$-centers and $k$-medians, we use the $\epsilon$-Gap-MinVC-3B-TF decision problem.

Our reductions have some common ingredients that we explain here. For all of them, given a graph $G=(V,E)$, where $V=\{1,\ldots,n\}$, we build an instance of the clustering problem under consideration by mapping every edge $e$ in $E$ onto a point $\mathbf{v}^{e}=(v^{e}_{1},\ldots,v^{e}_{n})$ in $\{0,1\}^{n}$ where $v^{e}_{i}=1$ if vertex $i$ is incident on $e$ and $v^{e}_{i}=0$ otherwise. This is exactly the mapping proposed in [13] to establish that the (standard) $k$-means problem is APX-Hard. We use ${\cal X}_{G}:=\{v^{e}|e\in E\}$ to denote the input of the resulting clustering instance.

Let $S=\{i_{1},i_{2},\ldots,i_{k}\}$ be a cover of size $k$ for $G$, where each $i_{j}$ is an integer in $[n]$ and $i_{j}<i_{j+1}$. We define ${\cal C}_{S}=(E_{1},\ldots,E_{k})$ as the $k$-clustering induced by $S$ on the points in ${\cal X}_{G}$, where the group $E_{j}$ includes all points $\mathbf{v}$ that simultaneously satisfy: its component $i_{j}$ is $1$ and its component $i_{j^{\prime}}$, for $j^{\prime}<j$, is 0.

We prove that the problem of finding an explainable clustering with minimum $k$-means cost function is hard to approximate. The reduction employed here is the one used by [13] to show that it is hard to find an $(1+\epsilon)$-approximation for the $k$-means cost function. The extra ingredient in our proof is the construction of an explainable clustering ${\cal C}_{S}$ from a vertex cover $S$ that was described in the previous section.

We prove that the problem of finding an explainable clustering with minimum $k$-medians cost function is hard to approximate. We show a gap preserving reduction from the $\epsilon$-Gap-MinVC-3B-TF problem to the $\eta$-Gap-Explainable-kmedians problem.

The following well-known fact will be useful.

The following lemma will be also useful.

In this section we discuss the computational complexity of minimizing the $k$-centers cost function. We show a gap preserving reduction from the $\epsilon$-Gap-MinVC-3B-TF problem to the $\eta$-Gap-Explainable-kcenters problem.