Optimal Decision Trees For Interpretable Clustering with Constraints

1 Introduction

Clustering is a core unsupervised machine learning problem that aims to partition a dataset into subgroups of similar data points. In practice, it is often used to discover meaningful sub-populations such as customer segments [Wu and Chou, 2011] or groups of correlated genes [Thalamuthu et al., 2006]. Constrained clustering is a semi-supervised learning task that exploits small amounts of supervision, provided in the form of constraints, to incorporate domain-specific knowledge and to significantly improve clustering performance [Wagstaff and Cardie, 2000; Wagstaff et al., 2001]. The most popular types of clustering constraints are so-called instance-level pairwise must-link constraints, cannot-link constraints, and additional types of constraints that can be translated to such pairwise constraints [Davidson and Ravi, 2005; Liu and Fu, 2015]. In the past decades, the topic of constrained clustering has received significant attention and different constrained clustering algorithms have been proposed [Bilenko et al., 2004; Pelleg and Baras, 2007; Liu et al., 2017; Cohen et al., 2020]. In particular, approaches that are based on exact optimization formulations, such as integer programming, constraint programming, and satisfiability have obtained state-of-the-art performance [Davidson et al., 2010; Berg and Järvisalo, 2017; Dao et al., 2017; Babaki et al., 2014].

Our interest is in developing an approach to constrained clustering that yields interpretable solutions with strong solution quality guarantees. Recent approaches to clustering via decision trees have yielded a degree of interpretability by exposing clustering rationale in the branching structure of the tree [Frost et al., 2020; Moshkovitz et al., 2020; Bertsimas et al., 2021; Gamlath et al., 2021]. However, these approaches do not support the incorporation of clustering constraints. Moreover, little is known about the compatibility of such clustering constraints with decision-tree clustering. While optimal decision trees have received significant attention in recent years, most of the literature is focused on classification tasks [Ignatiev et al., 2021].

In this work, we present the first approach for interpretable and constrained optimal clustering based on decision trees. We make the following contributions:

1. We present a novel SAT-based encoding of optimal constrained clustering that is interpretable via a decision tree. Our formulation supports two well-known clustering objectives as well as pairwise instance-level clustering constraints. To the best of our knowledge, this is the first approach for inherently-interpretable constrained clustering.
2. We introduce novel techniques for efficient encoding of clustering problems and for improving search performance. Specifically, we introduce the notion of distance classes to support bounded suboptimal clustering, and a set of pruning rules to reduce the number of clauses.
3. We empirically evaluate our approach over real-world and synthetic datasets and show that it leads to highquality, inherently-interpretable clustering solutions that satisfy a given set of pairwise constraints.
4. We present theoretical and empirical results on the tradeoff between interpretability via decision trees and satisfaction of user-provided clustering constraints.

2 Preliminaries

2.1 Decision Trees for Constrained Clustering

Definition 1 (Decision Tree). Given a set of features 𝐹 and number of clusters 𝑘, a decision tree  is a set of branching nodes 𝐵, a set of leaf nodes 𝐿, a root node 𝛿 ∈ 𝐵, a parent function 𝑝 ∶ 𝐵 ∪ 𝐿 → 𝐵, left and right child functions 𝑙, 𝑟 ∶ 𝐵 → 𝐵 ∪ 𝐿, a node feature selection function 𝛽 ∶ 𝐵 → 𝐹 together with a threshold selection function 𝛼 ∶ 𝐵 → 𝑑𝑜𝑚(𝐹), and finally a leaf labelling function 𝜃 ∶ 𝐿 → [1..𝑘].

Definition 2 (Tree Cluster Assignment). Given a dataset 𝑋, and the number of clusters 𝐾, a decision tree  direct each point 𝑥 ∈ 𝑋 ⊂ 𝑅|𝐹| to one of its leaves by starting from the root and recursively moving to its left or right child, depending on whether the value of the chosen feature is less than or equal to the threshold, or not. The point is then assigned the cluster label of the leaf, represented by Θ(𝑥).

The tree clustering Θ partitions 𝑋 into 𝑘 clusters such that each cluster is non-empty,

Consistent with recent work [Frost et al., 2020], each cluster is allowed to spread across multiple leaves to improve expressiveness and the ability to satisfy user-provided constraints. If two points are in the same cluster (resp. different clusters), they are said to be clustered together (resp. separately).

