Learning Customised Decision Trees for
Domain-knowledge Constraints

Géraldin Nanfack<sup>a,*</sup>, Paul Temple<sup>a</sup>, Benoît Frénay<sup>a</sup>

<sup>a</sup> PReCISE Research Center, Namur Digital Institute (NADI), University of Namur,
Belgium

**Abstract**

When applied to critical domains, machine learning models usually need to
comply with prior knowledge and domain-specific requirements. For example,
one may require that a learned decision tree model should be of limited size
and fair, so as to be easily interpretable, trusted, and adopted. However, most
state-of-the-art models, even on decision trees, only aim to maximising expected
accuracy. In this paper, we propose a framework in which a diverse family of
prior and domain knowledge can be formalised and imposed as constraints on
decision trees. This framework is built upon a newly introduced tree represen-
tation that leads to two generic linear programming formulations of the optimal
decision tree problem. The first one targets binary features, while the second
one handles continuous features without the need for discretisation. We the-
oretically show how a diverse family of constraints can be formalised in our
framework. We validate the framework with constraints on several applications
and perform extensive experiments, demonstrating empirical evidence of com-
parable performance w.r.t. state-of-the-art tree learners.

Keywords: Decision Trees, Constraints, Domain Knowledge

*Corresponding author
Email addresses: geraldin.nanfack@unamur.be (Géraldin Nanfack),
paul.temple@unamur.be (Paul Temple), benoit.frenay@unamur.be (Benoît Frénay)
# 1. Introduction

Decision trees are one of the most well-known classes of machine learning models thanks to their interpretability and ability to learn decision rules with relevant features [1, 2, 3]. They are even applied in critical domains involving high-stakes decision-making such as medical diagnosis and finance [4, 5]. Yet, in these critical domains, machine learning models need to be simple to explain, and meet ethical and domain-specific requirements [6]. For example, to predict heart disease, similar to a medical doctor, learned decision trees should take into consideration domain constraints like economic criteria when selecting features. Moreover, to validate decision trees, practitioners and domain experts may require a certain level of performance guarantee for an underrepresented target group of sample [7]. In these scenarios, the lack of satisfaction with domain-specific constraints and goals makes decision trees untrustworthy and likely to be rejected [8]. As an illustration of its importance, the issue of trustworthy artificial intelligence is also a major concern at the EU level <fnref n="1" />. To learn more trustworthy models, constraint enforcement represents a theoretically supported framework to customise the shape of the hypothesis set of models under a wide range of settings. However, designing learning algorithms may be complex, even for decision trees, when ethical and domain constraints must be met.

Recently, several decision tree methods [9, 10, 11, 12] have proposed to formalise the optimal decision tree problem as a mixed integer programming (MIP), a satisfiability (SAT) or a dynamic programming problem whose solutions often lead to small and accurate trees. A strong emphasis has been put on the speed of optimisation, neglecting the possibility of easily modeling prior and domain knowledge. Hence, these current methods are little to no applicable in settings where prior knowledge needs to be formalised, and enforced in order to learn more comprehensible and trustworthy trees. Yet, in domains as critical

<footnote n="1">¹Communication from the Commission of 8 April 2019, Building Trust in Human-Centric Artificial Intelligence, COM (2019) 168.</footnote>
as medicine and justice, the satisfaction of domain-knowledge constraints may
be more important than providing a good level of accuracy [13, 14, 15]. This
suggests that a broader family of constraints should be considered when mod-
eling the decision tree learning problem. In this paper, we, therefore, model
the optimal decision tree problem so as to easily formalise constraints while al-
lowing an explicit control of their complexity through both the number of leaf
nodes and the maximum depth. We present a tree representation based on con-
strained matrices that leads to two generic linear formulations of the optimal
decision tree problem. The first formulation targets binary features while the
second one copes with continuous features without the need for discretisation.
Moreover, in contrast to recent depth-centric models, our tree representation is
a branch-like model. We show its flexibility to straightforwardly formalise and
enforce a broad class of constraints that include but are not limited to ordering
on features, exclusion of features over branches, feature costs, and fairness.

The contributions of this paper can be summed up as follows: (1) we propose a tree representation based on constrained matrices that leads to two new generic linear programming formulations of the optimal decision tree problem allowing to easily integrate domain-knowledge constraints; (2) both formulations give the possibility for users to easily control complexity through the constraints on the number of leaf nodes and the maximum depth of the decision tree; (3) we theoretically show that elements of these matrices give the ability to easily formalise domain knowledge as constraints to improve trustworthiness.

The rest of the paper is organised as follows: Section 2 presents related
works, Section 3 introduces our tree representation, and our first generic linear
programming formulation for binary features (the second formulation is detailed
in Appendix<fnref n="2" /> A.1); Section 4 formalises the expression of domain-knowledge
constraints; Section 5 shows application to real-world applications; Section 6
benchmarks the performance of our models w.r.t. recent models and discusses
the results; Section 7 analyses computational time before concluding.

<footnote n="2">²Appendix is added via the link to "Supplementary Material for on-line publication only".</footnote>
## 2. Related Works

Several works exist to learn decision trees under constraints. We thoroughly present them in what follows.

Building upon standard top-down induction trees such as CART [16] and C4.5 [17], many works have attempted to enforce constraints on decision trees by learning in a greedy top-down fashion. The minimum description length (MDL) presented by Quinlan and Rivest [18], inspired the work of Garofalakis et al. [19] that proposed to find a trade-off between the size of the tree and its accuracy with a branch-and-bound algorithm. It learns either the smallest decision tree given the accuracy or, the other way around, retrieves the most accurate decision tree given the size of the tree. Although it is possible to incorporate some domain-knowledge constraints like test and misclassification costs on decision trees via data and feature engineering (e.g., by creating virtual instances or features), the such process remains highly non-trivial [20], supporting, therefore, the common approach of enforcing constraints directly through the model formulation. The former approach is all the more challenging for complex misclassification costs in multiclass settings and for feature acquisition costs. Also, data engineering may raise stability issues in learning procedures, e.g., when misclassification costs are highly different. Related to constraint enforcement through the model formulation, Núñez [21] encodes a hierarchy of features with ISA (Is A) relationships and feature costs on a cost-sensitive measure to learn decision trees in a greedy top-down fashion. By doing that, they suppose that learned trees will make more sense for domain experts. López-Vallverdú et al. [22, 23] also present an algorithm based on the priority and relevance of features. They propose to modify the list of features on a given node and also formalise background knowledge using healthcare criteria. However, top-down algorithms often produce sub-optimal trees which may result in poor solutions when constraints need to be enforced [24].

Some works try to learn optimal solutions under tree-structure constraints by enumerating possible solutions via dynamic programming. Garofalakis et al.
[25] build up on their previous work and learn an overfitted decision tree that they prune to satisfy constraints. One major drawback of post-pruning methods is that new interesting rules are not learned since the top of the tree remains unchanged while the bottom is cut-off. To get rid of it, Nijssen and Fromont [26] present the DL8 algorithm using dynamic programming. Later, it is transposed into a more general framework [24] which uses an item-set mining approach. They are able to learn optimal decision trees for different types of constraints (e.g., size of the tree and test costs). As stated by the authors, DL8 needs memory to encapsulate the huge amount of item sets. To address the limitations of DL8, Aglin et al. [27] propose DL8.5 that focuses on the task of minimising the misclassification error under depth constraint. To enforce the depth constraint, the authors had to drastically modify the DL8 algorithm. Authors highlight that “optimisation [of DL8] is hard to combine with a constraint on the depth of a tree” [27], to argue why they had to completely change DL8. As a result, the size of the tree is left aside and cannot be constrained, at the profit of accelerating learning through a branch-and-bound search. Moreover, without requiring another drastic change, DL8.5 cannot enforce constraints over test costs or the hierarchy of features which are both tree-structure dependent constraints [24].

Inspired by Angelino et al. [28], Hu et al. [29] proposed optimal sparse decision trees (OSDT) that also use branch-and-bound search, but are limited to binary classification. Analytic bounds are used to prune the search space while the number of leaves is constrained using a regularised loss function that balances accuracy and the number of leaves. Because OSDT and its extended version GOSDT [30] use a customised branch-and-bound search, similarly to DL8.5, integrating tree-structure dependent constraints that are not directly expressed in the objective function will need to completely accommodate the learning algorithm. Nonetheless, our work shares similarities with OSDT since our model also allows constraining directly the number of leaves.

Because of the speed improvement of machines, several works [10, 9, 12, 31] propose to exploit MIP and SAT solvers to learn optimal decision trees by constraining the depth. More specifically, Narodytska et al. [11] and Florent
<table><caption>Table 1: Comparison of state-of-the-art tree learning methods in terms of their ability to enforce the constraints considered in this paper. ✓ (resp. ✗) indicates that the current method allows (resp. does not allow) the integration of a specific constraint or is (resp. is not) able to deal with the multiclass setting.</caption><thead><tr><th>Constraints/Setting</th><th>BinOCT</th><th>[32]</th><th>DL8.5</th><th>OSDT<sup>3</sup></th></tr></thead><tbody><tr><td>Number of leaves</td><td>✗</td><td>✗</td><td>✗</td><td>✓</td></tr><tr><td>Depth</td><td>✓</td><td>✓</td><td>✓</td><td>✓</td></tr><tr><td>Hierarchy/ordering</td><td>✓</td><td>✓</td><td>✗</td><td>✓</td></tr><tr><td>Features/Misclassification costs</td><td>✗</td><td>✗</td><td>✗</td><td>✗</td></tr><tr><td>Minimum #instances in the same leaf</td><td>✗</td><td>✓</td><td>✓</td><td>✗</td></tr><tr><td>Instances belonging to the same leaf</td><td>✓</td><td>✓</td><td>✗</td><td>✗</td></tr><tr><td>Range of threshold splits cont. features</td><td>✗</td><td>✗</td><td>✗</td><td>✗</td></tr><tr><td>Multiclass setting</td><td>✓</td><td>✗</td><td>✓</td><td>✗</td></tr></tbody></table>

[31] use SAT solvers to learn the smallest tree for perfect classification. We do not tackle the same problem in this paper. Bertsimas and Dunn [10] present a MIP formulation of the optimal decision tree problem for a given depth. Their model (called OCT) handles both univariate and multivariate splits. As stated in [29], OCT is not easily reproducible and no public code is available [29].

A more recent MIP formulation (BinOCT) has been proposed by [9] to be efficient in computations. To speed up optimisation, BinOCT considers full and complete binary trees under depth constraints. This raises a question about the optimality of their learned trees when the optimal solution is not full and complete. In particular, in presence of domain constraints, BinOCT will not find a solution if trees do not need to be full and complete. Moreover, in order to accelerate optimisation, BinOCT does not keep track of misclassified instances through decision variables, making it impractical to change objective function in order to integrate instance-dependent constraints like misclassification costs. The work [32] uses constraint programming to learn optimal decision trees, but only under depth constraint, and targets only binary classification.

To date, previous models have focused on accelerating the learning of optimal decision trees. This work instead focuses on the enforcement of a broad class of

<footnote n="3">³PyGOSDT [30], an improvement of OSDT, does multiclass but only through one-vs-all.</footnote>
constraints for trustworthiness. As it is not the focus of previous works, they do not natively offer mechanisms to do that. For example, they may allow the setting of a depth constraint, but shallow decision trees may be over-simplistic and not meet domain-knowledge constraints. Such decision trees may be rejected by domain experts [1, 15]. Table 1 illustrates this with a representative sample of types of constraints that the above methods are (or are not) able to cope with, so as to incorporate a broad class of domain knowledge. For example, BinOCT, DL8.5 and Verhaeghe et al. [32] are depth-centric models that are not directly formulated to find the optimal decision tree for a fixed number of leaf nodes. Also, while BinOCT with its discretisation heuristic can cope with continuous features, all other methods require binary features. As a result, they (BinOCT included) cannot integrate the constraint that threshold splits must belong to a given interval, which is useful when seeking for relevant decision rules with respect to the domain expertise [33, 4, 34]. Some of the above methods could be modified at a significant cost to take into account some of the considered constraints (or even other ones). However, as they are not designed for that purpose, it is neither formally nor technically obvious how to do so (e.g., the transition from DL8 to DL8.5). This motivates our work to make constraint enforcement easier, thanks to a specifically designed tree representation.

