Explaining Kernel Clustering via Decision Trees
Authors: Maximilian Fleissner
Leena Chennuru Vankadara
Debarghya Ghoshdastidar
Venue: ICLR 2024 poster (2024)
Keywords: Kernel k-means
Price of explainability
Primary area: visualization or interpretation of learned representations

Abstract: Despite the growing popularity of explainable and interpretable machine learning, there is still surprisingly limited work on inherently interpretable clustering methods. Recently, there has been a surge of interest in explaining the classic k-means algorithm, leading to efficient algorithms that approximate k-means clusters using axis-aligned decision trees. However, interpretable variants of k-means have limited applicability in practice, where more flexible clustering methods are often needed to obtain useful partitions of the data. In this work, we investigate interpretable kernel clustering, and propose algorithms that construct decision trees to approximate the partitions induced by kernel k-means, a nonlinear extension of k-means. We further build on previous work on explainable k-means and demonstrate how a suitable choice of features allows preserving interpretability without sacrificing approximation guarantees on the interpretable model.

Published as a conference paper at ICLR 2024
EXPLAINING KERNEL CLUSTERING VIA DECISION TREES
Maximilian Fleissner
Leena C. Vankadara
Debarghya Ghoshdastidar
Technical University of Munich flei ssse récit. t.m.tumddde.
Amazon Research Tübingen v @ ama zon. com
Technical University of Munich ghoshdas tum de
ABSTRACT
Despite the growing popularity of explainable and interpretable machine learn- ing. there still surprisingly limited work on inherently interpretable clustering methods. Recently, there has been a surge of interest in explaining the classic k-means algorithm, leading to efficient algorithms that approximate k-means clus- ters using axis-aligned decision trees. However, interpretable variants of k-means have limited applicability in practice, where more flexible clustering methods are often needed to obtain useful partitions of the data. In this work, we investigate interpretable kernel clustering, and propose algorithms that construct decision trees approximate the partitions induced by kernel k-means, nonlinear extension of k-means. We further build on previous work on explainable k-means and demon- strate how a suitable choice of features allows preserving interpretability without sacrificing approximation guarantees on the interpretable model.
INTRODUCTION
The increasing predictive power of machine learning has made it a popular tool in many scientific fields. Sensitive applications such healthcare autonomous driving however require more than just good accuracy it is also crucial for model's 's decisions to be interpretable (Tjoa & Guan 2020 Varshney& & Alemzadeh] 2017). Unfortunately, popular machine learning models are not transparent and are often referred to as "black box" approaches. The demand for explainable machine learning has led to the development of several tools over the last few years, alheit mostly for supervised learning. Methods such as LIME or Shapley values (Ribeiro et al. 2016 Lundberg & Lee (017) are designed to explain the prediction of any given machine learning model. However, pesthoc-expllinabblie unreliable and has been critized for not providing insight into the underlying model itself (Rudin) 2019). Counterfactual explanations on the other hand explicitly show the change in prediction had the input variables been different (Wachter et al.) 2017), but do not lead to easily interpretable models. Hence, |Rudin| (209)) calls on researchers and practitioners to "Stop explaining black box machine learning models for high stakey decisions and use interpretable modely instead".
often
Decision trees are at the heart of several inherently interpretable machine learning models (Molnar) 2020; Breiman| 2017). and have recently also gained significant interest in the field of clustering (Bertsimas et al. 2018 Fraiman et al.) 2013 Ghattas et al. 2017). Through recursive partitioning of the data based on individual features, they provide interpretability on a global scale by identifying the important features, while at the same time also allowing to retrace the path of individual decisions through the tree. Despite the extensive empirical research on decision trees for clustering, Moshkovitz et al. (2020) were the first to introduce clustering model based on decision trees that also satishies worst-case approximation guarantees. They propose the Iterative Mistake Minimization (IMM) algorithm which approximates given k-means clustering by decision tree with k leaves, where each leaf represents a cluster. The quality of the resulting interpretable clustering is measured by the price explainability, defined the ratio between the cost of the decision tree and the optimal k-means cost. IMM returns a decision tree with price of explainability of order (R:2). implying that the interpretable clusters achieve a cost not much worse than the optimal partition.
Various interpretable clustering solutions for the k-means problem with theoretical guarantees have emerged (see Appendix A for overview). However, despite these advancements, fundamental

---