Definition 3 (Pairwise Clustering Constraints). Given a dataset 𝑋, a set of pairs of data points named must-link constraints 𝑀𝐿, and a set of pairs of data points named cannotlink constraints 𝐶𝐿, a clustering Θ is said to respect the constraints if it clusters all of must-link pairs together and all of cannot-link pairs separately:

Definition 4 (Minimum Split and Maximum Diameter). Given a dataset 𝑋, the number of clusters 𝑘, and a clustering Θ ∶ 𝑋 → 1..𝑘, the minimum split is the shortest distance between two points that are clustered separately,

and the maximum diameter is the longest distance between two points that are clustered together,

We assume |𝑥𝑖 - 𝑥𝑗 | to be the Euclidean distance, however any totally ordered measure of distance is applicable.

2.2 ProblemDefinitions

We consider two well-known clustering objectives [Dao et al., 2017]: (1) minimizing the maximum diameter (MD); (2) a bicriteria objective that consists of minimizing the maximum diameter and maximizing the minimum split ([MD,MS]). Specifically, we consider bounded approximations parameterized by 𝜖 such that 𝜖 = 0 indicates an optimal solution (or Pareto optimal for [MD,MS]).

Problem 1 (MD 𝜖-Optimal Tree Clustering). Given a dataset 𝑋, number of clusters 𝑘, a set of must-links constraints 𝑀𝐿, a set of cannot-links constraints 𝐶𝐿, decision tree depth 𝑑, and approximation parameter 𝜖, find a complete decision tree  of depth 𝑑 such that:

1. Θ respects the constraints 𝑀𝐿 and 𝐶𝐿;
2. 𝑀𝐷 ≤𝑀𝐷∗ + 𝜖,

where ∗ is an optimal solution with respect to the objective of minimizing the maximum diameter.

Problem 2 (MS-MD 𝜖-Pareto Optimal Tree Clustering). Given a dataset 𝑋, number of clusters 𝑘, a set of must-links constraints 𝑀𝐿, a set of cannot-links constraints 𝐶𝐿, decision tree depth 𝑑, and approximation parameter 𝜖, find a complete decision tree  of depth 𝑑 such that:

1. Θ respects the constraints 𝑀𝐿 and 𝐶𝐿;
2. 𝑀𝑆 ≥𝑀𝑆∗ - 𝜖;
3. 𝑀𝐷 ≤𝑀𝐷∗ + 𝜖,

where ∗ is a Pareto optimal solution with respect to the bicriteria objective of maximizing the minimum split and minimizing the maximum diameter.

Note that Problem 1 and Problem 2 are not always feasible since a decision tree of a given depth cannot represent all possible clusterings, and may not be able to represent any clustering that satisfies the 𝑀𝐿 and 𝐶𝐿 constraints. However in Proposition 1 we show that for every clustering there exists a tree of certain depth that can represent it. 1

Proposition 1 (Decision Tree Completeness). Given a dataset 𝑋 and an arbitrary clustering Θ𝐶 such that

there exists a complete decision tree  of sufficiently high depth 𝑑, which partitions 𝑋 into the same clusters ∀𝑥 ∈ 𝑋 ∶ Θ(𝑥) = Θ𝐶 (𝑥). 2

3 SAT-based 𝜖-Optimal Tree Clustering

In this section, we present our approach for solving the problems in Section 2.2. First, we present a way to simplify our handling of pairs while still maintaining the approximation guarantee. Then, we present a novel SAT-based encoding for interpretable and constrained tree clustering.

3.1 Distance Classes

To encode the 𝜖-approximation in Problem 1 and Problem 2, we divide the set of all pairs of data points based on their distance into 𝜇 non-overlapping intervals called distance classes  = {𝐷1,𝐷2, ...,𝐷𝜇} such that the smallest and largest distances in each class are less than 𝜖 apart. Specifically, we employ a greedy procedure that sorts all pairs from the smallest distance to the largest and greedily adds them one by one, creating new classes as needed to guarantee that the distances in each class are at most 𝜖 apart. All pairs in the same class are treated similarly w.r.t. being clustered together or not.

1 We only consider cases where the 𝑀𝐿 and 𝐶𝐿 constraints are consistent, i.e., where there exists a clustering that satisfies these constraints. For example, if the same pair of points is found in both the 𝑀𝐿 and 𝐶𝐿 constraints, there exists no clustering that would satisfy these constraints.