The above analysis of the state of the art shows the need for a general framework to i) efficiently handle complexity control for generalisation of decision trees; ii) and learn decision trees under domain constraints that are important for safety and trustworthiness. Therefore, we propose a tree representation based on constrained matrices that leads to two generic flexible linear programming formulations of the optimal decision tree problem, which eases the integration of a broad class of constraints. Indeed, based on a branch-like tree representation, our formulations take into account structural constraints such as the number of leaves and the maximum depth. Furthermore, thanks to the constrained matrices encoding this representation, our method allows us to enforce a broad class of constraints, which include those listed in Table 1.
<figure><img src="image_1.png" /><figcaption>Figure 1: Tree encoding detailed for a branch. (a) An example of a decision tree on which depths are depicted and the first branch of the tree is circled. (b) The corresponding encoding for only the branch 0 (circled in (a)) with pointers representing how to pass from one dimension to another (c) The encoding matrix *Q* for all branches. The branch label is at dimension 0, the depth at dimension 1, attributes and their values are at dimension 3 and 4. Note that here, attribute *X*₀ is not selected on the tree in (a) but it is encoded in the matrix *Q*.</figcaption></figure>

### 3. Tree Representation and the New Formulation to Enforce Constraints on Decision Trees

This section presents our tree representation and the first formulation of the tree learning classification problem via binary variables and linear constraints.

Let us consider a dataset where all features have been transformed into binary features (numeric features being discretised and binarised). A decision tree from this dataset is characterised by its number of leaf nodes *L*, its maximum depth *K*, and its size. In what follows, $\mathbf{X} \in \{0,1\}^{N \times M \times V}$ denotes the dataset (without labels), *N* is the number of instances, *M* is the number of features and *V* is the number of values which can be taken by a feature. Here, it is assumed that data only have binary features, thus *V* = 2. However, the following can be easily extended to *V* > 2 for *V*-array trees. $\mathbf{T} \in \{0,1\}^{N \times C}$ is the matrix providing the labels of instances (into their one-hot-encoding form) and *C* is the number of classes. Finally, [*n*] denotes the set $\{0, 1, ..., n-1\}$, for $n \in \mathbb{N}$.

#### 3.1. *Tree Representation*

We need a convenient and efficient way to encode trees so as to easily formalise domain constraints such as those related to the path of decisions (e.g., ordering on tests and test costs on branches). Rather than a tree representation
that decomposes a tree into a set of nodes, our decision trees are decomposed in terms of the set of branches. We propose to encode branches with the (multidimensional) matrix $Q \in \{0, 1\}^{L \times K \times M \times V}$. To illustrate, $Q_{ijlp} = 1$ if the $p$-th value of the $l$-th feature is selected, at depth $j$ of the $i$-th branch. Therefore, $Q_{i,*}$ encodes the $i$-th branch of the tree, $Q_{ij,*}$ encodes the selection of features and its values at depth $j$ of branch $i$, and $Q_{ijl,*}$ is the vector encoding whether the $l$-th feature has been selected$^4$ at depth $j$ of branch $i$. Figure 1 shows an example of a decision tree with its encoding matrix. As an illustration, on the branch 0 at depth 0 of the decision tree of Figure 1 (a), the attribute $X_1$ is selected with value 1. This means that $Q_{0,0,1,1} = 1$, as shown in Figure 1 (c).

From this description, $Q$ can be represented as a 4-dimensional binary matrix. The following constraints need to be added in order to encode the selection of features over branches of trees. We give an example for the first constraint. Similar examples can be derived for the rest of the constraints.

* The same feature is chosen at the top of all branches:

$$ \forall i \in [L], a \in [L], l \in [M]: \sum_{p \in [V]} Q_{i,0,l,p} = \sum_{p \in [V]} Q_{a,0,l,p}. \quad (1) $$

Linking it to Figure 1, at depth $j = 0$, the attribute $X_1$ (i.e., $l = 1$) is selected on branches $i = 0$ and $a = 1$, i.e., $\sum_{p \in [V]} Q_{i,0,l,p} = \sum_{p \in [V]} Q_{a,0,l,p}$.

* No more than one feature must be chosen on a branch $i$, at depth $j$:

$$ \forall i \in [L], j \in [K]: \sum_{l \in [M]} \sum_{p \in [V]} Q_{ijlp} \le 1. \quad (2) $$

* Each feature is chosen at most once on a branch:

$$ \forall i \in [L], l \in [M]: \sum_{j \in [K]} \sum_{p \in [V]} Q_{ijlp} \le 1. \quad (3) $$

* For every branch, if a feature is chosen at depth $j$, on all previous depths $0, \dots, j-1$, a feature must be selected:

$$ \forall i \in [L], j \in [K-1]: \sum_{l \in [M]} \sum_{p \in [V]} Q_{ijlp} \ge \sum_{l \in [M]} \sum_{p \in [V]} Q_{i(j+1)lp}. \quad (4) $$

<footnote>$^4$The $l$-th feature is selected if at least one its value is $\neq 0$.</footnote>
<figure><img src="image_2.png" /><figcaption>Figure 2: Relationship between branches (matrix Z). Left: branches of the tree. Center: the relationship between the first branch (branch 0) and the other branches; the deepest vector (with 3 bits horizontally aligned) defines the 3 possibilities of pair of branches given a depth: (i) branches are equal up to that depth, (ii) branches are siblings, (iii) branches are different with a variable or a value before the given depth. Right: the corresponding matrix Z which encodes the relationship between all the branches.</figcaption></figure>

From what has been described, *Q* models a set of *L* branches with at most *K* features selected per branch. However, for *Q* to represent a valid tree, relations between branches need to be defined. In particular, two branches *i* and *a* are siblings at depth *j* if all features and values that are selected on branch *i* and *a* until depth *j*, are equal, but on depth *j*, chosen features to remain the same between the two branches and only their values differ (e.g., branch 1 and 2 at depth 0). Formally, branch relations are encoded using the 4-dimensional matrix <fnref n="5" /> $Z \in \{0, 1\}^{L \times K \times L \times 3}$ and we define three types of relations: (i) $Z_{ija,0} = 1$ if all the features and their values on branches *i* and *a* are equals up to and including depth *j*; (ii) $Z_{ija,1} = 1$ if branches *i* and *a* are siblings at depth *j*; and (iii) $Z_{ija,2} = 1$ if it exists one feature or one value of feature selected on depth $j_1 < j$ which differs from branches *a* and *i*. For example, in Figure 2, at depth 1, branches 0 and 1 are siblings, so $Z_{011,1} = 1$; and at depth 1 branches 0 and 2 fall into the third case; so $Z_{012,2} = 1$.

With the above definitions for the *Q* and *Z* matrices, we can now express the constraints that a valid tree representation should satisfy.

<footnote n="5">⁵The Symmetry on this matrix *Z* w.r.t. branch indexes *i* and *a* at their respective dimensions 0 and 2 has been technically broken in the implementation by considering that *i* < *a*.</footnote>
* All branches must be pairwise different:

$$ \forall i \in [L], a \in [L] \setminus \{i\}: Z_{i,K-1,a,0} = 0. \qquad (5) $$

* Every pair of branches matches only one of the previous cases:

$$ \forall i, a \in [L], j \in [K]: \sum_{q \in \{0,1,2\}} Z_{ijaq} = 1. \qquad (6) $$

* Every pair of branches in case (i) at depth j must have selected on depths $j_1 \le j$ the same feature and have the same values of those features:

$$ \forall i, a \in [L], j \in [K], j_1 \in [j+1], p \in [V]: Z_{ija,0} = 1 \Rightarrow Q_{ij_1lp} = Q_{aj_1lp}. \qquad (7) $$

* On a branch, if no feature is chosen at a specific depth j, no other branch can be in case (i) at depth $j-1$:

$$ \forall i \in [L], a \in [L] \setminus \{i\}, j \in [K-1]: Z_{ija,0} \le \sum_{l \in [M]} \sum_{p \in [V]} Q_{i,j+1,lp}. \qquad (8) $$

* Every pair of branches in case (iii), which are different on at least one depth before j must have a depth where feature/value is different. This relationship appears when earlier on depth $j_1 < j$, the branches were siblings. Therefore, the constraint can be simply written as:

$$ \forall i \in [L], j \in [K], j_1 \in [j], a \in [L] \setminus \{i\}: Z_{ija,2} \ge Z_{ij_1a,1}. \qquad (9) $$

* If a feature is selected on a depth of a branch, the branch must have at least one sibling:

$$ \forall i \in [L], j \in [K]: \sum_{a \in [L] \setminus \{i\}} Z_{ija,1} \ge \sum_{l \in [M]} \sum_{p \in [V]} Q_{ijlp}. \qquad (10) $$

* Every pair of sibling branches must be equal (in terms of features and values) up to depth $j-1$:

$$ \forall i, a \in [L], j \in [K] \setminus \{0\}, j_1 \in [j], l \in [M], p \in [V]: Z_{ija,1} = 1 \Rightarrow Q_{ij_1lp} = Q_{aj_1lp}. \qquad (11) $$
* Every pair of sibling branches on depth j must have the same feature chosen on this depth:

$$ \forall i, a \in [L], j \in [K], l \in [M]: Z_{ija,1} = 1 \Rightarrow \sum_{p \in [V]} Q_{ijlp} = \sum_{p \in [V]} Q_{ajlp}. \quad (12) $$

* Values of features for each pair of sibling branches at depth j must be different if the feature is selected and equal to zero otherwise:

$$ \forall i, a \in [L], l \in [M], j \in [K], p_1 \in [V]: Z_{ija,1} = 1 \Rightarrow Q_{ijlp_1} + Q_{ajlp_1} = \sum_{p \in [V]} Q_{ijlp}. \quad (13) $$

* If no feature is selected at depth j of the branch i, no branch can be a sibling of another branch i:

$$ \forall i \in [L], a \in [L] \setminus \{i\}, l \in [M], j \in [K], p \in [V]: Z_{ija,1} \le \sum_{p \in [V], l \in [M]} Q_{ijlp}. \quad (14) $$

Our tree representation is composed of matrices Q and Z on which constraints (1-14) are applied. Matrices Q and Z respectively have L×K×M and L²×K variables. To learn trees, one needs to create an objective function where instance-dependent variables need to be explicitly introduced, as shown hereafter.

## 3.2. Encoding Global Objective Functions

This section introduces variables and constraints used to encode the global objective function. Section 4 will show how constraints can be easily enforced.

Let $S \in \{0, 1\}^{N \times L}$ denote the mapping between the set of examples of the dataset and the set of leaves (e.g., $S_{ei} = 1$ if example e belongs to the i-th leaf/branch and 0 otherwise). Let $H \in \{0, 1\}^{L \times C}$ denote the mapping between the set of branches and the set of classes (e.g., $H_{ic} = 1$ if c is the predicted class of branch i and 0 otherwise). Finally, $R \in \{0, 1\}^N$ defines the 0-1 loss over the example e. For recall, $T \in \{0, 1\}^{N \times C}$ represents labels of the dataset, as defined at beginning of this section.

The following constraints describe how to encode global objective functions.
* Each example must belong to one leaf:

$$ \forall e \in [N]: \sum_{i \in [L]} S_{ei} = 1. \qquad (15) $$

* If an example belongs to a leaf node, all the features/values chosen on the corresponding branch must be the same as this example:

$$ \forall e \in [N], i \in [L], j \in [K], l \in [M], p \in [V]: $$

