* (114) C. Bonanno, A. Cappelli, M. Kompaniets, S. Okuda, and K. J. Wiese, “Benchmarking the Ising Universality Class in $3\leqslant d<4$ dimensions,” SciPost Phys. 14 (2023) 135, arXiv:2210.03051 [hep-th].
  * (115) J. Maldacena and A. Zhiboedov, “Constraining Conformal Field Theories with A Higher Spin Symmetry,” J.Phys. A46 (2013) 214011, arXiv:1112.1016 [hep-th].
  * (116) M. Hogervorst, S. Rychkov, and B. C. van Rees, “Truncated conformal space approach in d dimensions: A cheap alternative to lattice field theory?,” Phys. Rev. D 91 (2015) 025005, arXiv:1409.1581 [hep-th].
  * (117) M. Hogervorst, S. Rychkov, and B. C. van Rees, “Unitarity violation at the Wilson-Fisher fixed point in 4-$\epsilon$ dimensions,” Phys. Rev. D 93 no. 12, (2016) 125025, arXiv:1512.00013 [hep-th].
  * (118) J. Golden and M. F. Paulos, “No unitary bootstrap for the fractal Ising model,” JHEP 03 (2015) 167, arXiv:1411.7932 [hep-th].
  * (119) G. P. Korchemsky, “On level crossing in conformal field theories,” JHEP 03 (2016) 212, arXiv:1512.05362 [hep-th].
  * (120) C. Behan, “Conformal manifolds: ODEs from OPEs,” JHEP 03 (2018) 127, arXiv:1709.03967 [hep-th].
  * (121) W. Janke and R. Villanova, “Three-dimensional three state Potts model revisited with new techniques,” Nucl. Phys. B 489 (1997) 679–696, arXiv:hep-lat/9612008.
  * (122) S. Rychkov, “Open Problems in Conformal Bootstrap. Problem 1: Bootstrap proof of first-order transitions?,”. 2020.
  * (123) J. Lee and J. M. Kosterlitz, “Three-dimensional q-state Potts model: Monte Carlo study near $q=3$,” Phys. Rev. B 43 (1991) 1268–1271.
  * (124) V. Gorbenko, S. Rychkov, and B. Zan, “Walking, Weak first-order transitions, and Complex CFTs,” JHEP 10 (2018) 108, arXiv:1807.11512 [hep-th].
  * (125) N. Su, “Skydiving to Bootstrap Islands: an Algorithm for Dynamically Constrained SDP,”. Talk at the 2022 Collaboration on the Nonperturbative Bootstrap Annual Meeting (November 10-11, 2022).
  * (126) A. Liu, D. Simmons-Duffin, N. Su, and B. C. van Rees, “Skydiving to Bootstrap Islands,” arXiv:2307.13046 [hep-th].
  * (127) N. Su, “The Hybrid Bootstrap,” arXiv:2202.07607 [hep-th].
  * (128) S. Hellerman, D. Orlando, S. Reffert, and M. Watanabe, “On the CFT Operator Spectrum at Large Global Charge,” JHEP 12 (2015) 071, arXiv:1505.01537 [hep-th].
  * (129) A. Monin, D. Pirtskhalava, R. Rattazzi, and F. K. Seibold, “Semiclassics, Goldstone Bosons and CFT data,” JHEP 06 (2017) 011, arXiv:1611.02912 [hep-th].
  * (130) S. M. Chester and N. Su, “Bootstrapping Deconfined Quantum Tricriticality,” arXiv:2310.08343 [hep-th].
  * (131) C. Behan, L. Di Pietro, E. Lauria, and B. C. Van Rees, “Bootstrapping boundary-localized interactions,” JHEP 12 (2020) 182, arXiv:2009.03336 [hep-th].
  * (132) C. Behan, L. Di Pietro, E. Lauria, and B. C. van Rees, “Bootstrapping boundary-localized interactions II. Minimal models at the boundary,” JHEP 03 (2022) 146, arXiv:2111.04747 [hep-th].
  * (133) J. Rong and J. Zhu, “On the $\phi$3 theory above six dimensions,” JHEP 04 (2020) 151, arXiv:2001.10864 [hep-th].
  * (134) Y. Nakayama, “Is there supersymmetric Lee–Yang fixed point in three dimensions?,” Int. J. Mod. Phys. A 36 no. 24, (2021) 2150176, arXiv:2104.13570 [hep-th].
  * (135) D. Poland, V. Prilepina, and P. Tadić, “The five-point bootstrap,” JHEP 10 (2023) 153, arXiv:2305.08914 [hep-th].
  * (136) A. Bissi, A. Manenti, and A. Vichi, “Bootstrapping mixed correlators in $\mathcal{N}$ = 4 super Yang-Mills,” JHEP 05 (2021) 111, arXiv:2010.15126 [hep-th].
  * (137) A. Gimenez-Grau and P. Liendo, “Bootstrapping line defects in $\mathcal{N}=2$ theories,” JHEP 03 (2020) 121, arXiv:1907.04345 [hep-th].
  * (138) D. J. Binder, S. M. Chester, M. Jerdee, and S. S. Pufu, “The 3d $\mathcal{N}$ = 6 bootstrap: from higher spins to strings to membranes,” JHEP 05 (2021) 083, arXiv:2011.05728 [hep-th].
  * (139) N. B. Agmon, S. M. Chester, and S. S. Pufu, “The M-theory Archipelago,” JHEP 02 (2020) 010, arXiv:1907.13222 [hep-th].
  * (140) Y.-H. Lin, D. Meltzer, S.-H. Shao, and A. Stergiou, “Bounds on Triangle Anomalies in (3+1)$d$,” arXiv:1909.11676 [hep-th].
  * (141) A. Gimenez-Grau and P. Liendo, “Bootstrapping Coulomb and Higgs branch operators,” JHEP 01 (2021) 175, arXiv:2006.01847 [hep-th].
  * (142) A. Bissi, F. Fucito, A. Manenti, J. F. Morales, and R. Savelli, “OPE coefficients in Argyres-Douglas theories,” JHEP 06 (2022) 085, arXiv:2112.11899 [hep-th].
  * (143) P. Liendo, C. Meneghelli, and V. Mitev, “Bootstrapping the half-BPS line defect,” JHEP 10 (2018) 077, arXiv:1806.01862 [hep-th].
  * (144) A. Cavaglià, N. Gromov, J. Julius, and M. Preti, “Integrability and conformal bootstrap: One dimensional defect conformal field theory,” Phys. Rev. D 105 no. 2, (2022) L021902, arXiv:2107.08510 [hep-th].
  * (145) A. Cavaglià, N. Gromov, J. Julius, and M. Preti, “Bootstrability in defect CFT: integrated correlators and sharper bounds,” JHEP 05 (2022) 164, arXiv:2203.09556 [hep-th].
  * (146) V. Niarchos, C. Papageorgakis, P. Richmond, A. G. Stapleton, and M. Woolley, “Bootstrability in Line-Defect CFT with Improved Truncation Methods,” arXiv:2306.15730 [hep-th].
  * (147) M. Picco, S. Ribault, and R. Santachiara, “On four-point connectivities in the critical 2d Potts model,” SciPost Phys. 7 no. 4, (2019) 044, arXiv:1906.02566 [hep-th].
  * (148) R. Nivesvivat and S. Ribault, “Logarithmic CFT at generic central charge: from Liouville theory to the $Q$-state Potts model,” SciPost Phys. 10 no. 1, (2021) 021, arXiv:2007.04190 [hep-th].
  * (149) L. Grans-Samuelsson, R. Nivesvivat, J. L. Jacobsen, S. Ribault, and H. Saleur, “Global symmetry and conformal bootstrap in the two-dimensional $O(n)$ model,” SciPost Phys. 12 no. 5, (2022) 147, arXiv:2111.01106 [hep-th].
  * (150) S. Ribault, “Diagonal fields in critical loop models,” SciPost Phys. Core 6 (2023) 020, arXiv:2209.09706 [hep-th].
  * (151) M. F. Paulos and Z. Zheng, “Bounding 3d CFT correlators,” JHEP 04 (2022) 102, arXiv:2107.01215 [hep-th].
  * (152) N. Afkhami-Jeddi, “Conformal bootstrap deformations,” JHEP 09 (2022) 225, arXiv:2111.01799 [hep-th].
  * (153) W. Landry. https://github.com/davidsd/sdpb/tree/outer.
  * (154) K. Ghosh and Z. Zheng, “Numerical Conformal bootstrap with Analytic Functionals and Outer Approximation,” arXiv:2307.11144 [hep-th].
  * (155) G. Kántor, V. Niarchos, and C. Papageorgakis, “Conformal bootstrap with reinforcement learning,” Phys. Rev. D 105 no. 2, (2022) 025018, arXiv:2108.09330 [hep-th].
  * (156) U. A. Luviano Valenzuela, Stochastic Minimization in the Conformal Bootstrap.  PhD thesis, SISSA, Trieste, 2022.
  * (157) A. Laio, U. L. Valenzuela, and M. Serone, “Monte Carlo approach to the conformal bootstrap,” Phys. Rev. D 106 no. 2, (2022) 025019, arXiv:2206.05193 [hep-th].
  * (158) Y.-H. Lin and S.-H. Shao, “Anomalies and Bounds on Charged Operators,” Phys. Rev. D100 no. 2, (2019) 025013, arXiv:1904.04833 [hep-th].
  * (159) Y.-H. Lin and S.-H. Shao, “$\mathbb{Z}_{N}$ symmetries, anomalies, and the modular bootstrap,” Phys. Rev. D 103 no. 12, (2021) 125001, arXiv:2101.08343 [hep-th].
  * (160) Y.-H. Lin and S.-H. Shao, “Bootstrapping noninvertible symmetries,” Phys. Rev. D 107 no. 12, (2023) 125025, arXiv:2302.13900 [hep-th].
  * (161) A. Grigoletto and P. Putrov, “Spin-Cobordisms, Surgeries and Fermionic Modular Bootstrap,” Commun. Math. Phys. 401 no. 3, (2023) 3169–3245, arXiv:2106.16247 [hep-th].
  * (162) A. Grigoletto, “Anomalies of fermionic CFTs via cobordism and bootstrap,” arXiv:2112.01485 [hep-th].
  * (163) L.-Y. Chiang, T.-C. Huang, Y.-t. Huang, W. Li, L. Rodina, and H.-C. Weng, “The Geometry of the Modular Bootstrap,” arXiv:2308.11692 [hep-th].
  * (164) A. L. Fitzpatrick and W. Li, “Improving Modular Bootstrap Bounds with Integrality,” arXiv:2308.08725 [hep-th].
  * (165) Y.-T. Huang, W. Li, and G.-L. Lin, “The geometry of optimal functionals,” arXiv:1912.01273 [hep-th].
  * (166) J.-B. Bae, S. Lee, and J. Song, “Modular Constraints on Superconformal Field Theories,” JHEP 01 (2019) 209, arXiv:1811.00976 [hep-th].
  * (167) J.-B. Bae, “Constraining Two dimensional CFTs with Modular Invariance,” PoS ICHEP2018 (2019) 318.
  * (168) T. Hartman, D. Mazáč, and L. Rastelli, “Sphere Packing and Quantum Gravity,” JHEP 12 (2019) 048, arXiv:1905.01319 [hep-th].
  * (169) N. Benjamin and Y.-H. Lin, “Lessons from the Ramond sector,” SciPost Phys. 9 no. 5, (2020) 065, arXiv:2005.02394 [hep-th].
  * (170) N. Benjamin and C.-H. Chang, “Scalar modular bootstrap and zeros of the Riemann zeta function,” JHEP 11 (2022) 143, arXiv:2208.02259 [hep-th].
  * (171) S. Collier, D. Mazac, and Y. Wang, “Bootstrapping boundaries and branes,” JHEP 02 (2023) 019, arXiv:2112.00750 [hep-th].
  * (172) N. Afkhami-Jeddi, H. Cohn, T. Hartman, D. de Laat, and A. Tajdini, “High-dimensional sphere packing and the modular bootstrap,” JHEP 12 (2020) 066, arXiv:2006.02560 [hep-th].
  * (173) R. A. Lanzetta and L. Fidkowski, “Bootstrapping Lieb-Schultz-Mattis anomalies,” Phys. Rev. B 107 no. 20, (2023) 205137, arXiv:2207.05092 [cond-mat.str-el].
  * (174) J. Bonifacio and K. Hinterbichler, “Bootstrap Bounds on Closed Einstein Manifolds,” JHEP 10 (2020) 069, arXiv:2007.10337 [hep-th].
  * (175) J. Bonifacio, “Bootstrap bounds on closed hyperbolic manifolds,” JHEP 02 (2022) 025, arXiv:2107.09674 [hep-th].
  * (176) P. Kravchuk, D. Mazac, and S. Pal, “Automorphic Spectra and the Conformal Bootstrap,” arXiv:2111.12716 [hep-th].
  * (177) J. Bonifacio, “Bootstrapping closed hyperbolic surfaces,” JHEP 03 (2022) 093, arXiv:2111.13215 [hep-th].
  * (178) J. Bonifacio, D. Mazac, and S. Pal, “Spectral Bounds on Hyperbolic 3-Manifolds: Associativity and the Trace Formula,” arXiv:2308.11174 [math.SP].
  * (179) E. Gesteau, S. Pal, D. Simmons-Duffin, and Y. Xu, “Bounds on spectral gaps of Hyperbolic spin surfaces,” arXiv:2311.13330 [math.SP].
  * (180) M. Kruczenski, J. Penedones, and B. C. van Rees, “Snowmass White Paper: S-matrix Bootstrap,” arXiv:2203.02421 [hep-th].
  * (181) P. D. Anderson and M. Kruczenski, “Loop Equations and bootstrap methods in the lattice,” Nucl. Phys. B 921 (2017) 702–726, arXiv:1612.08140 [hep-th].
  * (182) V. Kazakov and Z. Zheng, “Bootstrap for lattice Yang-Mills theory,” Phys. Rev. D 107 no. 5, (2023) L051501, arXiv:2203.11360 [hep-th].
  * (183) M. Cho, B. Gabai, Y.-H. Lin, V. A. Rodriguez, J. Sandor, and X. Yin, “Bootstrapping the Ising Model on the Lattice,” arXiv:2206.12538 [hep-th].
  * (184) H. W. Lin, “Bootstraps to strings: solving random matrix models with positivity,” JHEP 06 (2020) 090, arXiv:2002.08387 [hep-th].
  * (185) V. Kazakov and Z. Zheng, “Analytic and numerical bootstrap for one-matrix model and “unsolvable” two-matrix model,” JHEP 06 (2022) 030, arXiv:2108.04830 [hep-th].
  * (186) X. Han, S. A. Hartnoll, and J. Kruthoff, “Bootstrapping Matrix Quantum Mechanics,” Phys. Rev. Lett. 125 no. 4, (2020) 041601, arXiv:2004.10212 [hep-th].
  * (187) H. W. Lin, “Bootstrap bounds on D0-brane quantum mechanics,” JHEP 06 (2023) 038, arXiv:2302.04416 [hep-th].
  * (188) N. Afkhami-Jeddi, T. Hartman, and A. Tajdini, “Fast Conformal Bootstrap and Constraints on 3d Gravity,” JHEP 05 (2019) 087, arXiv:1903.06272 [hep-th].
  * (189) M. F. Paulos and B. Zan, “A functional approach to the numerical conformal bootstrap,” JHEP 09 (2020) 006, arXiv:1904.03193 [hep-th].
  * (190) K. Ghosh, A. Kaviraj, and M. F. Paulos, “Charging up the functional bootstrap,” JHEP 10 (2021) 116, arXiv:2107.00041 [hep-th].
  * (191) S. El-Showk, M. F. Paulos, D. Poland, S. Rychkov, D. Simmons-Duffin, and A. Vichi, “Solving the 3D Ising Model with the Conformal Bootstrap,” Phys. Rev. D 86 (2012) 025022, arXiv:1203.6064 [hep-th].