2 All proofs appear in the extended version [Shati et al., 2023].

In order to maximize the minimum split, we consider the index 𝜆+ such that any pair of data points in distance classes 𝐷1..𝐷𝜆+ must be clustered together (Eq. (5)). Similarly, to minimize the maximum diameter, we consider the index 𝜆such that any pair in distance classes 𝐷𝜆-+1..𝐷𝜇 must be clustered separately (Eq. (6)).

Note that in any feasible clustering, for all 𝜆+ and 𝜆- values that satisfy (Eqs. (5) and (6)), we have that MS ≥ 𝑚𝑖𝑛({|𝑥1 - 𝑥2| | (𝑥1, 𝑥2) ∈ 𝐷𝜆++1}) and MD ≤ 𝑚𝑎𝑥({|𝑥1 - 𝑥2| | (𝑥1, 𝑥2) ∈ 𝐷𝜆-}). We therefore focus on optimizing the indices 𝜆+ and 𝜆- to obtain 𝜖-optimal solutions to Problem 1 and Problem 2 (Proposition 2).

Proposition 2 (MD and MS-MD 𝜖-approximation). Let Θ be a tree cluster assignment. We have that:

1. If Θ is an optimal solution w.r.t minimizing 𝜆- thenΘ is an 𝜖-optimal solution w.r.t the MD objective.
2. If Θ is a Pareto-optimal solution w.r.t minimizing 𝜆and maximizing 𝜆+ then Θ is an 𝜖-Pareto optimal solution w.r.t the bi-criteria MD-MS objective.

3.2 MaxSAT Encoding

A SAT formula is a conjunction of clauses, a clause is a disjunction of literals, and a literal is either a Boolean variable or its negation. A clause is satisfied if at least one of its literals is true. The SAT problem consists of finding an assignment of the variables that satisfies all clauses in a formula [Biere et al., 2009]. We model the construction of 𝜖-optimal constrained clustering trees as Partial MaxSAT, an optimization variant of SAT that divides clauses into hard and soft clauses, requiring variable assignments to satisfy all hard clauses and to maximize the number of satisfied soft clauses.

Variables

Table 1 describes the set of Boolean variables.

Clauses

We encode the construction of the decision tree (Eqs. (7)- (15)) following Shati et al. [2021], a state-of-the-art SATbased decision-tree classifier that naturally supports numeric features that are prevalent in clustering problems. These clauses guarantee that exactly one feature is chosen at each branching node (Eqs. (7)-(8)), the points are directed to the left or right child of each branching node based on their value of the chosen feature (Eqs. (9)-(10)), the appearance of points at leaves correctly correspond to the path that they are directed through within the tree (Eqs. (11)-(13)), and thresholds are non-trivial (Eqs. (14)-(15)). 34

𝑗 ,𝑡 )

The following clauses extend the basic decision tree encoding to support 𝜖-optimal clustering trees that satisfy the 𝑀𝐿 and 𝐶𝐿 constraints. The clauses in Eq. (16) guarantee wellformed unary encoding of cluster labels in each leaf. 5

Eqs. (17)-(18) guarantee that the label assigned to each data point matches the label of leaf the data point reaches.

Eqs. (19)-(20) break the ties between the equivalent cluster assignments. We consider two cluster assignments Θ1 and Θ2 equivalent if there exists a relabelling, Γ ∶ 𝐾 → 𝐾, such that Γ◦Θ1 = Θ2 . To break ties, we force each 𝑥𝑖 in the ascending order to be assigned to the first empty cluster, if it needs a new one. This guarantees that there are no two feasible solutions that are relabellings of each other. Note that we do not eliminate viable solutions, since any clustering can be renamed into an equivalent one that respects this property.

3 The set 𝑂𝑗 (𝑋) contains all consecutive pairs of points when ordered according to feature 𝑗 and the set 𝐴𝑙 (𝑡) (𝐴𝑟 (𝑡)) contains all nodes that have 𝑡 as descendent of their left (right) child.

4 For a detailed description of the clauses in Eqs. (7)-(15), we refer the reader to Shati et al. [2021].

5 A unary encoding is well-formed if it does not include the sequence 01 at any point.