$$ Q_{ijlp} = 1 \Rightarrow S_{ei} \le 1 - \mathbf{X}_{elp} + Q_{ijlp}, \qquad (16a) $$

$$ Q_{ijlp} = 1 \Rightarrow S_{ei} \le 1 + \mathbf{X}_{elp} - Q_{ijlp}. \qquad (16b) $$

* Each branch of a leaf node must predict exactly one class:

$$ \forall i \in [L]: \sum_{c \in [C]} H_{ic} = 1. \qquad (17) $$

* The class of a leaf node (or branch) is the majority vote of examples belonging to this branch:

$$ \forall i \in [L], c_1, c_2 \in [C]: H_{ic_1} = 1 \Rightarrow \sum_{e \in [N]} S_{ei} * \mathbf{T}_{ec_1} \ge \sum_{e \in [N]} S_{ei} * \mathbf{T}_{ec_2}. \qquad (18) $$

* The error of the predicted class of an example is equal to one if the class of its branch is different from the true class and equal to zero, otherwise:

$$ \forall e \in [N], c \in [C], i \in [L]: $$

$$ S_{ei} = 1 \Rightarrow R_e \ge -H_{ic} + \mathbf{T}_{ec}, \qquad (19a) $$

$$ S_{ei} = 1 \Rightarrow R_e \le 2 - H_{ic} - \mathbf{T}_{ec}. \qquad (19b) $$

Using the above results, the misclassification error of the tree is

$$ \sum_{e \in [N]} R_e. \qquad (20) $$

This objective function can be used by solvers to search for an optimal tree.

**Proposition 1.** The complexity $C$ in terms of the number of variables of the entire constraint program of our formulation is $O(L \times K(L+M) + N \times L)$. It can be reduced to $O(L(L+M+N))$ for shallow trees when prior values of $L$ and $K$ are known.
Proof. The tree encoding complexity (in terms of the number of variables) is $O(L \times K \times M + L^2 \times K)$. The objective function encoding is $O(N \times L)$. Then, the total complexity is

$$C = O(L \times K \times M + L^2 \times K + N \times L) = O(L \times K(L+M) + N \times L)$$

For shallow trees, $K$ is small, therefore less than a fixed maximum value. So, $C = O(L^2 + L \times M + L \times N)$. □

The time to find the optimal solution increases proportionally with the size of the dataset and the number of leaves. Another important insight from Proposition 1 is the fact that, in terms of the number of variables, the complexity $C$ highly varies depending on which term is the biggest term between $N$ and $K(L+M)$. In particular, $N$ is not usually tunable (except with sub-sampling) whereas $M$ could be because of the binarisation step. Hence, Proposition 1 shows that in practical implementations with binary features, $M$ should be ideally negligible w.r.t. $N$ (i.e., a $o(N)$), when prior values of $K$ and $L$ are known.

Constraints 7, 11, 12, 13, 16a, 16b, 18, 19a and 19b are not directly expressed in a linear form. They are presented in a form called *indicator* constraints, but modern linear programming solvers generally prefer this form. Nonetheless, they can be linearised using big-M constraints (e.g., constraint 7 can be written as $Q_{ijlp} - Q_{ajlp} \le M*(1 - Z_{ija,0})$, with $M$ being a big positive number so that when $Z_{ija,0} = 1$, the left part of the inequality must be null).

It is worth mentioning that, in contrast to [10, 32, 9], our first model does not rely on a specific type of solver since we exploit only binary variables and linear constraints. Therefore, it has the advantage to be implementable on CP solvers as well as MIP and ILP solvers.

## 4. Formalising Domain Knowledge as Constraints

With the tree representation and the first formulation (the second one is detailed in Appendix A.1) presented in the previous section, in the following,
we show how useful domain knowledge can be straightforwardly formalised as constraints and integrated into our models.

### 4.1. Ordering of Features

It often appears that domain experts have a prior belief in a specific ordering of features. This prior may directly come from their background knowledge or hard material constraints which favor asking patients to perform tests before others. As an illustration, to predict liver diseases, doctors will ask patients their age before performing a bilirubin test since the interpretation of this test depends on the age of the patient [35]. Therefore, a comprehensible decision tree for domain experts should encode this prior knowledge. The constraint "feature $\mathbf{X}_{12}$ must not appear before $\mathbf{X}_{11}$" is expressed as

$$ \forall i \in [L], j \in [K] \setminus \{0\}, \sum_{j_1 \in [j]} \sum_{p \in [V]} Q_{ij_1 l_{2p}} \le 1 - \sum_{p \in [V]} Q_{ijl_{1p}}. $$

### 4.2. Test Costs on Features

Experts can also be constrained by economic considerations to ask patients to do tests before taking decisions [21]. A good illustration of this importance is the case of the application of machine learning algorithms in domains with a lack of available material resources to perform medical tests. Hence, one can specify test costs on features in order to limit the total cost to perform before reaching a decision. With our framework, it is possible to learn trees with a maximum classification cost $\tau$ on a cost-sensitive dataset. This constraint becomes

$$ \forall i \in [L]: \sum_{j \in [K]} \sum_{l \in [M]} \sum_{p \in [V]} Q_{ijlp} * \text{cost}(l) \le \tau. $$

where cost(l) denotes the test cost of feature $\mathbf{X}_1$.

### 4.3. Expected Cost for Classification

As for the same reasons with test costs, certain applications may require to constrain the expected classification cost. The weighted test cost of a branch i
is $\frac{1}{N} \sum_{e \in [N]} \sum_{l \in [M]} S_{ei} * \text{cost}(l) * (\sum_{p \in [V]} Q_{ijlp})$. As this previous term is non-linear, it is possible to linearise it with variables $N_{ij}$ representing the weighted test cost of the branch $i$ at depth $j$, with the constraints:

$$ \forall i \in [L], j \in [M], l \in [L], \sum_{p \in [V]} Q_{ijlp} = 1 \Rightarrow N_{ij} = \text{cost}(l) * \sum_{e \in [N]} S_{ei}, \\ \text{and } \forall i \in [L], j \in [M], \sum_{l \in [M] p \in [V]} Q_{ijlp} = 0 \Rightarrow N_{ij} = 0. $$

Therefore, the expected cost for classification is $\text{Ecost} = \frac{1}{N} \sum_{i \in [L]} \sum_{j \in [K]} N_{ij}$. Imposing a maximum expected cost for a decision tree can be stated as

$$ \sum_{i \in [L]} \sum_{j \in [K]} N_{ij} \leq N * \tau. $$

## 4.4. Number of Instances on Leaf Nodes

To reduce the growth of a tree, one can also give the minimum number of instances on leaf nodes. This can be easily done by adding

$$ \forall i \in [L], \sum_{e \in [N]} S_{ei} \geq \text{minNumberInstances}. $$

## 4.5. Instances that Must Be in the Same Leaf

It often appears that datasets come with instance names and domain experts may have background knowledge of specific instances. Similarly to clustering [36], practitioners may want to impose that certain instances satisfy the same decision rule, i.e., belong to the same leaf node. One can also specify that two instances must be in the same leaf node with the proposed framework using the constraint expressed as

$$ \forall i \in [L], S_{e_1,i} = S_{e_2,i}, \text{ if } e_1 \text{ and } e_2 \text{ has to be in the same leaf node.} $$

## 4.6. Presence or Exclusion of a Feature Over the Tree or Over a Branch

It often appears that in several situations (e.g., due to noisy data), the selected features of a decision tree are not properly the domain-related relevant features [23]. In such situations, domain experts may not trust the learned tree.
Using our formulation, it is possible to impose the selection of a feature $\mathbf{X}_l$ (without even knowing where it should be selected) thanks to the constraint

$$ \sum_{i \in [L]} \sum_{j \in [K]} \sum_{p \in [V]} Q_{ijlp} \geq 1. $$

Additionally, two or more features may be redundant in a decision rule (i.e., over a specific branch). For some specific reasons, they should not be selected simultaneously in a branch (i.e., decision-wise) or in the whole tree (i.e., model-wise). Domain experts can provide this knowledge which can be infused as constraints. It can be guaranteed that two features $\mathbf{X}_{l_1}$ and $\mathbf{X}_{l_2}$ do not appear on the same branch of a decision tree with

$$ \forall i \in [L], \sum_{j \in [K]} \sum_{p \in [V]} Q_{ij,l_1,p} + Q_{ij,l_2,p} \leq 1. $$

$\mathbf{X}_{l_1}$ and $\mathbf{X}_{l_2}$ will not appear simultaneously into the tree if

$$ \sum_{i \in [L]} \sum_{j \in [K]} \sum_{p \in [V]} Q_{ij,l_1,p} + Q_{ij,l_2,p} \leq 3. $$

### 4.7. Fairness through Demographic Parity and Minimum Accuracy for a Group

#### 4.7.1. Demographic Parity

One of the most popular measures to quantify the unfairness is the demography parity [37, 38]. Demographic parity fairness aims to ensure that the predictions of a classifier do not depend on a sensitive feature $z$ such as gender or race, i.e., $p(\hat{y} = 1 | \mathbf{x}_z) = p(\hat{y} = 1 | \mathbf{x}_{\bar{z}})$ [39]. In practice, the demographic parity fairness is evaluated on a sample, through the difference of demography parity (DDP) given by

$$ \text{DDP} = \left| \frac{|\{\mathbf{x} \in \mathcal{D}; \hat{y} = 1, \mathbf{x}_z = 1\}|}{|\{\mathbf{x} \in \mathcal{D}; \mathbf{x}_z = 1\}|} - \frac{|\{\mathbf{x} \in \mathcal{D}; \hat{y} = 1, \mathbf{x}_z = 0\}|}{|\{\mathbf{x} \in \mathcal{D}; \mathbf{x}_z = 0\}|} \right|. $$

Let $N_z$ (resp. $N_{\bar{z}}$) be the number of samples belonging to the first (second) category of the binary sensitive feature, $N_z^+$ (resp. $N_{\bar{z}}^+$) be the number of positively predicted samples belonging to the first (resp. second) category of the sensitive feature. Therefore, the DDP can be expressed as $\text{DDP} = |N_z^+/N_z -$
$N_{\bar{z}}^{+}/N_{\bar{z}}|$. Looking back at our tree formulation, thanks to the partitioning of the branch representation, we can partition samples according to branches/leaves $i \in [L]$, create variables $N_{iz}^{+}$ (resp. $N_{i\bar{z}}^{+}$) for each branch and express the DDP as $|\frac{N_{\bar{z}}*\sum_{i \in [L]} N_{iz}^{+} - N_{\bar{z}}*\sum_{i \in [L]} N_{i\bar{z}}^{+}}{N_{\bar{z}}*N_{\bar{z}}}|$. Hence, using our tree formulation, a decision tree satisfies the $\epsilon$-DDP if

$$-\epsilon * N_{\bar{z}} * N_z \le N_{\bar{z}} * \sum_{i \in [L]} N_{iz}^{+} - N_z * \sum_{i \in [L]} N_{i\bar{z}}^{+} \le \epsilon * N_{\bar{z}} * N_z,$$

where $N_{iz}^{+}$ and $N_{i\bar{z}}^{+}$ are variables defined thanks to the following constraints:

$$\forall i \in [L], H_{i,1} = 0 \Rightarrow \begin{cases} N_{i\bar{z}}^{+} = 0 \\ N_{iz}^{+} = 0 \end{cases}, H_{i,1} = 1 \Rightarrow \begin{cases} N_{i\bar{z}}^{+} = \sum_{e \in [N]} S_{ei} * (1 - \mathbf{X}_{ez}) \\ N_{iz}^{+} = \sum_{e \in [N]} S_{ei} * \mathbf{X}_{ez} \end{cases}$$

### 4.7.2. Minimum Accuracy on an Underrepresented Group