# On the price of explainability for some clustering problems

Eduardo Sany Laber
PUC-Rio, Brazil
<EMAIL_ADDRESS>Lucas Murtinho
PUC-Rio, Brazil
<EMAIL_ADDRESS>
###### Abstract

The price of explainability for a clustering task can be defined as the
unavoidable loss, in terms of the objective function, if we force the final
partition to be explainable.

Here, we study this price for the following clustering problems: $k$-means,
$k$-medians, $k$-centers and maximum-spacing. We provide upper and lower
bounds for a natural model where explainability is achieved via decision
trees. For the $k$-means and $k$-medians problems our upper bounds improve
those obtained by [Moshkovitz et. al, ICML 20] for low dimensions.

Another contribution is a simple and efficient algorithm for building
explainable clusterings for the $k$-means problem. We provide empirical
evidence that its performance is better than the current state of the art for
decision-tree based explainable clustering.

##  1 Introduction

Machine learning models and algorithms have been used in a number of systems
that take decisions that affect our lives. Thus, explainable methods are
desirable so that people are able to have a better understanding of their
behavior, which allows for comfortable use of these systems or, eventually,
the questioning of their applicability.

Although most of the work on the field of explainable machine learning has
been focusing on supervised learning [31, 23, 34], there has recently been
some effort to devise explainable methods for unsupervised learning tasks, in
particular, for clustering [26, 6]. We investigate the framework discussed by
[26], where an explainable clustering is given by a partition, induced by the
leaves of a decision tree, that optimizes some predefined objective function.

Figure 1 shows a clustering with three groups induced by a decision tree with
$3$ leaves. As an example, the blue cluster can be explained as the set of
points that satisfy Feature 1 $\leq 70$ and Feature 2 $>40$. Simple
explanations as this one are usually not available for the partitions produced
by popular methods such as the Lloyd’s algorithm for the $k$-means problem.

In order to achieve explainability, one may be forced to accept some loss in
terms of the quality of the chosen objective function (e.g. sum of squared
distances). In this sense, explainability has its price. [26] presents
theoretical bounds on this price for the $k$-medians and the $k$-means
objective functions.

Here, we expand on their work by presenting new bounds for these objectives
and also providing nearly tight bounds for two other goals that arise in
relevant clustering problems, namely, the $k$-centers and the maximum-spacing
problems. We note that the objective for the latter is the one optimized by
the widely known Single-Linkage method, employed for hierarchical clustering.
We also give a more practice-oriented contribution by devising and evaluating
a simple and efficient algorithm for building explainable clusterings for the
$k$-means problem.

###  1.1 Problem definition

Let ${\cal X}$ be a set of $n$ 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 $k$-means, $k$-medians and $k$-centers, 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

$cost({\cal C})=\sum_{i=1}^{k}\sum_{\mathbf{x}\in
C_{i}}||\mathbf{x}-\mu(C_{i})||_{2}^{2}.$

The $k$-medians and the $k$-centers problems are also minimization problems.
For the former, the cost of a partition ${\cal C}=(C_{1},\ldots,C_{k})$ is
given by

$cost({\cal C})=\sum_{i=1}^{k}\sum_{\mathbf{x}\in
C_{i}}||\mathbf{x}-\mu(C_{i})||_{1},$

while for the latter it is given by

$cost({\cal C})=\max_{i=1,\ldots,k}\max_{\mathbf{x}\in
C_{i}}\\{||\mathbf{x}-\mu(C_{i})||_{2}\\}.$

The maximum-spacing problem is a maximization problem for which the objective
to be maximized is the spacing $sp({\cal C})$ of a partition ${\cal C}$,
defined as

$sp({\cal C})=\min\\{||\mathbf{x}-\mathbf{y}||_{2}:\mathbf{x}\mbox{ and
}\mathbf{y}\mbox{ lie in distinct groups of ${\cal C}$}\\}$

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 decision trees.

Along the lines of [26], we define the price of explainability $\rho({\cal
P})$ for a clustering problem ${\cal P}$, with a minimization objective
function, as

$\rho({\cal P})=\max_{I}\left\\{\frac{OPT_{exp}(I)}{OPT_{unr}(I)}\right\\},$

where $I$ runs over all instances of ${\cal P}$; $OPT_{exp}(I)$ is the cost of
an optimal explainable clustering (via standard decision trees) for instance
$I$ and $OPT_{unr}(I)$ is the cost of an optimal unrestricted clustering for
$I$. If ${\cal P}$ has a maximization objective function, then $\rho({\cal
P})$ is defined as

$\rho({\cal P})=\max_{I}\left\\{\frac{OPT_{unr}(I)}{OPT_{exp}(I)}\right\\}.$

###  1.2 Our Contributions

We provide bounds on the price of explainability as a function of the
parameters $k,d$ and $n$ for the aforementioned objective functions. These
objectives cover a spectrum that includes both intra- and inter-clustering
criteria as well as worst-case and average-case measures.

First, we address the $k$-centers problem. We show that