Published as a conference paper at ICLR 2024
Figure 1: k-means does not perform well on halfmooos data that is not linearly separable, and explainable k-means naturally inherits its flaws. Kernel k-means perfectly finds the clusters and hence, its interpretable variant (proposed Kernel IMM) returns axis aliined decision tree with good clustering.
issue persists: the k-means cost ill-suited for real-world datasets, as it fails to identify clusters that not linearly separable. Clustering methods deployed in practice tend to be complex, and consequently even less interpretable than standard k-means. The kernel k-means algorithm (Dhillon) al., 2004) that extends the standard k-means by implicitly mapping data reproducing kernel Hilbert space (RKHS), is particularly notable. It allows to discern clusters beyond Voronoi partitions of the input space, but this increased flexibility further diminishes the model's interpretability.
Works on interpretable kernel methods are scarce. Chau et al. (2022) propose efficient methods for computing Shapley values for kernel regression, which provide post-hoc explanations. [W al.) (2019) enforce interpretability in kernel dimension reduction by linearly projecting the data into low-dimensional space before computing kernel matrices spite of operating on fewer features, the kernel step of this approach is not interpretable. As such, the interpretability of kernel methods remains an open problem. We resolve this the context of clustering by providing decision tree based interpretable approximations of the kernel k-means algorithm with provable guarantees.
Our contributions. While significant body of work decision trees for explaining k-means has emerged, these algorithms cannot directly be translated to the kernel setting. In particular, there are cases where explainable k-means does lead axis-aligned decision trees for any choice of features for the popular Gaussian kernel. We prove this in Section by introducing the notions of interpretable feature maps and interpretable decision trees, which provide a theoretical characterization of the obstacles that interpretability faces in kernel clustering. Building on these insights Section 4 we demonstrate how suitably chosen surrogate features can resolve this issue, and we derive kernelized variant of the IMM algorithm (Moshkovitz et al., 2020) that preserves interpretability. These surrogate features exist for several important product kernels, including the Gaussian and Laplace kernel. Crucially, the proposed algorithm (Kernel IMM) also comes with worst-case guarantees on the price of explainability for class of interpretable Taylor kernels that include the Gaussian kernel. By incorporating information encoded in the nonlinearity of kernel k-means, the resulting decision trees lead to significantly better results than explainable k-means, as Figure illlsstraess. In Section 5 we further build on previous work (Frost et al., (2200) derive two kernelized algorithms (Kernel Ex KMC and Kernel Expand) that can be used to further refine the partitions obtained from Kernel IMM (by adding more leaves to the tree). Both can also be run on an empty tree, but do not admit worst-case bounds in this case. We conclude by demonstrating the empirical performance of the proposed methods in Section The algorithms are included in Table
Table 1: Overview of our algorithms (x; denotes i-th coordinate of point æ E Ie))
Algorithm
Axis-aligned cuts
Worst price of explainability
Kernel IMM
for additive kernels
E 10, 0z]
O(k2)
(Remark
Appendix H
for interpretable Taylor kernels for distance-based product kernels
I; E
10, 02]
Oddk2) (Theorem
r; E
00, 0g
Oldk2 Caam) (Theorem
Kernel EX on empty tree
2 0 or 2; E [0,, 02]
Provably unbounded (Theorem
Kernel Expand on empty tree
24 2 or x4
00, 02]
Provably unbounded (Remark)
2

---

Published as a conference paper at ICLR 2024
2 BACKGROUND AND PRELIMINARIES
Consider a dataset of n points, X = {x(1), xx(2) ,.... 2011) } S Rdd We use x(0) to denote the i-th data
point in X, while the notation x; denoting the i-th coordinate of any E Rd appears more frequently.
k-means and kernel k-means. For a partition of X into k disjoint clusters Ci...., Ck with means c Ck Rd, the k-means cost of the partition is defined as
k cost(Ci,...,. = Σ
1 al1 2EC
The optimal k-means cost of X is the minimum achievable cost, over all partitions C1,... ......,C. C2- We define M = (ck as the set of cluster centers obtained from some algorithm designed to minimize the k-means cost ( Since finding the optimal set of centers is NP-hard (Dasgupta 2008), in practice M may not necessarily consist of the & optimal cluster centers. Kernel k-means c clustering DDillon al. 2004) replaces the squared Euclidean distance in ① by kernel-based distance. A kernel is a symmetric, positive definite function K : IR x Rd 7 R. Every kernel is implicitly associated with feature space H. called the reproducing kernel Hilbert space (RKHS), and a feature map 1b Rd + H satisfying K (Ir y) = (wb(z), (b()) for all x, y E R For algorithms that only require knowledge of inner products between points (xx)) and (by), there is no need to compute the feature map explicitly, but one may instead use the kernel ((r, y) to evaluate (xxxx), (V))). Thus the (implicit) feature map 1 transforms the data non-linearly to a high dimensional space that provides additional flexibility in the model, without increasing the computational complexity. This is commonly known as the kernel trick. Given data X C IR and a kernel K on Rd kernel k-means attempts to find a partitioning C {CI,..., ..., CR of X that minimizes
cost Ct) = Σ Σ 1=1 PEC
[1v(() - c/
where the centers C1...., Cj are the means of each cluster in the feature space H. Appendix shows how the cost (2) is expressed in terms of kernel K and also includes the kernel k-means algorithm.
Explainable k-means. The goal of explainable k-means clustering is approximate given partition CI...., Cs X C Rd, with centers M, by an inherently interpretable model. Axis-aligned decision trees with & leaves have emerged as a natural choice for this purpose, where every leaf of the tree T corresponds to one cluster. Intuitively, one could think that the tree can simply be obtained by using a supervised learning algorithm with the cluster assignments as labels. However, Moshkovitz et al. (2020) Section 3) show that such algorithms can have arbitrarily bad worst-case approximation guarantees on the cost of the clustering induced by the decision tree, which we denote by cost(T, X X). This observation has sparked the development of more sophisticated approaches (Moshkovitz et al. 2020 Esfandiari et al. 2022 Charikar & Hu 2022 Gamlath et al.) [021 Laber & Murtinho (021), all of which construct the tree T in top-down manner: At every internal node an axis-aligned cut x; रे f partitions the data at node u, while ensuring that every cluster center e E M ends up in exactly one leaf of T. This last requirement is crucial to obtain approximation guarantees. While several works restrict 7' to have exactly 1: leaves, few also allow more than k leaves for better approximation (Makarychev & Shan 2022; Frost et al.) 2020). Appendix A provides review of works on explainable k-means, while Appendix C gives a more detailed description of the Iterative Mistake Minimization (IMM) algorithm (Moshkovitz al. 2020) that we build on in Section
EXPLAINABLE KERNEL K-MEANS VIA CUTS ON FEATURE MAPS
The objective of this paper is to present an inherently interpretable model that approximates the kernel k-means algorithm. In this section, we make the first steps towards this goal. Standard supervised approaches for learning decision trees are questionable since they, as discussed earlier, can be arbitrarily bad for approximating even the standard k-means clustering. On the other hand, the aforementioned iterative decision tree construction admits good worst case guarantees in the context of k-means. Hence, natural starting point would be to kernelize it. Unfortunately however,
3

---

Published as a conference paper at ICLR 2024
the method heavily relies explicitly characterizing the cluster centers. In kernel clustering, these cluster centers C1, " Ck reside in the RKHS H. instead of IR and typically do not have a pre-image in the input space R Thus, operating on centers necessitates explicit computation of the feature maps, which is in contrast to the typical use of the kernel trick.
A naive kernelization of existing algorithms would hence aim to operate in H and find axis- alis-aligned cuts using the coordinates of the projection v(xx). This approach has two fundamental limitations. For one, requires an explicit characterization of the RKHS H. or the feature map the two famously implicit entities in the kernel trick. Explicit characterizations of H or to however are not known for most kernels, and even if they are known, the dimension of H. could be infinite Steinwart et al., 2006), making it practically impossible to iterate over all axes. This problem does not pose a practical concern when clustering finite set of points. Any kernel matrix K E 1nxx, computed on data X = {x(") ..... x r can be decomposed as K = Φ for some + [x(x)) ( (x(())))..)((())))) ;=1 E R through Cholesky or eigendecoomosition, providing a data- dett-dependent feature map that we denote as Ø X XXRR.
The second concern is how to translate axis axis-aligned cuts dy(x) 2 9 back to axis-aligned cuts in Rd. Here, 3j denotes the j-th coordinate of Φ X + RDD This issue is critically important in the context of interpretability, and can be decomposed into two principle concerns: Firstly, if Φy(z) is a function of more than one coordinate I;, then cut (x) रे 0 cannot correspond to an axis- aligned partition of TR.. Secondly, even if dby depends on exactly one coordinate zj, the cut Φ (xx ž 0 cannot correspond to a cut r, こ 0' unless Φy is monotonic.
These conditions are not trivial and, as we show below, the popular Gaussian kernel does not satisfy either of the two conditions, whereas some additive kernels satisfy both. To formally show this, we introduce the notion of interpretable feature maps.
Definition 1. (Interpretable feature maps) Let ob X + R.D be a feaurr map defined on the dataset X C Rdd such that K K(x, v) = (0(#),, Ei= " (y) for all x, E X. We say that the feature map o = (d1...., .D) is interpretable if each (1))) depends exactly on one coordinate of x.
The following result shows that no feature map for the Gaussian kemel can be interpretable, even if we allow the feature maps to be data- detaadepennent.
Theorem 1. (The Gaussian kernel cannot have interpretable feature maps) Consider the Gaussian
kernel K K(x, y) e vil in d > dimensions. There exists dataset X such that any feature map 6= X + IR. satisfying (Ø(x), o(y)) = K(x, y) for all x, y E X, there exists some j E [D]
such that Φ depends on more than just one input dimension of x X.
The short proof is given in Appendix D.I In Section 4 we resolve the inherent non- non-interpretability of feature maps for the Gaussian kernel by resorting to suitably chosen surrogate features. However, this still leaves the concern about monotonicity of $5. This too cannot hold for the Gaussian kernel. Theorem 2. (The Gaussian kernel does not admit monotonic features) Consider the one- dimensional Gaussian kernel K(x.g) y) =-->lz=-?? Then, there exists dataset X C R such that for any feature map o= X + R there exists component و5, j E [D] that is not monotonic.
The proof is included in Appendix D.2 Theorem 2 suggesst that the existing notion of interpretability, specified through threshold cuts x; こ. 6, is too restrictive for deriving interpretable decision trees for kernels. Hence, we propose to expand the definition of interpretability. Although the partitions at each node should still align with the axes of Red (this ensures that the important features can be identified), we allow the partition the node be any interval and its complement.
Definition 2. (Interpretable decision trees) Consider a decision tree T that partitions a dataset X C Fdd into & leaves. We call T an interpretable decision tree if at every node u E T. there exists some E [d], 01 < 02 E RR such that the data x that arrives at u is split into two disjoint subsets
X {a E X : 24 E 021} and X = {ar E X x, $ 02].
(3)
To conclude this section, we remark that several important additive kernels do in fact admit feature maps that give rise to interpretable decision trees. Remark 1. (Certain additive kernels have interpretable and monotonic features) Additive kernels on d refer to kernels that can be decomposed as K K(x,Y) E K2(2, y), where each K₃ is
4

---

Published as a conference paper at ICLR 2024
Algorithm 1 Kernel IMM for interpretable Taylor, or distance-based product kernels
Input: Data X, integer k. kernel K with surrogate feature map Φ. For interpretable Taylor kernels
see Definition 3 for distance- kernels see Equation (4).
Output: Interpretable decision tree T that partitions X into & leaves
Get reference clustering Cl...., Cj f- KERNEL K- C-MEANS(X, K, k)
Compute surrogate features @
(z) ... (a(x)) and centers M = {cI,..., C& under é.
Construct a decision tree < IMM( @, y, M), where y denotes the cluster assignments.
Translate threshold cuts of T back to decision tree on X.
a kernel on R. Additive kernels are commonly used for comparing histograms, e.g. in computer vision (Maji al. 2012 Vedaldi & Zisserman 2012). In Appendix H we consider three popular additive kernels and derive feature maps & for which any threshold cut 0,(x) 2 0 translates to an axis- axis-aligned cut 2; E [81, 02). Hence, one may run IMM on the map & and directly translate the tree from the feature space to an interpretable decision tree.
4 KERNEL ITERATIVE MISTAKE MINIMIZATION (KERNEL IMM)
In this section, we present an interpretable kernel k-mmans algorithm that is applicable to a wide range of bounded product kernels, which include the Gaussian kernel K(x, v) = ---
well as other bastance-based product kernels such the Laplace kernel K (ar, y) -- We focus on the aforementioned idea of constructing interpretable decision trees via axis-aligned cuts of suitably chosen feature maps é. therehy leveraging existing approximation guarantees. The base interpretable k-means method that we "kernelize" is the IMM algorithm, primarily due to its simpler analysis. We believe the same construction can also leverage worst-case approximation guarantees for other explainable k-means algorithms (with tighter guarantees). The proposed Kernel IMM algorithm is described in Algorithm [ and illustrated in Figure
Surrogate features. Bounded product kernels on 12d can be expressed as K y) II K2(2, y). where each K; is a kernel on R, operating on the i-th coordinate of data. We assume that K2(x, y) I K2( x) = for all æ, y E Rd. The RKHS of a product kernel K is given by the tensorization H = Hi ... @ Hd. where Hi is the RKHS of kernel KG The implicit feature map Vi Rd H associated with the product kernel K can be related to the feature maps th; RR + H4 of the d individual kernels K; via (x))),, (v)) = I[ (,) 4/ (vx)). In order to preserve axis- aligned structures, we propose to use a surrogate feature map (#I...., Φa), where each Φ is finite-dimensional approximation to v/. Notably, & does not approximate a map to H but instead to the Cartesian space H4 ... x Ha. and (Ø(z), Φ(v)) = Σi= (2,) (l.)).)) * (x(x),, (w)). Crucially however, we will show later that the additional cost induced by this step can be bounded. By construction, x (dx) is interpretable feature map, and we may compute the set of cluster centers M in the surrogate feature space associated with ø. As described in [[ we let IMM operate on M. Finally, interpretability of ensures that axis-aligned cuts of do in fact correspond to axis-aligned partitions of the input space Rdd For the Gaussian kernel, our surrogate features Φ; are Taylor approximations to vh;- We also present an alternative, quite general choice for Φ; that works for all distance-based product kernels, but leads to data-dependent approximation guarantees.
Interpretable Taylor kernels. We now define a class of kernels over E that we refer to as inter- pretable Taylor kernels, and construct surrogate features for these kernels.
Detinition 3. (Interpretable Taylor kernels and their surrogate features) Let K; be bounded kernel on connected domain X; C R. of the form K2(z, = for some differentiable function f and an fanyytic g. Denote by ( the j-th derivative of g. Assume that g 2 0 for all j E N and that 2و (zf' +f(z))) K; an interpretable Taylor kernel. Furthermore, assume K is product of d interpretable Taylor kernels Ki...., Kd, defined on a connected domain X C TRd. Given an integer M, we define the surrogate feature map for K as d(x) = (o:(x:)) where each 6, : R + RM+1 is given by (1(2) (or,( where we define (2) 23 f(x) (6)) (0)/3) for all j M.
has at most one solution z on Xt. Then, we call
5

---

Published as a conference paper at ICLR 2024
R²
6V. = ()(o))) exp xmm1p
1/ (ar)
21
R2
H
Decouple dimensions
(22
(xx) exp 11--11
#*
Output of kernel k-means
Gaussian RKHS
(11((z1)
Approximate ti M Taylor features
Surrogate space (o)
IMM
((x))
R
(g,)
Threshold tree
(x2)
feature space
22
Build surrogate features & centers
(1,)
0i(x;) RR
(M = 2)
cluster
cluster
01,2
Visualizing Taylor features (M = 2]
Output of Kernel IMM.
11,1
22 E [0, 0z]
2,,7
95.2
Translate back to imput space
cluster cluster
472,1
Interpretable decision tree
Figure 2: A schematic of Kernel IMM for Interpretable Taylor kernels.
The Gaussian kernel with bandwidth y > is a product of interpretable Taylor kernels, because with g(2) exp(2z) and f(z) exp( )22²), (2) + jf(z) O has at most one solution on (0, oo). This is sufficient because we can always assume data X that clustered using the Gaussian kernel to be contained in (0, oo)a, 3 as shifting does not affect the clustering cost.
Theorem 3. (Threshold cuts in the surrogate feature space of interpretable Taylor kernels yield interpretable decision trees) Let K be product interpretable Taylor kernels, and let & denote its surrogate feature map. Then, threshold cut of the form ( 2 0 leads to an interpretable decision tree in TRd.
Our choice of surrogate features doesn't 't only provide interpretable decision trees. but also preserves worst-case bounds on the cost. To formalize this, we generalize the price of explainability to kernels.
Definition 4. (The price of explainability) For a set C Rdd and un interpretable decision tree T defined in 2 the price of explainability of T X is defined the ratio p(T, X) cost(T, //costt (X), where costopt (X) is the optimal kernel k-means cost. The price of explain- ability of the data set X is given by p(X) min p(T, X), where the minimum is taken over all
interpretable decision trees.
The Kernel IMM algorithm admits worst-case guarantees quite similar to the ones obtained in the linear setting, albeit with additional factor of order d. This is result of operating the surrogate features that decouple the d input dimensions (see Appendix E.
Theorem (Price of explainability for interpretable Taylor kernels) Let CI...., Ce be the clusters of dataset X C _ derived from kernel k-means, where the kernel K is interpretable Taylor kernel. Denote by & x(X)
) the surrogate features for K on X. Then, the interpretable decision
tree obtained from Kernel IMM & satisfies pTT, X) O (dk?2 coottpt(X1] where 5 = 5(M) depends on the order M of the surrogate feature map and lim 8(M) = for any dataset X. Thus, by adaptively choosing M such that ă = (ccostopt) we obtain (dk?2) bounds.
O(dk²

---

Published as a conference paper at ICLR 2024
The proof can be found in Appendix For interpretable Taylor kernels, Kernel LMM operates in feature space of dimension O(dM). In practice, often even low orders M & of the Taylor- Taylor-based surrogate features provide enough flexibility to obtain good interpretable clusterings, and hence Kernel IMM computationally is not much more expensive than standard IMM
Extension to all distance- based product kernels. To conclude this section, present extension of Kernel IMM the entire class of distance-based product kernels K (2, y) = IT= h (lz; - y: l)+ where h is a decreasing function on the positive real line, with h(0) = 1. Examples include the Laplace kernel, for which (t) = exp(-t). For these kernels, we simply set
(x)( K; (x, 2(0) h((xa-11)) 1
where 2d6 denotes the jth point in the dataset X. Because $1. (x) S 0 if and only if |., 2!!) h (0), this leads to interpretable decision tree. However, the worst-case bounds obtained from
IMM do not translate directly.
Theorem 5. (Price of explainability for distance-based product kernels) Let Ci...., Cx be the clus-
ters of a dataset X C IR derived from kernel k-means, where the kernel K is distance-based prod- kernel. Denote by 4 == =x(x) the surrogate features for K on X, where &x (x) K1 x(1)). Then, the interpretable decision tree obtained from Kernel IMM on & satisfies p(T, X) O (Cak2). where C depends on the dataset X and the kernel K.
We discuss this in Appendix G Despite the data-dependent approximation guarantee, observe in practice that the surrogate features defined in (4) perform well, sometimes even outperforming the surrogate Taylor features of the Gaussian kernel.
GREEDY COST MINIMIZATION
While the previous two sections cover several important kernels, there may nonetheless be cases where Kernel IMM not applicable (because no suitable surrogate features exist), or not powerful enough to approximate kernel k-means (due to its restriction to just k leaves, as illustrate in Figure 3). To address these issues, we propose kernelized variants of the ExKMC algorithm (Frost al., 2020), which greedily add new leaves. This does not require computations in the feature space: Any set of reference clusters C1...., C3 obtained from kernel k-means implicitly comes with a set of reference centers M (cI...,,CK, c&) H. The kernel trick ensures that the distance between the feature map of any point (x) E H and a cluster center ej can be evaluated without explicitly computing the center as
(a)()) cill K( +
Σ B.EEC;
K(y,2)
2
K(a,y)
(5)
C
Kernel ExKMC (Algorithm 2
The algorithm proceeds sequentially. For every node u of the decision tree, let X denote the set of points that reach the node u. A threshold cut (i. f) is chosen,
separating X into two subsets X X" n {a, I f) and X X {z, 0). The Kernel ExKMC algorithm chooses (i, 0) as the minimizer of the cost function
costezkme (u, i, 0) = min
Σ (1+(()) j.E
c2 + Σ [10(z) - 21
(6)
ZEXY
TEX;
where the squared distances can be computed using (5). One reference center is chosen for each of the two child nodes of u. To decide on which node to split, choose the one that maximizes the difference between the cost of not splitting, given by min
Σ [[v(x) - e, 1|2 and cost 0).
jE[K x
Since all relevant computations happen in the input space, and no explicit feature map is needed, the algorithm is applicable to arbitrary kernels and can be used to refine any given partition CI...., Fa....,C,, Op- empty tree does not admit approximation
Unfortunately, can prove that Kernel ExKMC guarantees when limited to & leaves.
Theorem 6 (ExKMC does not admit worst-case bounds). For any N there exists a data set X C R such that the price of explainability on X is p(X) = 1, IMM attain this minimum, but ExKMC (initialized on an empty tree) constructs decision tree T with p(T, X) m.
7

---

(Kernel Expand does not admit worst-case bounds) In the same way as Kernel ExKMC, Kernel Expand does not admit worst-cas. bounds when initialized without Kernel IMM. This is Published as a conference paper at ICLR 2024
K-means
Kernel k-means
Kernel IMM
Kerne ExKMC
Kerne Expand
Fay
Figure 3: Standard k-means is ill-suited for clustering certain datasets, and this translates to explain- able k-means (not plotted here). Kernel k-means recovers the ground truth well. However, Kernel IMM is restricted to 3 leaves and not powerful enough to approximate it. To resolve this, we suggest Kernel ExKMC and Kernel Expand, which extend the tree leaves.
Algorithm 2 Kernel ExKMC
Algorithm 3 Kernel Expand
Input: Number of leaves E N, reference clusters C...., Ck. decision tree T with leaves CI...., Op Output: Tree with leaves L Initialize the set of leafs = Cpp
Input:
Number of leaves N, reference clusters
decision tree with leaves CI,..., CG Output: Tree with m leaves L Initialize the set of leafs as C (ČI...., Cpp
while G] < m do
while |4] < m do
Choose node X C and a cut (i, min-
Choose data X C and cut (i, 0) min-
imizing (6)
imizing (
Update by replacing X" L by its two child nodes XR
Update C by replacing X e C by its two
child nodes X X
end while
end while
The proof can be found in Appendix [ If Kernel ExKMC is run as refinement of Kernel IMM (which constructs an interpretable decision tree in the sense of Definition 2 with two-sided threshold cuts) then we suggest sticking to this expanded notion interpretability. and Kernel ExKMC at every node chooses (i, (1,02) E [d] x I²2 and checks whether Ię E [01. 0g] or not.
Kernel Expand (Algorithm 3). We suggest another algorithm, Kernel Expand, that also adds new leaves to an existing tree, but maximizes the purity of each leaf. This is achieved by minimizing
costezp 0) min (1f= XE c(x) # c + H[ E X : c(x) + ci) j.E((]
(7)
where c(x) denotes the cluster center of according the reference partition M. To decide on which node to split, we again choose the one that maximizes the difference between the cost of not splitting, given by min
(x E X" c(x) # Cj and costexpanddi. 8).
jE(k]
Remark 2.
obvious from the example in Section 3 of MMoskooviz el al. 2020
Finally, it is important to note that while adding more leaves improves the clustering, gradually reduces the interpretability of the tree. Thus, there is trade-off between explainability and accuracy in Kernel ExKMC and Kernel Expand.
EXPERIMENTS
We validate our algorithms on number of benchmark datasets, including three synthetic clustering datasets, Pathhased, Aggregation and Flame (Fränti & Sieranoja) and real datasets, Iris (Fisher 1936) and Wisconsin breast cancer (Strect et al., 1993). On all five datasets, we evaluate Kernel IMM as well as the greedy cost minimization algorithms from Section Kernel ExKMC and Kernel Expand, both which refine Kernel IMM by adding more leaves. All experiments reported here use either the Laplace the Gaussian kernel. In Appendix(H
derive suitable approximate feature maps and evaluate Kernel IMM for the additive x" kernel, which well-suited for clustering histograms or distributions. These results underline the usefulness of our method beyond distance-based product
8

---

Published as a conference paper at ICLR 2024
Price of explainability
Rand index
1.2
IMM
k-means
Kernel IMM
Keree Expend
IMM
Kernel EXKMC
Kemel EXCMC
Komel k-means
Kernel Expaid
Price of axplainailiyy
L0
0.9
Rand
077
a.c
0.2
Pathbased
Aggropation
Flame
Inis
Cancer
Pathbased Aggregation
Flame
Infs
Cancer
Figure 4: We verify the approximation properties of our algorithms by computing the price of explainability (left plot). We also compare the clusters obtained on k-means and IMM, as well as kernel k-means and our three algorithms to the ground truth via the Rand index (right plot).
kernels. Finally, we also compare Kernel IMM to CART, which performs similarly well. Details on all experiments can be found in Appendix [ Although Kernel IMM can lead to sub-optimal solutions, its greedy refinements mostly result in a price of explainability close to (see Figure for 4 the Pathbased dataset). Figure reports the price of explainability of the three proposed explainable kernel clustering methods (closer to is better). Since the ground truth is known in all datasets considered here, Figure also reports the adjusted Rand index (Pedregosa et al.) (201T) that measures the agreement between the interpretable clusters and the true labels (a higher value is better). This shows that kernel k-means is naturally superior to k-means and explainable k-means, and one can observe that Kernel ExKMC and Kernel Expand mostly achieve Rand index as good as that of kernel k-means, establishing that our methods provide both interpretable and accurate clusters. In addition, Kernel IMM improves over h-means and IMM in recovering the ground truth.
CONCLUSION AND DISCUSSION
In this paper, we contribute to the increasing need for interpretable clustering methods by explaining kernel k--means using decision trees. By operating on carefully chosen features, interpretability can be preserved, while still allowing for approximation guarantees. We characterize the obstacles that interpretability faces in kernel clustering, and find that interpretable feature maps play a key role. These maps may also be useful to understand the interpretability of other kernel methods, which still rely almost exclusively on post-hoc explainability.
On the price of explainability for kernels. We observe below that the price of explainability for kernel k-means, as defined in Definition 4 may not be finite for arbitrary kernels.
Theorem 7 (Unbounded price of explainability). Consider either the quadratic kernel K(x, y) = (a. 8) or the e-neighborhood kernel K (I. () 1 -1ll)). For both, there exists a dataset X such that p(X) Dc.
The above result, proved in Appendix K is in stark contrast standard k-means, where IMM always ensures a bounded price of explainability. Our experiments further show that the price of explainability is close to 1 even cases where the interpretable clustering model is quite different from the reference partition. In fact, if the kernel k-means cost is 2(n) for a dataset of size n and the kernel bounded, then the price of explainability is O(1). This indicates that typical metrics should be adjusted depending on the kernel and the data. While the Rand index may be used if ground truth is known, a fundamental question remains unsolved: Under what conditions on the data can decision tree achieve good agreement with the nonlinear partitions of kernel k-means? Another question is whether approximation guarantees can be improved. It is very likely that specific kernels benefit from algorithms tailored to their cost functions. Finally, investigating lower bounds (beyond the ones a linear kernel inherits from existing results on explainable k k-means) also poses an interesting direction for future work.

---

Published as a conference paper at ICLR 2024
Ethics statement. While we do not expect negative societal impacts of method, remark that clustering algorithms themselves can be biased, and this can translate to its interpretable approxima- tions.
Reproducibility.
We add further details on the experiments in Appendix ! In addition, all proofs for our theoretical results can be found in the appendix, and have been referenced in the main paper.
ACKNOWLEDGMENTS
This paper is supported by the DAAD programme Konrad Zuse Schools of Excellence in Artificial Intelligence, sponsored by the Federal Ministry of Education and Research, and the German Research Foundation (Research Grant GH 257/4-1).
REFERENCES
Dimitris Bertsimas, Agni Orfanoudaki, and Holly Wiberg, Interpretable clustering via optimal trees. arXiv preprint arXiv: arXiv:1812.00539) 2018.
Leo Breiman. Classification and regression trees. Routledge, 2017.
Emilio Carrizosa, Kseniia Kurishchenko, Alfredo Marín, and Dolores Romero Morales. Interpreting clusters via prototype optimization. Omega, 107:102543, 2022.
Moses Charikar and Lunjia Hu. Near-optimal explainbbee k-means for all dimensions. Proceedings of the 2022 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 2580-2606. SIAM, 2022.
Siu Lun Chau, Robert Hu, Javier Gonzalez, and Dino Sejdinovic. Rkhs-shap: Shapley values for kereel methods. Advances in Neural Information Processing Systems, 35:13050-13063, 2022.
Sanjoy Dasgupta. The hardness of k-means clustering. Department Computer Science and Engineering, University of California.... ..... 2008.
Chengyuan Deng, Surya Teja Gavva, Parth Patel, Adarsh Srinivasan, et Impossibility of depth reduction in explainable clustering. arXiv preprint arXiv:2305.02850 2023.
Inderjit S Dhillon, Yuqiang Guan, and Brian Kulis. Kernel k-means: spectral clustering and nor- malized cuts. In Proceedings of the tenth ACM SIGKDD international conference on Knowledge discovery and data mining, pp. 551-556, 2004.
Hossein Esfandiari, Vahab Mirrokni, and Shyam Narayanan. Almost tight approximation algorithms for explainable clustering. In Proceedings of the 2022 Annual ACM-SIAM Symposium Discrete Algorithms (SODA), pp. 2641-2663. SIAM, 2022.
Ronald A Fisher. The use of multiple measurements in taxonomic problems. Annals of eugenics, 7 (2):179-188, 1936.
Ricardo Fraiman, Badih Ghattas, and Marcela Svare. Interpretable clustering using unsupervised binary trees. Advances in Data Analysis and Classification, 7:125-145, 2013.
Pasi Fränti and Sami Sieranoja. K-means properties on six clustering benchmark datasets.
Nave Frost, Michal Moshkovitz, and Cyrus Rashtchian. Exkme: Expanding explainable k-means clustering. arXiv preprint arXiv:2006.023399, 2020.
Magzhan Gabidolla and Miguel Á Carreira-Perpiñán. Optimal interpretable clustering using oblique decision trees. In Proceedings of the 28th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, pp. 400-410, 2022.
Buddhima Gamlath, Xinrui Jia. Adam Polak, and Ola Svensson. Nearly-tight and oblivious algorithms for explainable clustering. Advances in Neural Information Processing Systems, 34:28929-2899 2021.
10

---

Published as a conference paper at ICLR 2024
Badih Ghattas, Pierre Michel, and Laurent Boyer. Clustering nominal data using unsupervised binary decision trees: Comparisons with the state of the art methods. Pattern Recognition, 67:177-185, 2017.
Anupam Gupta, Madhusudhan Reddy Pittu, Ola Svensson, and Rachel Yuan. The price of explain- ability for clustering. arXiv preprint arXi::2304.099: 09744,, 2023.
Eduardo Laber, Lucas Murtinho, and Felipe Oliveira. Shallow decision trees for explainable k-means clustering. Pattern Recognition, 137:109239 2023.
Eduardo S Laber and Lucas Murtinho. On the price of explainability for some clustering problems. In International Conference on Machine Learning, pp. 5915-5925, PMLR, 2021.
Connor Lawless and Oktay Gunluk. Cluster explanation via polyhedral descriptions. In International Conference on Machine Learning, pp. 18652-18666 PMLR, 2023.
Scott M Lundberg and Su-In Lee. A unified approach to interpreting model predictions. Advances in neural information processing systems, 30, 2017.
Subhransu Maji, Alexander C Berg, and Jitendra Malik. Efficient classification for additive kernel svms. IEEE transactions on pattern analysis and machine intelligence, 35(1):66-77, 2012.
Konstantin Makarychev and Liren Shan. Explainable k-means: don't be greedy, plant bigger trees! In Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing, pp. 1629-1642. 2022.
Konstantin Makarychev and Liren Shan. Random optimal for explainable k-medians. arXiv preprint arXiv:2304.091 13, 2023.
Christoph Molnar.
Interpretable machine learning. Lulu. com, 2020.
Michal Moshkovitz. Sanjoy Dasgupta, Cyrus Rashtchian, and Nave Frost. Explainable k-means and k-medians clustering. In International conference on machine learning, pp. 7055-7065. PMLR, 2020.
F. Pedregosa, G. Varoquaux, A. Gramfort, V. Michel, B. Thirion, O. Grisel, M. Blondel, P. Pretten- hofer, R. Weiss. V. Dubourg. J. Vanderplas, A. Passos, D. Cournapeau, M. Brucher, M. Perrot, and H. Duchesnay. Scikit-learn: Machine learning in Python. Journal of Machine Learning Research, 12:2825 2830, 2011.
Marco Tulio Ribeiro, Sameer Singh, and Carlos Guestrin. wwhy 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, pp. 1135-1144, 2016.
Cynthia Rudin. Stop explaining black box machine learning models for high stakes decisions and interpretable models instead. Nature machine intelligence, 1(5):206-215, 2019.
Ingo Steinwart, Don Hush, and Clint Scovel. An explicit description of the reproducing kernel hilbert spaces of gaussian rbf kernels. IEEE Transactions on Information Theory, 52(10):4635-400 4643, 2006.
W Nick Street, William H Wolberg, and Olvi I. Mangasarian. Nuclear feature extraction for breast tumor diagnosis. In Biomedical image processing and biomedical visualization, volume 1905, pp. 861-870. SPIE, 1993.
Erico Tjoa and Cuntai Guan. A survey explainable artificial intelligence (xai): Toward medical xai. IEEE transactions on neural networks and learning systems, 32(1 (1:411):79344 2020.
Kush R Varshney and Homa Alemzadeh. On the safety of machine learning: Cyber-physical systems, decision sciences, and data products. Big data, 5(3):246 225,, 2017.
Andrea Vedaldi and Andrew Zisserman. Efficient additive kernels via explicit feature maps. JEEE fransactions on pattern analysis and machine intelligence, 492,, 2012.

---

Published as a conference paper at ICLR 2024
Sandra Wachter, Brent Mittelstadt, and Chris Russell. Counterfactual explanations without opening the black box: Automated decisions and the gdpt. Harv. JL & Tech., 31:841, 2017.
Chieh Wu, Jared Miller, Yale Chang, Mario Sznaier, and Jennifer Dy. Solving interpretable kernel dimension reduction. arXiv preprint arXiv: 19009v::990000 999903993, 2019.
A RELATED WORK ON EXPLAINABLE CLUSTERING
There are several papers that suggest improvements of the original IMM algorithm (Moshkovitz al. 2020). Most rely on random threshold cuts obtain better worst-case bounds on the price of explainability for k-means and k-medians (Makarychev & Shan 2022 Esfandiari et al. 2022 Makarychev & Shan 2023). As of today, the sharpest known upper bound on the price of explainabil- ity for k-mmans is O log log k) (Gupta et al. 2023). It is also known that the price of explainability for k-means (2(k) (Gamlath et al.) 2021). leaving a small gap. While the above works provide guarantees, it is also known that in low dimensions, even better guarantees can be provided (Laber & Murtinho [201]] (Chaikkr & Hu 2022). A different line of research has with &o leaves, leading both improved practical perfor- mance (Frost et al.) 2020) and better worst-case bounds on the price of explainability (Makarychey
inmension-independee
loosened the restriction decision
& Shan 2022). In addition, Laber et al. (2023) investigate shallow decision trees for explainable clustering, while Deng et al. (203) show that depth reduction is impossible for explainable k-means and k-medians. There has also been some research on other cost functions such k-centers (Laber Murtinho 2021) or general ||- -lIpp norms (Gamlath et al. 2021). However, to the best of our knowledge, there has not yet been an extension to the closely related kernel k-means problem, gap that we aim to bridge in this work. Other works on interpretable clustering investigate polyhedral descriptions of the clusters (Lawless Gunluk, 2023), choose similarity-be prototypes for each cluster (Carrizosal al. 2022 fit sparse oblique trees to describe the clusters (Gabidolla & Carreira- Perpiñán 2022).
B THE KERNEL K-MEANS ALGORITHM
We first remind the reader of the following result.
Lemma 1. Let K be a kernel operating on data X C Rd. Denote & for a (possibly data-dependent) feature map of K. Let C1...., Cle be a partition of X into is clusters with means cI,..., E H. Then for any x X, we have
arg [1((x) - -a1/2 2012== arg min [E(H]
Σ
K(y,z)
2
Σ K(..y)
(8)
[
[c(K)
3.=EC;
Proof. First recall the identity ||a - b1| ||a|12 2 mean is given by
|[b||
2(a, b) and note that for any cluster Ci, its
1
Σ
((x)
=
C1
ZECr
Expressing everything in terms of the kernel K, we see that
[lx(x) cal K(x,,)
K(y, 2)
2 |C|
Σ
K(x,v)
CPP
M.sEC;
VEC:
Note that the first term does not depend on 1 E [k].
Clearly, equation alllows computing distances in the feature space by simply evaluating K.
12

---

Published as a conference paper at ICLR 2024
(xxx
Figure 5: The threshold cut illustrated by the black vertical line defines a decision tree T with 2 leaves. While some points do not end up in the same leaf as their corresponding center, the tree 7 clearly does good job in approximating the two clusters.
c(x)
Algorithm 4 Kernel k-means
Input:
Kernel K for data X C IR,, integer ht E N
Output: Partitioning of X into & clusters C = (CI,...,CC
Initialize the clusters CI...., Converged < FALSE
while Converged FALSE do for x E X do
Assign æ to C such that / argmin [lő(x) cyl1 using equation end for if C₁ Ci for all / E [k] then
Converged + TRUE
end if
Update
C²))
end while
C ITERATIVE MISTAKE MINIMIZATION (IMM) ALGORITHM
In this section, review the IMM algorithm (Moshkoviz al. 2020 Consider data X Rd and centers M obtained from the k-means algorithm. For any x E X, we denote c(x) E M for the correct center according to the k-means algorithm. The algorithm constructs decision tree T that sequentially the input space IRd into & exis-aligned cells using threshold cuts of the form 2; रे 0. At every node of the tree, IMM chooses the threshold cut that minimizes the number of mistakes. mistake happens if a point that arrives at node together with its correct cluster center c(z) E M, now separated from this center as result of cut. This happens when H; S but (x(x) > 0 or
vice versa. For any point E X, we denote μ(x) for the center that ends up in the same leaf of T as x. This not necessarily c(zr) as we illustrate Figure
Let us also briefly recap the theoretical analysis of IMM for k-means, presented by Moshkovitz ct al. (2020). For each node u of the tree built by IMM, denote by M the remaining set centers that arrive at the node. The tree T induces partitioning ĆI,..., Cg. Writing t(u) for the number of mistakes at node T and denoting Duu) max |la bll?. it holds that
b S cost(().......).))
Σ
Σ - 1xx)]
1=1
rEC,
k
22| - (2 +2(((()) - u(=)11²)
(9)
1=1 nEC:
cost Cl,..., Cx) + Σ t(u)D(u)
NET
13

---

Published as a conference paper at ICLR 2024
The main argument in IMM is now given by the following result. Lemma 2. Let T be any node of the IMM decision tree T. Denote X for the subset of points x that arrive at u together with their correct center d(r).
1. For any E [d], it holds that
t(u)
max (a, 1 b,)² S 4k: a.E.M"
Σ
cx())²
(10)
xEX
2. This directly implies
t(u)D(u) 1 4k
Σ mEX
|2 - cxx)1
(11)
The proof of the first statement is based on the observation that along every axis i E [d]. and for any threshold cut halfway between two centers a, b M" (projected to the i-th axis), least t(u) mistakes are made, by definition of t(u). The second statement then directly follows from the first by summing over all d coordinates. Together with Equation[]aan and the fact that the maximum depth of the IMM tree is k, Lemma 2 yields (lk?)) bounds on the price of explainability. Let us use this opportunity point out two things.
Since only threshold cuts halfway between two projected centers are considered in the proof of Lemma[] the algorithm actually preserves worst-case bounds even when we only check the number of mistakes along these (ddk threshold cuts, instead of along all possible (dn) cuts, In other words, the IMM algorithm (as well as our kernelized version) can be run in data-independent time.
The IMM algorithm is essentially supervised learning algorithm, recreating partition Ci...., C& no matter how optimal it may be. This observation is crucial when we analyze Kernel IMM on our surrogate features (with respect surrogate kernel), for which the reference clustering may not even be close to the optimal partition with respect to this surrogate kernel.
D PROOFS FROM SECTION 3
D.1 PROOF OF THBOREM II
Theorem. (The Gaussian kernel cannot have interpretable feature maps) Consider the Gaussian kernel in d dimensions. There exists dataset X such that for any feature map Φ : X + R. satisfying (0(x), ((v)) = K(x,, v) for all E X, there exists some j E [D] such that 63 depends on more than just one input dimension of x E
Proof. We present a simple dataset such that no feature map for the Gaussian kernel K(r,y) exp(->llæ y y can depend only input coordinate in each of its elements $1...,, ØD. no matter how large may be. Consider three vectors IR,,, given by
(1) (0)
(2)
1
(3)
(1)
For sufficiently large y 0, know that K1 + K2,3 1. Assume there exists some interpretable feature map X R, Then, write d(x) (f(x). (()),(())), where f(x) is function of ø and g(x) is a function of ø2. By our choice of points, we may write
((z(1)) (a.
((x = (c,
((x(3) (c.d)
14

---

Published as a conference paper at ICLR 2024
for some vectors a, b, d. This implies
K13 = a²c+
acct 1--11112 + (b" d - [b61
K1, + (b' d ||c||2 1)
K1, + K2, -
<0 0
a contradiction to K1,3 2 0. For other y > 0, simply rescale the data accordingly.
D.2 PROOF OF THEOREM 2
Theorem. Consider the one-dimensional Gaussian kernel K (x. exp(-1x - - Then, there
exists a dataset X C R such that for any feature map ((b)) there exists component 63 that is not monotonic.
Proof. Consider the Gaussian kernel (xx,y) exp (-(x 9) R. Choose dataset X (x(1), x2()) x1813 with r²(1) x2) < .3( and corresponding kernel matrix satisfying
K1,2 + 22,3 < K +1
This is surely the case when the points are at a sufficiently large distance. Now assume there exists a feature map Φ X - RD_ 6(x(())))))))))))))))))))))))) (uy, ws) where (1:) is non-decreasing and (w;) is non-increasing for i 1, 2,3. In other words, assume there exist two vectors v1, Wh well as non-negative vectors 62, e3, 51, 62, 83 such that, writing
61 en + +
(
01 en
+ 63 83
61
w1 61-61-88
W1 w1 - 81
it holds that x ④ K. This condition gives rise to
of + of w1 = (vi + +1) (vi + + + (wi - 6,) - 81) =
of (e( te1) + wf wf( (wi - -1)) K1,2
which implies
oa 61 wii 81 K
and hence
|| + =|11 = 222K
Using the same arguments for the two other pairs of points from X, derive in the same way
||e2 1 |52 12 = 2 2K
||3 2 + |63 1 2 2K
Since e3 = é1 + e2 and 83 = + 82. this implies
|| + ||=2|| + 26 e2 + || + 118211 + 20T -2K 1.3
However, this is equivalent to
- 2K 1,2 + +2-2Kg + (c + 5x')) = - 2K1,
<< | 5/
K1, + K2,3 K1.3 < 0
contradiction.
15

---

Published as a conference paper at ICLR 2024
E DECOUPLING DIMENSIONS FOR BOUNDED PRODUCT KERNELS
In this section, we prove that decoupling the input dimensions of bounded product kernels introduces errors no larger than O(d). Recall that our surrogate feature map given by
<(x)
(x)(
where each Ø; a valid feature map for the one- aneedimensional kernel K₁ This surrogate feature map itself is associated with a surrogate additive kernel:
(6(x), o(y))
Σ (d((z))
Σ Kl(x,)) + K(x,))
Of course, it is not clear that running IMM with respect to this surrogate kernel is actually sensible and not only ensures interpretability, but also preserves worst-case bounds. The justification given in the following Lemma.
Lemma 3. Let X C. Rd be dataset, partitioned into k clusters CR. Denote by (o.t.. C&) the kernel k-means cost function associated with a distance-basse product kernel K on RR,, and by cost; the cost with respect to the feature map Ør. Then
cost(C1,.... C,)
Σ cost, (Cst,,C S cost(Ci....,.o. Ck)
Proof. First, use the GM-AM inequality and the fact that K2(x, 8) S 1 to obtain
1/d
K(r,)) II (, - [ KI
Ki(2, v)
7 1=1
Thus, rewriting the kernel k-means cost function, we see that
k
cost(Cr......Co. = |
Σ
(2,
1=1
J,yEC:
k
2
X
K.(2,8) v)
C1
d
1=1
Z,yECI
iml
k
1
|
Σ Kz(
Cll
i=1
1=1
J,BEC
costi (Cld.,,
This implies the upper bound from Lemma
For the lower bound, note that for any x, IR
[| Φ(v) 2 2 (1
K K(r,)) v))
K2(2,))
1=1
< 2
Σ (1 (x,
1=1
| (x) 6.(1)11
16

---

Published as a conference paper at ICLR 2024
where we use the fact that IT a; the kernel k-means cost to make use of this observation, we arrive at
-1
as - bil for any lail, [6,| - 1. Rewriting
k
cost(C),...,,
Cx)
Σ
l o(y)ll
2|C
1=1
N.yEC,
(10((2)
d.(1)
Z,yEC,
cost;
(Cst:(C,....,Ck
F INTERPRETABLE TAYLOR KERNELS
F.1 PROOF OF THEOREM 3
Theorem. (Threshold cuts in the surrogate feature space of interpretable Taylor kernels yield interpretable decision trees) Let K be product of interpretable Taylor kernels, and let à denote its surrogate feature map. Then, a threshold cut of the form (15( 2 0 leads to an interpretable decision tree in Rdd.
Proof. Recall our notion of surrogate features for interpretable Taylor kernels: For all E [d] and E X, we define
M
(x(x)= (seaiartt gl) j!
j=0
and refer to the concatenation <(x) = (d)() as the surrogate feature map of order M. Note that (z) x x (Z,)2, + (zx)). For interpretable Taylor kernels, this expression is zero for most one point x in the domain of the kernel. Thus, when we run IMM on these surrogate features, the threshold cuts (x) こे 0 can be translated to interpretable decision trees in the input space. A
F.2 PROOF OF THEOREM
Theorem. Let Ci...., Cj be the clusters of dataset X C Rd derived from kernel k-means, where the kernel K an interpretable Taylor kernel. Denote by & o(X) the surrogate features for K X. Then, the interpretable decision tree obtained from Kernel IMM on & satisfies p(T, X) = O (dk2) + (X) where 8 = 8(M) depends on the order M of the surrogate feature map and Mim 5(M) = 0 for any dataset X. Thus, by adaptively choosing M such that Occostopt: we obtain Odk2) bounds.
O(dk' 8)
Proof. We begin by noting that for all i [d] and xr X, and any integer M, Taylor's formula ensures that
Σ (
(K, (d: (z
[(x;)[(1))
j!
j=M
|| ( (0.000))))) (N.y.)
max [((:))) NEX
M!
Since g is assumed to be analytic, lim (x),
K2 y) for all x, y. Thus, the surrogate features 6; approximate the one one-dimensional kernels K, within some 8 > 0 that vanishes M Now, fix dataset X and let Ć Ce be the interpretable clusters chosen by IMM
17

---

Published as a conference paper at ICLR 2024
on the surrogate features Φ. Denote by Ci.....CG CC the reference clusters obtained from unrestricted kernel k-means with respect to the original, interpretable Taylor kernel K. Denote by cost the kernel k-means cost with respect to the product kernel K, by cost, the costs with respect to the univariate kernels K,, and by cost, the cost with respect to the approximate kernel implicitly defined by virtue of the surrogate feature maps Ø; Using Lemma from Appendix and keeping track of the approximation error, we obtain
cost(Ci....., Cx) S Σ cost, cost,(Ci,...,Ca.)
(CIl,(().....,....
d
< 0dd)) +
Σ (0(K2) costi(Ci,,..,.Ca)
O(d6)
Σ
O(h2)
==1
0(dk20) + Σ O(k)) cost, (C,.,, Ck)
S O(dh3) cost(C .o.. C2) Odk22))
G DISTANCE-BASED PRODUCT KERNELS
Consider distance- based product kernel K(x, IT. h(1x; yil) on Rd. As pointed out in the main paper, may define surrogate features via ( (, x((1) were z(f) denotes the jth point in the dataset X. While these features lead to interpretable decision trees, they do not detine features that approximate the one-dimensional kernel: For all E [d], must be noted that (z,(2), (x)) * (2 y) under the standard Euclidean inner product. Of course, if we equip I with a new inner product given by (d,(x), (x()) 6,(x)² K, (vV), then our surrogate features remain valid features for the one-dimensional kernels K,, Consequently, when setting ø = (6.)
actually map to space V in which the inner product is given by (u, v) = Ei u,'' K U/- Running explainable clustering algorithms such as IMM in this space is possible, however introduces additional constants that depend the kernel matrices K;
Theorem. Let CI...., Cb be the clusters of a dataset X Rdd derived from kernel k-means, where the kernel K is distance-based product kernel. Denote by 4 = =x() the surrogate features for K on X, where (x) x()). Then, the interpretable decision tree obtained from Kernel IMM on & satisfies v(T, X) O (Cdk²), where C' depends on the dataset X and the kernel K.
Proof. To prove Theorem [5] we adopt the general proof strategy from IMM and again decouple dimensions discussed in Appendix E Again, cost; denotes the cost with respect to each one- dimensional kernel K₁.
cost(C),.... (k) S
cost, (ai,t,C
[1x(z) - mxx))11²
(12)
1=1 reCi
< 2 costytCi,.......................
Cc) +2 Σ t(u)
wET
18

---

Published as a conference paper at ICLR 2024
Now, would in principle like to use Lemma 2 However, the space V in which Kemel IMM runs equipped with the non- Euclidean inner product. Thus, the second part (II) of Lemma no longer follows from the first 10 Instead, arrive
t(u) = t(u)- max a.BEM"
||a -11
t(u).
a4 bi)² K; - bi)
max a.
Ki ((u)
max (a (a-b) (6) b) a.DEMM"
4k1 k Σ (o(x) - c(x))² (δ(x) c(x))
xEXu cor
Ak
l1((x) cc(x)
ZEX
where we use the first part Lemma in the second inequality, The constants 81, R2 are given by
E (a; - b.) K; (a; - bi)
a.bEMM'
Da=i - b,) - -b.)
- cx(x)) 2 2im1 (di(x) - cx)))) ", (0i(t) cc())
Limi (di(x)
K2 max
#EX
and depend the data.
H KERNEL IMM FOR ADDITIVE KERNELS
Additive kernels are of the form K(x, (x),,)=> = Ki(x, y) where every individual K; is kernel on suitable subset of IR, often the positive real line. Feature maps of additive kernels K can be written as the concatenation of the univariate feature maps associated with each kernel K,. If these maps consist of functions that have at most one change
univariate - and hence interpretable of slope, threshold cuts with respect the feature map lead directly to interpretable decision trees. Conveniently, this is the case for several important additive kernels.
Consider Hellinger's kernel Kxx = E'= Vayi on dataset X [0, oo)a Then K admits the simple interpretable (and monotonic) feature map Φ(z) = ( _1 Id).
Let K(x,y) = Di min (x
be the generalized histogram intersection kernel, for some parameter O. For any dataset X C. [0, oc) d there again exists a feature map that yields interpretable decision trees: Given feature e [d]. denote by 21 < <.. 2m, the X}. For every component [m,]. let
m; unique values in the set {ar
V2j 2--1
if 2 2 and x 2 2j
(x)
2j
if =
(13)
else
Then the concatenation Φ = (ed.))seidj.jEmm)) is composed of monotone functions. More- over, it straightforward to verify that for all x, y e holds that K(x, y) = (6(x). o(y)).
Thus, á is valid feature map.
19

---

defines an approximate feature map for K. Since each Φ1, is strictly increasing for x, < 1/ log( (M/M). and strictly decreasing for æ; 1/ /Mgg)) they give rise to a feature map for which threshold cuts lead to interpretable decision trees. For normalized histograms we find that even low values of M S 5 induce the same partitions as the additive x² kernel, and hence O (R:2) ) bounds are preserved when running (Kernel) IMM with respect to the kernel induced by the map Ø. Published as a conference paper at ICLR 2024
As third example, consider the additive x² kernel ((x EE X C oo)" Given some M E N, the kernel K can be approximated from
2
dataset
/
K K(z, v) Σ 2rsy
puitti-
Σ
22/t 12/t.x,t"1.
22/t y,th dt
(14)
d
M
j
j M
9t
V 2M/3
22222
yi
M
3=1
We conclude that the concatenation of all functions
2 V
1 M
2:
$ (z)
I EXPERIMENTS
Let us now give some details on the experiments. Our code available on GitHub
Main experiments for Kernel IMM. We first verify the approximation properties of our proposed methods on the synthetic datasets "Pathbased", "Aggregation" and "Flame" (Fränti & Sieranoja) which have = 3, k = 7 and & = clusters respectively. We start with linear k-means and IMM on all three, and then run kernel k-means with both the Laplace well the Gaussian kernel over range of hyperparameters y, choosing the best agreement with the ground truth as our starting point for Kernel IMM. When the Gaussian kernel is chosen, we run Kernel IMM both on the surrogate Taylor features from Definition with M = 5, as well as on the surrogate features based on the kernel matrix, as defined in Equation { and choose the better one. We then refine the partition induced by Kernel IMM using both Kernel ExKMC as well as Kernel Expand. constructing m = 6, m = 10 and m leaves respectively. Note that at every step. Kernel ExKMC and Kernel Expand only need to check the cost of the threshold cuts at the new nodes (obtained from the previous iteration). Thus, adding m leaves to an existing tree with p leaves amounts to p + 2m iterations over all possible threshold cuts.
We follow the same procedure for the two real world datasets. In Iris (Fisher 1936), there are three classes with 50 observations each. Every class refers to a type of iris plant. As illustrated in the barplot included in Section 6) kernel k-means slightly improves over k-means and this translates to Kernel IMM, Kernel ExKMC and Kernel Expand. The Wisconsin breast cancer dataset consists of 569 observations of benign and malignant cells. The 30-dimensional features describe characteristics of the cell nuclei observed in each image. Interestingly, IMM exactly replicates its suboptimal reference k-means clustering. Kernel k-means better identifies the ground truth, and Kernel IMM approximates it well (even achieving slightly higher agreement with the ground truth). The same is true for Kernel EX and Kernel Expand.
Kernel IMM for the x2 kernel. The additive x2 kernel evaluated on a toy dataset obtained from mixture model of four discrete distributions, with values in four bins. Figure 6 shows plot of the different distributions. For all four distribution, we draw instances 100 random samples, and compute the fraction of observations in each bin for every instance (thus 20 and d = 4). We repeat this procedure 100 times. We find that the x2 kernel achieves a Rand index that consistently higher than the one of k-means (see Figure G). This is not very surprising: The denominator of the
20

---

Published as a conference paper at ICLR 2024
Discrete Distributions
Distribution! Distribution
Distribution
Box Pict
Distribution IV
2.0
20-
0.3
Probabiitty
Rayd 11000
6--
Sandardk-maar
Figure 6: We cluster samples drawn from a mixture model of four discrete distributions by checking the fraction observations in each of four bins. The true underlying probabilities are shown in the left plot. Over 100 draws of samples, the x² kernel improves over standard k-means in recovering the ground truth, as the boxplot on the right shows.
x2 kernel accounts for the overall number of observations in each bin, penalizing deviations less probable bins more than in frequently visited bins nonlinear characteristic that standard k-means lacks.
To provide some intuition how Kernel IMM constructs interpretable decision trees, let us give some additional details for the x² kernel. Having drawn instances (containing 100 samples) for each distribution,
compute the class probabilities for the four bins and cluster using kernel k-means. We then map to higher-dimensional feature space using the features derived for the x² kernel (see Appendix H). We choose M 5 features for every dimension, and hence operate in D = Md = 20-dimensional space. Assuming the first threshold cut is chosen along the first axis in the feature space, Kernel IMM provides us with some such that we cut
21
(1)
5e = 22r1
<0
5
V2
All we are now left with is identifying which values of 21 satisfy the above inequality, and which do not. Equivalently, we can represent this as an interval (or its complement) in the sample space.
Comparison with CART. Standard decision tree algorithms such as CART also perform well in experiments. CART achieves a price of explainability very close to the that Kernel IMM attains (despite it being known that no approximation results exist for CART in the standard k-means setting). We show comparison of the results in Table 2 For the Wisconsin breast cancer dataset, CART even improves over unconstrained kernel k-means (which has, in this case, not found the optimal partition).
Table 2: Comparison of price of explainability (PoE) between CART with one-sided cuts and leaves, and Kernel IMM.
Dataset
Kernel
PoE (Kernel IMM)
PoE (CART)
Pathbased
Gaussian
1.06645
1.07004
Aggregation
Laplace
1.00125
1.00125
Flame
Gaussian
1.02256
1.02732
Iris
Laplace
1.00502
1.00502
Cancer
Gaussian
1.00179
0.99330
21

---

Published as a conference paper at ICLR 2024
J ЕXКMC ON AN EMPTY TREE ADMITS NO WORST-CASE GUARANTEES (THEOREM 6
Theorem. (ExKMC admits no worst-case bounds) For any m E N there exists a data set X C. R such that the price of explainability on X is p(X) 1. IMM attain this minimum, but ExKMC (initialized on an empty tree) constructs a decision tree T with (TT, X) 2 m.
Proof. Consider a dataset X of size in R. consisting of three clusters with centers given by C -1, 1 0g = 0, C3 = Assume all points of each cluster C₁ lie a distance of exactly from the center Cs half of them at and half of them + c. The optimal k-means cost is then given by
costopt ne"
At the first iteration ExKMC, suppose it chooses some cut that does not separate points belonging to the same cluster. We may then assumee that w.lo.g. (i, (1, 0.5), which implies eg Cy and w.l.o.g. CL = C1. Thus, the total cost of this cut
2n
f(i,0) =
+
Σ
|| - c1l2
3
CCC²
2n
2
+
n
(1 c)² + 6
(1 +1++) c)²
3
6
This cost can be improved upon when ExKMC cuts along (i,0) (1, 0). choosing Ci CL2 C3 CR. leading to a cost of
2n n f(i, f(i,0) 0)
(1
3 +
c)-
Since ExKMC can now only add one more leaf, it inevitably sepurates at least points from their correct cluster center. Thus, there exists leaf for which 2n n n² of at least - 2e, and the final cost of the associated decision tree T is hence
g pairs of points are at distance
cost (T) 2 ne²
1 (1)
ne²
2n(1 22)²
2
n
2
The price of explainability of T is given by
nE
2(1 - 22)
PTT,X)
2n
9c²
Thus, as e + O, we see that ExKMC gives rise to decision trees with an arbitrarily large price of explainability pTT, X) m. Note that IMM recreates the optimal partition perfectly, since it is possible to split clusters without making any mistakes. Thus p(X) = 1. Clearly, the fact that ExKMC restricts our choice of centers the set of reference centers limits its performance.
K THE PRICE OF EXPLAINABILITY CAN BE INFINITE FOR KERNEL CLUSTERING (THEOREM 7
The price of explainability, as defined in Definition may not be finite for all kernels.
Proposition 1. (Unbounded price for the quadratic kernel) Ler K(x, 9) = (x, ? Then, there exists dataset X C R² such that p(X) xo.
Proof. Let x (0,1),y (0, 1),, (1,0), w (-1,0) R², Consider the quadratic kernel
K(s,t) = ((s, {))² operating on X = {a, {I, 2, W. Then quadratic kernel 2-means achieves cost of zero by partitioning X into the two clusters C1 = {x. y). C22 = { w). since ((s,t) t) = 1 for all interpretable decision tree can reproduce this partitioning
s. 3.t. X from the same cluster. However, of X. Every decision tree with two leaves assigns one pair of points (s, t) from different clusters to the same leaf. Since K K(s, () 0 for this pair, (T) > 0 and thus p(X]
n
22

---

Published as a conference paper at ICLR 2024
This may not come surprise considering the special geometry of the quadratic kernel. However, the following result demonstrates that even distance-basee kernels can lead to similar problems. For this, consider the e-neighborhood kernel K(x, y) 1[] yll < e). While K is not positive definite kernel (its kernel matrix may have eigenvalues), commonly used in spectral and kernel clustering nonetheless.
Proposition 2. (Unbounded price for the e-neighborhood kernel) Let 0 and let K(x,y) 1(|= y S E). Then, there exists a dataset X such that p(X) = 0c.
(1),, there are exactly d' = 6 ways of assigning to two of them the value 0, and to the two others the value 1. Similarly, for four other points x(6) ..... x.1), there are two of them the value 0, and to the two others the value -1. x
Proof. For four points ,!")...,,,?
exactly d' = 6 ways of assigning
There are d = (d')² = 36 possible combinations of all these assignments. We define a d-dimensional cluster C1 by concatenating all of the combinations for each the points x:(1 ,..,,..,, x(1), Thus, every 11 is vector in (0,1)a Similarly, define C2 by concatenating all of the combinations for each of the points (5) they agree in exactly d/3 dimensions but differ by everywhere else. Thus ||<-=x'|
,.... ...... 28))) Thus, the vectors y C2 are E [0,-1]4 Note that for any x, x' Ct.
24. The same holds for any pair y. // C2. However, for any pair x E C1. y E C2 from different clusters, they agree on d/4 = 9 dimensions, but are separated by 1 along d/2 = 18 dimensions and are separated by 2 elsewhere. Thus, their distance || y/1² (v.
+ 36 54. By choosing the e-neighborhood
kernel with c 244, we see that ((x, implies optimal kernel k-means cost of zero. However, any threshold cut along any one of the dimensions will assign at least one pair (x, y) from distinct clusters to the same leaf, implying [xx, y) = 0. Thus, the kernel k- k-means cost for this explainable partition is strictly positive. This proves (XX) = cc. To produce the same result for other values 0, simply rescale the data accordingly.
for all x, E C1. y. V E C2. This
23


Reviews:
[{"review_id": "W7hYa5AJAB", "reviewer": "Reviewer_JcS6", "summary": "The paper proposes to learn axis-aligned decision trees for kernel k-means clustering problems. Conceptually, the idea of the paper is quite similar to the work by Moshkovitz et al. (2020) but for kernel k-means clustering. First, the paper motivates for kernels that are separable over each dimension (interpretable feature maps), and theoretically shows that axis-aligned splits in the transformed feature space does not result in axis-aligned splits in the original space for the popular Gaussian kernel. By approximating kernels to achieve interpretable feature maps, the paper  then adapts existing explainable regular k-means algorithms (IMM and ExKMC) to handle the kernel k-means clustering problem. Experiments are performed on 5 datasets showing the advantage explainable kernel k-means over regular k-means.", "questions": "1) How does the results (the price of explainability) compare with tranining a CART tree on the cluster assignments?", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "1) As far as I know, this is the first paper addressing the problem of explainable kernel k-means clustering.\n2) The paper proposes interesting approximations to the kernel function to obtain interpretable feature maps.", "weaknesses": "1) The paper states \"interpretable variants of k-means have limited applicability in practice\", but as far as I know, kernel k-means is not a widely used clustering algorithm (unlike regular k-means, spectral clustering or DBSCAN). And the need for an interpetable version of it also seems to be low.\n2) The paper views the optimization problem of interpretable clustering in a two step approach: first fitting a kernel k-means and then using the greedy tree induction algorithm to fit the tree on the result of kernel k-means. But this seems to be suboptimal in that one should aim to jointly optimize the clustering objective along with the decision tree parameters.\n3) The paper completely discards the approach of fitting a tree on the kernel k-means clustering labels as a supervised problem. It cites the result in Moshkovitz et al. (2020, Section 3), where an unusual Toy 2d example shown to illustrate the bad behavior which rarely occurs in practice. Fitting a classification tree (such as CART or even better algorithms such as optimal MIO-based or alternating optimization-based) on the clustering labels should produce adequate results in practice.\n4) The theoretical bounds on the price of explainability seem to be quite high and not really helpful in practice. For example, does the bound of $O(dk^2)$ mean that say for MNIST the tree will do worse by (784 * 100) times than the unconstrained kernel k-means? What is the practical value of these asymptotic bounds? Experimental results seem to show that trees are doing within a constant factor the reference clustering.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "mt7L3ISF99", "reviewer": "Reviewer_8Bws", "summary": "This manuscript extends the study of explainable $k$-means to the kernel $k$-means, also using decision trees as the \"representation\" of explanation but the node does not characterize axis-parallel threshold cuts anymore. In fact, the explainability is relaxed to be an interval or the complement of it. To address the issue of non-injectivity of cluster centers from the RKHS to $\\mathbb{R}^d$, the decision is also made on the proposed surrogate feature maps instead of Euclidean space. Based on these new notions and the previous Iterative Mistake Minimization algorithm for vanilla Explainable Clustering, a kernel IMM algorithm is proposed for several kernels. __Most importantly__, a roughly $O(k^2)$ upper bound on the price of explainability holds for many kernels., when the dimension $d$ is small.", "questions": "Minor:\n1. Missing related work on explainable clustering: Impossibility of Depth Reduction in Explainable Clustering\n2. Related work on other notions of EXC, up to you: Optimal interpretable clustering using oblique decision trees\n3. In the first work of explainable clustering, IMM also attains $O(k^2)$ upper bound but is later improved to $\\tilde{O}(k)$ by balancing the mistakes with the size in the SODA paper. Have you tried this? Any thought if that would be helpful?\n4. Maybe I missed it, but if not, please explain rand index.\n5. Will the codes turn public?", "limitations": "", "rating": 8, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "1. The paper is in general well-written, I had a good experience of reading.\n2. Due to the rush I unfortunately did not read all the proof, but by a glance I think the correctness is OK. I will be happy to come back to it if any concern is raised during the discussion.\n3. If this work is just combining kernelization with the decision tree framework, it is OK but not interesting enough. I like the relaxation of explainability to address this problem. More importantly, the authors give reason for doing this in Thm 1 & 2.\n4. It is good to show experimental results.", "weaknesses": "1. The work is refrained on kernel $k$-means only, which by itself is not a limitation. But note that the line of research on explainable clustering has coupled $k$-means and median together, and the proposed algorithms, even lower bounds are similar. The $k$-center objective is indeed studied separately. It is expected that some insights should be given on how this result sheds light to $k$-median, or $k$-center even better. However I am not able to find any discussion.\n2. No discussion on lower bound is involved.\n3. It is based on the previous two points, I think the scope of this paper can be wider.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "EGi0Jhn7V3", "reviewer": "Reviewer_762t", "summary": "This work aims to fill the gap in the literature on (inherently) interpretable clustering methods. Specifically, this work proposes algorithms to approximate kernel k-means methods. Similar approaches have been proposed before for classic k-means algorithms, however practice oftentimes requires more flexible clustering methods such as kernel k-means. The authors propose a variant of the interpretable clustering method Iterative Mistake Minimization (IMM), which is an algorithm that approximates a given k-means clustering by a decision tree with k leaves, where each leaf represents a cluster. The proposed algorithm (Kernel IMM) builds on IMM, and essentially constructs a decision tree to approximate the clusters induced by kernel k-means. Besides Kernel IMM they also present Kernel ExKMC and Kernel Expand, two methods where new leaves are added in a greedy approach to improve accuracy of the tree (potentially at a loss of interpretability). Performance of the approaches is evaluated on a few datasets.", "questions": "Is it possible to compare to other works constructing interpretable models (not necessarily based on k-means or kernel k-means), for example in terms of accuracy or interpretability (nr. of rules, for example)? If not, how so?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The paper is well written and has a clear structure. The motivation of the proposed algorithm(s) is clear and the paper addresses a relevant and timely issue. The paper discusses central ideas in a concise manner, with elaborations in the appendix. The approach seems novel in a sense that it extends ideas from interpretable k-means to kernel k-means, which has not been done before. The chosen figures support the manuscript, and especially Figure 2 is a nice visualisation of the proposed method.", "weaknesses": "see the main weakness of this paper in the limited experimental results. It would be nice to see a bit more elaborate experiments. The authors claim that the resulting trees are interpretable, as decision trees are generally understood to be both globally and locally interpretable. However, even decision trees may become uninterpretable with too many leaves and/or too deep paths. Hence, it would be interesting to see the size of the trees. In Figure 4 (right) it can be seen that Kernel IMM performs (much) worse than kernel k-means, while Kernel ExKMC and Kernel Expand show a good performance compared to kernel k-means — however at what price of interpretability? To me, it would be interesting to see a bit more elaboration and analysis of the interpretability (and the trade-off). Presenting a sort of a case study on one of the datasets may be a possible option to show such results. \n\nMinor comments: \n- why does (the reference to) appendix C appear before appendix B in the manuscript? They could be switched\n- the introduction may be shortened (especially 1st and 2nd paragraph) to allow for more space to report experimental results\n- it would be nice to include some references to works on (inherently) interpretable clustering methods that do not necessarily build on k-means (for example Carrizosa et al. (2023) or works on cluster description (e.g. Lawless & Günlük (2023))\n- contributions could be listed for conciseness \n- 2x “of” in paragraph on explainable k-means", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "rkYdfOTwCq", "reviewer": "Reviewer_aXrD", "summary": "This paper proposes an explainable kernel clustering algorithm. They consider the explainable clustering that uses a threshold decision tree to partition the data set. Their algorithm first computes a kernel k-means clustering on the data set. Then, the algorithm converts the kernel clustering into a (generalized) threshold decision tree. Each internal node of the threshold decision tree given by the algorithm is a threshold cut (or an interval cut with two thresholds) on a single feature of the original feature space.\nThey also prove the upper bound on the worst-case price of explainability for kernel k-means clustering. They define the price of explainability for kernel k-means clustering as the ratio of the cost given by the decision tree and the cost of optimal kernel k-means clustering. They show that their kernel IMM algorithm achieves O(k^2) upper bound for additive kernels, O(dk^2) upper bound for interpretable Taylor kernels, and O(Cdk^2) for distance-based product kernels, where C depends on the dataset X and the kernel K.", "questions": "1 Would this generalized threshold decision tree (with interval cut) significantly reduce the clustering cost since it partitions the space into more parts? It would be interesting to evaluate the effect of this tree structure change by converting it back to a regular threshold tree and comparing it with the expanded IMM with the same number of leaves.", "limitations": "", "rating": 8, "confidence": 5, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "1.\tThe paper is well-written and easy to follow. \n\n2.\tThe paper proposed a new problem explainable kernel clustering and an algorithm for it. This problem generalized the explainable clustering problem proposed by Dasgupta et al (2020). The explainable clustering problem has been extensively studied in recent years. The explainable k-means and k-medians clustering generate a threshold decision tree clustering which is easy to understand and visualized by humans. In practice, the data set might not be well-clustered by k-means and k-medians clustering in the original feature space. The kernel method is widely used to map the original data into a well-clustered space. The algorithm utilizes kernel clustering to create an explainable clustering in the original feature space. The problem is well-motivated and interesting. \n\n3.\tThey also provide theoretical analysis on the price of explainability for kernel k-means clustering. For several popular kernels, they show interesting upper bounds on the worst-case price of explainability.", "weaknesses": "1. Their kernel IMM algorithm is a direct generalization of the IMM algorithm proposed by Dasgupta et al (2020) to the kernel clustering. Although they compare the cost of the explainable clustering to the cost of optimal kernel k-means clustering, their upper bound loses a factor of d for interpretable Taylor kernels and distance-based product kernels. The dimension d might be very large in real-world data sets. \n\n2. They consider the generalized threshold decision tree, in which each internal node can partition the space by an interval on a single feature. The interval cuts can be seen as two threshold cuts. Therefore, this generalized threshold decision tree can be converted to a regular threshold decision tree with more than k leaves. The previous works showed that expanding the threshold decision tree to more than k leaves can reduce the clustering cost. Thus it is unclear to me whether the improvement in the clustering cost in the experiments are due to the better kernel clustering or due to these generalized decision tree structure.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (poster)