In the same direction, if one would like to guarantee that a certain percentage $\epsilon$ of instances from a targeted group $G$ should not be misclassified, it can be easily imposed using the following constraint: $\sum_{e \in G} r_e \le (1 - \epsilon) * |G|$.

More broadly, it is important to note that, by drawing inspiration from demographic parity measures and minimum accuracy, other constraints called in [7] as *rate constraints* (evaluated using input/outputs of models) can be formalised and expressed within the proposed formulation.

## 5. Domain-knowledge Constraint Enforcement on Real-world Data

This section demonstrates empirically the capability of our model to enforce various types of domain-knowledge constraints. We now refer to our decision trees as *CPTrees*. Following the methodology in [40] and [7], we experimentally validate the ability of our framework to enforce a broad class of domain-knowledge constraints on several real-world applications with prior domain knowledge that should be enforced. In the following, for each application, we briefly discuss the results obtained with CPTree and constrained CPTree in terms of trees and decision rules. In order to have a point of comparison, we also include CART in our experiments, although any other method benchmarked in
Section 6 could be chosen. We report the accuracy in our experiments to study whether constraint enforcement impacts it: constrained decision trees should remain reliable and accurate. Finally, datasets are split using the 67 – 33% train-test percentage (except on COMPAS with the 40 – 60%).

5.1. *Ordering Constraint Applied to the Prediction of Breast Cancer Survival*

The first application is related to the *Haberman's survival* dataset [41], which contains features like *age* and *positive_nodes* (number of positive axillary nodes detected), etc. The goal is to predict whether a patient survives after surgery for breast cancer. In this domain, breast cancer is extremely violent for younger patients because it can weaken the patient and make the surgery dangerous. On the other hand, older patients usually have difficulties recovering from surgeries (in general) since it puts the body under high stress. In between these two categories, patients have more chances to survive breast cancer surgery [42]. Moreover, it is established that knowing the age, the evolution of *positive_nodes* is piece-wise linear [39] and that the feature *age* precedes the feature *positive_nodes* on a causal directed graph [43]. Therefore, a medically valid decision tree should first select the feature *age* before the feature *positive_nodes*.

*Results.* Figure 3 shows learned trees (CART, unconstrained, and constrained CPTrees) from this dataset. It can be observed that both CART and the unconstrained CPTree violate the ordering constraint. In contrast, the constrained CPTree does not only satisfy the constraint but also, the new top feature is the feature *age*, which appears to be to some extent more natural since it is likely to be the first question a medical doctor would ask a breast-cancer patient. Additionally, Table 2 confirms that this prior knowledge is in phase with data since predictive accuracy is slightly improved for the constrained CPTree.

5.2. *Must-be-selected Constraint Applied to Diabetes Prediction*

Here, we study the problem of predicting diabetes on patients of the dataset *Pima Indian diabetes* [41]. Patients of this dataset are women of at least twenty-one years old [44]. The dataset contains socio-demographic features such as
<table><caption>Table 2: Accuracy of CART, (unconstrained) CPTree and (constrained CPTree) C-CPTree.</caption><thead><tr><th rowspan="2"></th><th colspan="2">Haberman's survival</th><th colspan="2">Diabetes</th></tr><tr><th>Train</th><th>Test</th><th>Train</th><th>Test</th></tr></thead><tbody><tr><th>CART</th><td>77.07</td><td>71.28</td><td>79.96</td><td>68.50</td></tr><tr><th>CPTree</th><td>80.97</td><td>68.31</td><td>81.90</td><td>68.89</td></tr><tr><th>C-CPTree</th><td>78.53</td><td>73.26</td><td>79.57</td><td>74.40</td></tr></tbody></table>

<figure><img src="image_3.png" /><figcaption>Figure 3: Ordering constraints. Decision trees were obtained on Haberman's survival dataset using (a) CART, (b) CPTree without constraints, and (c) CPTree with the constraint: "feature agePatient must appear before feature positive_nodes".</figcaption></figure>

<figure><img src="image_4.png" /><figcaption>Figure 4: Must-be-selected constraints. Decision trees were obtained on the Diabetes dataset using (a) CART, (b) CPTree without constraints, and (c) CPTree with the constraint: "feature pregnancy must appear on the tree". Zoomed versions of the trees are left in Appendix B.2.</figcaption></figure>

age, clinical features such as body max index (BMI), and pregnancy-related features. In this use-case, we impose the constraint that a feature related to the pregnancy (*pregnancy*) should be selected on the tree. Indeed, women who have been pregnant may have developed *gestational diabetes*, which may result
<table><caption>Table 3: Accuracy of CART, CPTree, P-CART (trained without the *L-CORE* feature) and constrained CPTree (C-CPTree) on Post-operative data.</caption><thead><tr><th></th><th>Train</th><th>Test</th></tr></thead><tbody><tr><td>CART</td><td>83.33</td><td>53.33</td></tr><tr><td>CPTree</td><td>85.00</td><td>56.67</td></tr><tr><td>P-CART</td><td>80.00</td><td>63.63</td></tr><tr><td>C-CPTree</td><td>83.33</td><td>66.67</td></tr></tbody></table>

in diabetes after giving birth [45].

*Results.* Figure 4 shows learned trees from this diabetes dataset. According to the figure both CART and unconstrained CPTree select the same features but with different decision rules. They also fail to select a feature related to pregnancy. With these trees, it is difficult to quickly differentiate patients who are likely to have developed gestational diabetes. In contrast, when infusing the prior information of the selection of the *pregnancy* feature the constrained CPTree provides decision rules where it may be possible to differentiate those patients. Furthermore, as shown in Table 2, this prior knowledge does not harm predictive accuracy but helps to better generalise on unseen data.

### 5.3. Exclusion Constraint Applied to Prediction of Post-operative Action

This application aims to predict whether a patient should stay in the same service, go to an intensive care unit or go back home for recovery after surgery. We use the *Post-operative* dataset [41]. Here, from prior knowledge, on average, the difference between the core temperature (*L-CORE*) and the surface temperature (*L-SURF*) is generally constant. So it would be surprising and useless to select these two (strongly correlated) features on the same branch.

*Results.* Table 3 shows the performance of CART, CPTree, and P-CART (CART with the feature *L-CORE* removed). It can be seen that adding this prior knowledge does not impair predictive accuracy. It further improves generalisation. Moreover, as shown in Figure 5, both CART and CPTree violate the constraint while P-CART and C-CPTree satisfy by design.
<figure><img src="image_5.png" /><figcaption>Figure 5: Exclusion constraints. Decision trees obtained on the Post-operative patient dataset with (a) CART without constraints, (b) CPTree without constraints, (c) CART with one of the two highly correlated features removed, (d) CPTree with the constraint: "L-SURF (surface temperature) and L-CORE (internal temperature) are mutually exclusive in a branch".</figcaption></figure>

## 5.4. Minimum Accuracy on an Underrepresented Group and Test Cost Constraints Applied to Heart Disease Prediction

In this application, we use the *heart disease dataset* for heart disease prediction. In this application, men are usually of higher risk to develop heart disease than women. Sick women represent therefore an underrepresented group in this domain application and very often they present atypical symptoms compared to men [46]. Since even medical doctors have to be cautious [47] when exam-

<table><caption>Table 4: Accuracy of CART, CPTree, and constrained CPTree (C-CPTree) on heart disease. Group represents the group of sick women patients.</caption><thead><tr><th></th><th>Train</th><th>Test</th><th>Train Group</th><th>Test Group</th></tr></thead><tbody><tr><td>CART</td><td>82.32</td><td>77.78</td><td>68.75</td><td>55.56</td></tr><tr><td>CPTree</td><td>85.35</td><td>83.84</td><td>68.75</td><td>66.67</td></tr><tr><td>C-CPTree</td><td>81.82</td><td>79.80</td><td>93.75</td><td>88.89</td></tr></tbody></table>
<figure><img src="image_6.png" /><figcaption>Figure 6: Minimum accuracy on a targeted group. Decision trees obtained on the heart disease dataset with (a) CART without constraints and (b) CPTree without constraint and (c) CPTree with the constraint: "90% of sick women should not be misclassified".</figcaption></figure>

<table><caption>Table 5: Accuracy and DDP of CART, CPTree, constrained CPTree (C-CPTree) on Compas.</caption><thead><tr><th></th><th>Train</th><th>Test</th><th>Train DDP</th><th>Test DDP</th></tr></thead><tbody><tr><td>CART</td><td>83.60</td><td>83.76</td><td>8.09</td><td>7.49</td></tr><tr><td>CPTree</td><td>83.14</td><td>83.45</td><td>12.25</td><td>12.80</td></tr><tr><td>C-CPTree</td><td>81.64</td><td>82.18</td><td>1.68</td><td>1.37</td></tr></tbody></table>

ining women patients for this disease, it is likely that a classifier will struggle to correctly classify these examples. In order to enhance the possible trust of learned decision trees, we, therefore, impose the constraint that a high percentage (90%) of sick women should not be misclassified. We additionally impose the constraint on test costs, which we leave in Appendix C.3.

Results. Table 4 shows results obtained on CART, unconstrained CPTree, and the constrained one. Without the constraint, both CART and CPTree correctly classify only 68.75% of sick women. However, when imposing the constraint, the constrained CPTree does not only increase this percentage on the training distribution (93.75%), but also on the test distribution (88.89%). Nonetheless, in this case, the accuracy of the constrained CPTree is slightly below the one of the unconstrained CPTrees.
5.5. Fairness constraint Applied to Recidivism Prediction

In this application, we use the ProPublicas COMPAS recidivism data. The task is to predict recidivism based on historical crime and demographic features. Studies have reported that the system built around this dataset was racially biased against African American defendants [40]. Inspired by Cotter et al. [7], we impose the constraint that the DDP (with race as the protected feature) should be less than 5%.

365

*Results.* Table 5 shows results<fnref n="6" /> obtained on CART, unconstrained CPTree, and constrained CPTree. It appears on one hand that, both CART and unconstrained have approximately the same predictive accuracy, but the unconstrained CPTree is less fair than CART according to DDP. On the other hand, when enforcing the fairness constraint DDP decreases by approximately at least 6% (down to ±1%) while keeping the same level of accuracy of unconstrained trees.

370

375

In summary for these use cases, this section showed that our framework allows enforcing domain-knowledge constraints in diverse real-world applications. For each application, our constrained CPTrees enforce constraints without loss in accuracy performance with respect to the unconstrained ones and CART baselines. In what follows, we show that if no constraints are enforced, CPTrees obtain competitive results with respect to state-of-the-art tree learners. We aim to show that domain experts can safely use our approach to obtain trees that (i) are reliable and (ii) straightforwardly enforce constraints that the models need to comply with.

380

385

6. Comparison to State-of-the-Art Decision Tree Learners

This section benchmarks the proposed CPTrees with respect to state-of-the-art decision tree learners in order to validate their relevance from an accuracy perspective. Indeed, Section 5 has shown that CPTrees can enforce domain