$\rho(k\mbox{-centers})\in\left\\{\begin{array}[]{ll}\Omega(k^{1-1/d}),&\mbox{
if }d\leq\frac{\ln k}{\ln\ln k}\\\
\Omega\left(\sqrt{d}\cdot\frac{k\cdot\sqrt{\ln\ln
k}}{\ln^{1.5}k}\right),&\mbox{ otherwise}\end{array}\right.$

and that $\rho(k\mbox{-centers})$ is $O(\sqrt{d}k^{1-1/d})$. Our bounds are
tight, up to constant factors, when $d$ is a constant. For an arbitrary $d$,
there is only a polylogarithmic gap in $k$ between the upper and the lower
bounds. The magnitude of this gap is exponentially smaller than that of these
bounds.

For the $k$-medians it is known that the price of explainability is $O(k)$ and
$\Omega(\log k)$ [26]. We contribute to the state of the art by showing that
$O(d\log k)$ is also an upper bound – an exponential improvement for constant
dimensions. The upper bound follows from an interesting connection with the
literature of binary searching in the presence of non-uniform testing costs
[8, 20].

For the $k$-means problem, we also improve, for low dimensions, the $O(k^{2})$
bound from [26] since we prove that $\rho(k\mbox{-means})$ is $O(kd\log k)$.
Still, for the $k$-means problem, we also give a more practice-oriented
contribution by devising and evaluating a simple and efficient greedy
algorithm. Our method outperformed the IMM method from [26] on an empirical
study involving 10 real datasets. It should be noticed that IMM is a strong
baseline since it got the best results against 5 other competitors on the same
datasets according to [12, 15].

Finally, for maximum-spacing we provide a tight bound by showing that the
price of explainability is $\Theta(n-k)$. The lower bound is particularly
interesting since it shows that this objective function is bad for guiding
explainable clustering, losing much more than the other considered objectives
in the worst-case.

To derive our upper bounds, we analyze polynomial-time algorithms that start
with an optimal $k$-clustering and transform it into an explainable one. The
unrestricted versions of all the problems considered here, except for the
maximum-spacing problem, are NP-Hard [24, 2]. However, all of them admit
polynomial-time algorithms with constant approximation [35, 18] and, hence, if
we start with the partitions given by them, instead of the optimal ones, we
obtain efficient algorithms with provable approximation guarantees. These
guarantees are exactly the upper bounds that we prove on the price of
explainability.

We believe that our results are helpful for the construction of explainable
clustering solutions as well as for guiding the choice of an objective
function when explainability is required.

###  1.3 Related Work

Our research is inspired by the recent work of [26], where they propose an
algorithm, namely IMM, for building explainable clusterings, via standard
decision trees, for both the $k$-means and the $k$-medians problems. At each
node IMM selects the cut that minimizes the number of points separated from
their representatives in a reference clustering. Our approach for these
problems, while similar, uses a significantly different strategy to build the
final decision tree, based on trees that look at a single dimension of the
data. Moreover, as mentioned before, our algorithms provide better upper
bounds for low dimensions.

Decision trees have long been associated to hierarchical agglomerative
clustering (HAC), which produces a hierarchy of clusters that is usually
represented by a dendrogram. Examples of models that explicitly use decision
trees for HAC include [13, 9, 7, 4]. To our knowledge, the use of decision
trees for non-hierarchical clustering was first suggested in [21], in which a
standard classification tree is used to identify dense and sparse regions of
data. In [14], unsupervised binary trees are also used to create interpretable
clusters. More recently, an approach was presented in [6] using optimal
classification trees [5], which are built in a single step by solving a mixed-
integer optimization problem. For numerical databases, [22] presents a
decision approach that decides on a split based on both the compactness of
clusters and the separation between them.

The regions of space defined by decision-tree clustering will be hyper-
rectangles (some of them may also be half-spaces if the overall region of
interest is unbounded). Other approaches towards building hyper-rectangular
clusters can be found in [29], with a generative model, and [11], with a
discriminative one. Both models allow for probabilistic (soft) clustering, and
[11] allows for incorporating previous knowledge to the model, but neither one
guarantees that the resulting clusters can be represented by decision trees.

The main reason for using a (short) decision tree to build clusters is that
the results of such algorithms are easily interpretable. Other avenues towards
interpretable clustering have been explored in recent years. The technique
presented in [30] is based on the information-theoretic concept of minimum
description length. In [33], a tunable parameter (the fraction of elements in
a cluster that share the same feature value) leverages the tradeoff between
clustering performance and interpretability. The same tradeoff is explored in
[15] by relaxing the requirement from [26] that the explainable clustering
should be induced by a tree with no more than $k$ leafs. In [17], a feature
selection model from [16] is used for clustering interpretation in the field
of wealth management compliance. [19] uses a two-step approach, rewriting
$k$-means clustering models as neural networks and applying to these networks
techniques for interpreting supervised learning models. More information
regarding explainable clustering may be found in [10, 3].

Of all the works mentioned in this section, only [26] presents approximation
guarantees with respect to the optimal unrestricted (i.e., potentially
uninterpretable) solution. Two algorithms from [33] also have an approximation
guarantee, but with respect to the optimal restricted (interpretable)
solution, and the definition of interpretability in that work is quite
different than ours (interpretable clusters are therein defined as those in
which a given proportion of points share the same value for a predefined
feature of interest).

Explainability and interpretability are topics of growing interest in the
machine learning community [31, 23, 1, 32, 27, 25]. While there has been some
focus on what [26] calls post-modeling explainability, or the ability to
explain the output of a black-box model [31, 23, 19], the practice has also
been criticized in contrast with pre-modelling explainability, or the use of
interpretable models to begin with [32]. Our present work and [26] may be
considered a middle-of-the-road approach, as the end result is a fully
interpretable model (instead of, for instance, a model for locally
interpreting the original model, or for explaining individual predictions)
based on the output from a potentially black-box model.

##  2 On the Price of Explainability for the $k$-centers problem

In this section we address the $k$-centers problem. We first present a lower
bound by constructing an instance for which the price of explainability is
high.

###  2.1 Lower Bound

Let $p\leq\min\\{d,\log_{3}k\\}$ be a positive integer whose exact value will
be defined later in the analysis and let $b$ be the largest integer for which
$b^{p}\leq k$. Note that $b\geq 3$. Moreover, let $k^{\prime}=b^{p}$.

Our instance $I$ has $k+k^{\prime}\cdot 2d$ points. We first discuss how to
construct the $k$ points, referred as centers, that will be set as
representatives in an unrestricted $k$-clustering for $I$ that has a low cost.
The first $k^{\prime}$ centers will be obtained from the representation of the
numbers $0,\ldots,k^{\prime}-1$ in base $b$ while the remaining $k-k^{\prime}$
centers will be located sufficiently far from the others so that they will be
isolated in the low-cost $k$-clustering for $I$. Let
$\mathbf{c}^{0},\ldots,\mathbf{c}^{k^{\prime}-1}$ be the first $k^{\prime}$
centers.

For a number $i\in[k^{\prime}-1]$ let $(i_{p-1},\ldots,i_{0})_{b}$ be its
representation in base $b$. For $j\in[d]$, the value of the $j$-th component
of center $\mathbf{c}^{i}$ is obtained by applying $(j-1)$ times a circular
shift on $(i_{p-1},\ldots,i_{0})_{b}$. The values of the remaining $d-p$
components of $\mathbf{c}^{i}$ are obtained by copying the $p$ first values
$d/p$ times so that $c^{i}_{j}=c^{i}_{j^{\prime}}$ if $(j-j^{\prime})\mod
p=0$.

As an example, if $b=3$, $p=3$ and $d=9$ then
$\mathbf{c}^{14}=(14,22,16,14,22,16,14,22,16)$. In fact, since
$14=(1,1,2)_{3}$ we have that $c^{14}_{1}=(1,1,2)_{3}=14$;
$c^{14}_{2}=(2,1,1)_{3}=22$ and $c^{14}_{3}=(1,2,1)_{3}=16$. The values of
$c^{14}_{4},\ldots,c^{14}_{9}$ are obtained by repeating the first 3 values.

The following observation is useful for our analysis.

######  Fact 1.

For every $\ell\in[p]$, the values of the $\ell$-th coordinate of the
$k^{\prime}$ first centers are a permutation of the integers
$0,\ldots,k^{\prime}-1$.

The remaining $k-k^{\prime}$ centers, as mentioned above, should be far from
each other and also far away from the $k^{\prime}$ first centers. We can
achieve that by setting $\mathbf{c}^{i}=k^{i}\mathbf{1}$ for all
$i>k^{\prime}-1$, where $\mathbf{1}$ is the unit vector in $\mathbb{R}^{d}$.

The next lemma gives a lower bound on the distance between any two centers.

######  Lemma 1.

For any two centers $\mathbf{c}^{i}$ and $\mathbf{c}^{j}$,

$||\mathbf{c}^{i}-\mathbf{c}^{j}||_{2}\geq\sqrt{\lfloor
d/p\rfloor}\cdot(b^{p-1}/2).$

###### Proof.

If one of the two centers is not among the $k^{\prime}$ first centers the
result clearly holds. Thus, we assume that $i,j\leq k^{\prime}-1$.

It is enough to show that there is $\ell\in[p]$ for which
$|c^{i}_{\ell}-c^{j}_{\ell}|\geq b^{p-1}/2$. In fact, if this inequality holds
for some $\ell$ then $|c^{i}_{\ell^{\prime}}-c^{j}_{\ell^{\prime}}|\geq
b^{p-1}/2$ for each $\ell^{\prime}$ that is congruent to $\ell$ modulo $p$.
Since there are $\lfloor d/p\rfloor$ of them, due to our construction, we get
the desired bound.

Let $i=(i_{p-1},\ldots,i_{0})_{b}$ and $j=(j_{p-1},\ldots,j_{0})_{b}$ be the
representations of $i$ and $j$ in base $b$, respectively. Let $f$ be such that
$|i_{f}-j_{f}|$ is maximum.

Thus, the difference between $\mathbf{c}^{i}$ and $\mathbf{c}^{j}$ in the
coordinate $[(f+1)\mod p]+1$ is at least

$|i_{f}-j_{f}|\cdot\left(b^{p-1}-\sum_{g=0}^{p-2}b^{g}\right)\geq b^{p-1}/2,$

where the last inequality holds because $|i_{f}-j_{f}|\geq 1$ and $b\geq 3$. ∎

Now, we define the remaining points of instance $I$.

For each of the first $k^{\prime}$ centers we create $2d$ associated points:
$\mathbf{x}^{i,1},\ldots,\mathbf{x}^{i,2d}$. For $j=1,\ldots,d$, the point
$\mathbf{x}^{i,2j-1}$ is identical to $\mathbf{c}^{i}$ in all coordinates but
on the $j$-th one, in which its value is $c^{i}_{j}-3/4$. Similarly, the point
$\mathbf{x}^{i,2j}$ is identical to $\mathbf{c}^{i}$ in all coordinates but in
the $j$-th one, in which its value is $c^{i}_{j}+3/4$. By considering the
$k$-clustering for $I$ where the $k$ representatives are the $k$ centers
$\mathbf{c}^{0},\ldots,\mathbf{c}^{k-1}$ and each point $\mathbf{x}^{i,j}$
lies in the group of $\mathbf{c}^{i}$, we obtain the following proposition.

######  Proposition 1.

There exists an unrestricted $k$-clustering for instance $I$ with cost $3/4$.

Now we analyse the cost of an optimal explainable clustering for $I$. The
following proposition is a simple consequence of Fact 1.

######  Proposition 2.

Let $(j,\theta)$ be a cut that separates at least two points from the set $A$
that includes the $k^{\prime}$ first centers and its associated
$k^{\prime}\cdot 2d$ points. Then, $(j,\theta)$ separates one point from its
associated center.

###### Proof.

Since $(j,\theta)$ separates at least two points from $A$ then
$\theta\in(-3/4,k^{\prime}-1+3/4)$.

If $\theta<0$, then $(j,\theta)$ separates the center that has the $j$-th
coordinate equal to 0 from its associated point that has coordinate $j$ equal
to $-3/4$. If $\theta>k^{\prime}-1$, then $(j,\theta)$ separates the center
that has the $j$-th coordinate equal to 0 from its associated point that has
coordinate $j$ equal to $k^{\prime}-1+3/4$. Let $z$ be an integer that
satisfies $0\leq z\leq k^{\prime}-2$ and such that $\theta\in(z,z+1)$. If
$\theta-z<1/2$ (resp. $\theta-z>1/2$), $(j,\theta)$ separates the center that
has the $j$-th coordinate equal to $z$ (resp. $z+1$) from its associated point
with $j$-th coordinate equal to $z+3/4$ (resp. $z+1-3/4$).

Note that the existence of centers with the aforementioned values for
coordinate $j$ is guaranteed by Fact 1. ∎

######  Lemma 2.

Any explainable $k$-clustering for instance $I$ has cost at least
$\sqrt{\lfloor d/p\rfloor}\cdot(b^{p-1}/4)-3/8$.

###### Proof.

Let ${\cal C}$ be an explainable $k$-clustering for instance $I$. It is enough
to show that there is a cluster $C\in{\cal C}$ that contains two points, say
$\mathbf{x}$ and $\mathbf{y}$, for which

$||\mathbf{x}-\mathbf{y}||_{2}\geq\sqrt{\lfloor
d/p\rfloor}\cdot(b^{p-1}/2)-3/4.$

In fact, in this case, due to the triangle inequality, for any choice of the
representative for $C$, either $\mathbf{x}$ or $\mathbf{y}$ will be at
distance at least $\sqrt{\lfloor d/p\rfloor}\cdot(b^{p-1}/4)-3/8$ from it.

If two centers lie in the same cluster of ${\cal C}$ then it follows from
Lemma 1 that their distance is at least $\sqrt{\lfloor
d/p\rfloor}\cdot(b^{p-1}/2)$.

On the other hand, if every center lies on a different cluster in ${\cal C}$
then let $\mathbf{x}$ be the point that was separated from its center, say
$\mathbf{c}^{i}$, by a cut that satisfies the condition of Proposition 2.
Then, $\mathbf{x}$ lies in the same cluster of $\mathbf{c}^{j}$, for some
$j\neq i$. From the triangle inequality we have that

$||\mathbf{c}^{i}-\mathbf{c}^{j}||_{2}\leq||\mathbf{c}^{i}-\mathbf{x}||_{2}+||\mathbf{c}^{j}-\mathbf{x}||_{2}.$

Hence, $||\mathbf{c}^{j}-\mathbf{x}||_{2}\geq\sqrt{\lfloor
d/p\rfloor}\cdot(b^{p-1}/2)-3/4$. ∎

By putting together Proposition 1 and Lemma 2 and, then, optimizing the value
of $p$ we obtain the following theorem.

######  Theorem 1.

The price of explainability for the $k$-centers problem satisfies

$\rho(k\mbox{-center})\in\left\\{\begin{array}[]{ll}\Omega(k^{1-1/d}),&\mbox{
if }d\leq\frac{\ln k}{\ln\ln k}\\\
\Omega\left(\sqrt{d}\cdot\frac{k\cdot\sqrt{\ln\ln
k}}{\ln^{1.5}k}\right),&\mbox{ otherwise.}\end{array}\right.$

###### Proof.

Proposition 1 assures the existence of a $k$-clustering of cost $3/4$ for
instance $I$. Let ${\cal C}$ be an explainable clustering for $I$ and recall
that $b^{p}=k^{\prime}$. It follows from the previous lemma that

$cost({\cal
C})\geq\sqrt{\frac{d}{p}}\cdot\frac{b^{p-1}}{4}-3/8=\sqrt{\frac{d}{p}}\cdot\frac{(k^{\prime})^{\frac{p-1}{p}}}{4}-3/8.$

Since $(b+1)^{p}>k$ we have

$k^{\prime}>\frac{k}{(1+1/b)^{p}}>\frac{k}{\exp(p/b)}.$

Thus,

$cost({\cal
C})\geq\sqrt{\frac{d}{p}}\cdot\frac{k^{\frac{p-1}{p}}}{4\exp((p-1)/b)}-3/8.$

Now we set $p=d$ if $d\leq\frac{\ln k}{\ln\ln k}$ and $p=\frac{\ln k}{\ln\ln
k}$, otherwise. Since $b>k^{1/p}-1$ we have that $b>\ln k-1>p-1$ for both
cases and, hence,

$cost({\cal C})\geq\sqrt{\frac{d}{p}}\cdot\frac{k^{\frac{p-1}{p}}}{4}-3/8.$

By replacing $p$ in the previous equation according to each of the cases we
obtain the desired result. ∎

###  2.2 Upper bound

In this section we show that the price of explainability for the $k$-center
problem is $O\left(\sqrt{d}k^{\frac{d-1}{d}}\right)$. Note that, for constant
$d$, the upper bound matches the lower bound given by Theorem 1.

To obtain the upper bound we analyze the cost of the explainable clustering
induced by the decision tree built by the algorithm presented in Algorithm 1.

The algorithm has access to the set of representatives of an optimal
$k$-clustering ${\cal C}^{*}$ for ${\cal X}$. These representatives are used
as reference centers for the points in ${\cal X}$, that is, the reference
center of a point $\mathbf{x}$ is the representative of $\mathbf{x}$’s group
in ${\cal C}^{*}$.

Let ${\cal X}^{\prime}$ and $S$ be, respectively, the subset of points in
${\cal X}$ and the set of reference centers that reach a given node $u$. To
split $u$, as long as it is possible, the algorithm applies an axis-aligned
cut that does not separate any point $\mathbf{x}\in{\cal X}^{\prime}$ from its
reference center. This type of cut is referred as a clean cut with respect to
$({\cal X}^{\prime},S)$. When there is no such cut available for $u$, the
algorithm partitions the bounding box of the points in ${\cal X}^{\prime}\cup
S$ into $\lfloor|S|^{1/d}\rfloor^{d}$ axis-aligned boxes of the same
dimensions by using a decision tree that emulates a grid. By the bounding box
of ${\cal X}^{\prime}\cup S$ we mean the smallest box (hyper-rectangle) with
axis-aligned sides that includes the points in ${\cal X}^{\prime}\cup S$.

Algorithm 1 Ex-kCenter( ${\cal X}^{\prime}$: set of points)

$S\leftarrow$ reference centers of the points in ${\cal X}^{\prime}$

if $|S|=1$ then

Return ${\cal X}^{\prime}$ and the single reference center in $S$

else

if there exists a clean cut w.r.t. $({\cal X}^{\prime},S)$ then

$({\cal X}^{\prime}_{L},{\cal X}^{\prime}_{R})$ $\leftarrow$ partition induced
by the clean cut

Create a node $u$

$u$.LeftChild $\leftarrow$Ex-kCenter(${\cal X}^{\prime}_{L})$

$u$.RightChild $\leftarrow$Ex-kCenter(${\cal X}^{\prime}_{R})$

Return the tree rooted at $u$

else

$H\leftarrow$ bounding box for ${\cal X}^{\prime}\cup S$

$D^{u}\leftarrow$ decision tree that partitions $H$ into
$\lfloor|S|^{1/d}\rfloor^{d}$ identical axis-aligned boxes

Return $D^{u}$ as well as an arbitrarily chosen representative for each of its
leaves

end if

end if

######  Theorem 2.

The price of explainability for $k$-centers is
$O\left(\sqrt{d}k^{1-1/d}\right)$.

###### Proof.

We argue that for each leaf $\ell$ of the tree ${\cal D}$ built by Ex-
kCenter(${\cal X}$), the maximum distance between a point in $\ell$ and its
representative is $OPT\sqrt{d}k^{1-1/d}$, where $OPT$ is the cost of the
optimal unrestricted clustering.

We split the proof into two cases. The first case addresses the scenario in
which only clean cuts are used in the path from the root of ${\cal D}$ to the
leaf $\ell$. The second case addresses the remaining scenarios.

Case 1. In this case all points that reach $\ell$ lie in the same cluster of
the optimal unrestricted $k$-clustering ${\cal C}^{*}$. Thus, the maximum
distance from a point in $\ell$ to the single reference center in $S$ is upper
bounded by $OPT$.

Case 2. Let $u$ be the first node in the path from the root to $\ell$ for
which a clean cut is not available. Moreover, let ${\cal X}^{u}$ be the set of
points that reach $u$ and let $s=|S|$, that is, the number of reference
centers that reach $u$. In this case the algorithm splits the bounding box for
${\cal X}^{u}\cup S$ into boxes of dimensions

$\frac{L_{1}}{\lfloor s^{1/d}\rfloor}\times\cdots\times\frac{L_{d}}{\lfloor
s^{1/d}\rfloor},$

where $L_{i}$ is the difference between the maximum and minimum values of the
$i$-th coordinate among points in ${\cal X}^{u}\cup S$.

The maximum distance between a point in $\ell$ and its representative can be
upper bounded by the length of the diagonal of the axis-aligned box
corresponding to $\ell$. Let $m\in[d]$ be such that
$L_{m}=\max\\{L_{1},\ldots,L_{d}\\}$. Then, the length of the diagonal is
upper bounded by $L_{m}\sqrt{d}/\lfloor s^{1/d}\rfloor\leq
2L_{m}\sqrt{d}/s^{1/d}$.

Thus, it suffices to show that $OPT\geq L_{m}/(2s)$. Let
$\mathbf{c}^{1},\ldots,\mathbf{c}^{s}$ be the $s$ reference centers that reach
node $u$. In addition, let $\mathbf{x}^{j}$ be a point in ${\cal X}^{u}$ with
reference center $\mathbf{c}^{j}$ and such that $|x^{j}_{m}-c^{j}_{m}|$ is
maximum, among the points in ${\cal X}^{u}$ with reference center
$\mathbf{c}^{j}$. Then, we must have

$\sum_{j=1}^{s}2|x^{j}_{m}-c^{j}_{m}|\geq L_{m},$

for otherwise there would be a clean cut $(m,\theta)$, with $\theta\in[a,b]$,
where $a=\min\\{y_{m}|\mathbf{y}\in{\cal X}^{u}\cup S\\}$ and
$b=\max\\{y_{m}|\mathbf{y}\in{\cal X}^{u}\cup S\\}$. Hence, for some point
$\mathbf{x}^{j}$, $|x^{j}_{m}-c^{j}_{m}|\geq L_{m}/(2s)$. Since
$OPT\geq|x^{j}_{m}-c^{j}_{m}|$ we get that $OPT\geq L_{m}/(2s)$. ∎

##  3 Improved Bounds on $k$-medians for low dimensions

We show that the price of explainability for $k$-medians is $O(d\log k)$,
which improves the bound from [26] when $d=o(k/\log k)$.

As in the previous section we use an optimal unrestricted $k$-clustering
${\cal C}^{*}$ for ${\cal X}$ as a guide for building an explainable
clustering. Again, by the reference center of a point $\mathbf{x}\in{\cal X}$
we mean its representative in ${\cal C}^{*}$.

We need some additional notation. For a decision tree ${\cal D}$ and a node
$u\in{\cal D}$, let $diam(u)$ be the $d$-dimensional vector whose $i$-th
coordinate $diam(u)_{i}$ is given by the difference between the maximum and
the minimum values of coordinate $i$ among the reference centers that reach
$u$. Let $t_{u}$ be the number of points that reach $u$ and are separated from
their reference centers by the cut employed in $u$. Note that a point
$\mathbf{x}\in{\cal X}$ can only contribute to $t_{u}$ if both $\mathbf{x}$
and its reference center reach $u$. Finally, we use $OPT$ to denote the cost
of the optimal unrestricted clustering ${\cal C}^{*}$.

The following lemma from [26], expressed in our notation, will be useful.

######  Lemma 3.

[26] Let ${\cal C}^{*}$ be an optimal unrestricted $k$-clustering for ${\cal
X}$ and let ${\cal D}$ be a decision tree for ${\cal X}$ in which each
representative of ${\cal C}^{*}$ lies in a distinct leaf. Then, the clustering
${\cal C}$ induced by ${\cal D}$ satisfies

$cost({\cal C})\leq OPT+\sum_{u\in{\cal D}}t_{u}||diam(u)||_{1}.$ (1)

In order to obtain a low-cost explainable clustering we focus on finding a
decision tree ${\cal D}$ for which the rightmost term of the above inequality
is small. This is the approach taken by IMM [26], a greedy strategy that at
each node $u$ selects the cut that yields the minimum possible value for
$t_{u}$.

Although we follow the same approach, our strategy for building the tree is
significantly different. In order to explain it, we first rewrite the
rightmost term of (1):

$\sum_{u\in{\cal D}}t_{u}||diam(u)||_{1}=\sum_{i=1}^{d}\sum_{u\in{\cal
D}}t_{u}diam(u)_{i}.$ (2)

Motivated by Lemma 3 and the above identity, our strategy constructs $d$
decision trees ${\cal D}_{1},\ldots,{\cal D}_{d}$, where ${\cal D}_{i}$ is
built with the aim of minimizing

$\sum_{u\in{\cal D}}t_{u}diam(u)_{i},$ (3)

ignoring the impact on the coordinates $j\neq i$.

Next, it constructs a decision tree ${\cal D}$ for ${\cal X}$ by picking nodes
from these $d$ trees. More precisely, to split a node $u$ of ${\cal D}$ the
strategy first selects a coordinate $i\in[d]$ for which $diam(u)_{i}$ is
maximum. Next, it applies the cut that is associated with the node in ${\cal
D}_{i}$ which is the least common ancestor (LCA) of the set of reference
centers that reach $u$.

In the pseudo-code presented in Algorithm 2, $S^{\prime}$ is a subset of the
set $S$ of representatives of ${\cal C}^{*}$. Moreover, ${\cal X}^{\prime}$ is
a subset of the points in ${\cal X}$. The procedure is called, initially, with
${\cal X}^{\prime}={\cal X}$ and $S^{\prime}=S$.

Algorithm 2 BuildTree(${\cal X}^{\prime}\cup S^{\prime}$)

Create a node $u$ and associate it with ${\cal X}^{\prime}\cup S^{\prime}$

if $|S^{\prime}|=1$ then

Return the leaf $u$

else

Select $i\in[d]$ for which $diam(u)_{i}$ is maximum.

$v\leftarrow$ node in ${\cal D}_{i}$ which is the LCA of the centers in
$S^{\prime}$

Split ${\cal X}^{\prime}\cup S^{\prime}$ into ${\cal X}^{\prime}_{L}\cup
S^{\prime}_{L}$ and ${\cal X}^{\prime}_{R}\cup S^{\prime}_{R}$ using the cut
associated with $v$.

$u$.LeftChild $\rightarrow$ BuildTree(${\cal X}^{\prime}_{L}\cup
S^{\prime}_{L}$)

$u$.RightChild $\rightarrow$ BuildTree(${\cal X}^{\prime}_{R}\cup
S^{\prime}_{R}$)

Return the decision tree rooted at $u$

end if

To fully specify the algorithm we need to explain how the decision trees
${\cal D}_{i}$ are built. Let $\mathbf{c}^{1},\ldots,\mathbf{c}^{k}$ be the
reference centers sorted by coordinate $i$, that is,
$c^{j}_{i}<c^{j_{+}1}_{i}$ for $j=1,\ldots,k-1$. Moreover, let
$(i,\theta^{j})$ be the cut that separates the points in ${\cal X}$ with the
$i$-th coordinate smaller than or equal to
$\theta^{j}=(c^{j}_{i}+c^{j+1}_{i})/2$ from the remaining ones.

For $1\leq a\leq b\leq k$, let ${\cal F}_{a,b}$ be the family of binary
decision trees with $(b-a)$ internal nodes and $b-a+1$ leaves defined as
follows:

  * (i)

if $a=b$, then ${\cal F}_{a,b}$ has a single tree and this tree contains only
one node.

  * (ii)

if $a<b$, then ${\cal F}_{a,b}$ consists of all the decision trees ${\cal
D^{\prime}}$ with the following structure: the root of ${\cal D^{\prime}}$ is
identified by a number $j\in\\{a,\ldots,b-1\\}$ and associated with the cut
$(i,\theta^{j})$; one child of the root of ${\cal D^{\prime}}$ is a tree in
the family ${\cal F}_{a,j}$ while the other is a tree in ${\cal F}_{j+1,b}$.

For our analysis, in the next sections, it will be convenient to view ${\cal
F}_{a,b}$ as the family of binary search trees for the numbers in the set
$\\{a,\ldots,b-1\\}$.

Let $T_{j}$ be the number of points in ${\cal X}$ that are separated from
their centers by cut $(i,\theta^{j})$. For every tree ${\cal
D}^{\prime}\in{\cal F}_{a,b}$ we define $UB_{i}({\cal D}^{\prime})$ as

$UB_{i}({\cal D}^{\prime})=\sum_{j=a}^{b-1}T_{j}\cdot diam(j)_{i},$

where $diam(j)$ is the diameter of the node identified by $j$ in ${\cal
D}^{\prime}$.

The tree ${\cal D}_{i}$ is, then, defined as

${\cal D}_{i}=\operatorname{argmin}\\{UB_{i}({\cal D}^{\prime})\mid{\cal
D}^{\prime}\in{\cal F}_{1,k}\\}.$

The motivation for minimizing $UB_{i}()$ is that for every tree ${\cal
D}^{\prime}\in{\cal F}_{1,k}$, $UB_{i}()$ is an upper bound on (3), that is,

$\sum_{u\in{\cal D}^{\prime}}t_{u}diam(u)_{i}\leq\sum_{j=1}^{k-1}T_{j}\cdot
diam(j)_{i}=UB_{i}({\cal D}^{\prime}).$

To see that, let $j$ be the integer identified with the node $u\in{\cal
D}^{\prime}$. By definition $diam(u)_{i}=diam(j)_{i}$. Moreover, we have
$t_{u}\leq T_{j}$ because $t_{u}$ only accounts the points that are separated
from their reference centers among those that reach $u$, while $T_{j}$
accounts all the points in ${\cal X}$ regardless of whether they reach $u$ or
not.

We discuss how to construct ${\cal D}_{i}$ efficiently. Let
$OPT_{a,b}=\min\\{UB_{i}({\cal D}^{\prime})\mid{\cal D}^{\prime}\in{\cal
F}_{a,b}\\},$ if $a<b$, and let $OPT_{a,b}=0$ if $a=b$. Hence, $UB_{i}({\cal
D}_{i})=OPT_{1,k}$. The following relation holds for all $a<b$:

$OPT_{a,b}=\min_{a\leq j\leq
b-1}\left\\{T_{j}(c^{b}_{i}-c^{a}_{i})+OPT_{a,j}+OPT_{j+1,b}\right\\}.$ (4)

Thus, given a set of $k$ reference centers and the values $T_{j}$’s, ${\cal
D}_{i}$ can be computed in $O(k^{3})$ time by solving equation (4), for $a=1$
and $b=k$, via standard dynamic programming techniques.

###  3.1 Approximation Analysis: Overview

We prove that the cost of the clustering induced by ${\cal D}$ is $O(d\log
k)\cdot OPT$. To reach this goal, we first show that

$UB_{i}({\cal D}_{i})\leq 2\log
k\left(\sum_{j=1}^{k-1}(c_{i}^{j+1}-c^{j}_{i})T_{j}\right).$ (5)

The proof of this bound relies on the fact that ${\cal D}_{i}$ can be seen as
a binary search tree with non-uniform probing costs. We use properties of this
kind of tree, in particular the one proved in [8] about its competitive ratio.

Let

$OPT_{i}=\sum_{\mathbf{x}\in{\cal X}}|x_{i}-c(\mathbf{x})_{i}|$

be the contribution of coordinate $i$ to $OPT$, where $c(\mathbf{x})$ is the
reference center of $\mathbf{x}$. Our second step consists of showing that

$\left(\sum_{j=1}^{k-1}(c_{i}^{j+1}-c^{j}_{i})T_{j}\right)/2\leq OPT_{i}.$ (6)

Roughly speaking, the proof of this bound consists of projecting the points of
${\cal X}$ and the reference centers onto the axis $i$ and then counting the
number of times the interval $[c_{i}^{j},c_{i}^{j+1}]$ appears in the segments
that connect points in ${\cal X}$ to their reference centers. This is exactly
the same line of reasoning employed to prove Lemma 6 from the supplementary
version of [26].

At this point, from the two previous inequalities, we obtain

$UB_{i}({\cal D}_{i})\leq 4\log k\cdot OPT_{i}.$ (7)

Finally, we prove that a factor of $d$ is incurred when we build the tree
${\cal D}$ from the nodes of the trees ${\cal D}_{1},\ldots,{\cal D}_{d}$:

$\sum_{v\in{\cal D}}t_{v}||diam(v)||_{1}\leq d\sum_{i=1}^{d}UB_{i}({\cal
D}_{i}).$ (8)

From (7), (8) and the identity $OPT=\sum_{i=1}^{d}OPT_{i}$, we obtain

$\sum_{v\in{\cal D}}t_{v}||diam(v)||_{1}\leq 4d\log k\cdot OPT.$

This together with Lemma 3 allows us to establish the main theorem of this
section.

######  Theorem 3.

The price of explainability for $k$-medians is $O(d\log k)$.

###  3.2 Approximation Analysis: Proofs

We start with the proof of inequality (5).

######  Lemma 4.

The tree ${\cal D}_{i}$ satisfies

$UB_{i}({\cal D}_{i})\leq 2\log
k\left(\sum_{j=1}^{k-1}(c_{i}^{j+1}-c^{j}_{i})T_{j}\right).$

###### Proof.

Let ${\cal D}^{\prime}$ be a tree in ${\cal F}_{1,k}$. By construction, the
set of centers that reach the node in ${\cal D}^{\prime}$ identified by $j$ is
a contiguous subsequence of $\mathbf{c}^{1},\ldots,\mathbf{c}^{k}$. Let $r(j)$
and $s(j)$ be, respectively, the first and the last indexes of the centers of
this subsequence. Thus,

$UB_{i}({\cal D}^{\prime})=\sum_{j=1}^{k-1}T_{j}\cdot
diam(j)_{i}=\sum_{j=1}^{k-1}T_{j}\sum_{\ell=r(j)}^{s(j)-1}(c^{\ell+1}_{i}-c^{\ell}_{i}).$
(9)

We can show that the right-hand side of the above equation satisfies

$\sum_{j=1}^{k-1}T_{j}\sum_{\ell=r(j)}^{s(j)-1}(c^{\ell+1}_{i}-c^{\ell}_{i})=\sum_{\ell=1}^{k-1}(c^{\ell+1}_{i}-c^{\ell}_{i})\cdot\sum_{j\in
An(\ell,{\cal D}^{\prime})}T_{j},$ (10)

where $An(\ell,{\cal D}^{\prime})$ is the set of nodes that are ancestors
(including $\ell$) of the node identified by $\ell$ in ${\cal D}^{\prime}$.

To see that, fix $j,\ell\in[k-1]$. The term
$T_{j}(c^{\ell+1}_{i}-c_{i}^{\ell})$ contributes the left-hand side of (10) if
the centers $\mathbf{c}^{\ell}$ and $\mathbf{c}^{\ell+1}$ reach the node $j$
in ${\cal D}^{\prime}$. This happens if and only if $j$ is an ancestor of the
node identified by $\ell$ in ${\cal D}^{\prime}$.

Now, we use Theorem 4.5 from [8]. It states that for any vector
$(p_{1},\ldots,p_{k})$ of $k$ non-negative real numbers there exists a binary
search tree $B$ having $k$ nodes, with each of them associated with a number
in $[k]$, that satisfies

$\sum_{j\in An(\ell,B)}p_{j}\leq(\log k+o(\log k))p_{\ell}\leq 2\log k\cdot
p_{\ell},$

for every node $\ell$ of $B$.

Let ${\cal D}_{c}$ be a tree obtained via the result of [8] for the vector
$(T_{1},\ldots,T_{k-1})$. It satisfies

$\sum_{j\in An(\ell,{\cal D}_{c})}T_{j}\leq 2\log(k-1)\cdot T_{\ell}.$

By using this inequality, (9) and (10), we get that

$UB_{i}({\cal
D}_{c})=\sum_{\ell=1}^{k-1}(c^{\ell+1}_{i}-c^{\ell}_{i})\sum_{j\in
An(\ell,{\cal D}_{c})}T_{j}\leq 2\log
k\sum_{\ell=1}^{k-1}(c^{\ell+1}_{i}-c^{\ell}_{i})T_{\ell}.$

The result follows because the minimality of ${\cal D}_{i}$ guarantees that
$UB_{i}({\cal D}_{i})\leq UB_{i}({\cal D}_{c})$. ∎

Inequality (6) is formalized in the next lemma.

######  Lemma 5.

Let $OPT_{i}$ be the contribution of the coordinate $i$ for the cost of an
optimal unrestricted clustering ${\cal C}^{*}$. Then,

$OPT_{i}=\sum_{\mathbf{x}\in{\cal
X}}|x_{i}-c(\mathbf{x})_{i}|\geq\sum_{j=1}^{k-1}\frac{(c^{j+1}_{i}-c^{j}_{i})T_{j}}{2},$
(11)

where $c(\mathbf{x})$ is the reference center of $\mathbf{x}$.

###### Proof.

Let $\mathbf{c}^{1},\ldots,\mathbf{c}^{k}$ be the reference centers sorted by
increasing order of coordinate $i$. Recall that
$\theta^{j}=(c^{j}_{i}+c^{j+1}_{i})/2$. For every $\mathbf{x}\in{\cal X}$, let
$Cut(\mathbf{x})=\\{j|(i,\theta^{j})\mbox{ separates }\mathbf{x}\mbox{ from
}c(\mathbf{x})\\}$.

Fix $\mathbf{x}\in{\cal X}$. If $j\in Cut(\mathbf{x})$ then either
$[c^{j}_{i},\theta^{j}]$ or $[\theta^{j},c^{j+1}_{i}]$ is included in the real
interval with endpoints $x_{i}$ and $c(x)_{i}$. Thus, we have that

$|x_{i}-c(x)_{i}|\geq\sum_{j\in Cut(\mathbf{x})}(c^{j+1}_{i}-c^{j}_{i})/2$

By adding the above inequality for all $\mathbf{x}\in{\cal X}$ we conclude
that the number of times that $(c^{j+1}_{i}-c^{j}_{i})/2$ contributes to the
right-hand side, for every $j\in[k-1]$, is exactly the number of times that
$(i,\theta^{j})$ separates a point $\mathbf{x}^{\prime}\in{\cal X}$ from its
reference center $c(\mathbf{x}^{\prime})$. This number is exactly $T_{j}$. ∎

Finally, we present the proof of inequality (8).

######  Lemma 6.

Let ${\cal D}$ be the decision tree built by Algorithm 2. Then,

$\sum_{v\in{\cal D}}t_{v}||diam(v)||_{1}\leq d\sum_{i=1}^{d}UB_{i}({\cal
D}_{i}).$

###### Proof.

For a node $j\in{\cal D}_{i}$, let $S_{i,j}$ be the (possibly empty) set of
nodes in the tree ${\cal D}$ that correspond to $j$, that is, the nodes that
use the cut associated with the node $j$ from ${\cal D}_{i}$. We have

$\sum_{v\in{\cal D}}t_{v}||diam(v)||_{1}=\sum_{i=1}^{d}\sum_{j\in{\cal
D}_{i}}\sum_{u\in S_{i,j}}t_{u}||diam(u)||_{1}.$ (12)

Moreover, we have that

$\displaystyle\sum_{u\in S_{i,j}}t_{u}||diam(u)||_{1}\leq\sum_{u\in
S_{i,j}}t_{u}\cdot d\cdot diam(u)_{i}\leq$ (13) $\displaystyle\sum_{u\in
S_{i,j}}d\cdot t_{u}\cdot\max_{u\in S_{i,j}}\\{diam(u)_{i}\\}\leq\sum_{u\in
S_{i,j}}d\cdot t_{u}\cdot diam(j)_{i},$ (14)

where the first inequality in (13) holds because $i$ is the coordinate for
which the diameter of $u$ is maximum and the inequality (14) holds because the
set of centers in $u$ is a subset of the set of centers that reach the node
identified by $j$ in ${\cal D}_{i}$.

######  Claim 1.

For a node $u\in S_{i,j}$, let ${\cal X}_{u}\subseteq{\cal X}$ be the set of
points that reach $u$ in ${\cal D}$. Then, ${\cal X}_{u}\cap{\cal
X}_{u^{\prime}}=\emptyset$ for every $u,u^{\prime}\in S_{i,j}$, with $u\neq
u^{\prime}$.

###### Proof.

Let $w$ be the least common ancestor of $u^{\prime}$ and $u$ in ${\cal D}$. If
$w\notin\\{u,u^{\prime}\\}$ then the cut associated with $w$ splits ${\cal
X}_{w}$ into two disjoint regions, one of them containing ${\cal X}_{u}$ and
the other containing ${\cal X}_{u^{\prime}}$ so that ${\cal X}_{u}$ and ${\cal
X}_{u^{\prime}}$ are disjoint.

If $w\in\\{u,u^{\prime}\\}$ let us assume w.l.o.g. that $w=u$. In this case,
the cut $(i,\theta^{j})$, associated with $u$, splits ${\cal X}_{u}$ into two
regions, one of them containing all the reference centers that reach
$u^{\prime}$. These centers are contained in the set of reference centers of
one of the children of $j$ in ${\cal D}_{i}$ and, hence, the LCA in ${\cal
D}_{i}$ of the set of centers that reach $u^{\prime}$ is not $j$, that is,
$u^{\prime}\notin S_{i,j}$. This contradiction shows that this case cannot
occur. ∎

From the previous claim we get that

$\sum_{u\in S_{i,j}}t_{u}\leq T_{j}.$

It follows from (13)-(14) and the above inequality that

$\sum_{u\in S_{i,j}}t_{u}||diam(u)||_{1}\leq d\cdot T_{j}\cdot diam(j)_{i}.$

Hence, it follows from (12) that

$\displaystyle\sum_{v\in{\cal
D}}t_{v}||diam(v)||_{1}\leq\sum_{i=1}^{d}\sum_{j\in{\cal D}_{i}}d\cdot
T_{j}\cdot diam(j)_{i}=$ $\displaystyle d\sum_{i=1}^{d}UB_{i}({\cal
D}_{i}).\qed$

##  4 The $k$-means problem

###  4.1 Improved bounds for low dimensions

The result we obtained for the $k$-medians problem can be extended to the
$k$-means problem:

######  Theorem 4.

The price of explainability for $k$-means is $O(dk\log k)$.

From an algorithmic perspective, in order to establish the theorem, we only
need to replace the definition of $UB_{i}({\cal D}^{\prime})$ for a tree
${\cal D}^{\prime}$ in ${\cal F}_{a,b}$ with

$UB^{\prime}_{i}({\cal
D^{\prime}})=\sum_{j=a}^{b-1}T_{j}\cdot(diam(j)_{i})^{2}.$

Note that the only difference is the replacement of $diam(j)_{i}$ with
$(diam(j)_{i})^{2}$. As a consequence, for the $k$-means problem, the tree
${\cal D}_{i}$ is defined as the tree ${\cal D}^{\prime}$ in ${\cal F}_{1,k}$
for which $UB^{\prime}_{i}({\cal D}^{\prime})$ is minimum. It can also be
constructed via dynamic programming. Theorem 4 can be proved by using
arguments similar to those employed to bound the price of explainability for
$k$-medians. The following inequalities are, respectively, counterparts of the
inequalities (1), (5), (6) and (8):

$cost({\cal C})\leq OPT+\sum_{v\in{\cal D}}t_{v}||diam(v)||^{2}_{2},$ (15)

$UB^{\prime}_{i}({\cal D}_{i})\leq 2k\log
k\left(\sum_{j=1}^{k-1}(c_{i}^{j+1}-c^{j}_{i})^{2}\cdot T_{j}\right),$ (16)

$\left(\sum_{j=1}^{k-1}(c_{i}^{j+1}-c^{j}_{i})^{2}\cdot T_{j}\right)/2\leq
OPT_{i},$ (17)

$\sum_{v\in{\cal D}}t_{v}||diam(v)||^{2}_{2}\leq
d\sum_{i=1}^{d}UB^{\prime}_{i}({\cal D}_{i}).$ (18)

From the three last inequalities and the identity $OPT=\sum_{i=1}^{d}OPT_{i}$,
we obtain

$\sum_{v\in{\cal D}}t_{v}||diam(v)||^{2}_{2}\leq 4dk\log k\cdot OPT.$

This together with the inequality (15) allows us to establish Theorem 4.

Inequality (15) is proved in [26]. The validity of inequalites (17) and (18)
can be established by using exactly the same arguments employed to prove their
counterparts. More specifically, the proof of Lemma 5 can be used for the
former while the proof of Lemma 6 can be used for the latter.

The inequality (16) incurs an extra factor of $k$ with respect to its
counterpart. In order to prove this inequality, we apply the arguments of the
proof of Lemma 4. The only required adaptation consists of replacing Equation
(9) with the inequality

$UB^{\prime}_{i}({\cal D}_{i})\leq
k\sum_{j=1}^{k-1}T_{j}\cdot\sum_{\ell=r(j)}^{s(j)-1}(c^{\ell+1}_{i}-c^{\ell}_{i})^{2}.$
(19)

Inequality (19) holds because

$UB^{\prime}_{i}({\cal
D}_{i})=\sum_{j=1}^{k-1}T_{j}\cdot(c_{i}^{s(j)}-c_{i}^{r(j)})^{2},$

and a simple application of Jensen’s inequality assures that

$(c_{i}^{s(j)}-c_{i}^{r(j)})^{2}\leq
k\sum_{\ell=r(j)}^{s(j)-1}(c^{\ell+1}_{i}-c^{\ell}_{i})^{2}.$

###  4.2 A practical algorithm

We propose a simple greedy algorithm, denoted by Ex-Greedy, for building
explainable clustering for the $k$-means problem. We provide evidence that it
performs very well in practice.

The algorithm starts with the set $S$ of representatives of an unrestricted
$k$-clustering ${\cal C}^{ini}$ for the dataset ${\cal X}$ and then builds a
decision tree ${\cal D}$ with $k$ leaves, where each of them includes exactly
one representative from $S$.

Let $u$ be a node of the decision tree and let ${\cal X}^{u}$ and ${\cal
S}^{u}$ be, respectively, the set of points and the set of reference centers
(representatives of ${\cal C}^{ini}$) that reach $u$. We define the cost of a
partition $(L,R)$ of the points in ${\cal X}^{u}\cup{\cal S}^{u}$ as

$\displaystyle cost(L,R)=$ $\displaystyle\sum_{\mathbf{x}\in L\cap{\cal
X}^{u}}\min_{\mathbf{c}\in L\cap{\cal
S}^{u}}||\mathbf{x}-\mathbf{c}||_{2}^{2}+$ $\displaystyle\sum_{\mathbf{x}\in
R\cap{\cal X}^{u}}\min_{\mathbf{c}\in R\cap{\cal
S}^{u}}||\mathbf{x}-\mathbf{c}||_{2}^{2}.$

To split a node $u$, that is reached by more than one representative, Ex-
Greedy selects the axis-aligned cut that induces a partition with minimum
cost.

Ex-Greedy can be implemented in $O(ndkH+nd\log n)$ time, where $H$ is the
depth of the resulting decision tree. Note that $H\leq k$ and in many relevant
applications $k$ is small. The time complexity corresponds to $H$ iterations
of Lloyd’s $k$-means algorithm.

####  4.2.1 An efficient implementation

To achieve this time complexity, in the preprocessing phase, Ex-Greedy builds
the following data structures:

  * •

a list ${\tt SL_{i}}$, for each $i\in[d]$, containing the points in ${\cal
X}\cup S$ sorted by coordinate $i$;

  * •

a list ${\tt M}_{\mathbf{x}}$ of size $k$, for each $\mathbf{x}\in{\cal X}$,
that stores the $k$ centers sorted by increasing order of their distances to
$\mathbf{x}$.

The lists ${\tt SL_{i}}$ can be built in $O(dn\log n)$ time and the lists
${\tt M}_{\mathbf{x}}$ in $O(nk\log k)$ time.

To decide how to split the root the algorithm finds the partition with minimum
cost for each coordinate $i\in[d]$ and then selects the one with minimum cost
among them.

Fix $i\in[d]$. The algorithm scans the list ${\tt SL_{i}}$ from left to the
right and evaluates the cost of $n-k+1$ partitions where the $j$-th one,
namely $(L_{j},R_{j})$, separates the first $j$ points in ${\tt SL_{i}}$ from
the remaining ones. During the scan the algorithm makes use of two vectors of
size $n$, ${\tt V}_{L}$ and ${\tt V}_{R}$. Right after evaluating
$(L_{j},R_{j})$, ${\tt V}_{L}$ (resp. ${\tt V}_{R}$) stores, for each
$\mathbf{x}$ that lies at $L_{j}$ (resp. $R_{j}$), the center that is closest
to $\mathbf{x}$ among those that also lie in $L_{j}$ (resp. $R_{j}$). The only
difference is that ${\tt V}_{L}[\mathbf{x}]$ stores the center directly while
${\tt V}_{R}[\mathbf{x}]$ stores the position of the center in ${\tt
M}_{\mathbf{x}}$.

Let us consider the moment in which the algorithm has just calculated the cost
${\tt Cost_{j}}$ of the $j$th partition $(L_{j},R_{j})$. To obtain ${\tt
Cost_{j+1}}$ and update ${\tt V}_{L}$ and ${\tt V}_{R}$, the algorithm first
set ${\tt Cost_{j+1}}={\tt Cost_{j}}$ and then proceeds according to the
following cases:

Case 1. The $(j+1)$-th point in ${\tt SL_{i}}$ corresponds to a point
$\mathbf{x}$ in ${\cal X}$. Then, the algorithm evaluates ${\tt Cost_{j+1}}$
in $O(k)$ time as follows:

  * i

it obtains the center $\mathbf{c}_{R}$ in $R_{j}$ that is closest to
$\mathbf{x}$. This is done in $O(1)$ time since ${\tt V}_{R}[\mathbf{x}]$
points to this center;

  * ii

By scanning ${\tt M_{\mathbf{x}}}$ it obtains the center $\mathbf{c}_{L}$ in
$L_{j+1}$ that is closest to $\mathbf{x}$ and then updates ${\tt
V}_{L}[\mathbf{x}]$ to $\mathbf{c}_{L}$ . This requires $O(k)$ time

  * iii

it updates ${\tt Cost_{j+1}}$ to ${\tt
Cost_{j}}+||\mathbf{x}-\mathbf{c}_{L}||_{2}^{2}-||\mathbf{x}-\mathbf{c}_{R}||_{2}^{2}$.

Case 2. The $(j+1)$-th point in ${\tt SL_{i}}$ corresponds to a reference
center $\mathbf{c}$ in $S$.Then, the algorithm evaluates ${\tt Cost_{j+1}}$ in
$O(n)$ amortized time as follows:

  * i

for each point $\mathbf{x}$ in $L_{j}$, Ex-Greedy compares
$||\mathbf{c}-\mathbf{x}||_{2}^{2}$ with $||{\tt
V}_{L}[x]-\mathbf{x}||_{2}^{2}$. If $\mathbf{c}$ is the closest then it
updates ${\tt Cost_{j+1}}$ to ${\tt
Cost_{j+1}}+||\mathbf{x}-\mathbf{c}||_{2}^{2}-||\mathbf{x}-{\tt
V}_{L}[x]||_{2}^{2}$ and ${\tt V}_{L}[\mathbf{x}]$ to $\mathbf{c}$. This
requires $O(n)$ time.

  * ii

for each point $\mathbf{x}$ in $R_{j}$ it verifies whether $V_{R}[\mathbf{x}]$
points to $\mathbf{c}$. In the negative case, nothing is done. In the positive
case, it scans ${\tt M}_{\mathbf{x}}$, starting from $V_{R}[\mathbf{x}]$
towards to its end , until it finds a center $\mathbf{c}^{\prime}$ that lies
in $R_{j}$. Then it updates ${\tt Cost_{j+1}}$ to ${\tt
Cost_{j}}-||\mathbf{x}-\mathbf{c}||_{2}^{2}+||\mathbf{x}-\mathbf{c}^{\prime}||_{2}^{2}.$
This operation requires $O(n)$ amortized time since the total cost spent on
these scans, when we take into account moving the $k$ centers, is $O(nk)$.

The algorithm applies the cut with minimum cost and then recurses on each the
children of the root. To process a child $u$ of the root, the implementation
updates the data structures ${\tt SL_{i}}$ and ${\tt M_{\mathbf{x}}}$ to only
comprise the points and the reference center that reach $u$. Each list ${\tt
SL_{i}}$ can be updated in $O(n)$ time by removing the points and the
reference centers that do not reach $u$. Similarly, each list ${\tt
M_{\mathbf{x}}}$ can be updated in $O(k)$ time by removing points and the
reference centers that do not reach $u$.

####  4.2.2 Experiments

[12, 15] compared 6 methods that build explainable clusterings, over 10
datasets. These methods also allow the construction of decision trees with
more than $k$ leaves but this is not relevant for our experiments. For trees
with $k$ leaves, the IMM algorithm proposed in [26] obtained the best results,
or was very close to it, for all datasets but one (CIFAR-10).

Table 1: Comparison of Ex-Greedy and IMM over 10 datasets Dataset | n | d | k | IMM | Ex-Greedy
---|---|---|---|---|---
BreastCancer | 569 | 30 | 2 | 1.00 | 1.00
Iris | 150 | 4 | 3 | 1.04 | 1.04
Wine | 178 | 13 | 3 | 1.00 | 1.00
Covtype | 581,012 | 54 | 7 | 1.03 | 1.03
Mice | 552 | 77 | 8 | 1.12 | 1.09
Digits | 1,797 | 64 | 10 | 1.23 | 1.21
CIFAR-10 | 50,000 | 3,072 | 10 | 1.23 | 1.17
Anuran | 7,195 | 22 | 10 | 1.30 | 1.15
Avila | 20,867 | 12 | 12 | 1.1 | 1.09
Newsgroups | 18,846 | 1,069 | 20 | 1.01 | 1.01

Given the success of IMM, we compared it with our method Ex-Greedy on the same
datasets. The column IMM (resp. Ex-Greedy) of Table 1 shows the average ratio
between the cost of the clustering obtained by IMM (resp. Ex-Greedy) and that
of the initial unrestricted clustering ${\cal C}^{ini}$ produced by scikit-
learn’s KMeans algorithm [28]. Following [15], the value of $k$ is the number
of classes for the classification task associated with the dataset.

Each dataset was run for 10 iterations, with random seeds from 1 to 10, to
ensure the reproducibility of results. For each iteration, we initially
achieve an unrestricted solution ${\cal C}^{ini}$ by running the KMeans
algorithm provided in the scikit-klearn package with default parameters. We
then pass ${\cal C}^{ini}$ to the implementation of IMM from [15], available
at https://github.com/navefr/ExKMC, and to our implementation of Ex-Greedy, to
find two explainable clustering solutions induced by decision trees.

For 5 datasets, the results were very similar while for the others (bold in
Table 1) Ex-Greedy performed better than IMM. Figure 1 presents box plots for
the 5 datasets where there was a difference of at least 0.01 on the average
results. It is interesting to note that the dispersion of Ex-Greedy is
considerably smaller.

In terms of running time both methods spent less than 1 second, for 6
datasets. For the remaining datasets IMM was the fastest as shown in Table 2.
In spite of that, we understand that Ex-Greedy is fast enough to be used in
practice.

Figure 1: Box Plots for the datasets with difference at least 0.01  Table 2: Average running times in seconds for Ex-Greedy and IMM Dataset |  IMM (sec) |  Ex-Greedy (sec)
---|---|---
Avila | 1.7 | 2.4
Covtype | 42 | 53
Newsgroups | 41 | 102
CIFAR-10 | 312 | 378

####  4.2.3 Details of the experimental settings and the datasets

All our experiments were executed in a MacBook Air, 8Gb of RAM, processor 1,6
GHz Dual-Core Intel Core i5, executing macOS Catalina, version 10.15.7. Our
code is availble in https://github.com/lmurtinho/ExKMC.

The datasets Iris, Wine, Breast Cancer, Digits, Covtype, Mice and Newsgroup
are available in Python’s scikit-learn; Cifar-10 is available in TensorFlow;
Anuran and Avila were downloaded from UCI.

For Mice, the examples with missing values were removed. For Avila, the
training set and the testing set are used together. Finally, for Newsgroup, we
removed headers, footers, quotes, stopwords, and words that either appear in
less than $1\%$ or more than $10\%$ of the documents, following [15].

##  5 Maximum-Spacing Clustering

We show that the price of explainability for the maximum-spacing problem is
$\Theta(n-k)$.

###  5.1 Lower bound

The following simple construction shows that the price of explainability is
$\Omega(n-k)$.

Let $C_{1}=\\{(0,i)|0\leq i\leq p\\}\cup\\{(i,0)|0\leq i\leq p\\}$. Moreover,
for $i=2,\ldots,k$, let $C_{i}=\\{(i-1)(p-1),(p-1)\\}$. The dataset ${\cal X}$
for our instance is given by $C_{1}\cup\ldots\cup C_{k}$.

The unrestricted $k$-clustering $(C_{1},\ldots,C_{k})$ has spacing
$p-1=(n-k)/2-1$. On the other hand, every explainable $k$-clustering has
spacing 1. To see that, note that we cannot have all the points of $C_{1}\cup
C_{2}$ in the same cluster, for otherwise we would have at most $k-1$
clusters. Thus, we need to separate at least 2 points from $C_{1}\cup C_{2}$
and the only way to accomplish that, via axis-aligned cuts, forces the
separation of 2 points in $C_{1}$ that are at distance 1 from each other.
Thus, the spacing will be 1.

######  Lemma 7.

The price of explainability for the maximum-spacing clustering problem is
$\Omega(n-k)$.

###  5.2 Upper Bound

We present an algorithm that always obtains an explainable clustering with
spacing $O((n-k)OPT)$, where $OPT$ is the spacing of the optimal unrestricted
clustering. That, together with the previous lemma, implies that the price of
explainability for the maximum-spacing problem is $\Theta(n-k)$.

Algorithm 3 receives an optimal $k$-clustering ${\cal C}^{*}$ as input and
uses it as a guide to transforming an initial single cluster containing all
points of ${\cal X}$ into an explainable $k$-clustering. The existence of
cluster $C$ at line (*) follows from a simple pigeonhole argument. The
motivation for this choice is that $C$ has two points at distance at least
$OPT$, which is used to show the existence of a cut with a large enough
margin.

Algorithm 3 Ex-SingleLink(${\cal X}$)

${\cal C}^{*}\leftarrow$ optimal unrestriced $k$-clustering for points in
${\cal X}$.

${\cal C}\leftarrow$ single cluster containing all points of ${\cal X}$

for $i=1,\ldots,k-1$ do

Select a cluster $C\in{\cal C}$ that contains two points that lie in different
clusters in ${\cal C}^{*}$. (*)

Split $C$ using an axis-aligned cut that yields a 2-clustering
$(C^{\prime},C^{\prime\prime})$ with maximum possible spacing.

Remove $C$ from ${\cal C}$ and update ${\cal C}$ to ${\cal
C}\cup\\{C^{\prime},C^{\prime\prime}\\}$

end for

######  Lemma 8.

Given a set of points ${\cal X}$, Ex-SingleLink(${\cal X}$) obtains a
$k$-clustering ${\cal C}$ with spacing at least $OPT/(n-k)$, where $OPT$ is
the spacing of an optimal unrestricted clustering.

###### Proof.

First, we observe that it is always possible to properly execute line (*) of
Ex-SingleLink. In fact, if we pick $k$ points covering all the $k$ clusters of
${\cal C^{*}}$ then, by the pigeonhole principle, two of them will lie in the
same group in ${\cal C}$ since ${\cal C}$ has less than $k$ groups when line
(*) is executed.

To establish the result it suffices to prove that there is always an axis-
aligned cut that splits the selected cluster $C$ into two clusters with
spacing at least $OPT/(n-k)$.

Let $\mathbf{p}$ and $\mathbf{q}$ be two points in $C$ that lie in distinct
clusters in ${\cal C}^{*}$ and let $G=(V,E)$ be a graph, where $V$ is the set
of points in $C$ and $E$ connects points in $V$ with distance smaller than
$OPT/(n-k)$. Moreover, let $F=(T_{1},\ldots,T_{\ell})$ be a forest that is
obtained by running Kruskal’s MST algorithm on $G$.

######  Claim 2.

Points in $C$ that belong to distinct clusters of ${\cal C}^{*}$ must also
belong to different trees in forest $F$.

###### Proof.

For the sake of contradiction we assume that the claim does not hold. In this
case, there would be a path from $\mathbf{p}$ to $\mathbf{q}$ in $F$ and this
path would have an edge joining two points that belong to different clusters
in ${\cal C}^{*}$, which cannot occur since their distance is at least
$OPT>OPT/(n-k)$. ∎

The previous claim implies that $\ell\geq 2$ since $\mathbf{p}$ and
$\mathbf{q}$ belong to different clusters. We say that an axis-aligned cut is
good with respect to a cluster $C$ if it satisfies the following properties:
(i) it separates the points in $C$ into two non-empty clusters and (ii) it
does not separate points that lie in the same tree of $F$. If a good cut
exists, then we can use it to split $C$ into two clusters with spacing at
least $OPT/(n-k)$ since, by construction, points in different trees have
distance at least $OPT/(n-k)$. For the sake of contradiction let us assume
that such a cut does not exist.

For each $j\in[d]$ let $I^{\mathbf{p}\mathbf{q}}_{j}$ be the real interval
that starts in $\min\\{p_{j},q_{j}\\}$ and ends in $\max\\{p_{j},q_{j}\\}$,
that is,
$I^{\mathbf{p}\mathbf{q}}_{j}=[\min\\{p_{j},q_{j}\\},\max\\{p_{j},q_{j}\\}]$.

Moreover, for each tree $T$ in $F$, let $I^{T}_{j}$ be the interval that
starts at $\min\\{x_{j}|\mathbf{x}\mbox{ is a node in }T\\}$ and ends at
$\max\\{x_{j}|\mathbf{x}\mbox{ is a node in }T\\}$. Finally, for each edge
$e=uv$ in $F$ and each $j\in[d]$, let $I^{e}_{j}$ be the real interval that
starts at $\min\\{u_{j},v_{j}\\}$ and ends at $\max\\{u_{j},v_{j}\\}$. For a
real interval $I$, let $len(I)$ be its length.

Since there are no good cuts, for $j=1,\ldots,d$, we have

$\sum_{T\in F}len(I^{T}_{j})\geq len(I^{\mathbf{p}\mathbf{q}}_{j}).$

From the triangle inequality we obtain

$\sum_{T\in F}\sum_{e\in T}len(I^{e}_{j})\geq\sum_{T\in F}len(I^{T}_{j}).$

From the two previous inequalities we get

$\sum_{e\in F}len(I^{e}_{j})=\sum_{T\in F}\sum_{e\in T}len(I^{e}_{j})\geq
len(I^{\mathbf{p}\mathbf{q}}_{j}).$

A simple application of Jensen inequality shows that

$\sum_{e\in
F}len(I^{e}_{j})^{2}\geq\frac{(len(I^{\mathbf{p}\mathbf{q}}_{j}))^{2}}{f},$

where $f$ is the number of edges in $F$. By adding the above inequality for
all $j\in[d]$ we get

$\sum_{e\in
F}||e||^{2}_{2}\geq\frac{1}{f}||\mathbf{p}-\mathbf{q}||_{2}^{2}\geq\frac{OPT^{2}}{f},$

where $||e||_{2}$ is the distance between the two endpoints of edge $e$.

The last inequality implies $||e||_{2}\geq OPT/f,$ for some edge $e$. Thus, to
obtain a contradiction, it suffices to show that $f\leq n-k$, since we cannot
have edges in $F$ with distance $\geq OPT/(n-k)$

To see that $f\leq n-k$, let $k^{\prime}$ be the number of clusters in ${\cal
C}$ that are singletons and let $S^{\prime}$ be the set of points in these
clusters. Moreover, let $S\subseteq{\cal X}-S^{\prime}$ be a set of
$k-k^{\prime}$ points with each of them belonging to a different cluster in
${\cal C}^{*}$. Note that cluster $C$ is not a singleton since
$\mathbf{p},\mathbf{q}\in C$. Since both $C$ and $S$ are subsets of ${\cal
X}-S^{\prime}$ we have $|C\cup S|=|C|+|S|-|C\cap S|\leq n-k^{\prime}$ so that
$|C|-|C\cap S|\leq n-k$. It follows from Claim 2 that the number of trees in
$F$ is at least $|C\cap S|$ and, as a result, its number of edges $f$
satisfies $f\leq|C|-|C\cap S|-1<n-k$ edges. ∎

We can state the main result of this section.

######  Theorem 5.

The price of explainability for the maximum-spacing problem is $\Theta(n-k)$.

## References

  * [1] A. Adadi and M. Berrada, Peeking inside the black-box: A survey on explainable artificial intelligence (xai), IEEE Access, 6 (2018), pp. 52138–52160.
  * [2] D. Aloise, A. Deshpande, P. Hansen, and P. Popat, Np-hardness of euclidean sum-of-squares clustering, Machine learning, 75 (2009), pp. 245–248.
  * [3] E. Baralis, D. E. Pastor, and M. Cannone, Explainable ai for clustering algorithms.
  * [4] J. Basak and R. Krishnapuram, Interpretable hierarchical clustering by constructing an unsupervised decision tree, IEEE Transactions on Knowledge and Data Engineering, 17 (2005), pp. 121–132.
  * [5] D. Bertsimas and J. Dunn, Optimal classification trees, Machine Learning, 106 (2017), pp. 1039–1082.
  * [6] D. Bertsimas, A. Orfanoudaki, and H. Wiberg, Interpretable clustering: an optimization approach, Machine Learning, (2020), pp. 1–50.
  * [7] H. Blockeel, L. De Raedt, and J. Ramon, Top-down induction of clustering trees, arXiv preprint cs/0011032, (2000).
  * [8] M. Charikar, R. Fagin, V. Guruswami, J. Kleinberg, P. Raghavan, and A. Sahai, Query strategies for priced information, Journal of Computer and System Sciences, 64 (2002), pp. 785–819.
  * [9] M. Chavent, C. Guinot, Y. Lechevallier, and M. Tenenhaus, Méthodes divisives de classification et segmentation non supervisée: Recherche d’une typologie de la peau humaine saine, Revue de statistique appliquée, 47 (1999), pp. 87–99.
  * [10] J. Chen, Interpretable Clustering Methods, PhD thesis, Northeastern University, 2018.
  * [11] J. Chen, Y. Chang, B. Hobbs, P. Castaldi, M. Cho, E. Silverman, and J. Dy, Interpretable clustering via discriminative rectangle mixture model, in 2016 IEEE 16th International Conference on Data Mining (ICDM), IEEE, 2016, pp. 823–828.
  * [12] S. Dasgupta, N. Frost, M. Moshkovitz, and C. Rashtchian, Explainable k-means clustering: Theory and practice, in XXAI: Extending Explainable AI Beyond Deep Models and Classifiers, 2020.
  * [13] D. H. Fisher, Knowledge acquisition via incremental conceptual clustering, Machine learning, 2 (1987), pp. 139–172.
  * [14] R. Fraiman, B. Ghattas, and M. Svarc, Interpretable clustering using unsupervised binary trees, Advances in Data Analysis and Classification, 7 (2013), pp. 125–145.
  * [15] N. Frost, M. Moshkovitz, and C. Rashtchian, Exkmc: Expanding explainable $k$-means clustering, arXiv preprint arXiv:2006.02399, (2020).
  * [16] E. Horel and K. Giesecke, Computationally efficient feature significance and importance for machine learning models, 2019.
  * [17] E. Horel, K. Giesecke, V. Storchan, and N. Chittar, Explainable clustering and application to wealth management compliance, 2020.
  * [18] T. Kanungo, D. M. Mount, N. S. Netanyahu, C. D. Piatko, R. Silverman, and A. Y. Wu, A local search approximation algorithm for k-means clustering, Computational Geometry, 28 (2004), pp. 89–112.
  * [19] J. Kauffmann, M. Esders, G. Montavon, W. Samek, and K.-R. Müller, From clustering to cluster explanations via neural networks, arXiv preprint arXiv:1906.07633, (2019).
  * [20] E. S. Laber, R. L. Milidiú, and A. A. Pessoa, On binary searching with nonuniform costs, SIAM Journal on Computing, 31 (2002), pp. 1022–1047.
  * [21] B. Liu, Y. Xia, and P. S. Yu, Clustering through decision tree construction, in Proceedings of the ninth international conference on Information and knowledge management, 2000, pp. 20–29.
  * [22] O. Loyola-González, A. E. Gutierrez-Rodríguez, M. A. Medina-Pérez, R. Monroy, J. F. Martínez-Trinidad, J. A. Carrasco-Ochoa, and M. García-Borroto, An explainable artificial intelligence model for clustering numerical databases, IEEE Access, 8 (2020), pp. 52370–52384.
  * [23] S. M. Lundberg and S.-I. Lee, A unified approach to interpreting model predictions, in Advances in neural information processing systems, 2017, pp. 4765–4774.
  * [24] N. Megiddo and K. J. Supowit, On the complexity of some common geometric location problems, SIAM journal on computing, 13 (1984), pp. 182–196.
  * [25] C. Molnar, Interpretable Machine Learning, Lulu.com, 2020.
  * [26] M. Moshkovitz, S. Dasgupta, C. Rashtchian, and N. Frost, Explainable k-means and k-medians clustering, in Proceedings of the 37th International Conference on Machine Learning, H. D. III and A. Singh, eds., vol. 119 of Proceedings of Machine Learning Research, PMLR, 13–18 Jul 2020, pp. 7055–7065.
  * [27] W. J. Murdoch, C. Singh, K. Kumbier, R. Abbasi-Asl, and B. Yu, Interpretable machine learning: definitions, methods, and applications, arXiv preprint arXiv:1901.04592, (2019).
  * [28] F. Pedregosa, G. Varoquaux, A. Gramfort, V. Michel, B. Thirion, O. Grisel, M. Blondel, P. Prettenhofer, R. Weiss, V. Dubourg, J. Vanderplas, A. Passos, D. Cournapeau, M. Brucher, M. Perrot, and E. Duchesnay, Scikit-learn: Machine learning in Python, Journal of Machine Learning Research, 12 (2011), pp. 2825–2830.
  * [29] D. Pelleg and A. Moore, Mixtures of rectangles: Interpretable soft clustering, in ICML, 2001, pp. 401–408.
  * [30] C. Plant and C. Böhm, Inconco: Interpretable clustering of numerical and categorical objects, in Proceedings of the 17th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD ’11, New York, NY, USA, 2011, Association for Computing Machinery, p. 1127–1135.
  * [31] M. T. Ribeiro, S. Singh, and C. Guestrin, ” why should i trust you?” explaining the predictions of any classifier, in Proceedings of the 22nd ACM SIGKDD international conference on knowledge discovery and data mining, 2016, pp. 1135–1144.
  * [32] C. Rudin, Stop explaining black box machine learning models for high stakes decisions and use interpretable models instead, Nature Machine Intelligence, 1 (2019), pp. 206–215.
  * [33] S. Saisubramanian, S. Galhotra, and S. Zilberstein, Balancing the tradeoff between clustering value and interpretability, in Proceedings of the AAAI/ACM Conference on AI, Ethics, and Society, 2020, pp. 351–357.
  * [34] T. Vidal and M. Schiffer, Born-again tree ensembles, in Proceedings of the 37th International Conference on Machine Learning, H. D. III and A. Singh, eds., vol. 119 of Proceedings of Machine Learning Research, Virtual, 13–18 Jul 2020, PMLR, pp. 9743–9753.
  * [35] D. P. Williamson and D. B. Shmoys, The Design of Approximation Algorithms, Cambridge University Press, 2011.