<footnote n="6">⁶Trees are left in Appendix D.4. due to a lack of space.</footnote>
<table><caption>Table 6: Datasets. N, M, C denote respectively the number of instances, features and classes.</caption><thead><tr><th>Dataset name</th><th>N</th><th>M</th><th>Type of features</th><th>C</th></tr></thead><tbody><tr><td>Balance scale</td><td>625</td><td>4</td><td>categorical</td><td>3</td></tr><tr><td>Banknote authentication</td><td>1372</td><td>5</td><td>numeric</td><td>2</td></tr><tr><td>Car evaluation</td><td>1728</td><td>6</td><td>categorical</td><td>3</td></tr><tr><td>Credit approval</td><td>690</td><td>15</td><td>categorical, numeric</td><td>2</td></tr><tr><td>Hepatitis</td><td>155</td><td>19</td><td>categorical, numeric</td><td>2</td></tr><tr><td>Ionosphere</td><td>351</td><td>34</td><td>numeric</td><td>2</td></tr><tr><td>Iris</td><td>150</td><td>4</td><td>numeric</td><td>3</td></tr><tr><td>Mammographic masses</td><td>961</td><td>6</td><td>categorical, numeric</td><td>2</td></tr><tr><td>Monk1</td><td>432</td><td>6</td><td>categorical</td><td>2</td></tr><tr><td>Monk2</td><td>432</td><td>6</td><td>categorical</td><td>2</td></tr><tr><td>Monk3</td><td>432</td><td>6</td><td>categorical</td><td>2</td></tr><tr><td>Pima Indian diabetes</td><td>768</td><td>10</td><td>numeric</td><td>2</td></tr><tr><td>QSAR biodegradation</td><td>1055</td><td>41</td><td>numeric</td><td>2</td></tr><tr><td>Post operative patient</td><td>90</td><td>8</td><td>categorical, numeric</td><td>3</td></tr><tr><td>Seismic-bumps</td><td>2584</td><td>19</td><td>numeric</td><td>2</td></tr><tr><td>Spambase</td><td>4601</td><td>57</td><td>numeric</td><td>2</td></tr><tr><td>Spect heart</td><td>267</td><td>22</td><td>categorical</td><td>2</td></tr><tr><td>Thoracy surgery</td><td>470</td><td>17</td><td>numeric</td><td>2</td></tr><tr><td>Tic tac toe</td><td>958</td><td>9</td><td>categorical</td><td>2</td></tr><tr><td>Wine</td><td>178</td><td>13</td><td>numeric</td><td>3</td></tr></tbody></table>

knowledge constraints, but they must also provide competitive accuracy to be of practical interest.

## 6.1. *Experimental Settings*

Most of the experiment settings that we use in this section have been set in accordance with [9] and [10]. Experiments have been performed on 20 UCI datasets [41] (mostly taken from the list of datasets used by Verwer and Zhang [9] plus additional ones as seen in Table 6). Depending on the datasets, the number of classes varies from 2 to 3 and the number of instances from 90 to 4601.

No code for preprocessing datasets was found on any of the following source code repositories: BinOCT 7 [9], Verhaeghe et al. [32] 8 , OSDT 9 [29] and DL8.5 10 [27]. However, some datasets that we have used, were found on the BinOCT

<footnote n="7">7 https://github.com/SiccoVerwer/binoct</footnote>

<footnote n="8">8 https://bitbucket.org/helene_verhaeghe/classificationtree</footnote>

<footnote n="9">9 https://github.com/xiyanghu/OSDT</footnote>

<footnote n="10">10 https://github.com/aglingael/dl8.5</footnote>
<table><thead><tr><th>Dataset</th><th>CART</th><th>BinOCT<sup>1</sup></th><th>BinOCT<sup>2</sup></th><th>[32]</th><th>DL8.5</th><th>OSDT</th><th>CPTree-1</th><th>CPTree-1*</th><th>CPTree-2</th></tr></thead><tbody><tr><td>Balance</td><td>61.15</td><td>63.06</td><td>65.35</td><td>N/A</td><td>65.35</td><td>N/A</td><td>65.35</td><td>66.50</td><td>66.62</td></tr><tr><td>Bank. A.</td><td>86.30</td><td>88.28</td><td>91.31</td><td>89.21</td><td>88.28</td><td>87.07</td><td>88.28</td><td>87.46</td><td>90.38</td></tr><tr><td>Biodeg</td><td>75.53</td><td>75.98</td><td>77.05</td><td>76.52</td><td>75.99</td><td>76.67</td><td>75.76</td><td>76.67</td><td>69.32</td></tr><tr><td>Car</td><td>77.13</td><td>77.13</td><td>77.13</td><td>N/A</td><td>77.13</td><td>N/A</td><td>77.13</td><td>77.13</td><td>72.08</td></tr><tr><td>Credit A.</td><td>85.37</td><td>84.27</td><td>84.63</td><td>85.37</td><td>84.03</td><td>85.37</td><td>84.27</td><td>85.61</td><td>74.27</td></tr><tr><td>Hepatitis</td><td>78.97</td><td>83.59</td><td>83.08</td><td>83.08</td><td>83.08</td><td>80.51</td><td>84.10</td><td>86.67</td><td>82.05</td></tr><tr><td>Ionosphere</td><td>78.64</td><td>81.82</td><td>88.86</td><td>81.82</td><td>81.82</td><td>78.18</td><td>82.27</td><td>80.45</td><td>89.55</td></tr><tr><td>Iris</td><td>93.68</td><td>93.68</td><td>90.53</td><td>N/A</td><td>94.21</td><td>N/A</td><td>93.68</td><td>93.68</td><td>92.11</td></tr><tr><td>Mam. M.</td><td>82.12</td><td>82.40</td><td>83.85</td><td>82.40</td><td>82.40</td><td>82.21</td><td>82.40</td><td>82.60</td><td>82.12</td></tr><tr><td>Monk1</td><td>76.83</td><td>75.02</td><td>75.02</td><td>74.55</td><td>75.02</td><td>74.59</td><td>75.97</td><td>75.54</td><td>75.97</td></tr><tr><td>Monk2</td><td>65.56</td><td>64.30</td><td>64.30</td><td>60.65</td><td>64.58</td><td>65.88</td><td>65.56</td><td>65.56</td><td>65.56</td></tr><tr><td>Monk3</td><td>95.83</td><td>95.70</td><td>95.70</td><td>95.96</td><td>95.70</td><td>95.70</td><td>95.83</td><td>95.83</td><td>95.83</td></tr><tr><td>Pima</td><td>74.58</td><td>74.58</td><td>74.38</td><td>74.58</td><td>74.58</td><td>73.75</td><td>74.58</td><td>74.58</td><td>73.02</td></tr><tr><td>Post O.</td><td>73.64</td><td>73.64</td><td>73.64</td><td>N/A</td><td>70.91</td><td>N/A</td><td>65.45</td><td>66.36</td><td>67.27</td></tr><tr><td>Seismic</td><td>93.44</td><td>93.34</td><td>93.10</td><td>93.03</td><td>93.34</td><td>93.44</td><td>93.34</td><td>93.34</td><td>93.19</td></tr><tr><td>Spambase</td><td>77.98</td><td>77.65</td><td>85.14</td><td>77.65</td><td>77.65</td><td>77.98</td><td>77.65</td><td>77.98</td><td>T/O</td></tr><tr><td>Spect H.</td><td>76.42</td><td>77.51</td><td>77.51</td><td>71.12</td><td>77.50</td><td>77.51</td><td>76.42</td><td>76.42</td><td>76.42</td></tr><tr><td>Thoracy S.</td><td>83.22</td><td>83.73</td><td>82.37</td><td>83.90</td><td>83.90</td><td>83.90</td><td>83.90</td><td>83.56</td><td>83.05</td></tr><tr><td>Tic T. T.</td><td>68.92</td><td>67.50</td><td>67.50</td><td>67.33</td><td>67.50</td><td>68.58</td><td>67.50</td><td>68.00</td><td>68.67</td></tr><tr><td>Wine</td><td>88.89</td><td>91.56</td><td>93.33</td><td>N/A</td><td>91.55</td><td>N/A</td><td>91.56</td><td>89.78</td><td>92.00</td></tr></tbody></table>

(a) Average test accuracy with maximum depth 2 over 5 repetitions.

<table><tbody><tr><td>Balance</td><td>66.75</td><td>68.15</td><td>68.79</td><td>N/A</td><td>69.94</td><td>N/A</td><td>69.68</td><td>69.68</td><td>64.33</td></tr><tr><td>Bank. A.</td><td>86.30</td><td>92.54</td><td>96.15</td><td>94.46</td><td>92.54</td><td>92.30</td><td>92.59</td><td>90.50</td><td>92.13</td></tr><tr><td>Biodeg</td><td>76.67</td><td>78.41</td><td>78.33</td><td>82.58</td><td>80.08</td><td>80.53</td><td>79.09</td><td>80.30</td><td>66.67</td></tr><tr><td>Car</td><td>78.89</td><td>80.0</td><td>80.00</td><td>N/A</td><td>79.82</td><td>N/A</td><td>79.81</td><td>79.81</td><td>T/O</td></tr><tr><td>Credit</td><td>84.39</td><td>85.12</td><td>85.49</td><td>87.20</td><td>85.74</td><td>85.61</td><td>85.98</td><td>86.10</td><td>76.52</td></tr><tr><td>Hepatitis</td><td>79.49</td><td>81.03</td><td>80.51</td><td>82.05</td><td>81.54</td><td>80.51</td><td>81.03</td><td>81.03</td><td>82.56</td></tr><tr><td>Ionosphere</td><td>81.14</td><td>85.45</td><td>87.05</td><td>89.32</td><td>88.64</td><td>80.91</td><td>86.36</td><td>86.82</td><td>80.91</td></tr><tr><td>Iris</td><td>93.16</td><td>94.21</td><td>92.11</td><td>N/A</td><td>93.68</td><td>N/A</td><td>95.26</td><td>93.68</td><td>96.32</td></tr><tr><td>Mammo.</td><td>82.98</td><td>83.56</td><td>83.46</td><td>83.56</td><td>83.46</td><td>83.75</td><td>83.37</td><td>83.65</td><td>80.29</td></tr><tr><td>Monk1</td><td>80.43</td><td>86.27</td><td>86.27</td><td>86.70</td><td>86.27</td><td>85.16</td><td>85.18</td><td>80.86</td><td>82.45</td></tr><tr><td>Monk2</td><td>63.71</td><td>58.92</td><td>57.59</td><td>59.08</td><td>59.31</td><td>63.89</td><td>57.75</td><td>61.46</td><td>63.44</td></tr><tr><td>Monk3</td><td>98.42</td><td>99.14</td><td>99.14</td><td>99.28</td><td>96.36</td><td>98.58</td><td>98.99</td><td>98.99</td><td>97.41</td></tr><tr><td>Pima</td><td>73.96</td><td>72.71</td><td>73.65</td><td>70.52</td><td>70.52</td><td>73.75</td><td>70.62</td><td>73.02</td><td>71.48</td></tr><tr><td>Post O.</td><td>72.73</td><td>69.09</td><td>69.09</td><td>N/A</td><td>66.36</td><td>N/A</td><td>59.09</td><td>62.73</td><td>61.82</td></tr><tr><td>Seismic</td><td>93.44</td><td>93.28</td><td>93.13</td><td>93.28</td><td>93.19</td><td>93.44</td><td>93.22</td><td>93.19</td><td>93.34</td></tr><tr><td>Spambase</td><td>83.25</td><td>83.35</td><td>84.36</td><td>83.75</td><td>83.76</td><td>83.84</td><td>83.75</td><td>83.75</td><td>T/O</td></tr><tr><td>Spect H.</td><td>75.82</td><td>76.86</td><td>76.86</td><td>74.62</td><td>77.67</td><td>77.51</td><td>78.51</td><td>79.10</td><td>77.91</td></tr><tr><td>Thoracy S.</td><td>82.54</td><td>82.54</td><td>81.86</td><td>81.86</td><td>80.85</td><td>83.39</td><td>81.53</td><td>82.54</td><td>83.73</td></tr><tr><td>Tic T. T.</td><td>72.83</td><td>72.00</td><td>71.75</td><td>73.17</td><td>73.33</td><td>73.67</td><td>73.17</td><td>74.25</td><td>T/O</td></tr><tr><td>Wine</td><td>87.56</td><td>92.00</td><td>90.22</td><td>N/A</td><td>92.44</td><td>N/A</td><td>90.22</td><td>93.33</td><td>94.22</td></tr></tbody></table>

(b) Average test accuracy with maximum depth 3 over 5 repetitions.

<table><tbody><tr><td>Balance</td><td>65.48</td><td>72.61</td><td>71.08</td><td>N/A</td><td>72.49</td><td>N/A</td><td>72.61</td><td>71.46</td><td>61.31</td></tr><tr><td>Bank.</td><td>92.36</td><td>93.94</td><td>97.26</td><td>95.63</td><td>94.58</td><td>92.77</td><td>94.46</td><td>93.76</td><td>93.41</td></tr><tr><td>Biodeg</td><td>77.42</td><td>78.79</td><td>79.09</td><td>81.06</td><td>80.38</td><td>78.56</td><td>78.26</td><td>79.17</td><td>T/O</td></tr><tr><td>Car</td><td>79.44</td><td>82.59</td><td>83.29</td><td>N/A</td><td>82.82</td><td>N/A</td><td>82.18</td><td>82.36</td><td>T/O</td></tr><tr><td>Credit A.</td><td>85.85</td><td>85.49</td><td>84.63</td><td>84.76</td><td>85.25</td><td>85.61</td><td>84.76</td><td>85.73</td><td>T/O</td></tr><tr><td>Hepatitis</td><td>78.97</td><td>74.87</td><td>82.56</td><td>78.46</td><td>78.46</td><td>76.92</td><td>82.56</td><td>83.08</td><td>82.05</td></tr><tr><td>Ionosphere</td><td>87.27</td><td>85.45</td><td>88.18</td><td>84.32</td><td>84.32</td><td>86.36</td><td>86.59</td><td>85.91</td><td>89.77</td></tr><tr><td>Iris</td><td>93.16</td><td>93.68</td><td>95.26</td><td>N/A</td><td>93.68</td><td>N/A</td><td>95.26</td><td>94.21</td><td>95.79</td></tr><tr><td>Mammo.</td><td>82.79</td><td>83.17</td><td>82.31</td><td>82.60</td><td>82.60</td><td>83.46</td><td>81.92</td><td>84.13</td><td>83.17</td></tr><tr><td>Monk1</td><td>82.88</td><td>100.00</td><td>100.00</td><td>100.00</td><td>100.00</td><td>100.00</td><td>100.00</td><td>100.00</td><td>81.58</td></tr><tr><td>Monk2</td><td>65.03</td><td>60.35</td><td>59.11</td><td>60.59</td><td>60.13</td><td>64.02</td><td>56.82</td><td>62.78</td><td>63.25</td></tr><tr><td>Monk3</td><td>98.99</td><td>97.47</td><td>97.47</td><td>96.19</td><td>97.28</td><td>98.58</td><td>98.56</td><td>98.99</td><td>96.83</td></tr><tr><td>Pima</td><td>71.88</td><td>71.77</td><td>71.25</td><td>69.27</td><td>70.52</td><td>72.92</td><td>69.38</td><td>72.08</td><td>74.35</td></tr><tr><td>Post O.</td><td>65.45</td><td>60.91</td><td>60.91</td><td>N/A</td><td>65.45</td><td>N/A</td><td>56.36</td><td>63.64</td><td>60.91</td></tr><tr><td>Seismic</td><td>93.44</td><td>93.13</td><td>92.94</td><td>93.13</td><td>93.06</td><td>93.44</td><td>93.07</td><td>93.16</td><td>93.30</td></tr><tr><td>Spambase</td><td>83.79</td><td>83.28</td><td>83.37</td><td>84.40</td><td>84.40</td><td>81.06</td><td>83.54</td><td>83.72</td><td>T/O</td></tr><tr><td>Spect H.</td><td>77.31</td><td>75.86</td><td>75.56</td><td>74.37</td><td>76.73</td><td>77.51</td><td>74.93</td><td>77.91</td><td>75.75</td></tr><tr><td>Thoracy S.</td><td>81.86</td><td>83.22</td><td>82.20</td><td>80.68</td><td>80.17</td><td>84.24</td><td>81.02</td><td>81.86</td><td>84.18</td></tr><tr><td>Tic T. T.</td><td>81.75</td><td>78.42</td><td>78.92</td><td>80.83</td><td>81.25</td><td>77.92</td><td>80.33</td><td>77.08</td><td>T/O</td></tr><tr><td>Wine</td><td>92.00</td><td>92.89</td><td>89.33</td><td>N/A</td><td>89.33</td><td>N/A</td><td>88.44</td><td>92.89</td><td>92.89</td></tr></tbody></table>

(c) Average test accuracy with maximum depth 4 over 5 repetitions.

<caption>Table 7: Test accuracy for several maximum depths. N/A means that the method cannot do multiclass classification. T/O means that no solution was found within the time limit (600s).</caption>
<table><thead><tr><th>Dataset</th><th>CART</th><th>BinOCT<sup>1</sup></th><th>BinOCT<sup>2</sup></th><th>[32]</th><th>DL8.5</th><th>OSDT</th><th>CPTree-1</th><th>CPTree-1*</th><th>CPTree-2</th></tr></thead><tbody><tr><td>Balance</td><td>65.64</td><td>69.87</td><td>69.10</td><td>N/A</td><td>69.10</td><td>N/A</td><td>69.10</td><td>68.72</td><td>68.68</td></tr><tr><td>Bank.</td><td>87.27</td><td>88.80</td><td>92.93</td><td>88.34</td><td>88.80</td><td>87.77</td><td>88.80</td><td>87.81</td><td>92.30</td></tr><tr><td>Biodeg</td><td>78.66</td><td>79.32</td><td>80.43</td><td>79.27</td><td>79.32</td><td>79.24</td><td>79.32</td><td>79.24</td><td>70.47</td></tr><tr><td>Car</td><td>77.99</td><td>77.99</td><td>77.99</td><td>N/A</td><td>77.99</td><td>N/A</td><td>77.99</td><td>77.99</td><td>71.40</td></tr><tr><td>Credit A.</td><td>86.95</td><td>87.28</td><td>87.53</td><td>86.71</td><td>87.28</td><td>86.71</td><td>87.28</td><td>87.03</td><td>75.01</td></tr><tr><td>Hepatitis</td><td>82.76</td><td>86.21</td><td>89.83</td><td>86.21</td><td>86.21</td><td>80.69</td><td>86.21</td><td>85.17</td><td>89.66</td></tr><tr><td>Ionosphere</td><td>80.99</td><td>86.01</td><td>91.94</td><td>86.01</td><td>86.01</td><td>83.88</td><td>86.01</td><td>85.32</td><td>90.42</td></tr><tr><td>Iris</td><td>95.18</td><td>95.54</td><td>92.86</td><td>N/A</td><td>95.54</td><td>N/A</td><td>95.54</td><td>95.18</td><td>93.93</td></tr><tr><td>Mammo.</td><td>83.18</td><td>84.08</td><td>84.66</td><td>84.08</td><td>84.08</td><td>83.47</td><td>84.08</td><td>83.89</td><td>84.12</td></tr><tr><td>Monk1</td><td>73.91</td><td>78.99</td><td>78.99</td><td>81.62</td><td>79.00</td><td>78.32</td><td>78.13</td><td>77.46</td><td>78.13</td></tr><tr><td>Monk2</td><td>65.78</td><td>65.88</td><td>65.88</td><td>76.80</td><td>65.88</td><td>65.05</td><td>65.78</td><td>65.78</td><td>65.78</td></tr><tr><td>Monk3</td><td>96.58</td><td>96.09</td><td>96.09</td><td>96.42</td><td>96.09</td><td>96.09</td><td>96.58</td><td>96.58</td><td>96.58</td></tr><tr><td>Pima</td><td>76.70</td><td>76.70</td><td>78.68</td><td>76.70</td><td>76.70</td><td>76.32</td><td>76.70</td><td>76.70</td><td>78.23</td></tr><tr><td>Post O.</td><td>72.62</td><td>75.38</td><td>75.38</td><td>N/A</td><td>80.00</td><td>N/A</td><td>75.38</td><td>73.85</td><td>75.38</td></tr><tr><td>Seismic</td><td>93.42</td><td>93.43</td><td>93.68</td><td>93.45</td><td>93.43</td><td>93.42</td><td>93.43</td><td>93.43</td><td>93.61</td></tr><tr><td>Spambase</td><td>78.67</td><td>78.99</td><td>85.43</td><td>78.99</td><td>78.99</td><td>78.67</td><td>78.99</td><td>78.67</td><td>T/O</td></tr><tr><td>Spect H.</td><td>80.00</td><td>79.35</td><td>79.35</td><td>85.12</td><td>79.35</td><td>79.35</td><td>80.00</td><td>80.00</td><td>80.00</td></tr><tr><td>Thoracy S.</td><td>86.08</td><td>86.48</td><td>86.82</td><td>86.48</td><td>86.48</td><td>85.85</td><td>86.48</td><td>86.14</td><td>86.42</td></tr><tr><td>Tic T. T.</td><td>70.75</td><td>71.23</td><td>71.23</td><td>71.23</td><td>71.23</td><td>70.81</td><td>71.23</td><td>71.17</td><td>69.67</td></tr><tr><td>Wine</td><td>93.08</td><td>93.83</td><td>97.29</td><td>N/A</td><td>93.83</td><td>N/A</td><td>93.83</td><td>93.53</td><td>96.99</td></tr></tbody></table>

(a) Average train accuracy with maximum depth 2 over 5 repetitions.

<table><tbody><tr><td>Balance</td><td>70.34</td><td>75.00</td><td>74.87</td><td>N/A</td><td>75.00</td><td>N/A</td><td>75.09</td><td>73.80</td><td>66.32</td></tr><tr><td>Bank.</td><td>87.27</td><td>93.37</td><td>97.26</td><td>92.61</td><td>93.37</td><td>93.00</td><td>93.37</td><td>92.23</td><td>93.22</td></tr><tr><td>Biodeg</td><td>79.87</td><td>82.23</td><td>83.34</td><td>83.06</td><td>83.54</td><td>82.23</td><td>83.16</td><td>82.78</td><td>68.27</td></tr><tr><td>Car</td><td>79.63</td><td>81.20</td><td>81.20</td><td>N/A</td><td>81.57</td><td>N/A</td><td>81.57</td><td>81.57</td><td>T/O</td></tr><tr><td>Credit A.</td><td>87.28</td><td>88.71</td><td>88.63</td><td>89.16</td><td>89.57</td><td>86.99</td><td>89.57</td><td>88.63</td><td>78.53</td></tr><tr><td>Hepatitis</td><td>87.07</td><td>91.03</td><td>93.28</td><td>91.55</td><td>91.38</td><td>81.38</td><td>91.55</td><td>88.10</td><td>90.86</td></tr><tr><td>Ionosphere</td><td>85.40</td><td>92.02</td><td>93.92</td><td>93.16</td><td>93.08</td><td>85.32</td><td>92.17</td><td>90.57</td><td>86.84</td></tr><tr><td>Iris</td><td>95.54</td><td>98.39</td><td>99.64</td><td>N/A</td><td>98.22</td><td>N/A</td><td>98.39</td><td>96.79</td><td>98.75</td></tr><tr><td>Mammo.</td><td>84.50</td><td>85.14</td><td>85.34</td><td>85.31</td><td>85.27</td><td>83.92</td><td>85.31</td><td>84.57</td><td>78.91</td></tr><tr><td>Monk1</td><td>77.84</td><td>90.71</td><td>90.71</td><td>91.86</td><td>90.72</td><td>90.55</td><td>90.46</td><td>85.28</td><td>83.65</td></tr><tr><td>Monk2</td><td>66.09</td><td>69.71</td><td>69.76</td><td>73.59</td><td>69.71</td><td>65.63</td><td>68.62</td><td>67.47</td><td>66.71</td></tr><tr><td>Monk3</td><td>98.41</td><td>98.15</td><td>98.15</td><td>98.22</td><td>98.15</td><td>97.82</td><td>98.89</td><td>98.89</td><td>98.07</td></tr><tr><td>Pima</td><td>76.77</td><td>77.78</td><td>80.69</td><td>78.33</td><td>78.33</td><td>76.32</td><td>78.33</td><td>77.74</td><td>78.78</td></tr><tr><td>Post O.</td><td>75.38</td><td>81.85</td><td>81.85</td><td>N/A</td><td>84.92</td><td>N/A</td><td>82.15</td><td>77.54</td><td>77.54</td></tr><tr><td>Seismic</td><td>93.42</td><td>93.47</td><td>93.80</td><td>93.47</td><td>93.47</td><td>93.42</td><td>93.47</td><td>93.47</td><td>93.53</td></tr><tr><td>Spambase</td><td>84.08</td><td>83.86</td><td>84.61</td><td>84.22</td><td>84.22</td><td>84.22</td><td>84.22</td><td>84.22</td><td>T/O</td></tr><tr><td>Spect H.</td><td>81.00</td><td>82.25</td><td>82.25</td><td>84.29</td><td>82.00</td><td>79.35</td><td>82.20</td><td>82.10</td><td>81.90</td></tr><tr><td>Thoracy S.</td><td>86.76</td><td>87.44</td><td>87.90</td><td>88.12</td><td>88.01</td><td>86.02</td><td>88.12</td><td>86.82</td><td>86.31</td></tr><tr><td>Tic T. T.</td><td>75.96</td><td>77.30</td><td>77.19</td><td>78.80</td><td>78.50</td><td>76.77</td><td>78.77</td><td>76.96</td><td>T/O</td></tr><tr><td>Wine</td><td>95.19</td><td>97.89</td><td>99.85</td><td>N/A</td><td>97.89</td><td>N/A</td><td>97.89</td><td>96.39</td><td>99.40</td></tr></tbody></table>

(b) Average train accuracy with maximum depth 3 over 5 repetitions.

<table><tbody><tr><td>Balance</td><td>72.01</td><td>78.21</td><td>77.95</td><td>N/A</td><td>79.06</td><td>N/A</td><td>78.93</td><td>76.79</td><td>61.75</td></tr><tr><td>Bank.</td><td>93.26</td><td>94.52</td><td>98.10</td><td>94.27</td><td>94.83</td><td>93.59</td><td>94.83</td><td>94.36</td><td>94.50</td></tr><tr><td>Biodeg</td><td>83.08</td><td>83.84</td><td>83.69</td><td>86.60</td><td>86.78</td><td>81.95</td><td>82.76</td><td>83.19</td><td>T/O</td></tr><tr><td>Car</td><td>80.19</td><td>83.63</td><td>83.53</td><td>N/A</td><td>84.55</td><td>N/A</td><td>83.89</td><td>83.80</td><td>T/O</td></tr><tr><td>Credit A.</td><td>89.98</td><td>89.61</td><td>89.08</td><td>91.41</td><td>91.74</td><td>88.02</td><td>90.67</td><td>89.53</td><td>T/O</td></tr><tr><td>Hepatitis</td><td>90.00</td><td>94.83</td><td>97.41</td><td>97.76</td><td>97.76</td><td>84.48</td><td>97.59</td><td>90.00</td><td>91.38</td></tr><tr><td>Ionosphere</td><td>90.11</td><td>94.52</td><td>95.59</td><td>97.26</td><td>97.26</td><td>89.05</td><td>95.59</td><td>92.02</td><td>91.33</td></tr><tr><td>Iris</td><td>97.50</td><td>98.39</td><td>100.00</td><td>N/A</td><td>98.39</td><td>N/A</td><td>98.39</td><td>97.68</td><td>97.68</td></tr><tr><td>Mammo.</td><td>85.14</td><td>85.92</td><td>86.11</td><td>86.43</td><td>86.40</td><td>84.21</td><td>86.21</td><td>85.24</td><td>81.94</td></tr><tr><td>Monk1</td><td>83.69</td><td>100.00</td><td>100.00</td><td>100.00</td><td>100.00</td><td>100.00</td><td>100.00</td><td>100.00</td><td>81.97</td></tr><tr><td>Monk2</td><td>68.53</td><td>73.93</td><td>73.83</td><td>77.78</td><td>74.51</td><td>69.40</td><td>72.22</td><td>70.13</td><td>66.89</td></tr><tr><td>Monk3</td><td>98.89</td><td>98.48</td><td>98.48</td><td>98.92</td><td>98.81</td><td>97.82</td><td>98.94</td><td>98.89</td><td>96.92</td></tr><tr><td>Pima</td><td>78.44</td><td>79.79</td><td>80.87</td><td>81.11</td><td>80.97</td><td>77.22</td><td>79.90</td><td>79.06</td><td>77.82</td></tr><tr><td>Post O.</td><td>77.85</td><td>86.46</td><td>86.77</td><td>N/A</td><td>91.69</td><td>N/A</td><td>90.46</td><td>79.08</td><td>78.77</td></tr><tr><td>Seismic</td><td>93.42</td><td>93.52</td><td>93.89</td><td>93.57</td><td>93.57</td><td>93.42</td><td>93.56</td><td>93.51</td><td>93.50</td></tr><tr><td>Spambase</td><td>84.60</td><td>84.84</td><td>84.01</td><td>85.50</td><td>85.50</td><td>81.88</td><td>84.57</td><td>84.52</td><td>T/O</td></tr><tr><td>Spect H.</td><td>82.90</td><td>85.95</td><td>85.95</td><td>88.54</td><td>86.95</td><td>79.35</td><td>86.90</td><td>84.60</td><td>82.25</td></tr><tr><td>Thoracy S.</td><td>88.01</td><td>88.81</td><td>88.86</td><td>90.28</td><td>90.17</td><td>85.51</td><td>89.77</td><td>88.12</td><td>86.08</td></tr><tr><td>Tic T. T.</td><td>83.62</td><td>83.82</td><td>83.87</td><td>87.05</td><td>86.69</td><td>81.78</td><td>84.43</td><td>80.84</td><td>T/O</td></tr><tr><td>Wine</td><td>98.80</td><td>99.10</td><td>100.00</td><td>N/A</td><td>100.00</td><td>N/A</td><td>100.00</td><td>97.44</td><td>98.80</td></tr></tbody></table>

(c) Average train accuracy with maximum depth 4 over 5 repetitions.

<caption>Table 8: Train accuracy obtained for several maximum depths. N/A means that the method cannot do multiclass classification. T/O means that no solution was found within the time limit (600s).</caption>
repository⁷, were already preprocessed. In order to extend preproprecessing for other datasets, we had to preprocess the datasets, which may explain little differences with published performances (e.g., slightly different accuracy) on a few datasets. Additionally, the small differences with published performances may also be explained by the division, which does not match exactly the one done in the papers. For methods that require binary features (DL8.5, OSDT, Verhaeghe et al. [32] and our first model), datasets are preprocessed by transforming numeric features into (3 bins using the quantile discretiser from Scikit-learn<fnref n="11" />) categorical ones and then transforming all categorical features into binary features through one-hot-encoding.

Datasets have been divided into 3 sets: training (50%), validation (25%), and testing (25%). BinOCT, DL8.5 and Verhaeghe et al. [32] do not have any additional hyperparameters nor the number of leaves to tune. We ran these models directly on training plus validation sets. Since BinOCT has an intrinsic heuristic to binarise numeric features, we keep datasets with their numeric features for experiments with BinOCT. This gives two versions of BinOCT (BinOCT¹ for only binary features and BinOCT² with numeric features). Other methods only work with binary features according to their released code. In the experiments, we also include CART [16] from Scikit-learn using the entropy as a heuristic.

OSDT and CPTree require cross-validation to select hyperparameters $\lambda$ and $L$, respectively. Therefore, $\lambda$ has been selected after validation according to the default range of values provided by Hu et al. [29]. The number of leaves $L$ of our model CPTrees has also been validated considering values from $3(K - 1)$ to $2^K$, where $K$ is the maximum depth. Once tuning is done, we ran OSDT and our model on training plus validation sets, according to the best $\lambda$ and $L$, respectively. Since our model is more general than [9], we made three versions of CPTrees. CPTree-1 and CPTree-1* come from the first formulation and are respectively the model for complete tree structures ($L = 2^K$ as BinOCT) and the model for which the number of leaves has been validated. Second, CPTree-2

<footnote n="11">¹¹We used KBinsDiscretizer from the preprocessing package.</footnote>
430 is the third model related to the second formulation (i.e., with numeric features) detailed in Appendix A.1.

To be fair, all models ran without a warm start such as CART. No additional constraint has been added since the goal of this section is to assess the ability of our method to produce decision trees that achieve similar accuracy to those obtained by state-of-the-art methods described in Section 2.

Since our first formulation uses linear constraints and binary variables, it can be implemented into CP or MIP solvers. We used the CP-SAT solver of the Google OR-Tools library [48], which is freely available in Python. For our second formulation, we used the MIP solver of Gurobi [49].

Based on the work of BinOCT [9], we set to 10 minutes the time limit for each run of all the methods. Experiments have been conducted on 5 independent runs by dataset, by depth (the maximal depth was set to 2, 3, and 4) also according to [9]. We ran them sequentially (to be fair with all methods) on a server with a Common KVM processor (2.294 GHz) and 16GB of RAM. Running completely all the evaluations took more than 2 weeks<fnref n="12" /> of extensive computations.

The code for CPTrees is available<fnref n="13" /> and learned trees can be inspected and visualised as in Scikit-learn. All scripts that we used to benchmark all these recent models are also available for future reproducibility.

## 6.2. How do CPTrees Perform Comparatively to BinOCT, OSDT and DL8.5?

Our benchmarking procedure aims to evaluate the generalisation of optimal decision tree models rather than how close they are to optimal solutions. Therefore, Table 7a, 7b and 7c present the average test accuracy (on depth 2, 3 and 4, respectively) over 5 independent runs as detailed in Section 6.1. Similarly, Table 8 shows the average training accuracy. Here, the training accuracy of optimal methods differs because, as a reminder, in accordance with Verwer and Zhang [9], all runs were done within the time limit of 10 minutes. Figure 7a, Figure 7b

<footnote n="12">¹²The total number of runs is ≈ 20(datasets) × 3(deepths) × 8(model) × 5(runs) = 2400.</footnote>

<footnote n="13">¹³https://github.com/gerald4/CPTree</footnote>
<figure><img src="image_7.png" /><figcaption>Figure 7: Nemenyi statistical significance test. From left to right, algorithms are ranked from best to worst. The bold horizontal line indicates no significant difference between algorithms.</figcaption></figure>

and Figure 7c show results of the Nemenyi statistical significant test, which is a non-parametric test that compares algorithms pairwise of their performance. Figure 7 shows that none of the compared methods outperforms the others, in terms of generalisation, according to the Nemenyi test. This is confirmed by the analysis of Table 7, which shows predictive performance. In terms of test accuracy, Table 7 shows that OSDT and CPTree-1* are usually close to each other, which is not surprising since they both are branch-like models. In terms of train accuracy, Table 8 shows that CPTrees are similar to state-of-the-art learners that are designed to find optimal decision trees.

It is also worth noting that, CPTree-2 is the only model (with CART) in Table 7 and Table 8, which does not involve preprocessing or heuristic discretisation of features. It is usually slow to reach an optimal solution, in particular for datasets with categorical features. This is due to the existence of multiple choices of splits that give the same semantic explanation. However, for pure numeric features (e.g., *Bank.*, *Ionosphere*, *Iris*, *Pima*, etc.), it usually provides good results, making it especially suitable for enforcing domain constraints in cases where datasets present numeric features.

Overall, CPTree-1, CPTree-1*, and CPTree-2 generally have similar perfor-
<figure><img src="image_8.png" /><figcaption>Figure 8: Accuracy curve within 3 hours of optimisation.</figcaption></figure>

mances. They perform sometimes better (or worse) than state-of-the-art methods, but overall, there is no significant difference, according to the Nemenyi statistical tests. However, the particularity of CPTrees is to be as flexible as possible to incorporate a broad class of domain constraints as in Section 5.

## 7. Computational Time

This section examines how much computational time does CPTree requires to find a good decision tree that generalises well. We ran additional experiments on three datasets with maximum depths ($K = 3, 4; L = 2 * K$) and a time limit of 3 hours to explore more feasible space. We implemented a *callback* to keep track of both the training and testing accuracy during optimisation.

Figure 8 shows results obtained along optimisation path. At the first glance, it appears that predictive accuracy saturates and sometimes decreases after a reasonable amount of time. This confirms that we can avoid increasing the time limit. More specifically, at depth 3, Figure 8a shows that for *Pima Indian diabetes* and *Mammographic masses*, the time required to learn a good CPTree is less than $10^3$ s. This time is slightly higher for *Ionosphere*. On the other
hand, at depth 4, from Figure 8b, this time is less than or around $6 \times 10^3$ s. For *Ionosphere* (maximum depth 3) and *Mammographic masses* (maximum depth 4), the occasional drop in predictive accuracy is due to the oversearching problem, a well-known issue for optimal searching methods [50]. This question needs further investigation, especially on tree learners and we leave it for future work.

In brief, our finding from this optimisation time/path analysis is that it is not necessary to reach optimality with CPTree since this may harm predictive performance without any strategies to counter overfitting from oversearching.

## 8. Conclusion

This paper introduces a tree representation that leads to two new formulations to enforce domain-knowledge constraints on decision trees. With these formulations, we are able to enforce a broader family of constraints compared to recently proposed methods. These constraints include but are not limited to the number of leaf nodes, the maximum depth, domain-knowledge constraints like the ordering of features on a branch of the tree or costs on features, or even regarding fairness. These formulations provide a flexible framework in which several constraints both regarding the complexity and domain knowledge can be easily formulated seeking to learn more interpretable and trustworthy trees. The learned CPTrees ensure that the constraints are satisfied while keeping the same level of accuracy with baselines. However, users should also make sure, when adding constraints, that the optimisation problem has feasible solutions. Otherwise, the problem may not have a feasible solution simply because it is overconstrained. Finally, future work includes more experiments to validate interpretability's improvement directly with users or domain experts.

*Acknowledgement.* This work has been funded by the EOS-VeriLearn, project number 30992574 of the Fonds de la Recherche Scientifique (F.R.S-FNRS) in Belgium. The authors also thank the medical Doctor Drem's Tailor Fomekong for domain knowledge, Prof. Hendrik Blockeel, Prof. Sebastijan Dumancic, and Kshitij Goyal for their useful comments that helped to improve the framework.
[1] A. A. Freitas, Comprehensible classification models: A position paper, SIGKDD Explorations Newsletter 15 (2014) 1–10.

[2] H. K. Sok, M. P.-L. Ooi, Y. C. Kuang, S. Demidenko, Multivariate alternating decision trees, Pattern Recognition 50 (2016) 195–209.

[3] L. Ma, S. Destercke, Y. Wang, Online active learning of decision trees with evidential data, Pattern Recognition 52 (2016) 33–45.

[4] J. Y. Verbakel, M. B. Lemiengre, T. De Burghgraeve, A. De Sutter, B. Aertgeerts, D. M. Bullens, B. Shinkins, A. Van den Bruel, F. Buntinx, Validating a decision tree for serious infection: diagnostic accuracy in acutely ill children in ambulatory care, BMJ open 5 (2015).

[5] S. Y. Sohn, J. W. Kim, Decision tree-based technology credit scoring for start-up firms: Korean case, Expert Systems with Applications 39 (2012) 4007–4012.

[6] L. Floridi, Establishing the rules for building trustworthy ai, Nature Machine Intelligence 1 (2019) 261–262.

[7] A. Cotter, H. Jiang, M. Gupta, S. Wang, T. Narayan, S. You, K. Sridharan, Optimization with non-differentiable constraints with applications to fairness, recall, churn, and other goals, Journal of Machine Learning Research 20 (2019) 1–59.

[8] D. Martens, J. Vanthienen, W. Verbeke, B. Baesens, Performance of classification models from a user perspective, Decision Support Systems 51 (2011) 782–793.

[9] S. Verwer, Y. Zhang, Learning optimal classification trees using a binary linear program formulation, in: 33rd AAAI Conference on Artificial Intelligence, 2019.

[10] D. Bertsimas, J. Dunn, Optimal classification trees, Mach. Learn. 106 (2017) 1039–1082.

[11] N. Narodytska, A. Ignatiev, F. Pereira, J. Marques-Silva, Learning optimal decision trees with sat, in: 27th International Joint Conference on Artificial Intelligence, 2018.

[12] S. Aghaei, M. J. Azizi, P. Vayanos, Learning optimal and fair decision trees for non-discriminative decision-making, in: 33rd AAAI, 2019.

[13] G. K. Dziugaite, S. Ben-David, D. M. Roy, Enforcing interpretability and its statistical impacts: Trade-offs between accuracy and interpretability, ArXiv:2010.13764 (2020).

[14] M. T. Ribeiro, S. Singh, C. Guestrin, Model-agnostic interpretability of machine learning, in: ICML Workshop on Human Interpretability in Machine Learning, 2016.

[15] A. Barredo Arrieta, N. Díaz-Rodríguez, J. Del Ser, A. Bennetot, S. Tabik, A. Barbado, S. Garcia, S. Gil-Lopez, D. Molina, R. Benjamins, R. Chatila, F. Herrera, Explainable artificial intelligence (xai): Concepts, taxonomies, opportunities and challenges toward responsible ai, Information Fusion 58 (2020) 82–115.
[16] L. Breiman, J. Friedman, C. J. Stone, R. Olshen, Classification and Regression Trees, Wadsworth and Brooks, Monterey, CA, 1984.

[17] J. R. Quinlan, C4.5: Programs for Machine Learning, Morgan Kaufmann publishers Inc., San Francisco, CA, USA, 1993.

[18] J. R. Quinlan, R. L. Rivest, Inferring decision trees using the minimum description length principle, Information and Computation 80 (1989) 227-248.

[19] M. Garofalakis, D. Hyun, R. Rastogi, K. Shim, Efficient algorithms for constructing decision trees with constraints, in: 6th KDD, 2000.

[20] P. Niyogi, F. Girosi, T. Poggio, Incorporating prior information in machine learning by creating virtual examples, Proceedings of the IEEE 86 (1998) 2196-2209.

[21] M. Núñez, The use of background knowledge in decision tree induction, Mach. Learn. 6 (1991) 231-250.

[22] J. A. López-Vallverdú, D. Riaño, A. Collado, Increasing acceptability of decision trees with domain attributes partial orders, in: 20th IEEE CBMS, 2007.

[23] J. A. López-Vallverdú, D. Riaño, J. A. Bohada, Improving medical decision trees by combining relevant health-care criteria, Expert Syst. Appl. 39 (2012) 11782-11791.

[24] S. Nijssen, E. Fromont, Optimal constraint-based decision tree induction from itemset lattices, Data Mining and Knowledge Discovevery 21 (2010) 9-51.

[25] M. Garofalakis, D. Hyun, R. Rastogi, K. Shim, Building decision trees with constraints, Data Mining and Knowledge Discovery 7 (2003) 187-214.

[26] S. Nijssen, E. Fromont, Mining optimal decision trees from itemset lattices, in: 13th SIGKDD International Conference on Knowledge Discovery and Data Mining, 2007.

[27] G. Aglin, S. Nijssen, P. Schaus, Learning optimal decision trees using caching branch-and-bound search, in: 34th AAAI Conference on Artificial Intelligence, 2020.

[28] E. Angelino, N. Larus-Stone, D. Alabi, M. Seltzer, C. Rudin, Learning certifiably optimal rule lists for categorical data, Journal of Machine Learning Research 18 (2018) 1-78.

[29] X. Hu, C. Rudin, M. Seltzer, Optimal sparse decision trees, in: Neurips, 2019.

[30] J. Lin, C. Zhong, D. Hu, C. Rudin, M. Seltzer, Generalized and scalable optimal sparse decision trees, in: 37th International Conference on Machine Learning, 2020.

[31] A. Florent, Efficient inference of optimal decision trees, in: 34th AAAI, 2020.

[32] H. Verhaeghe, S. Nijssen, G. Pesant, C.-G. Quimper, P. Schaus, Learning optimal decision trees using constraint programming, in: 25th CP, 2019.

[33] H. Liu, F. Hussain, C. L. Tan, M. Dash, Discretization: An enabling technique, Data mining and knowledge discovery 6 (2002) 393-423.

[34] I. N. M. Shaharanee, F. Hadzic, T. S. Dillon, Interestingness measures for association rules based on statistical validity, Knowledge-Based Systems 24 (2011) 386-392.
[35] J. M. Hodgson, V. H. van Someren, C. Smith, A. Goyale, Direct bilirubin levels observed in prolonged neonatal jaundice: a retrospective cohort study, BMJ Paediatr. open 2 (2018).

[36] K. Wagstaff, C. Cardie, S. Rogers, S. Schrödl, et al., Constrained k-means clustering with background knowledge, in: 18th ICML, 2001.

[37] T. Calders, S. Verwer, Three naive bayes approaches for discrimination-free classification, Data mining and knowledge discovery 21 (2010) 277-292.

[38] T. Calders, F. Kamiran, M. Pechenizkiy, Building classifiers with independency constraints, in: ICDM Workshop on Domain Driven Data Mining, 2009.

[39] M. Lohaus, M. Perrot, U. Von Luxburg, Too relaxed to be fair, in: 37th ICML, 2020.

[40] W. Yang, L. Lorch, M. Graule, H. Lakkaraju, F. Doshi-Velez, Incorporating interpretable output constraints in bayesian neural networks, in: Neurips, 2020.

[41] D. Dua, C. Graff, UCI mach. learn. repo., 2017. URL: http://archive.ics.uci.edu/ml.

[42] M. Tina Binesh, M. Sydney, Toronto Notes for Medical Students: comprehensive medical reference and review for MCCQE and USMLE II, 34th ed ed., Toronto Notes 2018, 2018.

[43] R. Li, R. Daniel, B. Rachet, How much do tumor stage and treatment explain socioeconomic inequalities in breast cancer survival? applying causal mediation analysis to population-based data, European journal of epidemiology 31 (2016) 603-611.

[44] J. W. Smith, J. E. Everhart, W. Dickson, W. C. Knowler, R. S. Johannes, Using the adap learning algorithm to forecast the onset of diabetes mellitus, in: annual symposium on computer application in medical care, American Medical Informatics Association, 1988.

[45] S. H. Read, L. C. Rosella, H. Berger, D. S. Feig, K. Fleming, P. Kaul, J. G. Ray, B. R. Shah, L. L. Lipscombe, Diabetes after pregnancy: a study protocol for the derivation and validation of a risk prediction model for 5-year risk of diabetes following pregnancy, Diagnostic and Prognostic Research 5 (2021) 1-8.

[46] N. K. Wenger, L. Speroff, B. Packard, Cardiovascular health and disease in women, New England Journal of Medicine 329 (1993) 247-256.

[47] V. Okunrintemi, J. Valero-Elizondo, B. Patrick, J. Salami, M. Tibuakuu, S. Ahmad, O. Ogunmoroti, S. Mahajan, S. U. Khan, M. Gulati, et al., Gender differences in patient-reported outcomes among adults with atherosclerotic cardiovascular disease, Journal of the American Heart Association 7 (2018) e010498.

[48] L. Perron, V. Furnon, Google: Or-tools, https://developers.google.com/optimization/, 2019.

[49] G. Optimization, Gurobi optimizer reference manual, http://www.gurobi.com, 2021.

[50] J. Quinlan, R. Cameron-Jones, Oversearching and layered search in empirical learning, in: 14th International Joint Conference on Artificial Intelligence 95, 1995.