# Blossom: an Anytime Algorithm for Computing Optimal Decision Trees

Emir Demirović, Emmanuel Hebrard, Louis Jean

► To cite this version:

Emir Demirović, Emmanuel Hebrard, Louis Jean. Blossom: an Anytime Algorithm for Computing Optimal Decision Trees. International Conference on Machine Learning, Jul 2023, Honolulu, United States. hal-04108022

HAL Id: hal-04108022

https://laas.hal.science/hal-04108022

Submitted on 26 May 2023

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# Blossom: an Anytime Algorithm for Computing Optimal Decision Trees

Emir Demirović *<fnref n="1" /> Emmanuel Hebrard *² Louis Jean *³

## Abstract

We propose a simple algorithm to learn optimal decision trees of bounded depth. This algorithm is essentially an anytime version of the state-of-the-art dynamic programming approach. It has virtually no overhead compared to heuristic methods and is comparable to the best exact methods to prove optimality on most data sets. Experiments show that whereas existing exact methods hardly scale to deep trees, this algorithm learns trees comparable to standard heuristics without computational overhead, and can significantly improve their accuracy when given more computation time, even for deep trees.

## 1. Introduction

In their paper proving that computing decision trees of maximum accuracy is NP-hard, Hyafil and Rivest write: "it is to be expected that good heuristics for constructing near-optimal binary decision trees will be the best solution to this problem in the near future." (Laurent & Rivest, 1976).<fnref n="1" /> Indeed, heuristics such as CART (Breiman et al., 1984), ID3 (Quinlan, 1986) or C4.5 (Quinlan, 1993) have been prevalent long afterward, and are still vastly more commonly used in practice than exact methods. We propose a new algorithm (Blossom) which, while being effective at proving optimality, has no computational nor memory overhead compared to heuristics.

There has been some experiments indicating that optimal trees (for some combination of accuracy, depth and size) generalize better to unseen data (Bertsimas & Dunn, 2017). However, these experiments were of limited scope because of the poor scalability of exact algorithms. Our experiments

confirm a significant gain in test accuracy, for the objective criterion considered in this paper and in (Bertsimas & Dunn, 2017; Bertsimas & Shioda, 2007; Demirović et al., 2022; Hu et al., 2020; Nijssen & Fromont, 2007): maximizing the training accuracy given an upper bound on the depth. Other criteria have been considered. For instance, OSDT (Hu et al., 2019), GOSDT (Lin et al., 2020) optimize a linear combination of accuracy and number of leaves. However maximizing the accuracy under a constrained depth has is easier to tackle algorithmically, and the predictions of shallower trees are easier to explain.

Despite these desirable features, exact methods have not yet been widely adopted because they do not scale. Exact methods made significant progress lately, and the most recent approaches show very promising results. However, no exact method can replace heuristics in all contexts. For SAT (Avellaneda, 2020; Narodytska et al., 2018) and Integer Programming (Aghaei et al., 2020; Bertsimas & Dunn, 2017; Bertsimas & Shioda, 2007; Verwer & Zhang, 2019), the size of the encoding is a first hurdle. These models require a number of variables proportional to the size of the tree and to the number of datapoints and hence scaling beyond a few thousands datapoints is hard. On the other hand, dynamic programming algorithms DL8 (Nijssen & Fromont, 2007) and DL8.5 (Aglin et al., 2020) scale very well to large data sets. Moreover, these algorithms leverage branch independence: sibling subtrees can be optimized independently, which has a significant impact on the computational complexity. However, DL8.5 tends to be memory hungry and is not anytime. The constraint programming approach of Verhaeghe et al. emulates these positive features using propagation algorithms and search strategies (Verhaeghe et al., 2020), while being potentially anytime, although it does not quite match DL8.5's efficiency. Recently, some approaches aiming at improving the anytime aspect have been proposed. For instance, LDS-DL8.5 (Kiossou et al., 2022) uses DL8.5 within a limited discrepancy search method (Harvey & Ginsberg, 1995) thus prioritizing solutions with small deviation from an initial heuristic tree. Similarly to the dynamic programming approaches, the algorithm Murtree (Demirović et al., 2022) optimizes one subtree before moving to the other. However, this choice is dynamic. Moreover, it improves on these approaches in several ways. In particular, it optimizes with respect to

This paper has been published in the Proceedings of the 40th International Conference on Machine Learning, Honolulu, Hawaii, USA. PMLR 202, 2023

<footnote>*Equal contribution
¹TU DELFT, The Netherlands
²LAAS-CNRS, Université de Toulouse, CNRS, France
³Jolibrain, Toulouse, France. Correspondence to: Emir Demirović <e.demirovic@tudelft.nl>, Emmanuel Hebrard <hebrard@laas.fr>, Louis Jean <louis.jean@jolibrain.com>.</footnote>

<footnote n="1">¹Their proof does not consider the exact same problem as in the present paper, however it does apply with trivial changes.</footnote>
combinations of size and accuracy and implements several methods dedicated to exploring the whole search space efficiently: delaying feature frequency count to a specialized algorithm for subtree of depth two, and implementing an efficient recomputation method for the classification error. As a result, both *Murtree* and *LDS-DL8.5* have better anytime behavior than previous exact methods. However, experimental results show that for deeper trees *Blossom* can significantly outperform all of these methods, while being more memory efficient than approaches that rely on caching the results of subtree computation.

In a nutshell, *Blossom* emulates the dynamic programming approach (see Algorithm 1) implemented for instance in DL8 (Nijssen & Fromont, 2007) and DL8.5 (Aglin et al., 2020), while always expanding non-terminal branches (a.k.a “blossoms”) before optimizing grown branches. As a result, this algorithm is in a sense strictly better than both the standard dynamic programming approach (because it is anytime and at least as fast) and than classic heuristics (because it emulates them during search, without significant overhead). Our experiments show that it outperforms the state of the art, to the exception of *Murtree* on relatively shallow trees (typically for depths up to 5), for which its more sophisticated (albeit more complex) algorithmic features can pay off.

## 2. Preliminaries

A data set on a binary feature set $\mathcal{F}$ is a pair $\langle \mathcal{N}, \mathcal{P} \rangle$ where $\mathcal{N}$ and $\mathcal{P}$ are subsets of the feature space $\prod_{f \in \mathcal{F}} \{f, \bar{f}\}$, and are standing, respectively, for negative and positive datapoints, with $\mathcal{D} = \mathcal{N} \cup \mathcal{P}$ being the set containing all datapoints. Given a set of data points $S$ and a feature $f$, $S(f)$ stands for the subset $\{x \mid x \in S, f \in x\}$ and $S(\bar{f})$ stands for the subset $\{x \mid x \in S, \bar{f} \in x\}$.

A *binary decision tree* is a tree whose internal vertices are labelled with features and the two edges exiting a node labelled with $f$ are respectively labelled with the feature $f$ and its negation $\bar{f}$. To a *branch* of a decision tree we associate the ordered set of labels on its edges, from root to leaf. E.g., the leftmost branch in the decision tree of Figure 2 is $(r, a, \bar{h})$. Given a branch $b$, and a set of data points $S$ we write $S(b)$ for $\bigcap_{f \in b} S(f)$ and we write $b \oplus f$ as a shortcut for $b \cup \{f\}$. The classification error for branch $b$ is $error(b) = \min(|\mathcal{N}(b)|, |\mathcal{P}(b)|)$.

Given a binary data set $\langle \mathcal{N}, \mathcal{P} \rangle$ on the features $\mathcal{F}$, the *minimum error bounded depth decision tree problem* consists of finding a binary decision tree with vertex labels in $\mathcal{F}$ whose branches have cardinality at most $k$ and the sum of the classification error of its maximal branches is minimum. We say that a branch $b$ of a tree is *terminal* if and only if its length $|b|$ is $k$ or if $error(b)$ is null, and we say that a

non-terminal branch is a *bud*.

### 2.1. Dynamic Programming Algorithm

The dynamic programming approach for the minimum error bounded depth decision tree problem relies on the independence of the two subproblems under a given feature test. Algorithm 1 gives a simplified view of this idea implemented e.g. in (Nijssen & Fromont, 2007; Aglin et al., 2020; Demirović et al., 2022).

<caption>**Algorithm 1:** Dynamic Programming Algorithm</caption>

**Algorithm:** DP
**Data:** $\mathcal{N}, \mathcal{P}, \mathcal{F}, k$
**Result:** Min. error of $k$-bounded trees on data set $\langle \mathcal{N}, \mathcal{P} \rangle$
    error ← min($|\mathcal{N}|, |\mathcal{P}|$)
    **if** $k > 0$ **and** error > 0 **then**
        **foreach** $f \in \mathcal{F}$ **do**
            error ← min($error, DP(\mathcal{N}(f), \mathcal{P}(f), \mathcal{F} \setminus f, k - 1) + DP(\mathcal{N}(\bar{f}), \mathcal{P}(\bar{f}), \mathcal{F} \setminus f, k - 1)$)
        **return** error

Let $n = |\mathcal{P}| + |\mathcal{N}|$, $m = |\mathcal{F}|$, and let $k$ be the maximum depth. We can safely assume $k \le m$ (otherwise all features can be tested on every branch) and $k \le \log n$ (otherwise we could have one distinct branch per datapoint), and it is often assumed that $k \ll m$ and $k \ll \log n$.

Algorithm 1 explores, in the worst case, $2^k$ branches for each of the number of permutations of $k$ features in $\mathcal{F}$ ($P(m, k) = m!(m-k)!$) for a total of $\Theta(P(m, k)2^k)$ recursive calls. Note that this is a significant improvement with respect to the $\Theta(m^{2^k})$ trees (with redundant branches) explored by a brute-force algorithm.

Moreover, at each call, data points must be split into two subsets. This takes linear time. However, consider an ordered set of $k$ features and the $2^{k-1}$ branches testing these features in that order. Their corresponding data sets form a partition of the original data set. Therefore, the $k$-th split can done in $\Theta(n)$ time amortized over these $2^{k-1}$ splits since each data points is considered only once, in one of these branches. It follows that the overall time complexity for splitting the data set is in $\Theta(P(m, k)n)$.

Algorithm 1 therefore runs in $\Theta((n + 2^k)P(m, k)) \subset O((n + 2^k)m^k)$ time. Moreover, with the above assumptions on $n, m$ and $k$, $O(nm^k)$ is a good approximation of its worst-case time complexity.

## 3. An Anytime Algorithm

Algorithm 2 shows the pseudo-code of an iterative, anytime, version of Algorithm 1 (highlighted code should be ignored for now, it corresponds to improvements detailed
in Section 4). This algorithm explores the same search space as Algorithm 1: the same branch is never explored twice. However, incomplete branches are expanded before trying alternative features for already explored branches. In other words, instead of optimizing the left subtree before exploring the right subtree as in Algorithm 1, Algorithm 2 first fully expands a decision tree before exploring alternatives for any branch. For instance, in Figure 1 DP explores branch (a, c) third, whereas *Blossom* explores ($\bar{a}$, b) third, and (a, c) only in seventh. The first full decision tree has the branches (a, b), (a, $\bar{b}$), ($\bar{a}$, b) and ($\bar{a}$, $\bar{b}$). This is the fourth leave for *Blossom*, but the sixth for DP.

Let $f_i <_b f_j$ if and only if feature $f_i$ is selected before feature $f_j$ when expanding branch $b$ at Line 4. Algorithm 2 has the following invariants, from which a formal proof of correctness easily follows:

* If a branch $b$ has been added to $S$ but is not currently in $S$, then the *optimal* subtree below this branch has been found and $best(b)$ is its classification error.

* If $(b, f) \in S$, then for every feature $f' <_b f$, the optimal subtree of $b$ starting with $f'$ has been found. The set $dom(b)$ contains all *untried* feature tests for branch $b$ ($dom(b) = \{f' | f' \in \mathcal{F} \wedge f <_b f'\}$).

* If $(b, f) \in S$ but neither $b \oplus f$ nor $b \oplus \bar{f}$ are in $S$, $b'$ is terminal, or $b'$ is a *bud* yet to be expanded, and $b' \in B$.

As long as there is a *bud* ($B \neq \emptyset$), we pick any one $b \in B$ at Line 2 and check if it can or need to be expanded in Line 3. If so, we pick a feature $f$ marked as *untried* for $b$, unmark it, expand the tree with the test $f$ at branch $b$. The two children $b \oplus f$ and $b \oplus \bar{f}$ can then be added to $B$.

If there is no *bud* ($B = \emptyset$), then the current tree is complete: every maximal branch $b$ is either terminal or optimal. In that case we pop the last assignment $(b, f)$ from $S$ and update the best error of its subtrees. If there is at least one *untried* feature for branch $b$, we add $b$ to $B$. Otherwise, it is optimal, and $best(b)$ contains the minimum error for any subtree of branch $b$. This branch will never be expanded anymore since it is not added to $B$. When the algorithm ends, $best(\emptyset)$ contains the minimum error of any decision tree of depth $k$.

To simplify the pseudo-code, we use branches to index array-like data structures in Algorithm 2 (e.g. $dom(b)$). Actually, a set of *indices* (at most $2^k$ in the worst case) are used as proxy for branches in all contexts, since the current tree cannot have more than $2^k$ branches. At Line 9, the indices for $b \oplus f$, $b \oplus \bar{f}$ are released, and a free index is marked as used when expanding a branch at Line 5. Moreover, the pseudo-code in Algorithm 2 does not show how the best subtrees of optimal branches are recorded, nor how the overall best error is updated when completing a new decision tree at Line 6.

<caption>**Algorithm 2: Blossom Algorithm**</caption>

**Algorithm:** *Blossom*
**Data:** $\mathcal{N}, \mathcal{P}, k$
**Result:** Min. error of $k$-bounded trees on data set $\langle \mathcal{N}, \mathcal{P} \rangle$
$S \leftarrow \emptyset$
$B \leftarrow \text{GrowBud}(\emptyset, \emptyset)$
**while** $|S| + |B| > 0$ **do**
    if $B \neq \emptyset$ **then**
        pick and remove $b$ from $B$
        **if** $|b| < k$ and best($b$) > 0 **then**
            pick and remove $f$ from $dom(b)$
            push $(b, f)$ on $S$
            **foreach** $v \in \{f, \bar{f}\}$ **do**
                $B \leftarrow \text{GrowBud}(B, b \oplus v)$
        else
            **while** $|S| > 0$ **do**
                pop $(b, f)$ from $S$
                best($b$) ←
                min(best($b$), best($b \oplus f$) + best($b \oplus \bar{f}$))
                **if** $dom(b) \neq \emptyset$ and $|b| < k$ **then**
                    **if** $\forall b' \in A(b), lb(b', b) < best(b')$ **then**
                        $B \leftarrow B \cup \{b\}$
                    **break**
            **return** best(\emptyset)
            **Procedure** GrowBud($B, b$)
                compute $\mathcal{N}(b), \mathcal{P}(b)$, $p(f, \mathcal{N}(b)), p(f, \mathcal{P}(b)), \forall f \in \mathcal{F}$
                $dom(b) \leftarrow \mathcal{F} \setminus \{f | f \in b \lor \bar{f} \in b\}$ sorted by score
                $best(b) \leftarrow \min(|\mathcal{N}(b)|, |\mathcal{P}(b)|)$
                **return** $B \cup \{b\}$

**Theorem 3.1.** *The worst case time complexity of Algorithm 2 is in $\Theta((n + 2^k)P(m, k)) \subset O((n + 2^k)m^k)$ and its worst case space complexity is in $\Theta(2^k m)$.*

*Proof.* The invariants show that Algorithm 2 explores the same set of $P(m, k)2^k$ branches (i.e., the $2^k$ outcomes of each permutation of $k$ features). Moreover, the “yes” branch of Condition 1 dominates the time complexity since at most one element is added to $S$, whereas Loop 7 suppresses exactly one element of $S$ at every (constant time) iteration.

The complexity is thus dominated by the splitting procedure whereby $\mathcal{N}(b \oplus f), \mathcal{N}(b \oplus \bar{f}), \mathcal{P}(b \oplus f)$ and $\mathcal{P}(b \oplus \bar{f})$ are computed from $\mathcal{N}(b)$ and $\mathcal{P}(b)$. As discussed earlier, this takes linear time amortized over the $2^k$ branches sharing the same set of $k$ features. Therefore, the overall time complexity for the splitting operations is in $\Theta(P(m, k)n)$.

A branch can be stored in constant space via indexing, so the worst case space complexity is in $\Theta(2^k m)$, to record in the sets $dom$ which features have been tried. $\square$

The key difference between Algorithms 1 and 2 is the or-
<figure><img src="image_2.png" /><figcaption>Figure 1: The search tree order: left to right for Algorithm 1 and in the order indicated below for Algorithm 2</figcaption></figure>

der in which branches are explored (see Figure 1). In particular, DP must complete the first recursive call before finding a full tree. Therefore, it finds a first full tree in $\Theta((n+2^k)P(m-1, k-1))$, that is $O(n(m-1)^{k-1})$ time. On the other hand, *Blossom* finds a first tree in linear time: $\Theta(2^k + nk) = \Theta(nk)$. Another difference with actual implementations of Algorithm 1 (DL8, DL8.5 or *Murtree*) is that the latter methods use a cache structure in order to reduce the number of branches that need to be explored. Our experimental evaluations, however, show that the overhead of cache lookups may not always be beneficial. Moreover, Algorithm 2 is essentially memoryless. Indeed, under the standard assumption that $2^k \le n$, its worst-case space complexity is not greater than the size of the input.

# 4. Extensions of the Algorithm

The pseudo-code given in Algorithm 2 shows the basic structure of the algorithm. Some important (but rather tedious) parts of the algorithm have been omitted, such as how the best subtrees are stored in Line 9 when the best classification score is updated. We discuss here some additional features that have an impact on the efficiency of the algorithm.

## 4.1. Heuristic Ordering

Testing first the most promising features helps finding accurate trees faster. We used three scores to minimize: classification error (error($b \oplus f$) + error($b \oplus \bar{f}$)), entropy (Quinlan, 1986), and *Gini impurity* (Breiman et al., 1984).

In Line 4, the features are explored in non-decreasing order of the chosen score. All scores are based on the frequencies $p(f, \mathcal{N}(b))$ and $p(f, \mathcal{P}(b))$ of each feature $f$ in each class. These scores are computed by the highlighted instruction in Line 13, and used for sorting in Line 14. *Gini impurity* was the best in our experiments, and all reported results are using it unless stated otherwise. For branches of length $k-1$ we use classification error instead. Indeed, the optimal feature $f$ for a terminal branch $b$ is the one minimizing the error and other features can be ignored. This is implemented by the highlighted code at Line 10: since the first feature choice cannot be improved, branches of length $k-1$ do not have to be put back into $\mathcal{B}$, and can be backtracked upon.

Computing the frequencies of all features can be done in $\Theta(mn)$ time where $n = |\mathcal{N}(b)| + |\mathcal{P}(b)|$, while $p(\bar{f}, \mathcal{N}(b))$ and $p(\bar{f}, \mathcal{P}(b))$ can be obtained by taking the complement to $|\mathcal{N}(b)|$ and $|\mathcal{P}(b)|$, respectively. In other words, this is more expensive than the splitting procedure by a factor $m$, but can be similarly amortized. However, since the depth of the branches is effectively reduced by one, the number of terminal branches is reduced by the same factor $m$, hence this incurs no asymptotic increase in complexity. Furthermore, ordering the features (at Line 14) costs $\Theta(m \log m)$ for each of the $2^{k-1}m^{k-1}$ branches added to $\mathcal{B}$ at Line 5. Again, there is no need to branch on the $k$-th test of a branch, and the complexity is $O((n + 2^k \log m)m^k)$. This slight increase is inconsequential when $n$ is the dominating term.

The feature ordering has a significant impact on how quickly the algorithm can improve the accuracy of the classifier. Moreover, it also has an indirect, and less significant, impact on the time necessary to prove optimality, because of the lower bound technique detailed in the next section.

## 4.2. Lower Bound

One can fail early thanks to a lower bound on the error given prior decisions, similarly as DL8.5 does (Nijssen & Fromont, 2007). When some subtrees along a branch $b$ are optimal and their total error is larger than the current upper bound, then there is no point in exploring branch $b$ further.

Observe that $best(b)$ is an upper bound on the classification error for any subtree rooted at $b$ (witnessed by a tree when $best(b)$ is updated). We can propagate this bound to parent nodes efficiently (in $O(|b|)$ time). We assume that this is done recursively for the parent branch, every time the value $best(b)$ is updated. Now, when the condition in Line 10 fails for a branch $b$, it means that $best(b)$ is optimal: no subtree rooted at $b$ of maximum depth $k - |b|$ has a classification error lower than $best(b)$. This is true either because every subtree has been explored, or, with the changes described in Section 4.1, because $k - |b| = 1$ and the feature $f$ with least $error(b \oplus f) + error(b \oplus \bar{f})$ has been chosen. Let $optimal(b) = 1$ if the branch is optimal and $optimal(b) = 0$ otherwise. Notice that this is equivalent, for a branch $b \oplus v$ ending on test $v \in \{f, \bar{f}\}$, to checking if $|b| = k-1$, or if $(b, f) \in S$ but there is no $g \in \mathcal{F}$ such that $(b \oplus v, g) \in S$.
<figure><img src="image_3.png" /><figcaption>Figure 2: Example of lower bound for a given branch</figcaption></figure>

Moreover, let $\mathcal{A}(b)$ denote the ancestors of branch $b$ in the current tree, i.e., $\mathcal{A}(b) = \{b' \mid (b', v) \in \mathcal{S} \wedge b' \subset b\}$. Now, consider the highlighted code in Line 11. For any ancestor $b'$ of $b$, we define a lower bound $lb(b', b)$, given the feature tests in $b \setminus b'$ as follows:

$$lb(b', b) = \sum_{b' \subset b'' \oplus f \subseteq b} optimal(b'' \oplus \bar{f}) \cdot best(b'' \oplus \bar{f})$$

That is, $lb(b', b)$ is the total errors of optimal “sibling” branches between $b'$ and $b$. As long as $b$ belongs to the current tree, these subtrees cannot be improved, hence this lower bound is correct.

**Example 1 (Lower bound reasoning).** Figure 2 shows a snapshot of the execution of **Blossom**. Every node is labelled with the feature test on that node, and with the values of best($b$) for the branch $b$ ending on that node. When all subtrees of a branch $b$ have been explored (hence optimal($b$) = 1), this is marked by a “*”. We assume that the branch considered at Line 11 is $b = \{r, \bar{a}, \bar{c}, g\}$. For instance, we can suppose that a tree rooted at $b$ with feature $e$ has been found (misclassifying 2 data points). Then, search moved to the sibling branch $\{r, \bar{a}, \bar{c}, g\}$, which was then optimized for a total error of 4, and now the pair $(b, e)$ is popped out of $\mathcal{S}$. For all branches $b'$ of $b$, we give the values of $lb(b', b)$ and best($b'$) between brackets. Since there exists $b'$ such that $lb(b', b) \geq best(b')$ (e.g., $\emptyset$ and $\{r, \bar{a}\}$), we know that $b$ cannot belong to an improving solution, and hence there is no need to try to extend it further.

This reasoning is more effective when good upper bounds are found early, hence the feature ordering discussed in the previous section has an impact. Moreover, the choice of branch in Line 2 has an impact as well. We found that the simplest branch selection strategy was also the one giving the best results: we expand first the branch that was inserted into $\mathcal{B}$ first (i.e., $\mathcal{B}$ is **FIFO**). One possible explanation is that by avoiding to unnecessarily “jump” to different parts of

the decision tree, this strategy promotes optimizing sibling subtrees first, and therefore, deeper tree earlier.

### 4.3. Preprocessing

Finally, we use two preprocessing techniques, one on the data set and one on the feature set. Although straightforward, they both have a significant impact.

**Dataset reduction.** It is easy to adapt **Blossom** to handle weighted data sets by redefining the error as follows, given a weight function $w$ on $\mathcal{D}$: error($b$) = $\min(\sum_{x \in \mathcal{N}(b)} w(x), \sum_{x \in \mathcal{P}(b)} w(x))$.

We can use weights as an optimization in the context of noisy data, by merging duplicated datapoints and suppressing inconsistent datapoints. Let $w^-$ (resp. $w^+$) denote the number of occurrences of $x$ in $\mathcal{D}^-$ (resp. $\mathcal{D}^+$). We use the weight function $w(x) = |w^-(x) - w^+(x)|$. Then, for any datapoint $x$, we remove all but one of its occurrences, in $\mathcal{D}^-$ if $w^- > w^+$, in $\mathcal{D}^+$ if $w^+ > w^-$, and suppress it completely if $w^+ = w^-$. The reported error will then need to be offset by the number of pairs of suppressed inconsistent datapoints, that is: $\sum_{x \in \mathcal{D}} \min(w^-(x), w^+(x))$. Reducing the number of datapoints in the data set has a non-null, although tiny impact on efficiency. However, suppressing inconsistent datapoints is very important. In particular, proving optimality when the minimum error is positive basically requires to exhaust the search space and is therefore extremely costly. On the other hand, when there exists a perfect tree within the maximum depth, we can stop as soon as we find it. This preprocessing allows to benefit from that when we find a tree whose error is equal to the number of pair of inconsistent datapoints in the original data set. This preprocessing can be done in $O(mn \log n)$ by ordering the datapoints in lexicographic order and then processing them in sequence.

**Feature reduction.** A feature $f$ is redundant if there exists another feature $f'$ such that either: $\forall x \in \mathcal{D}, f \in x \Leftrightarrow f' \in x$, or $\forall x \in \mathcal{D}, f \in x \Leftrightarrow f' \notin x$. They can be found in $O(nm^2)$ time by comparing pairs of rows of the data set.

Removing redundant features may appear naive, however, it turns out that the binarization techniques (one-hot encoding) are often not optimized and many redundant features do exist in standard data sets. The number of features ($m$) has a huge impact on the complexity: the branching factor of the algorithm is indeed $2m$ (see Figure 1). Moreover, at every branch, “informationless” features (i.e., features $f$ such that $(\forall x \in \mathcal{P}(b) f \in x) \Leftrightarrow (\forall x \in \mathcal{N}(b) f \in x)$) can be suppressed at no additional cost since this can be detected when computing the feature ordering criterion.
<table><caption>Table 1: Comparison with the state of the art: accuracy and optimality proofs</caption><thead><tr><th rowspan="2">k</th><th colspan="3">Blossom</th><th colspan="3">Murtree</th><th colspan="3">Murtree<sup>P</sup></th><th colspan="3">CP</th><th colspan="3">DL8.5</th><th colspan="2">binOCT</th></tr><tr><th>opt.</th><th>acc.</th><th>cpu</th><th>opt.</th><th>acc.</th><th>cpu*</th><th>opt.</th><th>acc.</th><th>cpu*</th><th>opt.</th><th>acc.</th><th>cpu*</th><th>sol.</th><th>opt.</th><th>acc.*</th><th>cpu*</th><th>sol.</th><th>acc.*</th></tr></thead><tbody><tr><td colspan="22" style="text-align:center;">m &lt; 100 (29 data sets)</td></tr><tr><td>3</td><td>1.00</td><td>0.8871</td><td>0.23</td><td>1.00</td><td>0.8871</td><td>+0.31</td><td>1.00</td><td>0.8871</td><td>+0.22</td><td>1.00</td><td>0.8871</td><td>+3.2</td><td>1.00</td><td>1.00</td><td>-0.00%</td><td>+2.5</td><td>0.52</td><td>-1.21%</td></tr><tr><td>4</td><td>1.00</td><td>0.9130</td><td>14</td><td>1.00</td><td>0.9130</td><td>+8.0</td><td>1.00</td><td>0.9130</td><td>+4.0</td><td>1.00</td><td>0.9130</td><td>+115</td><td>1.00</td><td>1.00</td><td>+0.00%</td><td>+105</td><td>0.52</td><td>-2.62%</td></tr><tr><td>5</td><td>0.93</td><td>0.9344</td><td>187</td><td>0.97</td><td>0.9344</td><td>-12</td><td>0.97</td><td>0.9344</td><td>-89</td><td>0.62</td><td>0.9337</td><td>+121</td><td>1.00</td><td>0.86</td><td>-0.01%</td><td>+2.0</td><td>0.52</td><td>-3.81%</td></tr><tr><td>7</td><td>0.66</td><td>0.9596</td><td>81</td><td>0.69</td><td>0.9564</td><td>+90</td><td>0.79</td><td>0.9587</td><td>-69</td><td>0.45</td><td>0.9075</td><td>+193</td><td>1.00</td><td>0.84</td><td>-0.46%</td><td>+6.7</td><td>0.52</td><td>-7.30%</td></tr><tr><td>10</td><td>0.79</td><td>0.9733</td><td>85</td><td>0.52</td><td>0.9623</td><td>+83</td><td>0.83</td><td>0.9669</td><td>-70</td><td>0.45</td><td>0.8691</td><td>+2.6</td><td>1.00</td><td>0.83</td><td>-1.34%</td><td>+49</td><td>0.41</td><td>-29.46%</td></tr><tr><td colspan="22" style="text-align:center;">m &ge; 100 (29 data sets)</td></tr><tr><td>3</td><td>0.89</td><td>0.8874</td><td>100</td><td>0.89</td><td>0.8874</td><td>-42</td><td>0.89</td><td>0.8874</td><td>-45</td><td>0.75</td><td>0.8870</td><td>+256</td><td>1.00</td><td>0.86</td><td>-0.25%</td><td>+247</td><td>0.64</td><td>-2.36%</td></tr><tr><td>4</td><td>0.57</td><td>0.9060</td><td>662</td><td>0.75</td><td>0.9053</td><td>+64</td><td>0.75</td><td>0.9052</td><td>-266</td><td>0.29</td><td>0.8930</td><td>+576</td><td>1.00</td><td>0.54</td><td>-0.85%</td><td>+258</td><td>0.64</td><td>-4.78%</td></tr><tr><td>5</td><td>0.36</td><td>0.9211</td><td>452</td><td>0.36</td><td>0.9202</td><td>+99</td><td>0.39</td><td>0.9207</td><td>-357</td><td>0.14</td><td>0.8327</td><td>+11</td><td>1.00</td><td>0.33</td><td>-1.85%</td><td>+12</td><td>0.64</td><td>-8.55%</td></tr><tr><td>7</td><td>0.32</td><td>0.9449</td><td>11</td><td>0.32</td><td>0.9337</td><td>+7.4</td><td>0.32</td><td>0.9389</td><td>-3.4</td><td>0.29</td><td>0.8170</td><td>+571</td><td>1.00</td><td>0.44</td><td>-3.02%</td><td>+793</td><td>0.57</td><td>-22.33%</td></tr><tr><td>10</td><td>0.46</td><td>0.9613</td><td>101</td><td>0.43</td><td>0.9542</td><td>+19</td><td>0.46</td><td>0.9555</td><td>-12</td><td>0.39</td><td>0.8604</td><td>+85</td><td>1.00</td><td>0.67</td><td>-2.59%</td><td>+183</td><td>0.21</td><td>-55.08%</td></tr></tbody></table>

<figure><img src="image_4.png" /><figcaption>Figure 3: Test accuracy w.r.t. depth (All data sets)</figcaption></figure>

<figure><img src="image_5.png" /><figcaption>Figure 4: Test accuracy w.r.t. depth (Filtered data sets)</figcaption></figure>

## 5. Experimental Results

All experiments were run on 4 cluster nodes, each with 36 Intel Xeon CPU E5-2695 v4 2.10GHz cores running Linux Ubuntu 16.04.4. Sources were compiled using `g++8.2`. Every algorithm was run until completion or until reaching a time limit of one hour, and within a memory limit of 50GB.

We used a collection of 58 data sets from related work (Aglin et al., 2020; Narodytska et al., 2018; Verwer & Zhang, 2019), plus 8 large extra data sets from Kaggle and UCI. Further details on the data sets, as well as the raw data of our experiments can be found in the Appendix.

### 5.1. Generalization of optimal decision trees

The capacity of optimized trees to generalize to unseen data has been empirically evaluated and evidence of gains over heuristic trees have been found (Bertsimas & Dunn, 2017; Demirović et al., 2022). We reproduce this type of experiments here, however, because they are rare and often restricted to shallow trees. Therefore we first tried to reproduce those findings.

Figure 3 shows the test accuracy, averaged across all 58 data sets of CART (in red), Blossom (in green) and several post-pruned versions of Blossom (in shades of blue). For each data set we generated 50 random samples of 20% of the datapoints to be used for validation, while the rest was used for training, and we report the averages. Given the large number of runs, we stopped Blossom after 10 minutes in each run, and kept the last tree it returned. For shallow trees ($k \le 6$), Blossom is more accurate on these data sets. The difference is statistically significant for $k = 3$ (99.9% confidence) and $k = 4$ (95%), but with only 50%

<footnote n="2">²The source code for Blossom is available at https://gitlab.laas.fr/ehebrard/blossom</footnote>
and 60% confidence for *k* = 5 and 6 respectively. For
deeper trees there is no statistically significant difference,
and CART seems even slightly better.

We believe that this is due to overfitting. In order to test this
hypothesis, we report on the same figure the accuracy of
*Blossom*'s trees, but pruned using *cost complexity pruning*
up until a cumulative loss of accuracy of 1% (*Blossom
1%*) or 3% (*Blossom 3%*).<fnref n="3" /> Pruned optimized trees have
a better accuracy than *CART*'s even when the depth grows.
Moreover, since pruning is more helpful for deeper trees, we
also report the results of *Blossom* pruned with an adaptive
limit of 0.3·*k*²%. This approach is the best overall, although
the confidence level is below 50% for *k* = 7 and 8.

The statistical significance of these results is not entirely sat-
isfying. Moreover, the difference is very much dependent on
the data set.<fnref n="4" /> After a careful analysis of the experiment data,
we observed that in some data sets, none of the methods is
able to learn a meaningful decision tree, in the sense that
their test accuracy is very weakly correlated to training accu-
racy. For instance, suppose we are trying to learn the parity
function. There is no way to represent this function with a
tree whose depth is not equal to the number of features. We
believe that some of these data sets have similar properties.
Under this hypothesis, we tried to design a mecanism to
filter out such data sets, and came up with the following
simple test: *we keep only those data sets where CART with
k = 10 is at least as good as the best single-feature test.*
This condition excludes 18 of the 58 data sets. Although this
selection is by design favorable to CART, we can observe in
Figure 4 that *Blossom* (without post-pruning), generalizes
better in average to unseen data on these 40 data sets (the
paired *t*-test gives about 75% confidence that *Blossom* is
more accurate than *CART* for *k* ≥ 5).

Finally, to further test the hypothesis that more search im-
proves test accuracy, we also report the accuracy of the first
(Blossom (1st)), or the third (Blossom (3rd)) solution
found by Blossom. The former is equivalent to CART, and
the latter yields trees with higher accuracy, but not as high
as the full version, which supports our hypothesis.<fnref n="5" />

**5.2. Computing (optimally) accurate classifiers**

We then compare *Blossom* to state-of-the-art algorithms,
*Murtree* (Demirović et al., 2022) and *DL8.5* (Aglin et al.,
2020), as well as the best MIP (*binOCT*) (Verwer & Zhang,
2019) and CP (*CP*) (Verhaeghe et al., 2020) models, for
computing and proving optimal trees. We also ran all these
methods on *preprocessed* data sets, using the approach de-

scribed in Section 4.3 to remove inconsistent data points
and redundant features. We only report those results for
*Murtree* (with superscript ‘P’) for lack of space, although
all results are in the appendix. Unfortunately, at the time
of writing, we were not aware of *LDS-DL8.5* and did not
use it in our experimental evaluation. Since it is similar to
*DL8.5* in terms of overall performance, we are confident
that *Blossom* is more efficient for deep trees. The any-
time behavior of this algorithm is however vastly better than
*DL8.5*'s and would need to be compared with *Blossom's*.
We did not compare our algorithm to approaches that di-
rectly learn on non-binary data sets (e.g. (Shati et al., 2021;
Mazumder et al., 2022)), factoring in the binary encoding
makes fair comparisons difficult.

In Table 1 we split the data sets in two classes according
to the number of features *m*. Every method is run with
the bound *k* on the depth shown in the first column. We
report the ratio of data sets for which an optimality proof
could be derived (opt.); the average training accuracy (acc.);
and the average CPU time (cpu) to prove optimality. Since
comparing CPU times only makes sense when optimality is
proven by both methods, we report the average difference
w.r.t. *Blossom*'s on the data sets for which both methods
*prove optimality*. Similarly, since *DL8.5* and *binOCT* ex-
ceed the memory limit of 50GB in some cases, we compute
their accuracy *relative* to *Blossom* on the subset of runs
where at least one tree was found. Moreover, the column
(sol.) gives the ratio of such “successful” runs. Columns
with results *relative to* *Blossom* are marked by a “*”.

The first observation is that *Blossom* and *Murtree* are
significantly more efficient than other methods on all cri-
teria. Moreover *CP*, *DL8.5* and *binOCT* clearly do not
scale to high depths, the two latter even often exceeding the
memory limit (set to 50GB). With respect to *Murtree*, the
experimental results support two conclusions:

*Blossom* systematically dominates *Murtree* for the aver-
age training accuracy, especially as the depth and the feature
set grow. Since the accuracy results in Table 1 include data
sets for which an optimal tree is found, the gap on other
data sets is larger. Moreover, they are averaged over 58
data sets, so a gap of a fraction of a point is significant: the
full results in appendix show that if the gaps are variable,
they are consistently in favor of *Blossom*. For instance,
for *k* = 7 (resp. *k* = 10) the average gain of *Blossom*
w.r.t. *Murtree* is of 1.6 (resp. 1.1) points, over the 31
(resp. 39) data sets not solved to optimality. This gain is due
to *Blossom*'s integration of feature frequency counting to
guide search via heuristics toward promising trees (and also
reduce the search space) as described in Section 4.

However, *Murtree*'s use of caching makes it better at
proving optimality. The raw results are not always in favor
of *Murtree*, especially for high depths. However, there

<footnote n="3">³CART's trees are pruned with default settings</footnote>

<footnote n="4">⁴A few data sets account for most of the gap, cf. appendix.</footnote>

<footnote n="5">⁵The number of improving solutions found by *Blossom* in 10 minutes was in average 7.47 for *k* = 3 and up to 31.94 for *k* = 10.</footnote>
are two types of proofs: "non-trivial" proofs obtained by exhausting the search space, and "trivial" proofs obtained by finding a perfect tree (whose classification error is null, or equal to the number of inconsistent data points when using preprocessing). Caching helps for the former hence *Murtree's* higher proof ratio for shallower trees. In the case of deeper trees, however, non-trivial proofs are harder to obtain, and the ratio of trivial proofs increases because finding a perfect tree is easier. Since *Blossom* finds more accurate tree faster, it also obtains more of these proofs. Indeed, *Murtree*^P (i.e., with our preprocessing) is the best method to prove optimality overall, since preprocessing means that more data sets have a trivial proof.

## 5.3. Anytime behavior

Next, we shift our focus to how fast can we obtain accurate trees and how fast can we improve the accuracy over basic solutions found by heuristics. We use the scikit-learn implementation of CART, which has a parameter to bound the depth of the tree, as baseline. Here we report the average error, over all 58 data sets, after a given period of time (first solution, after 10 seconds, or after 1 minute), both for *Murtree* and *Blossom* in Table 3.

Firstly, this experiment shows that the initial solution is very similar to that found by CART. There is actually a slight advantage for *Blossom*, which can be explained by CART's post-pruning as well as by the fact that whereas CART systematically selects the feature with minimum Gini impurity, *Blossom* does so for all *but the deepest feature tests*, for which it uses least classification error instead. Secondly, this first tree is found extremely quickly, and there is no scaling issue with respect to the depth of the tree nor to the size of the data set. Thirdly, even for large data sets and deep trees, the accuracy of the initial classifier can be significantly improved given more computation time.

Figure 5 reports the evolution, averaged across all 58 data sets, of the accuracy over time, giving a good view of the difference between *Murtree* and *Blossom* during search. The accuracy of the tree returned by CART is given for reference. We can see in those graphs *Blossom's* anytime accuracy is significantly higher than that of *Murtree*. Notice that the first few improving solutions reported by *Murtree* are not complete trees. This is apparent in Table 3 which shows the accuracy at different time points during search. However, this has an impact only on the first milliseconds of search and have no impact on the graphs in the long run.

## 5.4. Analysis of the extensions

Finally, we report in Table 2 the results of three variants, in order to analyse the impact of the factors described in Section 4. For each variant, we give the average accuracy (acc.), ratio of proofs (opt.) and relative increase in cpu time

<figure><img src="image_6.png" /><figcaption>Figure 5: Accuracy over time, averaged across all data sets</figcaption></figure>
<table><caption>Table 2: Factor analysis</caption><thead><tr><th rowspan="2">k</th><th colspan="3">Blossom</th><th colspan="3">No heuristic</th><th colspan="3">No preprocessing</th><th colspan="3">No lower bound</th></tr><tr><th>acc.</th><th>opt.</th><th>cpu</th><th>acc.</th><th>opt.</th><th>cpu*</th><th>acc.</th><th>opt.</th><th>cpu*</th><th>acc.</th><th>opt.</th><th>cpu*</th></tr></thead><tbody><tr><td>3</td><td>0.8875</td><td>0.93</td><td>67</td><td>0.8871</td><td>0.93</td><td>-1.6</td><td>0.8875</td><td>0.93</td><td>+4.3</td><td>0.8875</td><td>0.93</td><td>-2.8</td></tr><tr><td>4</td><td>0.9095</td><td>0.78</td><td>388</td><td>0.9081</td><td>0.79</td><td>-61</td><td>0.9093</td><td>0.72</td><td>+47</td><td>0.9095</td><td>0.78</td><td>+13</td></tr><tr><td>5</td><td>0.9275</td><td>0.64</td><td>479</td><td>0.9257</td><td>0.67</td><td>-30</td><td>0.9272</td><td>0.55</td><td>+276</td><td>0.9275</td><td>0.64</td><td>+39</td></tr><tr><td>7</td><td>0.9517</td><td>0.48</td><td>1045</td><td>0.9455</td><td>0.48</td><td>+17</td><td>0.9512</td><td>0.43</td><td>+163</td><td>0.9512</td><td>0.48</td><td>+30</td></tr><tr><td>10</td><td>0.9667</td><td>0.62</td><td>570</td><td>0.9583</td><td>0.53</td><td>+66</td><td>0.9656</td><td>0.43</td><td>+63</td><td>0.9665</td><td>0.60</td><td>+8.0</td></tr></tbody></table>

<table><caption>Table 3: Anytime comparison with state the of the art</caption><thead><tr><th rowspan="2">k</th><th colspan="3">Blossom</th><th colspan="3">Murtree<sup>P</sup></th><th>CART</th></tr><tr><th>first</th><th>&le;10s</th><th>&le;1m</th><th>first</th><th>&le;10s</th><th>&le;1m</th><th>first</th></tr></thead><tbody><tr><td>3</td><td>795</td><td>734</td><td>729</td><td>2101</td><td>895</td><td>891</td><td>808</td></tr><tr><td>4</td><td>688</td><td>650</td><td>642</td><td>2101</td><td>792</td><td>786</td><td>694</td></tr><tr><td>5</td><td>607</td><td>575</td><td>569</td><td>2101</td><td>718</td><td>710</td><td>609</td></tr><tr><td>7</td><td>499</td><td>471</td><td>467</td><td>2101</td><td>566</td><td>558</td><td>507</td></tr><tr><td>10</td><td>407</td><td>382</td><td>374</td><td>2101</td><td>448</td><td>441</td><td>412</td></tr></tbody></table>

(cpu*), on runs where an optimal tree has been found.

The variant “No heuristic” disables the Gini impurity heuristic described in Section 4.1, and replaces it by simply selecting first the feature with minimum error. For shallow trees (depth 3 or 4), since in many cases the search space is completely exhausted, not computing the slightly more costly Gini impurity score may actually be a good choice and we observe run time reductions of about 15% to 20%. However, the accuracy of the trees decreases rapidly for larger maximum depth. As a results, less optimality proofs are obtained, and they take longer to compute.

The variant “No preprocessing” disables the preprocessing described in Section 4.3. The feature ordering is impacted by the removal of datapoints, and hence a more accurate tree might be found without preprocessing. However, in most cases, preprocessing does pay off, yielding more optimality proofs, better accuracy, and shorter runtimes. We estimate that most of the gain is due to the removal of redundant features, and of inconsistent datapoints, whereas the fusion of datapoints accounts for only a slight speed-up.

The variant “No lower bound” disables the bound described in (4.2). We observe a slight increase in CPU time in average (but up to 200% for some data sets) but it only slightly negatively affects the accuracy and the number of proofs.

## 6. Conclusion

We have introduced a simple, exact, iterative, memory-efficient and anytime algorithm for computing optimally-accurate tree classifiers of bounded depth. This algorithm

scales significantly better than state-of-the-art exact algorithms to high depths while having no significant time nor memory overhead with respect to greedy heuristic methods.

Our experiments provide further evidence that trees of bounded depth and optimal training accuracy generalize better to unseen data than heuristic trees. However they also indicate that using the size of tree in the objective is beneficial as well, raising the question of the tradeoff between adequacy and complexity in the objectives and models.

## Acknowledgements

This work was supported by the AI Interdisciplinary Institute ANITI, funded by the French program “Investing for the Future – PIA3” under Grant agreement no. ANR-19-PI3A-0004; and by the European Union’s Horizon Europe Research and Innovation program under the grant agreement TUPLES No101070149.

## References

* Aghaei, S., Gomez, A., and Vayanos, P. Learning Optimal Classification Trees: Strong Max-Flow Formulations. *arXiv preprint arXiv:2002.09142*, 2020.

* Aglin, G., Nijssen, S., and Schaus, P. Learning Optimal Decision Trees Using Caching Branch-and-Bound Search. In *Proceedings of the AAAI Conference on Artificial Intelligence*, pp. 3146–3153, 2020.

* Avellaneda, F. Efficient Inference of Optimal Decision Trees. In *Proceedings of the AAAI Conference on Artificial Intelligence*, pp. 3195–3202, 2020.

* Bertsimas, D. and Dunn, J. Optimal classification trees. *Machine Learning*, 106(7):1039–1082, 2017.

* Bertsimas, D. and Shioda, R. Classification and regression via integer optimization. *Operations Research*, 55(2): 252–271, 2007.

* Breiman, L., Friedman, J., Olshen, R., and Stone, C. Classification and Regression Trees. Wadsworth & Brooks, 1984.
Demirović, E., Lukina, A., Hebrard, E., Chan, J., Bailey, J., Leckie, C., Ramamohanarao, K., and Stuckey, P. J. *MurTree: Optimal Decision Trees via Dynamic Programming and Search.* *Journal of Machine Learning Research*, 23(26):1–47, 2022.

Harvey, W. D. and Ginsberg, M. L. Limited Discrepancy Search. In *Proceedings of the 14th International Joint Conference on Artificial Intelligence (IJCAI)*, pp. 607–613, 1995.

Hu, H., Siala, M., Hebrard, E., and Huguet, M. Learning Optimal Decision Trees with MaxSAT and its Integration in AdaBoost. In *Proceedings of the Twenty-Ninth International Joint Conference on Artificial Intelligence (IJCAI)*, pp. 1170–1176, 2020.

Hu, X., Rudin, C., and Seltzer, M. Optimal Sparse Decision Trees. In *Advances in Neural Information Processing Systems (NeurIPS)*, pp. 7265–7273, 2019.

Kiossou, H. S., Schaus, P., Nijssen, S., and Houndji, V. R. Time Constrained DL8.5 Using Limited Discrepancy Search. In *Proceedings of the European Conference on Machine Learning and Knowledge Discovery in Databases (ECML PKDD)*, pp. 443–459, 2022.

Laurent, H. and Rivest, R. L. Constructing Optimal Binary Decision Trees is NP-complete. *Information Processing Letters*, 5(1):15–17, 1976.

Lin, J., Zhong, C., Hu, D., Rudin, C., and Seltzer, M. Generalized and Scalable Optimal Sparse Decision Trees. In *Proceedings of the 37th International Conference on Machine Learning (ICML)*, pp. 6150–6160, 2020.

Mazumder, R., Meng, X., and Wang, H. Quant-BnB: A Scalable Branch-and-Bound Method for Optimal Decision Trees with Continuous Features. In *Proceedings of the 39th International Conference on Machine Learning (ICML)*, pp. 15255–15277, 2022.

Narodytska, N., Ignatiev, A., Pereira, F., and Marques-Silva, J. Learning Optimal Decision Trees with SAT. In *Proceedings of the Twenty-Seventh International Joint Conference on Artificial Intelligence (IJCAI)*, pp. 1362–1368, 2018.

Nijssen, S. and Fromont, E. Mining Optimal Decision Trees from Itemset Lattices. In *Proceedings of the 13th ACM SIGKDD international conference on Knowledge discovery and data mining*, pp. 530–539, 2007.

Quinlan, J. R. Induction of Decision Trees. *Mach. Learn.*, 1 (1):81–106, 1986.

Quinlan, R. C4.5: Programs for Machine Learning. Kaufmann, 1993.

Shati, P., Cohen, E., and McIlraith, S. SAT-Based Approach for Learning Optimal Decision Trees with Non-Binary Features. In *Proceedings of the 27th International Conference on Principles and Practice of Constraint Programming (CP)*, pp. 50–50, 2021.

Verhaeghe, H., Nijssen, S., Pesant, G., Quimper, C.-G., and Schaus, P. Learning Optimal Decision Trees Using Constraint Programming. *Constraints*, 25(3–4):226–250, 2020.

Verwer, S. and Zhang, Y. Learning Optimal Classification Trees using a Binary Linear Program Formulation. In *Proceedings of the AAAI Conference on Artificial Intelligence*, pp. 1625–1632, 2019.
# A. Appendix

Section A.1 provides information about the chosen data sets. Section A.2, provides the raw data from all our experiments (for every method and every data set).

## A.1. Information about the data sets

The benchmark of classification data set we used is described in Table 4. It consists of 50 data sets commonly used in related work articles (namely, (Aglin et al., 2020; Narodytska et al., 2018; Verwer & Zhang, 2019)), to which we added the following large data sets in order to stress how well the different approaches scale.

The *taiwan_binarised* and *adult_discretized* data sets come from the UCI repository and were discretized using ad-hoc threshold on continuous or large numerical features, and one-hot encoding for symbolic features.

The *compas_discretized*, *bank*, *titanic*, *surgical-deepnet* and *weather-aus* data sets come from Kaggle and were binarized using the one-hot encoding.

The data set *mnist_0* is the well known data set on hand written digits binarized as follows: every pixel is a binary attribute whose value is 1 if its greyscale is larger than 0.5 and 0 otherwise. The data point is positive if it is the digit “0” and negative otherwise.

We report the number of data points (|D|), the number of features (|F|), the same parameters after preprocessing (respectively |D|* and |F|*), and the “noise” ratio, that is: 2|P ∩ N|/(|P| + |N|).

## A.2. Full experimental results

### A.2.1. TEST ACCURACY

We report here the raw data from our experimental evaluation of the test accuracy of *Blossom's* trees in the following tables:

$$k = 3 \ k = 4 \ k = 5 \ k = 6 \ k = 7 \ k = 8 \ k = 9 \ k = 10$$

Tab. 5 Tab. 6 Tab. 7 Tab. 8 Tab. 9 Tab. 10 Tab. 11 Tab. 12

In Tables 5 to 12, data sets filtered-out according to the condition defined in (5.1) are given between parenthesis.

### A.2.2. COMPARISON WITH THE STATE OF THE ART

We report here the raw data from our experimental comparison with the state of the art for $k = 3, 4, 5, 7, 10$ and for the four size categories in the following tables:

<table><thead><tr><th>m</th><th>k = 3</th><th>k = 4</th><th>k = 5</th><th>k = 7</th><th>k = 10</th></tr></thead><tbody><tr><td>&lt; 100</td><td>Table 13</td><td>Table 15</td><td>Table 17</td><td>Table 19</td><td>Table 21</td></tr><tr><td>≥ 100</td><td>Table 16</td><td>Table 14</td><td>Table 18</td><td>Table 20</td><td>Table 22</td></tr></tbody></table>

For every instance, we give the classification error of the best tree found within a time limit of 1h for every method. Moreover, we give the CPU time taken by each method to prove optimality when optimality is proven (in which case we mark it by a “*”), and to find the best solution otherwise. Notice that CP and DL8.5 are not anytime and hence only report a solution at the end of the time limit when optimality is not proven. In this case, we write $≥ 1h$.

Every process was first run with a memory limit of 3.5GB. Many runs of DL8.5, CP and binOCT went well over that limit and were rerun with a limit of 50GB. Still, 138 runs of binOCT and 164 runs of DL8.5 (out of 460) went over the limit. As binOCT can output trees anytime, the data for these runs (up until the memory blow-out) are in the tables. For DL8.5, however, this is marked as a “-” since there was no output.
<table><caption>Table 4: Benchmark and preprocessing data</caption><thead><tr><th>set</th><th>|D|</th><th>|F|</th><th>|D|*</th><th>|F|*</th><th>noise</th></tr></thead><tbody><tr><td>monk3</td><td>122</td><td>11</td><td>122</td><td>11</td><td>0.0000</td></tr><tr><td>monk1</td><td>124</td><td>11</td><td>124</td><td>11</td><td>0.0000</td></tr><tr><td>hepatitis</td><td>137</td><td>68</td><td>136</td><td>34</td><td>0.0000</td></tr><tr><td>lymph</td><td>148</td><td>68</td><td>148</td><td>47</td><td>0.0000</td></tr><tr><td>iris</td><td>150</td><td>12</td><td>28</td><td>10</td><td>0.0133</td></tr><tr><td>monk2</td><td>169</td><td>11</td><td>169</td><td>11</td><td>0.0000</td></tr><tr><td>heart-cleveland</td><td>296</td><td>95</td><td>296</td><td>54</td><td>0.0000</td></tr><tr><td>primary-tumor</td><td>336</td><td>31</td><td>240</td><td>17</td><td>0.0893</td></tr><tr><td>vote</td><td>435</td><td>48</td><td>342</td><td>48</td><td>0.0000</td></tr><tr><td>balance-scale</td><td>625</td><td>16</td><td>625</td><td>16</td><td>0.0000</td></tr><tr><td>soybean</td><td>630</td><td>50</td><td>502</td><td>43</td><td>0.0063</td></tr><tr><td>breast-cancer</td><td>683</td><td>89</td><td>449</td><td>89</td><td>0.0000</td></tr><tr><td>IndiansDiabetes</td><td>768</td><td>43</td><td>723</td><td>40</td><td>0.0208</td></tr><tr><td>anneal</td><td>812</td><td>93</td><td>495</td><td>49</td><td>0.0837</td></tr><tr><td>tic-tac-toe</td><td>958</td><td>27</td><td>958</td><td>27</td><td>0.0000</td></tr><tr><td>messidor</td><td>1151</td><td>86</td><td>1124</td><td>82</td><td>0.0104</td></tr><tr><td>banknote</td><td>1372</td><td>28</td><td>358</td><td>26</td><td>0.0029</td></tr><tr><td>yeast</td><td>1484</td><td>89</td><td>1418</td><td>46</td><td>0.0067</td></tr><tr><td>wine1</td><td>178</td><td>1276</td><td>178</td><td>646</td><td>0.0000</td></tr><tr><td>wine2</td><td>178</td><td>1276</td><td>178</td><td>646</td><td>0.0000</td></tr><tr><td>wine3</td><td>178</td><td>1276</td><td>178</td><td>646</td><td>0.0000</td></tr><tr><td>audiology</td><td>216</td><td>148</td><td>186</td><td>84</td><td>0.0000</td></tr><tr><td>ionosphere</td><td>351</td><td>445</td><td>350</td><td>222</td><td>0.0000</td></tr><tr><td>forest-fires</td><td>517</td><td>989</td><td>504</td><td>656</td><td>0.0155</td></tr><tr><td>australian-credit</td><td>653</td><td>125</td><td>653</td><td>74</td><td>0.0000</td></tr><tr><td>breast-wisconsin</td><td>683</td><td>120</td><td>449</td><td>60</td><td>0.0000</td></tr><tr><td>diabetes</td><td>768</td><td>112</td><td>768</td><td>56</td><td>0.0000</td></tr><tr><td>vehicle</td><td>846</td><td>252</td><td>846</td><td>126</td><td>0.0000</td></tr><tr><td>titanic</td><td>887</td><td>333</td><td>803</td><td>333</td><td>0.0361</td></tr><tr><td>german-credit</td><td>1000</td><td>112</td><td>998</td><td>86</td><td>0.0000</td></tr><tr><td>biodeg</td><td>1055</td><td>304</td><td>1017</td><td>291</td><td>0.0019</td></tr><tr><td>winequality-red</td><td>1599</td><td>42</td><td>1073</td><td>39</td><td>0.0025</td></tr><tr><td>car</td><td>1728</td><td>21</td><td>1728</td><td>21</td><td>0.0000</td></tr><tr><td>car.evaluation</td><td>1728</td><td>14</td><td>1072</td><td>14</td><td>0.0926</td></tr><tr><td>seismic_bumps</td><td>2584</td><td>91</td><td>1663</td><td>87</td><td>0.0255</td></tr><tr><td>chess</td><td>3196</td><td>73</td><td>3196</td><td>39</td><td>0.0000</td></tr><tr><td>kr-vs-kp</td><td>3196</td><td>73</td><td>3196</td><td>38</td><td>0.0000</td></tr><tr><td>hypothyroid</td><td>3247</td><td>88</td><td>2527</td><td>44</td><td>0.0105</td></tr><tr><td>compas_discretized</td><td>6167</td><td>25</td><td>4181</td><td>20</td><td>0.5928</td></tr><tr><td>HTRU_2</td><td>17898</td><td>70</td><td>12710</td><td>70</td><td>0.0193</td></tr><tr><td>magic04</td><td>19020</td><td>86</td><td>18174</td><td>86</td><td>0.0083</td></tr><tr><td>adult_discretized</td><td>30299</td><td>59</td><td>17804</td><td>56</td><td>0.2149</td></tr><tr><td>segment</td><td>2310</td><td>235</td><td>2027</td><td>114</td><td>0.0000</td></tr><tr><td>splice-1</td><td>3190</td><td>287</td><td>3005</td><td>255</td><td>0.0006</td></tr><tr><td>Statlogsatellite</td><td>4435</td><td>539</td><td>4432</td><td>531</td><td>0.0000</td></tr><tr><td>bankoj conv</td><td>4521</td><td>212</td><td>4520</td><td>207</td><td>0.0000</td></tr><tr><td>pendigits</td><td>7494</td><td>216</td><td>7415</td><td>108</td><td>0.0000</td></tr><tr><td>mushroom</td><td>8124</td><td>119</td><td>8124</td><td>100</td><td>0.0000</td></tr><tr><td>surgical-deepnet</td><td>14635</td><td>6047</td><td>11733</td><td>6046</td><td>0.0000</td></tr><tr><td>letter</td><td>20000</td><td>224</td><td>18200</td><td>112</td><td>0.0000</td></tr><tr><td>default_credit</td><td>30000</td><td>307</td><td>29823</td><td>304</td><td>0.0025</td></tr><tr><td>taiwan_binarised</td><td>30000</td><td>205</td><td>29112</td><td>198</td><td>0.0253</td></tr><tr><td>Statlog_shuttle</td><td>43500</td><td>746</td><td>23352</td><td>727</td><td>0.0000</td></tr><tr><td>bank</td><td>45211</td><td>9531</td><td>45211</td><td>9530</td><td>0.0000</td></tr><tr><td>mnist_0</td><td>60000</td><td>784</td><td>59987</td><td>671</td><td>0.0000</td></tr><tr><td>hand_posture</td><td>78095</td><td>3864</td><td>72896</td><td>3860</td><td>0.0000</td></tr><tr><td>weather-aus</td><td>142193</td><td>4759</td><td>142151</td><td>4756</td><td>0.0000</td></tr></tbody></table>
<table><caption>Table 5: Depth 3 – Test accuracy of CART and Blossom, without and with pruning (up to 1%, 3% or 0.3 · k²% loss)</caption><thead><tr><th rowspan="2"></th><th rowspan="2">single test</th><th>CART</th><th>Blossom</th><th>Blossom<sup>1%</sup></th><th>Blossom<sup>3%</sup></th><th>Blossom<sup>*</sup></th></tr><tr><th>test acc.</th><th>test acc.</th><th>test acc.</th><th>test acc.</th><th>test acc.</th></tr></thead><tbody><tr><td>adult_discretized</td><td>0.795</td><td>0.8095</td><td><strong>0.8346</strong></td><td>0.8286</td><td>0.8195</td><td>0.8335</td></tr><tr><td>anneal</td><td>0.808</td><td>0.8092</td><td><strong>0.8639</strong></td><td>0.8475</td><td>0.8374</td><td>0.8535</td></tr><tr><td>audiology</td><td>0.874</td><td><strong>0.9541</strong></td><td>0.9473</td><td>0.9414</td><td>0.9350</td><td>0.9423</td></tr><tr><td>(australian-credit)</td><td>0.871</td><td>0.8518</td><td><strong>0.8767</strong></td><td>0.8636</td><td>0.8585</td><td>0.8639</td></tr><tr><td>(balance-scale)</td><td>0.921</td><td>0.9202</td><td><strong>0.9206</strong></td><td><strong>0.9206</strong></td><td><strong>0.9206</strong></td><td><strong>0.9206</strong></td></tr><tr><td>bank</td><td>0.893</td><td><strong>0.9002</strong></td><td>0.8997</td><td>0.8979</td><td>0.8830</td><td>0.8987</td></tr><tr><td>(bank-)conv</td><td>0.891</td><td><strong>0.8972</strong></td><td>0.8949</td><td>0.8945</td><td>0.8844</td><td>0.8958</td></tr><tr><td>banknote</td><td>0.843</td><td>0.9087</td><td>0.9732</td><td>0.9734</td><td>0.9595</td><td><strong>0.9740</strong></td></tr><tr><td>biodeg</td><td>0.760</td><td>0.8004</td><td><strong>0.8185</strong></td><td>0.8143</td><td>0.8068</td><td>0.8180</td></tr><tr><td>breast-cancer</td><td>0.895</td><td>0.9381</td><td>0.9409</td><td>0.9396</td><td>0.9374</td><td><strong>0.9415</strong></td></tr><tr><td>breast-wisconsin</td><td>0.923</td><td>0.9422</td><td><strong>0.9586</strong></td><td>0.9574</td><td>0.9501</td><td>0.9585</td></tr><tr><td>car</td><td>0.714</td><td><strong>0.8758</strong></td><td>0.8717</td><td>0.8742</td><td>0.8723</td><td>0.8753</td></tr><tr><td>car_evaluation</td><td>0.699</td><td>0.8687</td><td>0.8617</td><td><strong>0.8768</strong></td><td>0.8761</td><td>0.8686</td></tr><tr><td>(chess)</td><td>1.000</td><td><strong>1.0000</strong></td><td><strong>1.0000</strong></td><td><strong>1.0000</strong></td><td><strong>1.0000</strong></td><td><strong>1.0000</strong></td></tr><tr><td>compas_discretized</td><td>0.644</td><td>0.6534</td><td>0.6701</td><td><strong>0.6717</strong></td><td>0.6643</td><td>0.6704</td></tr><tr><td>(default-credit)</td><td>0.820</td><td>0.8208</td><td><strong>0.8214</strong></td><td>0.8193</td><td>0.8190</td><td>0.8193</td></tr><tr><td>(diabetes)</td><td>0.744</td><td><strong>0.7492</strong></td><td>0.7348</td><td>0.7381</td><td>0.7342</td><td>0.7418</td></tr><tr><td>(forest-fires)</td><td>0.540</td><td>0.5367</td><td><strong>0.5427</strong></td><td>0.5381</td><td>0.5398</td><td>0.5390</td></tr><tr><td>(german-credit)</td><td>0.701</td><td>0.7105</td><td><strong>0.7376</strong></td><td>0.7275</td><td>0.7271</td><td>0.7273</td></tr><tr><td>handposture</td><td>0.794</td><td>0.8922</td><td><strong>0.9021</strong></td><td>0.8993</td><td>0.8993</td><td>0.8993</td></tr><tr><td>(heart-cleveland)</td><td>0.745</td><td><strong>0.7943</strong></td><td>0.7707</td><td>0.7830</td><td>0.7883</td><td>0.7787</td></tr><tr><td>(hepatitis)</td><td>0.826</td><td>0.7883</td><td><strong>0.7893</strong></td><td>0.7814</td><td>0.7807</td><td>0.7759</td></tr><tr><td>HTRU2</td><td>0.962</td><td>0.9764</td><td><strong>0.9766</strong></td><td>0.9752</td><td>0.9671</td><td>0.9752</td></tr><tr><td>hypothyroid</td><td>0.962</td><td>0.9790</td><td>0.9783</td><td>0.9784</td><td>0.9750</td><td><strong>0.9794</strong></td></tr><tr><td>(IndiansDiabetes)</td><td>0.738</td><td>0.7497</td><td><strong>0.7584</strong></td><td>0.7453</td><td>0.7404</td><td>0.7482</td></tr><tr><td>ionosphere</td><td>0.813</td><td><strong>0.8989</strong></td><td>0.8622</td><td>0.8676</td><td>0.8704</td><td>0.8670</td></tr><tr><td>iris</td><td>0.937</td><td>0.9807</td><td><strong>0.9893</strong></td><td>0.9827</td><td>0.9700</td><td>0.9847</td></tr><tr><td>kr-vs-kp</td><td>0.675</td><td>0.9040</td><td><strong>0.9382</strong></td><td>0.9362</td><td>0.9351</td><td>0.9362</td></tr><tr><td>letter</td><td>0.959</td><td>0.9655</td><td>0.9808</td><td><strong>0.9816</strong></td><td>0.9593</td><td><strong>0.9816</strong></td></tr><tr><td>letter_recognition</td><td>0.961</td><td>0.9912</td><td><strong>0.9924</strong></td><td>0.9876</td><td>0.9876</td><td>0.9917</td></tr><tr><td>lymph</td><td>0.799</td><td>0.7974</td><td>0.8000</td><td><strong>0.8213</strong></td><td>0.8155</td><td>0.8194</td></tr><tr><td>magic04</td><td>0.738</td><td>0.8009</td><td>0.8164</td><td>0.8125</td><td>0.8025</td><td><strong>0.8168</strong></td></tr><tr><td>messidor</td><td>0.591</td><td><strong>0.6576</strong></td><td>0.6479</td><td>0.6476</td><td>0.6434</td><td>0.6468</td></tr><tr><td>mnist_0</td><td>0.920</td><td>0.9423</td><td><strong>0.9558</strong></td><td>0.9504</td><td>0.9501</td><td>0.9554</td></tr><tr><td>monk1</td><td>0.733</td><td>0.8331</td><td><strong>0.8957</strong></td><td>0.8908</td><td>0.8908</td><td>0.8908</td></tr><tr><td>monk2</td><td>0.618</td><td>0.5629</td><td><strong>0.6522</strong></td><td>0.6347</td><td>0.6471</td><td>0.6341</td></tr><tr><td>monk3</td><td>0.754</td><td>0.9152</td><td><strong>0.9292</strong></td><td>0.9136</td><td>0.9272</td><td>0.9136</td></tr><tr><td>mushroom</td><td>0.887</td><td>0.9652</td><td><strong>0.9991</strong></td><td>0.9974</td><td>0.9852</td><td>0.9974</td></tr><tr><td>pendigits</td><td>0.932</td><td><strong>0.9921</strong></td><td>0.9918</td><td>0.9884</td><td>0.9795</td><td>0.9913</td></tr><tr><td>(primary-tumor)</td><td>0.789</td><td>0.7909</td><td><strong>0.8446</strong></td><td>0.8332</td><td>0.8362</td><td>0.8338</td></tr><tr><td>segment</td><td>0.983</td><td>0.9960</td><td><strong>0.9979</strong></td><td>0.9904</td><td>0.9902</td><td>0.9975</td></tr><tr><td>(seismic-bumps)</td><td>0.934</td><td>0.9314</td><td>0.9297</td><td><strong>0.9342</strong></td><td><strong>0.9342</strong></td><td>0.9297</td></tr><tr><td>soybean</td><td>0.850</td><td>0.9024</td><td>0.9397</td><td>0.9323</td><td>0.9304</td><td><strong>0.9413</strong></td></tr><tr><td>spambase</td><td>0.786</td><td><strong>0.8427</strong></td><td>0.8358</td><td>0.8356</td><td>0.8255</td><td>0.8403</td></tr><tr><td>splice-1</td><td>0.822</td><td>0.9085</td><td><strong>0.9329</strong></td><td>0.9305</td><td>0.9117</td><td>0.9305</td></tr><tr><td>Statlog.satellite</td><td>0.757</td><td>0.9165</td><td>0.9471</td><td><strong>0.9507</strong></td><td>0.9316</td><td><strong>0.9507</strong></td></tr><tr><td>Statlog.shuttle</td><td>0.928</td><td>0.9985</td><td><strong>0.9999</strong></td><td>0.9987</td><td>0.9987</td><td>0.9987</td></tr><tr><td>surgical-deepnet</td><td>0.786</td><td>0.8056</td><td><strong>0.8250</strong></td><td>0.8228</td><td>0.8099</td><td>0.8240</td></tr><tr><td>(taiwan_binarised)</td><td>0.820</td><td>0.8210</td><td><strong>0.8214</strong></td><td>0.8186</td><td>0.8159</td><td>0.8197</td></tr><tr><td>tic-tac-toe</td><td>0.698</td><td>0.7319</td><td>0.6942</td><td><strong>0.7353</strong></td><td>0.7303</td><td>0.7252</td></tr><tr><td>titanic</td><td>0.780</td><td>0.8163</td><td><strong>0.8191</strong></td><td>0.8179</td><td>0.8071</td><td>0.8163</td></tr><tr><td>vehicle</td><td>0.769</td><td>0.9087</td><td><strong>0.9656</strong></td><td>0.9628</td><td>0.9491</td><td>0.9622</td></tr><tr><td>(vote)</td><td>0.955</td><td>0.9491</td><td>0.9455</td><td>0.9452</td><td><strong>0.9498</strong></td><td>0.9395</td></tr><tr><td>(wine1)</td><td>0.677</td><td><strong>0.6789</strong></td><td>0.6611</td><td>0.6606</td><td>0.6606</td><td>0.6611</td></tr><tr><td>wine2</td><td>0.604</td><td><strong>0.6303</strong></td><td>0.6168</td><td>0.6232</td><td>0.6238</td><td>0.6232</td></tr><tr><td>(wine3)</td><td>0.726</td><td><strong>0.7211</strong></td><td>0.7189</td><td>0.7178</td><td>0.7172</td><td>0.7194</td></tr><tr><td>(winequality-red)</td><td>0.993</td><td>0.9922</td><td>0.9907</td><td><strong>0.9937</strong></td><td><strong>0.9937</strong></td><td><strong>0.9937</strong></td></tr><tr><td>yeast</td><td>0.701</td><td><strong>0.7148</strong></td><td>0.6925</td><td>0.6930</td><td>0.6899</td><td>0.6930</td></tr><tr><td>Average (all data sets)</td><td></td><td>0.8516</td><td><strong>0.8616</strong></td><td>0.8603</td><td>0.8559</td><td>0.8608</td></tr><tr><td>Average (filtered data sets)</td><td></td><td>0.8672</td><td>0.8804</td><td>0.8795</td><td>0.8736</td><td><strong>0.8804</strong></td></tr></tbody></table>
<table><caption>Table 6: Depth 4 – Test accuracy of CART and Blossom, without and with pruning (up to 1%, 3% or 0.3 · k²% loss)</caption><thead><tr><th rowspan="2"></th><th rowspan="2">single test</th><th>CART</th><th>Blossom</th><th>Blossom<sup>1%</sup></th><th>Blossom<sup>3%</sup></th><th>Blossom<sup>*</sup></th></tr><tr><th>test acc.</th><th>test acc.</th><th>test acc.</th><th>test acc.</th><th>test acc.</th></tr></thead><tbody><tr><td>adult_discretized</td><td>0.795</td><td>0.8269</td><td><strong>0.8477</strong></td><td>0.8412</td><td>0.8411</td><td>0.8452</td></tr><tr><td>anneal</td><td>0.808</td><td>0.8011</td><td><strong>0.8722</strong></td><td>0.8591</td><td>0.8502</td><td>0.8616</td></tr><tr><td>audiology</td><td>0.874</td><td><strong>0.9541</strong></td><td>0.9518</td><td>0.9418</td><td>0.9509</td><td>0.9436</td></tr><tr><td>(australian-credit)</td><td>0.871</td><td>0.8611</td><td><strong>0.8697</strong></td><td>0.8665</td><td>0.8605</td><td>0.8655</td></tr><tr><td>(balance-scale)</td><td>0.921</td><td>0.9125</td><td>0.9073</td><td><strong>0.9206</strong></td><td><strong>0.9206</strong></td><td>0.9133</td></tr><tr><td>bank</td><td>0.893</td><td>0.9006</td><td><strong>0.9016</strong></td><td>0.8959</td><td>0.8881</td><td>0.8994</td></tr><tr><td>(bank(conv)</td><td>0.891</td><td><strong>0.8999</strong></td><td>0.8939</td><td>0.8960</td><td>0.8953</td><td>0.8966</td></tr><tr><td>banknote</td><td>0.843</td><td>0.9631</td><td><strong>0.9877</strong></td><td>0.9821</td><td>0.9632</td><td>0.9842</td></tr><tr><td>biodeg</td><td>0.760</td><td>0.8191</td><td><strong>0.8253</strong></td><td>0.8207</td><td>0.8175</td><td>0.8206</td></tr><tr><td>breast-cancer</td><td>0.895</td><td><strong>0.9391</strong></td><td>0.9307</td><td>0.9334</td><td>0.9293</td><td>0.9343</td></tr><tr><td>breast-wisconsin</td><td>0.923</td><td>0.9476</td><td>0.9525</td><td><strong>0.9553</strong></td><td>0.9534</td><td>0.9530</td></tr><tr><td>car</td><td>0.714</td><td>0.8819</td><td><strong>0.9073</strong></td><td>0.8988</td><td>0.8920</td><td>0.9013</td></tr><tr><td>car_evaluation</td><td>0.699</td><td><strong>0.9210</strong></td><td>0.9164</td><td>0.9180</td><td>0.9186</td><td>0.9182</td></tr><tr><td>(chess)</td><td>1.000</td><td><strong>1.0000</strong></td><td><strong>1.0000</strong></td><td><strong>1.0000</strong></td><td><strong>1.0000</strong></td><td><strong>1.0000</strong></td></tr><tr><td>compas_discretized</td><td>0.644</td><td>0.6638</td><td>0.6696</td><td>0.6726</td><td><strong>0.6739</strong></td><td>0.6719</td></tr><tr><td>(default_credi)</td><td>0.820</td><td><strong>0.8209</strong></td><td>0.8209</td><td>0.8196</td><td>0.8196</td><td>0.8196</td></tr><tr><td>(diabetes)</td><td>0.744</td><td>0.7416</td><td><strong>0.7439</strong></td><td>0.7375</td><td>0.7355</td><td>0.7374</td></tr><tr><td>(forest-fires)</td><td>0.540</td><td>0.5438</td><td><strong>0.5646</strong></td><td>0.5425</td><td>0.5435</td><td>0.5425</td></tr><tr><td>(german-credit)</td><td>0.701</td><td>0.7090</td><td>0.7230</td><td><strong>0.7241</strong></td><td>0.7240</td><td>0.7193</td></tr><tr><td>handposture</td><td>0.794</td><td>0.9211</td><td><strong>0.9360</strong></td><td>0.9352</td><td>0.9228</td><td>0.9352</td></tr><tr><td>(heart-cleveland)</td><td>0.745</td><td>0.7640</td><td>0.7820</td><td>0.7777</td><td><strong>0.7887</strong></td><td>0.7757</td></tr><tr><td>(hepatitis)</td><td>0.826</td><td><strong>0.7766</strong></td><td>0.7587</td><td>0.7628</td><td>0.7745</td><td>0.7566</td></tr><tr><td>HTRU2</td><td>0.962</td><td><strong>0.9765</strong></td><td>0.9764</td><td>0.9729</td><td>0.9651</td><td>0.9741</td></tr><tr><td>hypothyroid</td><td>0.962</td><td>0.9810</td><td>0.9796</td><td>0.9786</td><td>0.9660</td><td><strong>0.9812</strong></td></tr><tr><td>(IndiansDiabetes)</td><td>0.738</td><td><strong>0.7568</strong></td><td>0.7371</td><td>0.7277</td><td>0.7252</td><td>0.7288</td></tr><tr><td>ionosphere</td><td>0.813</td><td>0.8704</td><td>0.8578</td><td>0.8758</td><td><strong>0.8806</strong></td><td>0.8721</td></tr><tr><td>iris</td><td>0.937</td><td>0.9807</td><td><strong>0.9893</strong></td><td>0.9827</td><td>0.9700</td><td>0.9847</td></tr><tr><td>kr-vs-kp</td><td>0.675</td><td>0.9391</td><td><strong>0.9561</strong></td><td>0.9489</td><td>0.9361</td><td>0.9512</td></tr><tr><td>letter</td><td>0.959</td><td>0.9771</td><td><strong>0.9857</strong></td><td>0.9853</td><td>0.9593</td><td>0.9853</td></tr><tr><td>letter_recognition</td><td>0.961</td><td>0.9922</td><td><strong>0.9933</strong></td><td>0.9889</td><td>0.9881</td><td>0.9916</td></tr><tr><td>lymph</td><td>0.799</td><td>0.8258</td><td>0.8325</td><td>0.8342</td><td><strong>0.8484</strong></td><td>0.8277</td></tr><tr><td>magic04</td><td>0.738</td><td>0.8221</td><td><strong>0.8316</strong></td><td>0.8267</td><td>0.8131</td><td>0.8294</td></tr><tr><td>messidor</td><td>0.591</td><td><strong>0.6460</strong></td><td>0.6340</td><td>0.6360</td><td>0.6397</td><td>0.6348</td></tr><tr><td>mnist_0</td><td>0.920</td><td>0.9599</td><td><strong>0.9606</strong></td><td>0.9561</td><td>0.9431</td><td>0.9571</td></tr><tr><td>monk1</td><td>0.733</td><td>0.8462</td><td>0.9557</td><td><strong>0.9592</strong></td><td>0.9569</td><td><strong>0.9592</strong></td></tr><tr><td>monk2</td><td>0.618</td><td>0.5906</td><td>0.6367</td><td>0.6388</td><td><strong>0.6476</strong></td><td>0.6288</td></tr><tr><td>monk3</td><td>0.754</td><td><strong>0.9152</strong></td><td>0.8708</td><td>0.8832</td><td>0.8640</td><td>0.8832</td></tr><tr><td>mushroom</td><td>0.887</td><td>0.9991</td><td><strong>1.0000</strong></td><td>0.9941</td><td>0.9852</td><td>0.9989</td></tr><tr><td>pendigits</td><td>0.932</td><td><strong>0.9957</strong></td><td>0.9950</td><td>0.9899</td><td>0.9803</td><td>0.9924</td></tr><tr><td>(primary-tumor)</td><td>0.789</td><td>0.8074</td><td><strong>0.8571</strong></td><td>0.8450</td><td>0.8412</td><td>0.8444</td></tr><tr><td>segment</td><td>0.983</td><td>0.9975</td><td><strong>0.9984</strong></td><td>0.9956</td><td>0.9830</td><td>0.9960</td></tr><tr><td>(seismic_bumps)</td><td>0.934</td><td>0.9316</td><td>0.9303</td><td>0.9276</td><td><strong>0.9342</strong></td><td>0.9266</td></tr><tr><td>soybean</td><td>0.850</td><td>0.9266</td><td>0.9569</td><td>0.9573</td><td>0.9461</td><td><strong>0.9609</strong></td></tr><tr><td>spambase</td><td>0.786</td><td>0.8538</td><td>0.8585</td><td>0.8536</td><td>0.8383</td><td><strong>0.8586</strong></td></tr><tr><td>splice-1</td><td>0.822</td><td>0.9529</td><td><strong>0.9571</strong></td><td>0.9468</td><td>0.9457</td><td>0.9535</td></tr><tr><td>Statlog.satellite</td><td>0.757</td><td>0.9378</td><td>0.9614</td><td>0.9606</td><td>0.9509</td><td><strong>0.9618</strong></td></tr><tr><td>Statlog.shuttle</td><td>0.928</td><td>0.9989</td><td><strong>0.9999</strong></td><td>0.9961</td><td>0.9961</td><td>0.9969</td></tr><tr><td>surgical-deepnet</td><td>0.786</td><td>0.8137</td><td><strong>0.8447</strong></td><td>0.8338</td><td>0.8194</td><td>0.8402</td></tr><tr><td>(taiwan_binarised)</td><td>0.820</td><td><strong>0.8209</strong></td><td>0.8206</td><td>0.8196</td><td>0.8193</td><td>0.8198</td></tr><tr><td>tic-tac-toe</td><td>0.698</td><td><strong>0.8147</strong></td><td>0.7856</td><td>0.8045</td><td>0.8101</td><td>0.8008</td></tr><tr><td>titanic</td><td>0.780</td><td>0.8210</td><td><strong>0.8296</strong></td><td>0.8175</td><td>0.8133</td><td>0.8180</td></tr><tr><td>vehicle</td><td>0.769</td><td>0.9367</td><td><strong>0.9659</strong></td><td>0.9579</td><td>0.9473</td><td>0.9609</td></tr><tr><td>(vote)</td><td>0.955</td><td>0.9427</td><td><strong>0.9455</strong></td><td>0.9425</td><td>0.9425</td><td>0.9400</td></tr><tr><td>(wine1)</td><td>0.677</td><td><strong>0.6789</strong></td><td>0.6600</td><td>0.6578</td><td>0.6583</td><td>0.6583</td></tr><tr><td>wine2</td><td>0.604</td><td>0.6470</td><td>0.6274</td><td>0.6465</td><td><strong>0.6476</strong></td><td>0.6465</td></tr><tr><td>(wine3)</td><td>0.726</td><td>0.7217</td><td><strong>0.7300</strong></td><td>0.7167</td><td>0.7150</td><td>0.7167</td></tr><tr><td>(winequality-red)</td><td>0.993</td><td>0.9909</td><td>0.9917</td><td><strong>0.9937</strong></td><td><strong>0.9937</strong></td><td>0.9937</td></tr><tr><td>yeast</td><td>0.701</td><td><strong>0.7168</strong></td><td>0.6795</td><td>0.6900</td><td>0.6895</td><td>0.6896</td></tr><tr><td>Average (all data sets)</td><td></td><td>0.8613</td><td><strong>0.8682</strong></td><td>0.8663</td><td>0.8625</td><td>0.8665</td></tr><tr><td>Average (filtered data sets)</td><td></td><td>0.8819</td><td><strong>0.8905</strong></td><td>0.8891</td><td>0.8833</td><td>0.8901</td></tr></tbody></table>
<table><caption>Table 7: Depth 5 – Test accuracy of CART and Blossom, without and with pruning (up to 1%, 3% or 0.3 · k²% loss)</caption><thead><tr><th rowspan="2"></th><th rowspan="2">single test</th><th>CART</th><th>Blossom</th><th>Blossom<sup>1%</sup></th><th>Blossom<sup>3%</sup></th><th>Blossom<sup>*</sup></th></tr><tr><th>test acc.</th><th>test acc.</th><th>test acc.</th><th>test acc.</th><th>test acc.</th></tr></thead><tbody><tr><td>adult_discretized</td><td>0.795</td><td>0.8401</td><td><strong>0.8520</strong></td><td>0.8459</td><td>0.8398</td><td>0.8474</td></tr><tr><td>anneal</td><td>0.808</td><td>0.8226</td><td><strong>0.8776</strong></td><td>0.8677</td><td>0.8629</td><td>0.8682</td></tr><tr><td>audiology</td><td>0.874</td><td><strong>0.9582</strong></td><td>0.9373</td><td>0.9418</td><td>0.9445</td><td>0.9418</td></tr><tr><td>(australian-credit)</td><td>0.871</td><td><strong>0.8573</strong></td><td>0.8342</td><td>0.8397</td><td>0.8482</td><td>0.8365</td></tr><tr><td>(balance-scale)</td><td>0.921</td><td>0.8987</td><td>0.8857</td><td>0.8887</td><td><strong>0.9206</strong></td><td>0.8867</td></tr><tr><td>bank</td><td>0.893</td><td>0.9008</td><td><strong>0.9024</strong></td><td>0.9002</td><td>0.8994</td><td>0.9004</td></tr><tr><td>(bank(conv)</td><td>0.891</td><td>0.8968</td><td>0.8946</td><td>0.8966</td><td>0.8953</td><td><strong>0.8969</strong></td></tr><tr><td>banknote</td><td>0.843</td><td>0.9826</td><td><strong>0.9896</strong></td><td>0.9820</td><td>0.9688</td><td>0.9825</td></tr><tr><td>biodeg</td><td>0.760</td><td>0.8250</td><td>0.8275</td><td>0.8280</td><td>0.8251</td><td><strong>0.8288</strong></td></tr><tr><td>breast-cancer</td><td>0.895</td><td><strong>0.9390</strong></td><td>0.9357</td><td>0.9331</td><td>0.9334</td><td>0.9331</td></tr><tr><td>breast-wisconsin</td><td>0.923</td><td>0.9491</td><td>0.9443</td><td>0.9514</td><td><strong>0.9521</strong></td><td>0.9502</td></tr><tr><td>car</td><td>0.714</td><td>0.9349</td><td><strong>0.9397</strong></td><td>0.9289</td><td>0.9283</td><td>0.9284</td></tr><tr><td>car_evaluation</td><td>0.699</td><td>0.9250</td><td><strong>0.9460</strong></td><td>0.9410</td><td>0.9372</td><td>0.9431</td></tr><tr><td>(chess)</td><td>1.000</td><td><strong>1.0000</strong></td><td><strong>1.0000</strong></td><td><strong>1.0000</strong></td><td><strong>1.0000</strong></td><td><strong>1.0000</strong></td></tr><tr><td>compas_discretized</td><td>0.644</td><td>0.6733</td><td>0.6697</td><td>0.6711</td><td><strong>0.6732</strong></td><td>0.6709</td></tr><tr><td>(default_credi)</td><td>0.820</td><td>0.8203</td><td><strong>0.8213</strong></td><td>0.8196</td><td>0.8196</td><td>0.8200</td></tr><tr><td>(diabetes)</td><td>0.744</td><td><strong>0.7368</strong></td><td>0.7140</td><td>0.7271</td><td>0.7270</td><td>0.7266</td></tr><tr><td>(forest-fires)</td><td>0.540</td><td>0.5462</td><td><strong>0.5585</strong></td><td>0.5365</td><td>0.5356</td><td>0.5367</td></tr><tr><td>(german-credit)</td><td>0.701</td><td>0.6988</td><td>0.7144</td><td>0.7205</td><td><strong>0.7272</strong></td><td>0.7191</td></tr><tr><td>handposture</td><td>0.794</td><td>0.9559</td><td><strong>0.9581</strong></td><td>0.9572</td><td>0.9368</td><td>0.9572</td></tr><tr><td>(heart-cleveland)</td><td>0.745</td><td>0.7487</td><td><strong>0.7727</strong></td><td>0.7563</td><td>0.7593</td><td>0.7527</td></tr><tr><td>(hepatitis)</td><td>0.826</td><td><strong>0.7614</strong></td><td>0.7400</td><td>0.7441</td><td>0.7545</td><td>0.7448</td></tr><tr><td>HTRU2</td><td>0.962</td><td>0.9767</td><td><strong>0.9772</strong></td><td>0.9736</td><td>0.9637</td><td>0.9742</td></tr><tr><td>hypothyroid</td><td>0.962</td><td><strong>0.9803</strong></td><td>0.9781</td><td>0.9783</td><td>0.9715</td><td>0.9792</td></tr><tr><td>(IndiansDiabetes)</td><td>0.738</td><td><strong>0.7304</strong></td><td>0.7086</td><td>0.7138</td><td>0.7175</td><td>0.7118</td></tr><tr><td>ionosphere</td><td>0.813</td><td>0.8769</td><td>0.8689</td><td>0.8738</td><td><strong>0.8772</strong></td><td>0.8738</td></tr><tr><td>iris</td><td>0.937</td><td>0.9807</td><td><strong>0.9893</strong></td><td>0.9827</td><td>0.9700</td><td>0.9847</td></tr><tr><td>kr-vs-kp</td><td>0.675</td><td>0.9391</td><td><strong>0.9712</strong></td><td>0.9633</td><td>0.9499</td><td>0.9653</td></tr><tr><td>letter</td><td>0.959</td><td>0.9814</td><td><strong>0.9886</strong></td><td>0.9845</td><td>0.9845</td><td>0.9848</td></tr><tr><td>letter_recognition</td><td>0.961</td><td>0.9931</td><td><strong>0.9945</strong></td><td>0.9887</td><td>0.9867</td><td>0.9898</td></tr><tr><td>lymph</td><td>0.799</td><td><strong>0.8161</strong></td><td>0.8150</td><td>0.8097</td><td>0.8142</td><td>0.8071</td></tr><tr><td>magic04</td><td>0.738</td><td>0.8281</td><td><strong>0.8410</strong></td><td>0.8370</td><td>0.8223</td><td>0.8374</td></tr><tr><td>messidor</td><td>0.591</td><td>0.6432</td><td><strong>0.6452</strong></td><td>0.6314</td><td>0.6346</td><td>0.6322</td></tr><tr><td>mnist_0</td><td>0.920</td><td>0.9649</td><td><strong>0.9688</strong></td><td>0.9622</td><td>0.9500</td><td>0.9667</td></tr><tr><td>monk1</td><td>0.733</td><td>0.8415</td><td><strong>1.0000</strong></td><td><strong>1.0000</strong></td><td>0.9915</td><td><strong>1.0000</strong></td></tr><tr><td>monk2</td><td>0.618</td><td>0.5900</td><td><strong>0.7033</strong></td><td>0.6824</td><td>0.6806</td><td>0.6824</td></tr><tr><td>monk3</td><td>0.754</td><td><strong>0.9048</strong></td><td>0.8246</td><td>0.8184</td><td>0.8232</td><td>0.8184</td></tr><tr><td>mushroom</td><td>0.887</td><td>0.9995</td><td><strong>1.0000</strong></td><td>0.9941</td><td>0.9852</td><td>0.9947</td></tr><tr><td>pendigits</td><td>0.932</td><td>0.9966</td><td><strong>0.9970</strong></td><td>0.9915</td><td>0.9811</td><td>0.9930</td></tr><tr><td>(primary-tumor)</td><td>0.789</td><td>0.8003</td><td>0.8103</td><td>0.8047</td><td><strong>0.8221</strong></td><td>0.8009</td></tr><tr><td>segment</td><td>0.983</td><td>0.9975</td><td><strong>0.9982</strong></td><td>0.9955</td><td>0.9830</td><td>0.9956</td></tr><tr><td>(seismic_bumps)</td><td>0.934</td><td>0.9296</td><td>0.9151</td><td>0.9223</td><td><strong>0.9342</strong></td><td>0.9215</td></tr><tr><td>soybean</td><td>0.850</td><td>0.9435</td><td>0.9459</td><td><strong>0.9546</strong></td><td>0.9534</td><td>0.9520</td></tr><tr><td>spambase</td><td>0.786</td><td>0.8652</td><td><strong>0.8741</strong></td><td>0.8701</td><td>0.8596</td><td>0.8716</td></tr><tr><td>splice-1</td><td>0.822</td><td>0.9527</td><td>0.9519</td><td>0.9561</td><td>0.9409</td><td><strong>0.9563</strong></td></tr><tr><td>Statlog.satellite</td><td>0.757</td><td>0.9593</td><td>0.9657</td><td>0.9665</td><td>0.9528</td><td><strong>0.9671</strong></td></tr><tr><td>Statlog.shuttle</td><td>0.928</td><td>0.9995</td><td><strong>0.9999</strong></td><td>0.9961</td><td>0.9961</td><td>0.9961</td></tr><tr><td>surgical-deepnet</td><td>0.786</td><td>0.8342</td><td><strong>0.8499</strong></td><td>0.8467</td><td>0.8350</td><td>0.8481</td></tr><tr><td>(taiwan_binarised)</td><td>0.820</td><td><strong>0.8202</strong></td><td>0.8194</td><td>0.8195</td><td>0.8196</td><td>0.8202</td></tr><tr><td>tic-tac-toe</td><td>0.698</td><td><strong>0.8994</strong></td><td>0.8581</td><td>0.8830</td><td>0.8738</td><td>0.8827</td></tr><tr><td>titanic</td><td>0.780</td><td><strong>0.8164</strong></td><td>0.8131</td><td>0.8093</td><td>0.8111</td><td>0.8089</td></tr><tr><td>vehicle</td><td>0.769</td><td>0.9459</td><td>0.9553</td><td><strong>0.9564</strong></td><td>0.9478</td><td>0.9547</td></tr><tr><td>(vote)</td><td>0.955</td><td>0.9427</td><td>0.9291</td><td>0.9395</td><td><strong>0.9473</strong></td><td>0.9373</td></tr><tr><td>(wine1)</td><td>0.677</td><td><strong>0.6800</strong></td><td>0.6678</td><td>0.6578</td><td>0.6572</td><td>0.6578</td></tr><tr><td>wine2</td><td>0.604</td><td>0.6519</td><td>0.6379</td><td>0.6595</td><td><strong>0.6605</strong></td><td>0.6595</td></tr><tr><td>(wine3)</td><td>0.726</td><td><strong>0.7200</strong></td><td>0.7133</td><td>0.7056</td><td>0.7050</td><td>0.7056</td></tr><tr><td>(winequality-red)</td><td>0.993</td><td>0.9895</td><td>0.9884</td><td><strong>0.9937</strong></td><td><strong>0.9937</strong></td><td><strong>0.9937</strong></td></tr><tr><td>yeast</td><td>0.701</td><td><strong>0.7136</strong></td><td>0.6943</td><td>0.6980</td><td>0.7014</td><td>0.6979</td></tr><tr><td>Average (all data sets)</td><td></td><td>0.8651</td><td><strong>0.8685</strong></td><td>0.8672</td><td>0.8653</td><td>0.8672</td></tr><tr><td>Average (filtered data sets)</td><td></td><td>0.8900</td><td><strong>0.8972</strong></td><td>0.8953</td><td>0.8901</td><td>0.8957</td></tr></tbody></table>
<table><caption>Table 8: Depth 6 – Test accuracy of CART and Blossom, without and with pruning (up to 1%, 3% or 0.3 · k²% loss)</caption><thead><tr><th rowspan="2"></th><th rowspan="2">single test</th><th>CART</th><th>Blossom</th><th>Blossom<sup>1%</sup></th><th>Blossom<sup>3%</sup></th><th>Blossom<sup>*</sup></th></tr><tr><th>test acc.</th><th>test acc.</th><th>test acc.</th><th>test acc.</th><th>test acc.</th></tr></thead><tbody><tr><td>adult_discretized</td><td>0.795</td><td>0.8473</td><td><strong>0.8540</strong></td><td>0.8491</td><td>0.8385</td><td>0.8483</td></tr><tr><td>anneal</td><td>0.808</td><td>0.8394</td><td><strong>0.8729</strong></td><td>0.8550</td><td>0.8523</td><td>0.8545</td></tr><tr><td>audiology</td><td>0.874</td><td><strong>0.9555</strong></td><td>0.9382</td><td>0.9514</td><td>0.9473</td><td>0.9514</td></tr><tr><td>(australian-credit)</td><td>0.871</td><td><strong>0.8468</strong></td><td>0.8176</td><td>0.8277</td><td>0.8395</td><td>0.8277</td></tr><tr><td>(balance-scale)</td><td>0.921</td><td><strong>0.8865</strong></td><td>0.8390</td><td>0.8556</td><td>0.8819</td><td>0.8592</td></tr><tr><td>bank</td><td>0.893</td><td>0.9005</td><td><strong>0.9023</strong></td><td>0.9016</td><td>0.8984</td><td>0.9010</td></tr><tr><td>(bank-)conv</td><td>0.891</td><td>0.8964</td><td>0.8937</td><td>0.8956</td><td><strong>0.8970</strong></td><td>0.8958</td></tr><tr><td>banknote</td><td>0.843</td><td>0.9865</td><td><strong>0.9899</strong></td><td>0.9826</td><td>0.9707</td><td>0.9819</td></tr><tr><td>biodeg</td><td>0.760</td><td>0.8250</td><td>0.8311</td><td><strong>0.8364</strong></td><td>0.8358</td><td>0.8363</td></tr><tr><td>breast-cancer</td><td>0.895</td><td><strong>0.9371</strong></td><td>0.9258</td><td>0.9327</td><td>0.9349</td><td>0.9327</td></tr><tr><td>breast-wisconsin</td><td>0.923</td><td>0.9448</td><td>0.9458</td><td>0.9485</td><td><strong>0.9561</strong></td><td>0.9485</td></tr><tr><td>car</td><td>0.714</td><td>0.9348</td><td><strong>0.9710</strong></td><td>0.9663</td><td>0.9552</td><td>0.9658</td></tr><tr><td>car_evaluation</td><td>0.699</td><td><strong>0.9403</strong></td><td>0.9296</td><td>0.9379</td><td>0.9325</td><td>0.9372</td></tr><tr><td>(chess)</td><td>1.000</td><td><strong>1.0000</strong></td><td><strong>1.0000</strong></td><td><strong>1.0000</strong></td><td><strong>1.0000</strong></td><td><strong>1.0000</strong></td></tr><tr><td>compas_discretized</td><td>0.644</td><td><strong>0.6694</strong></td><td>0.6654</td><td>0.6684</td><td>0.6694</td><td>0.6686</td></tr><tr><td>(default-credit)</td><td>0.820</td><td><strong>0.8199</strong></td><td>0.8193</td><td>0.8197</td><td>0.8196</td><td>0.8198</td></tr><tr><td>(diabetes)</td><td>0.744</td><td>0.7199</td><td>0.6891</td><td>0.7149</td><td><strong>0.7209</strong></td><td>0.7149</td></tr><tr><td>(forest-fires)</td><td>0.540</td><td>0.5515</td><td><strong>0.5596</strong></td><td>0.5390</td><td>0.5388</td><td>0.5390</td></tr><tr><td>(german-credit)</td><td>0.701</td><td>0.6962</td><td>0.6998</td><td>0.7017</td><td><strong>0.7078</strong></td><td>0.7009</td></tr><tr><td>handposture</td><td>0.794</td><td>0.9777</td><td><strong>0.9790</strong></td><td>0.9784</td><td>0.9554</td><td>0.9784</td></tr><tr><td>(heart-cleveland)</td><td>0.745</td><td>0.7423</td><td>0.7440</td><td>0.7553</td><td><strong>0.7643</strong></td><td>0.7570</td></tr><tr><td>(hepatitis)</td><td>0.826</td><td><strong>0.7628</strong></td><td>0.7360</td><td>0.7503</td><td>0.7566</td><td>0.7503</td></tr><tr><td>HTRU2</td><td>0.962</td><td><strong>0.9768</strong></td><td>0.9767</td><td>0.9759</td><td>0.9710</td><td>0.9759</td></tr><tr><td>hypothyroid</td><td>0.962</td><td><strong>0.9796</strong></td><td>0.9778</td><td>0.9763</td><td>0.9684</td><td>0.9760</td></tr><tr><td>(IndiansDiabetes)</td><td>0.738</td><td><strong>0.7279</strong></td><td>0.7026</td><td>0.6981</td><td>0.7045</td><td>0.6981</td></tr><tr><td>ionosphere</td><td>0.813</td><td>0.8777</td><td>0.8806</td><td>0.8814</td><td><strong>0.8887</strong></td><td>0.8868</td></tr><tr><td>iris</td><td>0.937</td><td>0.9807</td><td><strong>0.9893</strong></td><td>0.9827</td><td>0.9700</td><td>0.9827</td></tr><tr><td>kr-vs-kp</td><td>0.675</td><td>0.9363</td><td><strong>0.9734</strong></td><td>0.9680</td><td>0.9518</td><td>0.9672</td></tr><tr><td>letter</td><td>0.959</td><td>0.9866</td><td><strong>0.9894</strong></td><td>0.9858</td><td>0.9839</td><td>0.9849</td></tr><tr><td>letter_recognition</td><td>0.961</td><td>0.9938</td><td><strong>0.9939</strong></td><td>0.9893</td><td>0.9892</td><td>0.9893</td></tr><tr><td>lymph</td><td>0.799</td><td><strong>0.8277</strong></td><td>0.8125</td><td>0.8058</td><td>0.8123</td><td>0.8058</td></tr><tr><td>magic04</td><td>0.738</td><td>0.8371</td><td><strong>0.8467</strong></td><td>0.8423</td><td>0.8313</td><td>0.8418</td></tr><tr><td>messidor</td><td>0.591</td><td><strong>0.6306</strong></td><td>0.6250</td><td>0.6270</td><td>0.6296</td><td>0.6274</td></tr><tr><td>mnist_0</td><td>0.920</td><td>0.9678</td><td><strong>0.9719</strong></td><td>0.9669</td><td>0.9612</td><td>0.9662</td></tr><tr><td>monk1</td><td>0.733</td><td>0.8423</td><td><strong>1.0000</strong></td><td><strong>1.0000</strong></td><td>0.9915</td><td><strong>1.0000</strong></td></tr><tr><td>monk2</td><td>0.618</td><td>0.6606</td><td><strong>0.8800</strong></td><td>0.8488</td><td>0.8276</td><td>0.8488</td></tr><tr><td>monk3</td><td>0.754</td><td><strong>0.8928</strong></td><td>0.8277</td><td>0.8544</td><td>0.8712</td><td>0.8680</td></tr><tr><td>mushroom</td><td>0.887</td><td>0.9997</td><td><strong>1.0000</strong></td><td>0.9941</td><td>0.9852</td><td>0.9941</td></tr><tr><td>pendigits</td><td>0.932</td><td><strong>0.9974</strong></td><td>0.9970</td><td>0.9914</td><td>0.9847</td><td>0.9911</td></tr><tr><td>(primary-tumor)</td><td>0.789</td><td><strong>0.8065</strong></td><td>0.7886</td><td>0.7821</td><td>0.7941</td><td>0.7821</td></tr><tr><td>segment</td><td>0.983</td><td>0.9972</td><td><strong>0.9982</strong></td><td>0.9955</td><td>0.9830</td><td>0.9955</td></tr><tr><td>(seismic_bumps)</td><td>0.934</td><td><strong>0.9269</strong></td><td>0.9127</td><td>0.9163</td><td>0.9227</td><td>0.9163</td></tr><tr><td>soybean</td><td>0.850</td><td><strong>0.9469</strong></td><td>0.9413</td><td>0.9457</td><td>0.9452</td><td>0.9457</td></tr><tr><td>spambase</td><td>0.786</td><td>0.8753</td><td><strong>0.8801</strong></td><td>0.8786</td><td>0.8717</td><td>0.8784</td></tr><tr><td>splice-1</td><td>0.822</td><td><strong>0.9552</strong></td><td>0.9436</td><td>0.9537</td><td>0.9513</td><td>0.9536</td></tr><tr><td>Statlog.satellite</td><td>0.757</td><td>0.9633</td><td>0.9659</td><td><strong>0.9661</strong></td><td>0.9559</td><td>0.9656</td></tr><tr><td>Statlog.shuttle</td><td>0.928</td><td>0.9996</td><td><strong>0.9999</strong></td><td>0.9961</td><td>0.9961</td><td>0.9961</td></tr><tr><td>surgical-deepnet</td><td>0.786</td><td>0.8510</td><td><strong>0.8606</strong></td><td>0.8555</td><td>0.8462</td><td>0.8554</td></tr><tr><td>(taiwan_binarised)</td><td>0.820</td><td>0.8196</td><td>0.8175</td><td>0.8196</td><td>0.8196</td><td><strong>0.8199</strong></td></tr><tr><td>tic-tac-toe</td><td>0.698</td><td>0.9231</td><td>0.9223</td><td><strong>0.9321</strong></td><td>0.9211</td><td>0.9320</td></tr><tr><td>titanic</td><td>0.780</td><td>0.8120</td><td>0.8164</td><td>0.8092</td><td><strong>0.8174</strong></td><td>0.8103</td></tr><tr><td>vehicle</td><td>0.769</td><td>0.9489</td><td><strong>0.9659</strong></td><td>0.9579</td><td>0.9551</td><td>0.9576</td></tr><tr><td>(vote)</td><td>0.955</td><td>0.9380</td><td>0.9436</td><td>0.9455</td><td><strong>0.9509</strong></td><td>0.9455</td></tr><tr><td>(wine1)</td><td>0.677</td><td><strong>0.6694</strong></td><td>0.6678</td><td>0.6461</td><td>0.6444</td><td>0.6461</td></tr><tr><td>wine2</td><td>0.604</td><td>0.6497</td><td>0.6411</td><td>0.6562</td><td><strong>0.6573</strong></td><td>0.6562</td></tr><tr><td>(wine3)</td><td>0.726</td><td><strong>0.7183</strong></td><td>0.6956</td><td>0.7022</td><td>0.7017</td><td>0.7022</td></tr><tr><td>(winequality-red)</td><td>0.993</td><td>0.9878</td><td>0.9897</td><td><strong>0.9937</strong></td><td><strong>0.9937</strong></td><td><strong>0.9937</strong></td></tr><tr><td>yeast</td><td>0.701</td><td>0.7074</td><td><strong>0.7129</strong></td><td>0.7054</td><td>0.7086</td><td>0.7054</td></tr><tr><td>Average (all data sets)</td><td></td><td>0.8671</td><td>0.8709</td><td>0.8709</td><td>0.8695</td><td><strong>0.8712</strong></td></tr><tr><td>Average (filtered data sets)</td><td></td><td>0.8944</td><td><strong>0.9049</strong></td><td>0.9038</td><td>0.8993</td><td>0.9041</td></tr></tbody></table>
<table><caption>Table 9: Depth 7 – Test accuracy of CART and Blossom, without and with pruning (up to 1%, 3% or 0.3 · k²% loss)</caption><thead><tr><th rowspan="2"></th><th rowspan="2">single test</th><th>CART</th><th>Blossom</th><th>Blossom<sup>1%</sup></th><th>Blossom<sup>3%</sup></th><th>Blossom<sup>*</sup></th></tr><tr><th>test acc.</th><th>test acc.</th><th>test acc.</th><th>test acc.</th><th>test acc.</th></tr></thead><tbody><tr><td>adult_discretized</td><td>0.795</td><td>0.8490</td><td><strong>0.8535</strong></td><td>0.8511</td><td>0.8426</td><td>0.8489</td></tr><tr><td>anneal</td><td>0.808</td><td>0.8480</td><td><strong>0.8724</strong></td><td>0.8601</td><td>0.8618</td><td>0.8611</td></tr><tr><td>audiology</td><td>0.874</td><td><strong>0.9555</strong></td><td>0.9382</td><td>0.9505</td><td>0.9473</td><td>0.9505</td></tr><tr><td>(australian-credit)</td><td>0.871</td><td><strong>0.8371</strong></td><td>0.8018</td><td>0.8189</td><td>0.8291</td><td>0.8215</td></tr><tr><td>(balance-scale)</td><td>0.921</td><td><strong>0.8600</strong></td><td>0.7844</td><td>0.8019</td><td>0.8308</td><td>0.8116</td></tr><tr><td>bank</td><td>0.893</td><td>0.9009</td><td>0.9018</td><td><strong>0.9027</strong></td><td>0.8987</td><td>0.9020</td></tr><tr><td>(bank(conv)</td><td>0.891</td><td>0.8931</td><td>0.8920</td><td>0.8952</td><td><strong>0.8973</strong></td><td>0.8967</td></tr><tr><td>banknote</td><td>0.843</td><td><strong>0.9894</strong></td><td>0.9890</td><td>0.9817</td><td>0.9729</td><td>0.9801</td></tr><tr><td>biodeg</td><td>0.760</td><td>0.8248</td><td>0.8221</td><td>0.8282</td><td><strong>0.8327</strong></td><td>0.8287</td></tr><tr><td>breast-cancer</td><td>0.895</td><td>0.9339</td><td>0.9328</td><td>0.9368</td><td><strong>0.9439</strong></td><td>0.9374</td></tr><tr><td>breast-wisconsin</td><td>0.923</td><td>0.9416</td><td>0.9414</td><td>0.9476</td><td><strong>0.9509</strong></td><td>0.9486</td></tr><tr><td>car</td><td>0.714</td><td>0.9646</td><td><strong>0.9724</strong></td><td>0.9665</td><td>0.9555</td><td>0.9639</td></tr><tr><td>car_evaluation</td><td>0.699</td><td><strong>0.9376</strong></td><td>0.9146</td><td>0.9349</td><td>0.9299</td><td>0.9349</td></tr><tr><td>(chess)</td><td>1.000</td><td><strong>1.0000</strong></td><td><strong>1.0000</strong></td><td><strong>1.0000</strong></td><td><strong>1.0000</strong></td><td><strong>1.0000</strong></td></tr><tr><td>compas_discretized</td><td>0.644</td><td>0.6666</td><td>0.6633</td><td>0.6672</td><td><strong>0.6688</strong></td><td>0.6680</td></tr><tr><td>(default_credi)</td><td>0.820</td><td>0.8188</td><td>0.8177</td><td>0.8188</td><td><strong>0.8196</strong></td><td>0.8192</td></tr><tr><td>(diabetes)</td><td>0.744</td><td><strong>0.7179</strong></td><td>0.6655</td><td>0.6791</td><td>0.6919</td><td>0.6819</td></tr><tr><td>(forest-fires)</td><td>0.540</td><td>0.5458</td><td><strong>0.5638</strong></td><td>0.5321</td><td>0.5319</td><td>0.5321</td></tr><tr><td>(german-credit)</td><td>0.701</td><td><strong>0.6946</strong></td><td>0.6834</td><td>0.6843</td><td>0.6911</td><td>0.6862</td></tr><tr><td>hand_posture</td><td>0.794</td><td>0.9878</td><td><strong>0.9884</strong></td><td>0.9860</td><td>0.9629</td><td>0.9860</td></tr><tr><td>(heart-cleveland)</td><td>0.745</td><td>0.7283</td><td>0.7527</td><td>0.7617</td><td><strong>0.7733</strong></td><td>0.7647</td></tr><tr><td>(hepatitis)</td><td>0.826</td><td><strong>0.7607</strong></td><td>0.7307</td><td>0.7545</td><td>0.7600</td><td>0.7545</td></tr><tr><td>HTRU2</td><td>0.962</td><td><strong>0.9768</strong></td><td>0.9757</td><td>0.9761</td><td>0.9700</td><td>0.9759</td></tr><tr><td>hypothyroid</td><td>0.962</td><td><strong>0.9784</strong></td><td>0.9756</td><td>0.9728</td><td>0.9703</td><td>0.9720</td></tr><tr><td>(IndiansDiabetes)</td><td>0.738</td><td><strong>0.7164</strong></td><td>0.6751</td><td>0.6757</td><td>0.6886</td><td>0.6792</td></tr><tr><td>ionosphere</td><td>0.813</td><td>0.8789</td><td>0.8694</td><td>0.8820</td><td><strong>0.8932</strong></td><td>0.8896</td></tr><tr><td>iris</td><td>0.937</td><td>0.9807</td><td><strong>0.9893</strong></td><td>0.9827</td><td>0.9700</td><td>0.9827</td></tr><tr><td>kr-vs-kp</td><td>0.675</td><td>0.9628</td><td><strong>0.9848</strong></td><td>0.9780</td><td>0.9718</td><td>0.9765</td></tr><tr><td>letter</td><td>0.959</td><td>0.9893</td><td><strong>0.9908</strong></td><td>0.9893</td><td>0.9840</td><td>0.9886</td></tr><tr><td>letter_recognition</td><td>0.961</td><td>0.9941</td><td><strong>0.9943</strong></td><td>0.9905</td><td>0.9892</td><td>0.9892</td></tr><tr><td>lymph</td><td>0.799</td><td><strong>0.8252</strong></td><td>0.8137</td><td>0.8142</td><td>0.8194</td><td>0.8142</td></tr><tr><td>magic04</td><td>0.738</td><td>0.8404</td><td>0.8454</td><td><strong>0.8457</strong></td><td>0.8381</td><td>0.8445</td></tr><tr><td>messidor</td><td>0.591</td><td><strong>0.6317</strong></td><td>0.6191</td><td>0.6171</td><td>0.6228</td><td>0.6184</td></tr><tr><td>mnist_0</td><td>0.920</td><td>0.9747</td><td><strong>0.9750</strong></td><td>0.9709</td><td>0.9603</td><td>0.9687</td></tr><tr><td>monk1</td><td>0.733</td><td>0.8569</td><td><strong>1.0000</strong></td><td><strong>1.0000</strong></td><td>0.9915</td><td><strong>1.0000</strong></td></tr><tr><td>monk2</td><td>0.618</td><td>0.6900</td><td><strong>0.8722</strong></td><td>0.8512</td><td>0.8306</td><td>0.8512</td></tr><tr><td>monk3</td><td>0.754</td><td><strong>0.8896</strong></td><td>0.8569</td><td>0.8728</td><td>0.8872</td><td>0.8880</td></tr><tr><td>mushroom</td><td>0.887</td><td>1.0000</td><td><strong>1.0000</strong></td><td>0.9941</td><td>0.9852</td><td>0.9932</td></tr><tr><td>pendigits</td><td>0.932</td><td>0.9976</td><td><strong>0.9978</strong></td><td>0.9918</td><td>0.9886</td><td>0.9886</td></tr><tr><td>(primary-tumor)</td><td>0.789</td><td><strong>0.7988</strong></td><td>0.7829</td><td>0.7679</td><td>0.7865</td><td>0.7694</td></tr><tr><td>segment</td><td>0.983</td><td>0.9974</td><td><strong>0.9982</strong></td><td>0.9955</td><td>0.9830</td><td>0.9954</td></tr><tr><td>(seismic_bumps)</td><td>0.934</td><td><strong>0.9233</strong></td><td>0.8985</td><td>0.9062</td><td>0.9176</td><td>0.9078</td></tr><tr><td>soybean</td><td>0.850</td><td>0.9482</td><td>0.9425</td><td>0.9520</td><td>0.9496</td><td><strong>0.9534</strong></td></tr><tr><td>spambase</td><td>0.786</td><td>0.8816</td><td><strong>0.8826</strong></td><td>0.8809</td><td>0.8752</td><td>0.8794</td></tr><tr><td>splice-1</td><td>0.822</td><td>0.9515</td><td>0.9488</td><td>0.9567</td><td>0.9577</td><td><strong>0.9582</strong></td></tr><tr><td>Statlog.satellite</td><td>0.757</td><td>0.9669</td><td>0.9672</td><td><strong>0.9679</strong></td><td>0.9600</td><td>0.9668</td></tr><tr><td>Statlog.shuttle</td><td>0.928</td><td>0.9999</td><td><strong>0.9999</strong></td><td>0.9961</td><td>0.9961</td><td>0.9961</td></tr><tr><td>surgical-deepnet</td><td>0.786</td><td>0.8606</td><td><strong>0.8679</strong></td><td>0.8647</td><td>0.8604</td><td>0.8634</td></tr><tr><td>(taiwan_binarised)</td><td>0.820</td><td>0.8186</td><td>0.8149</td><td>0.8177</td><td><strong>0.8196</strong></td><td>0.8181</td></tr><tr><td>tic-tac-toe</td><td>0.698</td><td>0.9339</td><td><strong>0.9753</strong></td><td>0.9645</td><td>0.9450</td><td>0.9609</td></tr><tr><td>titanic</td><td>0.780</td><td>0.8051</td><td>0.8031</td><td>0.7912</td><td><strong>0.8124</strong></td><td>0.7980</td></tr><tr><td>vehicle</td><td>0.769</td><td>0.9452</td><td>0.9475</td><td><strong>0.9558</strong></td><td>0.9535</td><td>0.9535</td></tr><tr><td>(vote)</td><td>0.955</td><td>0.9366</td><td>0.9427</td><td>0.9468</td><td><strong>0.9520</strong></td><td>0.9486</td></tr><tr><td>(wine1)</td><td>0.677</td><td><strong>0.6722</strong></td><td>0.6689</td><td>0.6561</td><td>0.6539</td><td>0.6561</td></tr><tr><td>wine2</td><td>0.604</td><td>0.6546</td><td>0.6484</td><td>0.6627</td><td><strong>0.6638</strong></td><td>0.6632</td></tr><tr><td>(wine3)</td><td>0.726</td><td><strong>0.7100</strong></td><td>0.6944</td><td>0.7050</td><td>0.7033</td><td>0.7044</td></tr><tr><td>(winequality-red)</td><td>0.993</td><td>0.9863</td><td>0.9895</td><td>0.9936</td><td><strong>0.9937</strong></td><td><strong>0.9937</strong></td></tr><tr><td>yeast</td><td>0.701</td><td><strong>0.7119</strong></td><td>0.6883</td><td>0.7019</td><td>0.7080</td><td>0.7013</td></tr><tr><td>Average (all data sets)</td><td></td><td>0.8679</td><td>0.8686</td><td>0.8698</td><td>0.8697</td><td><strong>0.8705</strong></td></tr><tr><td>Average (filtered data sets)</td><td></td><td>0.8980</td><td>0.9055</td><td>0.9058</td><td>0.9026</td><td><strong>0.9060</strong></td></tr></tbody></table>
<table><caption>Table 10: Depth 8 – Test accuracy of CART and Blossom, without and with pruning (up to 1%, 3% or 0.3 · k²% loss)</caption><thead><tr><th rowspan="2"></th><th rowspan="2">single test</th><th>CART</th><th>Blossom</th><th>Blossom<sup>1%</sup></th><th>Blossom<sup>3%</sup></th><th>Blossom<sup>*</sup></th></tr><tr><th>test acc.</th><th>test acc.</th><th>test acc.</th><th>test acc.</th><th>test acc.</th></tr></thead><tbody><tr><td>adult_discretized</td><td>0.795</td><td>0.8502</td><td><strong>0.8528</strong></td><td>0.8515</td><td>0.8450</td><td>0.8488</td></tr><tr><td>anneal</td><td>0.808</td><td>0.8520</td><td><strong>0.8763</strong></td><td>0.8648</td><td>0.8694</td><td>0.8671</td></tr><tr><td>audiology</td><td>0.874</td><td><strong>0.9523</strong></td><td>0.9382</td><td>0.9505</td><td>0.9473</td><td>0.9518</td></tr><tr><td>(australian-credit)</td><td>0.871</td><td>0.8279</td><td>0.8185</td><td>0.8268</td><td><strong>0.8420</strong></td><td>0.8380</td></tr><tr><td>(balance-scale)</td><td>0.921</td><td><strong>0.8478</strong></td><td>0.7530</td><td>0.7884</td><td>0.8156</td><td>0.8005</td></tr><tr><td>bank</td><td>0.893</td><td>0.9002</td><td>0.9009</td><td><strong>0.9029</strong></td><td>0.8995</td><td>0.9021</td></tr><tr><td>(bank(conv)</td><td>0.891</td><td>0.8921</td><td>0.8916</td><td>0.8929</td><td><strong>0.8958</strong></td><td>0.8952</td></tr><tr><td>banknote</td><td>0.843</td><td><strong>0.9914</strong></td><td>0.9888</td><td>0.9827</td><td>0.9749</td><td>0.9793</td></tr><tr><td>biodeg</td><td>0.760</td><td><strong>0.8284</strong></td><td>0.8234</td><td>0.8206</td><td>0.8231</td><td>0.8227</td></tr><tr><td>breast-cancer</td><td>0.895</td><td>0.9350</td><td>0.9316</td><td>0.9320</td><td><strong>0.9391</strong></td><td>0.9345</td></tr><tr><td>breast-wisconsin</td><td>0.923</td><td>0.9425</td><td>0.9441</td><td>0.9447</td><td><strong>0.9479</strong></td><td>0.9474</td></tr><tr><td>car</td><td>0.714</td><td>0.9649</td><td><strong>0.9910</strong></td><td>0.9790</td><td>0.9673</td><td>0.9748</td></tr><tr><td>car_evaluation</td><td>0.699</td><td>0.9288</td><td>0.9126</td><td>0.9340</td><td>0.9336</td><td><strong>0.9363</strong></td></tr><tr><td>(chess)</td><td>1.000</td><td><strong>1.0000</strong></td><td><strong>1.0000</strong></td><td><strong>1.0000</strong></td><td><strong>1.0000</strong></td><td><strong>1.0000</strong></td></tr><tr><td>compas_discretized</td><td>0.644</td><td>0.6649</td><td>0.6604</td><td>0.6628</td><td><strong>0.6673</strong></td><td>0.6658</td></tr><tr><td>(default_credi)</td><td>0.820</td><td>0.8165</td><td>0.8141</td><td>0.8163</td><td><strong>0.8196</strong></td><td>0.8184</td></tr><tr><td>(diabetes)</td><td>0.744</td><td><strong>0.7113</strong></td><td>0.6727</td><td>0.6921</td><td>0.7064</td><td>0.6986</td></tr><tr><td>(forest-fires)</td><td>0.540</td><td>0.5477</td><td><strong>0.5546</strong></td><td>0.5433</td><td>0.5440</td><td>0.5419</td></tr><tr><td>(german-credit)</td><td>0.701</td><td><strong>0.6916</strong></td><td>0.6846</td><td>0.6775</td><td>0.6846</td><td>0.6803</td></tr><tr><td>hand_posture</td><td>0.794</td><td>0.9892</td><td><strong>0.9908</strong></td><td>0.9878</td><td>0.9765</td><td>0.9878</td></tr><tr><td>(heart-cleveland)</td><td>0.745</td><td>0.7430</td><td>0.7280</td><td>0.7490</td><td><strong>0.7573</strong></td><td>0.7520</td></tr><tr><td>(hepatitis)</td><td>0.826</td><td>0.7579</td><td>0.7467</td><td>0.7545</td><td><strong>0.7607</strong></td><td>0.7593</td></tr><tr><td>HTRU2</td><td>0.962</td><td>0.9761</td><td>0.9743</td><td><strong>0.9769</strong></td><td>0.9752</td><td>0.9759</td></tr><tr><td>hypothyroid</td><td>0.962</td><td><strong>0.9781</strong></td><td>0.9730</td><td>0.9749</td><td>0.9762</td><td>0.9755</td></tr><tr><td>(IndiansDiabetes)</td><td>0.738</td><td><strong>0.7123</strong></td><td>0.6597</td><td>0.6556</td><td>0.6708</td><td>0.6613</td></tr><tr><td>ionosphere</td><td>0.813</td><td>0.8848</td><td>0.8661</td><td>0.8837</td><td><strong>0.8927</strong></td><td>0.8913</td></tr><tr><td>iris</td><td>0.937</td><td>0.9807</td><td><strong>0.9893</strong></td><td>0.9827</td><td>0.9700</td><td>0.9720</td></tr><tr><td>kr-vs-kp</td><td>0.675</td><td>0.9823</td><td><strong>0.9843</strong></td><td>0.9819</td><td>0.9669</td><td>0.9765</td></tr><tr><td>letter</td><td>0.959</td><td>0.9906</td><td><strong>0.9917</strong></td><td>0.9900</td><td>0.9834</td><td>0.9855</td></tr><tr><td>letter_recognition</td><td>0.961</td><td><strong>0.9942</strong></td><td>0.9941</td><td>0.9913</td><td>0.9892</td><td>0.9892</td></tr><tr><td>lymph</td><td>0.799</td><td><strong>0.8213</strong></td><td>0.8163</td><td>0.8142</td><td>0.8194</td><td>0.8168</td></tr><tr><td>magic04</td><td>0.738</td><td>0.8410</td><td>0.8446</td><td><strong>0.8466</strong></td><td>0.8423</td><td>0.8454</td></tr><tr><td>messidor</td><td>0.591</td><td><strong>0.6275</strong></td><td>0.6133</td><td>0.6158</td><td>0.6235</td><td>0.6173</td></tr><tr><td>mnist_0</td><td>0.920</td><td>0.9776</td><td><strong>0.9794</strong></td><td>0.9757</td><td>0.9671</td><td>0.9705</td></tr><tr><td>monk1</td><td>0.733</td><td>0.8731</td><td><strong>1.0000</strong></td><td><strong>1.0000</strong></td><td>0.9915</td><td><strong>1.0000</strong></td></tr><tr><td>monk2</td><td>0.618</td><td>0.6953</td><td><strong>0.8722</strong></td><td>0.8500</td><td>0.8294</td><td>0.8429</td></tr><tr><td>monk3</td><td>0.754</td><td><strong>0.9000</strong></td><td>0.8600</td><td>0.8712</td><td>0.8824</td><td>0.8832</td></tr><tr><td>mushroom</td><td>0.887</td><td><strong>1.0000</strong></td><td><strong>1.0000</strong></td><td>0.9942</td><td>0.9852</td><td>0.9852</td></tr><tr><td>pendigits</td><td>0.932</td><td>0.9975</td><td><strong>0.9977</strong></td><td>0.9918</td><td>0.9888</td><td>0.9888</td></tr><tr><td>(primary-tumor)</td><td>0.789</td><td><strong>0.7894</strong></td><td>0.7657</td><td>0.7718</td><td>0.7838</td><td>0.7774</td></tr><tr><td>segment</td><td>0.983</td><td>0.9971</td><td><strong>0.9982</strong></td><td>0.9955</td><td>0.9830</td><td>0.9925</td></tr><tr><td>(seismic_bumps)</td><td>0.934</td><td><strong>0.9178</strong></td><td>0.8900</td><td>0.8993</td><td>0.9145</td><td>0.9070</td></tr><tr><td>soybean</td><td>0.850</td><td>0.9490</td><td>0.9484</td><td>0.9545</td><td>0.9546</td><td><strong>0.9569</strong></td></tr><tr><td>spambase</td><td>0.786</td><td>0.8847</td><td><strong>0.8869</strong></td><td>0.8839</td><td>0.8793</td><td>0.8818</td></tr><tr><td>splice-1</td><td>0.822</td><td>0.9495</td><td>0.9508</td><td>0.9541</td><td><strong>0.9592</strong></td><td>0.9581</td></tr><tr><td>Statlog.satellite</td><td>0.757</td><td><strong>0.9695</strong></td><td>0.9673</td><td>0.9681</td><td>0.9627</td><td>0.9668</td></tr><tr><td>Statlog.shuttle</td><td>0.928</td><td>0.9998</td><td><strong>0.9999</strong></td><td>0.9961</td><td>0.9961</td><td>0.9961</td></tr><tr><td>surgical-deepnet</td><td>0.786</td><td>0.8769</td><td><strong>0.8858</strong></td><td>0.8804</td><td>0.8758</td><td>0.8792</td></tr><tr><td>(taiwan_binarised)</td><td>0.820</td><td>0.8169</td><td>0.8132</td><td>0.8145</td><td><strong>0.8190</strong></td><td>0.8173</td></tr><tr><td>tic-tac-toe</td><td>0.698</td><td>0.9398</td><td><strong>0.9734</strong></td><td>0.9654</td><td>0.9485</td><td>0.9606</td></tr><tr><td>titanic</td><td>0.780</td><td>0.8046</td><td>0.7967</td><td>0.7926</td><td><strong>0.8082</strong></td><td>0.7990</td></tr><tr><td>vehicle</td><td>0.769</td><td>0.9442</td><td>0.9494</td><td>0.9544</td><td><strong>0.9548</strong></td><td>0.9538</td></tr><tr><td>(vote)</td><td>0.955</td><td>0.9357</td><td>0.9450</td><td>0.9464</td><td><strong>0.9525</strong></td><td>0.9486</td></tr><tr><td>(wine1)</td><td>0.677</td><td><strong>0.6800</strong></td><td>0.6678</td><td>0.6639</td><td>0.6617</td><td>0.6639</td></tr><tr><td>wine2</td><td>0.604</td><td>0.6600</td><td>0.6516</td><td>0.6714</td><td><strong>0.6719</strong></td><td><strong>0.6719</strong></td></tr><tr><td>(wine3)</td><td>0.726</td><td>0.7050</td><td>0.6900</td><td>0.7083</td><td>0.7061</td><td><strong>0.7089</strong></td></tr><tr><td>(winequality-red)</td><td>0.993</td><td>0.9864</td><td>0.9895</td><td>0.9936</td><td><strong>0.9937</strong></td><td><strong>0.9937</strong></td></tr><tr><td>yeast</td><td>0.701</td><td><strong>0.7072</strong></td><td>0.6829</td><td>0.6928</td><td>0.6990</td><td>0.6950</td></tr><tr><td>Average (all data sets)</td><td></td><td>0.8686</td><td>0.8680</td><td>0.8700</td><td>0.8706</td><td><strong>0.8708</strong></td></tr><tr><td>Average (filtered data sets)</td><td></td><td>0.9001</td><td>0.9065</td><td><strong>0.9066</strong></td><td>0.9042</td><td>0.9062</td></tr></tbody></table>
<table><caption>Table 11: Depth 9 – Test accuracy of CART and Blossom, without and with pruning (up to 1%, 3% or 0.3 · k²% loss)</caption><thead><tr><th rowspan="2"></th><th rowspan="2">single test</th><th>CART</th><th>Blossom</th><th>Blossom<sup>1%</sup></th><th>Blossom<sup>3%</sup></th><th>Blossom<sup>*</sup></th></tr><tr><th>test acc.</th><th>test acc.</th><th>test acc.</th><th>test acc.</th><th>test acc.</th></tr></thead><tbody><tr><td>adult_discretized</td><td>0.795</td><td><strong>0.8531</strong></td><td>0.8522</td><td>0.8529</td><td>0.8489</td><td>0.8497</td></tr><tr><td>anneal</td><td>0.808</td><td>0.8582</td><td><strong>0.8678</strong></td><td>0.8568</td><td>0.8620</td><td>0.8610</td></tr><tr><td>audiology</td><td>0.874</td><td><strong>0.9541</strong></td><td>0.9382</td><td>0.9505</td><td>0.9473</td><td>0.9477</td></tr><tr><td>(australian-credit)</td><td>0.871</td><td>0.8218</td><td>0.8197</td><td>0.8305</td><td><strong>0.8448</strong></td><td>0.8406</td></tr><tr><td>(balance-scale)</td><td>0.921</td><td><strong>0.8371</strong></td><td>0.7451</td><td>0.7649</td><td>0.7857</td><td>0.7833</td></tr><tr><td>bank</td><td>0.893</td><td>0.8998</td><td>0.9005</td><td><strong>0.9028</strong></td><td>0.9009</td><td>0.9025</td></tr><tr><td>(bank(conv)</td><td>0.891</td><td>0.8897</td><td>0.8906</td><td>0.8922</td><td><strong>0.8963</strong></td><td>0.8956</td></tr><tr><td>banknote</td><td>0.843</td><td><strong>0.9912</strong></td><td>0.9888</td><td>0.9826</td><td>0.9748</td><td>0.9775</td></tr><tr><td>biodeg</td><td>0.760</td><td><strong>0.8258</strong></td><td>0.8202</td><td>0.8186</td><td>0.8249</td><td>0.8247</td></tr><tr><td>breast-cancer</td><td>0.895</td><td>0.9320</td><td>0.9322</td><td>0.9349</td><td><strong>0.9391</strong></td><td>0.9380</td></tr><tr><td>breast-wisconsin</td><td>0.923</td><td>0.9418</td><td>0.9446</td><td>0.9439</td><td><strong>0.9470</strong></td><td>0.9457</td></tr><tr><td>car</td><td>0.714</td><td>0.9803</td><td><strong>0.9953</strong></td><td>0.9831</td><td>0.9701</td><td>0.9737</td></tr><tr><td>car_evaluation</td><td>0.699</td><td>0.9218</td><td>0.9126</td><td><strong>0.9392</strong></td><td>0.9357</td><td>0.9378</td></tr><tr><td>(chess)</td><td>1.000</td><td><strong>1.0000</strong></td><td><strong>1.0000</strong></td><td><strong>1.0000</strong></td><td><strong>1.0000</strong></td><td><strong>1.0000</strong></td></tr><tr><td>compas_discretized</td><td>0.644</td><td>0.6622</td><td>0.6607</td><td>0.6623</td><td><strong>0.6661</strong></td><td>0.6653</td></tr><tr><td>(default_credi)</td><td>0.820</td><td>0.8146</td><td>0.8106</td><td>0.8138</td><td><strong>0.8182</strong></td><td>0.8170</td></tr><tr><td>(diabetes)</td><td>0.744</td><td>0.7030</td><td>0.6816</td><td>0.6943</td><td><strong>0.7100</strong></td><td>0.7062</td></tr><tr><td>(forest-fires)</td><td>0.540</td><td>0.5438</td><td><strong>0.5658</strong></td><td>0.5350</td><td>0.5360</td><td>0.5352</td></tr><tr><td>(german-credit)</td><td>0.701</td><td>0.6827</td><td>0.6694</td><td>0.6790</td><td><strong>0.6841</strong></td><td>0.6823</td></tr><tr><td>hand_posture</td><td>0.794</td><td>0.9904</td><td><strong>0.9925</strong></td><td>0.9890</td><td>0.9849</td><td>0.9890</td></tr><tr><td>(heart-cleveland)</td><td>0.745</td><td>0.7323</td><td>0.7260</td><td>0.7530</td><td><strong>0.7587</strong></td><td>0.7567</td></tr><tr><td>(hepatitis)</td><td>0.826</td><td><strong>0.7641</strong></td><td>0.7440</td><td>0.7545</td><td>0.7607</td><td>0.7593</td></tr><tr><td>HTRU2</td><td>0.962</td><td>0.9755</td><td>0.9730</td><td><strong>0.9775</strong></td><td>0.9759</td><td>0.9759</td></tr><tr><td>hypothyroid</td><td>0.962</td><td>0.9770</td><td>0.9741</td><td>0.9760</td><td><strong>0.9782</strong></td><td>0.9772</td></tr><tr><td>(IndiansDiabetes)</td><td>0.738</td><td><strong>0.7038</strong></td><td>0.6657</td><td>0.6708</td><td>0.6804</td><td>0.6769</td></tr><tr><td>ionosphere</td><td>0.813</td><td>0.8772</td><td>0.8617</td><td>0.8851</td><td><strong>0.8918</strong></td><td>0.8896</td></tr><tr><td>iris</td><td>0.937</td><td>0.9807</td><td><strong>0.9893</strong></td><td>0.9827</td><td>0.9700</td><td>0.9720</td></tr><tr><td>kr-vs-kp</td><td>0.675</td><td><strong>0.9898</strong></td><td>0.9890</td><td>0.9845</td><td>0.9753</td><td>0.9783</td></tr><tr><td>letter</td><td>0.959</td><td>0.9916</td><td><strong>0.9920</strong></td><td>0.9906</td><td>0.9839</td><td>0.9844</td></tr><tr><td>letter_recognition</td><td>0.961</td><td>0.9944</td><td><strong>0.9947</strong></td><td>0.9917</td><td>0.9892</td><td>0.9892</td></tr><tr><td>lymph</td><td>0.799</td><td><strong>0.8284</strong></td><td>0.8163</td><td>0.8135</td><td>0.8187</td><td>0.8161</td></tr><tr><td>magic04</td><td>0.738</td><td>0.8412</td><td>0.8433</td><td>0.8445</td><td>0.8446</td><td><strong>0.8452</strong></td></tr><tr><td>messidor</td><td>0.591</td><td><strong>0.6273</strong></td><td>0.6048</td><td>0.6087</td><td>0.6171</td><td>0.6143</td></tr><tr><td>mnist_0</td><td>0.920</td><td>0.9801</td><td><strong>0.9821</strong></td><td>0.9784</td><td>0.9692</td><td>0.9700</td></tr><tr><td>monk1</td><td>0.733</td><td>0.8654</td><td><strong>1.0000</strong></td><td><strong>1.0000</strong></td><td>0.9915</td><td>0.9915</td></tr><tr><td>monk2</td><td>0.618</td><td>0.7071</td><td><strong>0.8733</strong></td><td>0.8500</td><td>0.8294</td><td>0.8429</td></tr><tr><td>monk3</td><td>0.754</td><td><strong>0.8968</strong></td><td>0.8631</td><td>0.8736</td><td>0.8848</td><td>0.8848</td></tr><tr><td>mushroom</td><td>0.887</td><td><strong>1.0000</strong></td><td><strong>1.0000</strong></td><td>0.9942</td><td>0.9852</td><td>0.9852</td></tr><tr><td>pendigits</td><td>0.932</td><td>0.9975</td><td><strong>0.9977</strong></td><td>0.9918</td><td>0.9888</td><td>0.9888</td></tr><tr><td>(primary-tumor)</td><td>0.789</td><td><strong>0.7847</strong></td><td>0.7663</td><td>0.7700</td><td>0.7750</td><td>0.7726</td></tr><tr><td>segment</td><td>0.983</td><td>0.9974</td><td><strong>0.9982</strong></td><td>0.9955</td><td>0.9830</td><td>0.9830</td></tr><tr><td>(seismic_bumps)</td><td>0.934</td><td><strong>0.9122</strong></td><td>0.8836</td><td>0.8958</td><td>0.9118</td><td>0.9075</td></tr><tr><td>soybean</td><td>0.850</td><td>0.9463</td><td>0.9434</td><td><strong>0.9513</strong></td><td>0.9480</td><td>0.9509</td></tr><tr><td>spambase</td><td>0.786</td><td>0.8859</td><td>0.8877</td><td><strong>0.8879</strong></td><td>0.8847</td><td>0.8862</td></tr><tr><td>splice-1</td><td>0.822</td><td>0.9480</td><td>0.9447</td><td>0.9547</td><td><strong>0.9605</strong></td><td>0.9590</td></tr><tr><td>Statlog.satellite</td><td>0.757</td><td>0.9692</td><td>0.9668</td><td><strong>0.9696</strong></td><td>0.9653</td><td>0.9671</td></tr><tr><td>Statlog.shuttle</td><td>0.928</td><td>0.9998</td><td><strong>0.9999</strong></td><td>0.9961</td><td>0.9961</td><td>0.9961</td></tr><tr><td>surgical-deepnet</td><td>0.786</td><td>0.8900</td><td>0.8937</td><td><strong>0.8950</strong></td><td>0.8927</td><td>0.8944</td></tr><tr><td>(taiwan_binarised)</td><td>0.820</td><td>0.8148</td><td>0.8097</td><td>0.8122</td><td><strong>0.8171</strong></td><td>0.8161</td></tr><tr><td>tic-tac-toe</td><td>0.698</td><td>0.9402</td><td>0.9623</td><td>0.9610</td><td>0.9582</td><td><strong>0.9629</strong></td></tr><tr><td>titanic</td><td>0.780</td><td><strong>0.8020</strong></td><td>0.7898</td><td>0.7842</td><td>0.8001</td><td>0.7939</td></tr><tr><td>vehicle</td><td>0.769</td><td>0.9440</td><td>0.9506</td><td><strong>0.9554</strong></td><td>0.9532</td><td>0.9538</td></tr><tr><td>(vote)</td><td>0.955</td><td>0.9375</td><td>0.9450</td><td>0.9466</td><td><strong>0.9539</strong></td><td>0.9511</td></tr><tr><td>(wine1)</td><td>0.677</td><td>0.6650</td><td><strong>0.6667</strong></td><td>0.6600</td><td>0.6578</td><td>0.6606</td></tr><tr><td>wine2</td><td>0.604</td><td>0.6681</td><td>0.6474</td><td>0.6670</td><td><strong>0.6697</strong></td><td>0.6670</td></tr><tr><td>(wine3)</td><td>0.726</td><td>0.7039</td><td>0.6800</td><td><strong>0.7089</strong></td><td>0.7006</td><td>0.7050</td></tr><tr><td>(winequality-red)</td><td>0.993</td><td>0.9856</td><td>0.9892</td><td><strong>0.9937</strong></td><td><strong>0.9937</strong></td><td><strong>0.9937</strong></td></tr><tr><td>yeast</td><td>0.701</td><td><strong>0.7082</strong></td><td>0.6819</td><td>0.6825</td><td>0.6917</td><td>0.6879</td></tr><tr><td>Average (all data sets)</td><td></td><td>0.8679</td><td>0.8670</td><td>0.8696</td><td><strong>0.8704</strong></td><td>0.8704</td></tr><tr><td>Average (filtered data sets)</td><td></td><td>0.9010</td><td>0.9057</td><td><strong>0.9065</strong></td><td>0.9050</td><td>0.9055</td></tr></tbody></table>
<table><caption>Table 12: Depth 10 – Test accuracy of CART and Blossom, without and with pruning (up to 1%, 3% or 0.3 · k²% loss)</caption><thead><tr><th rowspan="2"></th><th rowspan="2">single test</th><th>CART</th><th>Blossom</th><th>Blossom<sup>1%</sup></th><th>Blossom<sup>3%</sup></th><th>Blossom<sup>*</sup></th></tr><tr><th>test acc.</th><th>test acc.</th><th>test acc.</th><th>test acc.</th><th>test acc.</th></tr></thead><tbody><tr><td>adult_discretized</td><td>0.795</td><td>0.8532</td><td>0.8523</td><td><strong>0.8541</strong></td><td>0.8519</td><td>0.8519</td></tr><tr><td>anneal</td><td>0.808</td><td>0.8579</td><td>0.8768</td><td>0.8748</td><td>0.8784</td><td><strong>0.8785</strong></td></tr><tr><td>audiology</td><td>0.874</td><td><strong>0.9527</strong></td><td>0.9382</td><td>0.9505</td><td>0.9473</td><td>0.9473</td></tr><tr><td>(australian-credit)</td><td>0.871</td><td>0.8203</td><td>0.8200</td><td>0.8291</td><td><strong>0.8415</strong></td><td><strong>0.8415</strong></td></tr><tr><td>(balance-scale)</td><td>0.921</td><td><strong>0.8306</strong></td><td>0.7479</td><td>0.7681</td><td>0.7897</td><td>0.7897</td></tr><tr><td>bank</td><td>0.893</td><td>0.8990</td><td>0.8991</td><td>0.9022</td><td><strong>0.9027</strong></td><td>0.9027</td></tr><tr><td>(bank(conv)</td><td>0.891</td><td>0.8886</td><td>0.8898</td><td>0.8906</td><td><strong>0.8950</strong></td><td>0.8949</td></tr><tr><td>banknote</td><td>0.843</td><td><strong>0.9913</strong></td><td>0.9888</td><td>0.9826</td><td>0.9748</td><td>0.9748</td></tr><tr><td>biodeg</td><td>0.760</td><td>0.8211</td><td>0.8175</td><td>0.8185</td><td><strong>0.8249</strong></td><td><strong>0.8249</strong></td></tr><tr><td>breast-cancer</td><td>0.895</td><td>0.9336</td><td>0.9313</td><td>0.9352</td><td><strong>0.9396</strong></td><td><strong>0.9396</strong></td></tr><tr><td>breast-wisconsin</td><td>0.923</td><td>0.9412</td><td>0.9455</td><td>0.9438</td><td><strong>0.9472</strong></td><td>0.9467</td></tr><tr><td>car</td><td>0.714</td><td>0.9790</td><td><strong>0.9963</strong></td><td>0.9831</td><td>0.9706</td><td>0.9706</td></tr><tr><td>car_evaluation</td><td>0.699</td><td>0.9176</td><td>0.9126</td><td><strong>0.9392</strong></td><td>0.9374</td><td>0.9374</td></tr><tr><td>(chess)</td><td>1.000</td><td><strong>1.0000</strong></td><td><strong>1.0000</strong></td><td><strong>1.0000</strong></td><td><strong>1.0000</strong></td><td><strong>1.0000</strong></td></tr><tr><td>compas_discretized</td><td>0.644</td><td>0.6594</td><td>0.6601</td><td>0.6625</td><td><strong>0.6668</strong></td><td><strong>0.6668</strong></td></tr><tr><td>(default_credi)</td><td>0.820</td><td>0.8116</td><td>0.8061</td><td>0.8109</td><td>0.8155</td><td><strong>0.8156</strong></td></tr><tr><td>(diabetes)</td><td>0.744</td><td>0.7018</td><td>0.6865</td><td>0.6943</td><td>0.7081</td><td><strong>0.7084</strong></td></tr><tr><td>(forest-fires)</td><td>0.540</td><td>0.5402</td><td><strong>0.5769</strong></td><td>0.5317</td><td>0.5329</td><td>0.5333</td></tr><tr><td>(german-credit)</td><td>0.701</td><td>0.6844</td><td>0.6638</td><td>0.6796</td><td>0.6852</td><td><strong>0.6863</strong></td></tr><tr><td>handposture</td><td>0.794</td><td>0.9911</td><td><strong>0.9939</strong></td><td>0.9892</td><td>0.9886</td><td>0.9886</td></tr><tr><td>(heart-cleveland)</td><td>0.745</td><td>0.7347</td><td>0.7227</td><td>0.7513</td><td><strong>0.7583</strong></td><td><strong>0.7583</strong></td></tr><tr><td>(hepatitis)</td><td>0.826</td><td>0.7552</td><td>0.7440</td><td>0.7545</td><td><strong>0.7607</strong></td><td><strong>0.7607</strong></td></tr><tr><td>HTRU2</td><td>0.962</td><td>0.9744</td><td>0.9712</td><td><strong>0.9775</strong></td><td>0.9759</td><td>0.9759</td></tr><tr><td>hypothyroid</td><td>0.962</td><td>0.9761</td><td>0.9729</td><td>0.9768</td><td><strong>0.9786</strong></td><td><strong>0.9786</strong></td></tr><tr><td>(IndiansDiabetes)</td><td>0.738</td><td><strong>0.6964</strong></td><td>0.6636</td><td>0.6678</td><td>0.6821</td><td>0.6821</td></tr><tr><td>ionosphere</td><td>0.813</td><td>0.8769</td><td>0.8650</td><td>0.8820</td><td><strong>0.8924</strong></td><td><strong>0.8924</strong></td></tr><tr><td>iris</td><td>0.937</td><td>0.9807</td><td><strong>0.9893</strong></td><td>0.9827</td><td>0.9700</td><td>0.9700</td></tr><tr><td>kr-vs-kp</td><td>0.675</td><td><strong>0.9927</strong></td><td>0.9904</td><td>0.9848</td><td>0.9747</td><td>0.9747</td></tr><tr><td>letter</td><td>0.959</td><td>0.9919</td><td><strong>0.9920</strong></td><td>0.9906</td><td>0.9838</td><td>0.9838</td></tr><tr><td>letter_recognition</td><td>0.961</td><td>0.9949</td><td><strong>0.9955</strong></td><td>0.9924</td><td>0.9893</td><td>0.9893</td></tr><tr><td>lymph</td><td>0.799</td><td><strong>0.8316</strong></td><td>0.8163</td><td>0.8135</td><td>0.8168</td><td>0.8168</td></tr><tr><td>magic04</td><td>0.738</td><td>0.8393</td><td>0.8352</td><td>0.8384</td><td><strong>0.8425</strong></td><td>0.8424</td></tr><tr><td>messidor</td><td>0.591</td><td><strong>0.6287</strong></td><td>0.6002</td><td>0.6094</td><td>0.6138</td><td>0.6154</td></tr><tr><td>mnist_0</td><td>0.920</td><td>0.9827</td><td><strong>0.9838</strong></td><td>0.9812</td><td>0.9702</td><td>0.9702</td></tr><tr><td>monk1</td><td>0.733</td><td>0.8692</td><td><strong>1.0000</strong></td><td><strong>1.0000</strong></td><td>0.9915</td><td>0.9915</td></tr><tr><td>monk2</td><td>0.618</td><td>0.6965</td><td><strong>0.8722</strong></td><td>0.8494</td><td>0.8294</td><td>0.8294</td></tr><tr><td>monk3</td><td>0.754</td><td><strong>0.8992</strong></td><td>0.8631</td><td>0.8736</td><td>0.8848</td><td>0.8848</td></tr><tr><td>mushroom</td><td>0.887</td><td><strong>1.0000</strong></td><td><strong>1.0000</strong></td><td>0.9942</td><td>0.9852</td><td>0.9852</td></tr><tr><td>pendigits</td><td>0.932</td><td>0.9976</td><td><strong>0.9977</strong></td><td>0.9918</td><td>0.9888</td><td>0.9888</td></tr><tr><td>(primary-tumor)</td><td>0.789</td><td>0.7741</td><td>0.7760</td><td>0.7753</td><td><strong>0.7803</strong></td><td><strong>0.7803</strong></td></tr><tr><td>segment</td><td>0.983</td><td>0.9974</td><td><strong>0.9982</strong></td><td>0.9955</td><td>0.9830</td><td>0.9830</td></tr><tr><td>(seismic_bumps)</td><td>0.934</td><td>0.9040</td><td>0.8815</td><td>0.8955</td><td>0.9115</td><td><strong>0.9117</strong></td></tr><tr><td>soybean</td><td>0.850</td><td>0.9430</td><td>0.9428</td><td><strong>0.9498</strong></td><td>0.9488</td><td>0.9488</td></tr><tr><td>spambase</td><td>0.786</td><td>0.8884</td><td>0.8890</td><td><strong>0.8907</strong></td><td>0.8887</td><td>0.8888</td></tr><tr><td>splice-1</td><td>0.822</td><td>0.9466</td><td>0.9441</td><td>0.9533</td><td><strong>0.9608</strong></td><td>0.9607</td></tr><tr><td>Statlog.satellite</td><td>0.757</td><td>0.9692</td><td>0.9670</td><td><strong>0.9694</strong></td><td>0.9659</td><td>0.9659</td></tr><tr><td>Statlog.shuttle</td><td>0.928</td><td>0.9998</td><td><strong>0.9999</strong></td><td>0.9961</td><td>0.9961</td><td>0.9961</td></tr><tr><td>surgical-deepnet</td><td>0.786</td><td>0.8903</td><td>0.8919</td><td>0.8946</td><td><strong>0.8967</strong></td><td><strong>0.8967</strong></td></tr><tr><td>(taiwan_binarised)</td><td>0.820</td><td>0.8117</td><td>0.8069</td><td>0.8097</td><td><strong>0.8144</strong></td><td>0.8144</td></tr><tr><td>tic-tac-toe</td><td>0.698</td><td>0.9415</td><td><strong>0.9619</strong></td><td>0.9613</td><td>0.9581</td><td>0.9588</td></tr><tr><td>titanic</td><td>0.780</td><td><strong>0.7954</strong></td><td>0.7884</td><td>0.7785</td><td>0.7898</td><td>0.7898</td></tr><tr><td>vehicle</td><td>0.769</td><td>0.9440</td><td>0.9494</td><td><strong>0.9545</strong></td><td>0.9535</td><td>0.9535</td></tr><tr><td>(vote)</td><td>0.955</td><td>0.9370</td><td>0.9445</td><td>0.9475</td><td>0.9539</td><td><strong>0.9541</strong></td></tr><tr><td>(wine1)</td><td>0.677</td><td>0.6700</td><td><strong>0.6733</strong></td><td>0.6572</td><td>0.6561</td><td>0.6561</td></tr><tr><td>wine2</td><td>0.604</td><td>0.6546</td><td>0.6516</td><td>0.6665</td><td><strong>0.6676</strong></td><td><strong>0.6676</strong></td></tr><tr><td>(wine3)</td><td>0.726</td><td><strong>0.7094</strong></td><td>0.6833</td><td>0.7089</td><td>0.7044</td><td>0.7044</td></tr><tr><td>(winequality-red)</td><td>0.993</td><td>0.9851</td><td>0.9892</td><td><strong>0.9937</strong></td><td><strong>0.9937</strong></td><td><strong>0.9937</strong></td></tr><tr><td>yeast</td><td>0.701</td><td><strong>0.7037</strong></td><td>0.7015</td><td>0.6940</td><td>0.6989</td><td>0.6991</td></tr><tr><td>Average (all data sets)</td><td></td><td>0.8665</td><td>0.8676</td><td>0.8697</td><td>0.8708</td><td><strong>0.8709</strong></td></tr><tr><td>Average (filtered data sets)</td><td></td><td>0.9001</td><td>0.9061</td><td><strong>0.9070</strong></td><td>0.9056</td><td>0.9057</td></tr></tbody></table>
<table><caption>Table 13: Comparison with state of the art: $m < 100$, depth 3</caption><thead><tr><th rowspan="2"></th><th colspan="2">Blossom</th><th colspan="2">Murtree</th><th colspan="2">Murtree<sup>P</sup></th><th colspan="2">DL8.5</th><th colspan="2">DL8.5<sup>P</sup></th><th colspan="2">CP</th><th colspan="2">CP<sup>P</sup></th><th colspan="2">binOCT</th><th colspan="2">CART</th></tr><tr><th>error</th><th>cpu</th><th>error</th><th>cpu</th><th>error</th><th>cpu</th><th>error</th><th>cpu</th><th>error</th><th>cpu</th><th>error</th><th>cpu</th><th>error</th><th>cpu</th><th>error</th><th>cpu</th><th>error</th><th>cpu</th></tr></thead><tbody><tr><td>adult_discretized</td><td><b>5020</b></td><td>0.43*</td><td><b>5020</b></td><td>0.84*</td><td><b>5020</b></td><td>0.51*</td><td><b>5020</b></td><td>8.4*</td><td><b>5020</b></td><td>3.6*</td><td><b>5020</b></td><td>6.4*</td><td><b>5020</b></td><td>3.8*</td><td>5600</td><td>3503</td><td>5758</td><td>0.05</td></tr><tr><td>anneal</td><td><b>112</b></td><td>0.03*</td><td><b>112</b></td><td>0.14*</td><td><b>112</b></td><td>0.06*</td><td><b>112</b></td><td>2.1*</td><td><b>112</b></td><td>0.40*</td><td><b>112</b></td><td>6.0*</td><td><b>112</b></td><td>3.0*</td><td>123</td><td>3042</td><td>149</td><td>0.00</td></tr><tr><td>balance-scale</td><td><b>49</b></td><td>0.00*</td><td><b>49</b></td><td>0.01*</td><td><b>49</b></td><td>0.00*</td><td><b>49</b></td><td>0.02*</td><td><b>49</b></td><td>0.02*</td><td><b>49</b></td><td>0.55*</td><td><b>49</b></td><td>1.0*</td><td>-</td><td>-</td><td><b>49</b></td><td>0.00</td></tr><tr><td>banknote</td><td><b>36</b></td><td>0.01*</td><td><b>36</b></td><td>0.02*</td><td><b>36</b></td><td>0.02*</td><td><b>36</b></td><td>0.09*</td><td><b>36</b></td><td>0.06*</td><td><b>36</b></td><td>0.88*</td><td><b>36</b></td><td>1.4*</td><td>-</td><td>-</td><td>118</td><td>0.00</td></tr><tr><td>breast-cancer</td><td><b>24</b></td><td>0.16*</td><td><b>24</b></td><td>0.07*</td><td><b>24</b></td><td>0.06*</td><td><b>24</b></td><td>0.89*</td><td><b>24</b></td><td>0.78*</td><td><b>24</b></td><td>5.7*</td><td><b>24</b></td><td>4.4*</td><td>25</td><td>3131</td><td>28</td><td>0.00</td></tr><tr><td>car</td><td><b>192</b></td><td>0.01*</td><td><b>192</b></td><td>0.01*</td><td><b>192</b></td><td>0.01*</td><td><b>192</b></td><td>0.03*</td><td><b>192</b></td><td>0.03*</td><td><b>192</b></td><td>1.7*</td><td><b>192</b></td><td>1.4*</td><td><b>192</b></td><td>1141</td><td>202</td><td>0.00</td></tr><tr><td>car_evaluation</td><td><b>202</b></td><td>0.00*</td><td><b>202</b></td><td>0.01*</td><td><b>202</b></td><td>0.01*</td><td><b>202</b></td><td>0.02*</td><td><b>202</b></td><td>0.01*</td><td><b>202</b></td><td>0.44*</td><td><b>202</b></td><td>0.62*</td><td>-</td><td>-</td><td>226</td><td>0.00</td></tr><tr><td>chess</td><td><b>0</b></td><td>0.00*</td><td><b>0</b></td><td>0.00*</td><td><b>0</b></td><td>0.00*</td><td><b>0</b></td><td>0.00*</td><td><b>0</b></td><td>0.00*</td><td><b>0</b></td><td>0.04*</td><td><b>0</b></td><td>0.14*</td><td>-</td><td>-</td><td><b>0</b></td><td>0.00</td></tr><tr><td>compas_discretized</td><td><b>2004</b></td><td>0.00*</td><td><b>2004</b></td><td>0.06*</td><td><b>2004</b></td><td>0.02*</td><td><b>2004</b></td><td>0.21*</td><td><b>2004</b></td><td>0.04*</td><td><b>2004</b></td><td>1.8*</td><td><b>2004</b></td><td>1.5*</td><td>2032</td><td>806</td><td>2072</td><td>0.01</td></tr><tr><td>heart-cleveland</td><td><b>41</b></td><td>0.05*</td><td><b>41</b></td><td>0.12*</td><td><b>41</b></td><td>0.04*</td><td><b>41</b></td><td>3.5*</td><td><b>41</b></td><td>0.60*</td><td><b>41</b></td><td>6.8*</td><td><b>41</b></td><td>4.5*</td><td>42</td><td>870</td><td>43</td><td>0.00</td></tr><tr><td>hepatitis</td><td><b>10</b></td><td>0.00*</td><td><b>10</b></td><td>0.03*</td><td><b>10</b></td><td>0.01*</td><td><b>10</b></td><td>1.1*</td><td><b>10</b></td><td>0.10*</td><td><b>10</b></td><td>3.9*</td><td><b>10</b></td><td>2.5*</td><td><b>10</b></td><td>2314</td><td>16</td><td>0.00</td></tr><tr><td>HTRU_2</td><td><b>401</b></td><td>1.2*</td><td><b>401</b></td><td>3.6*</td><td><b>401</b></td><td>2.8*</td><td><b>401</b></td><td>12*</td><td><b>401</b></td><td>7.3*</td><td><b>401</b></td><td>5.7*</td><td><b>401</b></td><td>4.9*</td><td>-</td><td>-</td><td>422</td><td>0.05</td></tr><tr><td>hypothyroid</td><td><b>61</b></td><td>0.07*</td><td><b>61</b></td><td>0.41*</td><td><b>61</b></td><td>0.19*</td><td><b>61</b></td><td>3.8*</td><td><b>61</b></td><td>0.52*</td><td><b>61</b></td><td>6.6*</td><td><b>61</b></td><td>2.8*</td><td>62</td><td>2662</td><td>62</td><td>0.01</td></tr><tr><td>IndiansDiabetes</td><td><b>166</b></td><td>0.02*</td><td><b>166</b></td><td>0.07*</td><td><b>166</b></td><td>0.05*</td><td><b>166</b></td><td>0.31*</td><td><b>166</b></td><td>0.29*</td><td><b>166</b></td><td>1.6*</td><td><b>166</b></td><td>4.0*</td><td>-</td><td>-</td><td>180</td><td>0.00</td></tr><tr><td>iris</td><td><b>1</b></td><td>0.00*</td><td><b>1</b></td><td>0.00*</td><td><b>1</b></td><td>0.00*</td><td><b>1</b></td><td>0.00*</td><td><b>1</b></td><td>0.00*</td><td><b>1</b></td><td>0.15*</td><td><b>1</b></td><td>0.07*</td><td>-</td><td>-</td><td><b>1</b></td><td>0.00</td></tr><tr><td>kr-vs-kp</td><td><b>198</b></td><td>0.09*</td><td><b>198</b></td><td>0.22*</td><td><b>198</b></td><td>0.04*</td><td><b>198</b></td><td>2.3*</td><td><b>198</b></td><td>0.17*</td><td><b>198</b></td><td>4.8*</td><td><b>198</b></td><td>3.0*</td><td>375</td><td>2200</td><td>306</td><td>0.01</td></tr><tr><td>lymph</td><td><b>12</b></td><td>0.01*</td><td><b>12</b></td><td>0.03*</td><td><b>12</b></td><td>0.01*</td><td><b>12</b></td><td>0.56*</td><td><b>12</b></td><td>0.19*</td><td><b>12</b></td><td>3.7*</td><td><b>12</b></td><td>3.1*</td><td>14</td><td>2298</td><td>17</td><td>0.00</td></tr><tr><td>magic04</td><td><b>3446</b></td><td>3.8*</td><td><b>3446</b></td><td>7.6*</td><td><b>3446</b></td><td>7.5*</td><td><b>3446</b></td><td>26*</td><td><b>3446</b></td><td>20*</td><td><b>3446</b></td><td>11*</td><td><b>3446</b></td><td>10*</td><td>-</td><td>-</td><td>3788</td><td>0.06</td></tr><tr><td>messidor</td><td><b>366</b></td><td>0.25*</td><td><b>366</b></td><td>0.63*</td><td><b>366</b></td><td>0.50*</td><td><b>366</b></td><td>4.9*</td><td><b>366</b></td><td>3.6*</td><td><b>366</b></td><td>5.3*</td><td><b>366</b></td><td>5.4*</td><td>-</td><td>-</td><td>384</td><td>0.00</td></tr><tr><td>monk1</td><td><b>11</b></td><td>0.00*</td><td><b>11</b></td><td>0.00*</td><td><b>11</b></td><td>0.00*</td><td><b>11</b></td><td>0.00*</td><td><b>11</b></td><td>0.00*</td><td><b>11</b></td><td>0.27*</td><td><b>11</b></td><td>0.44*</td><td>-</td><td>-</td><td><b>11</b></td><td>0.00</td></tr><tr><td>monk2</td><td><b>42</b></td><td>0.00*</td><td><b>42</b></td><td>0.00*</td><td><b>42</b></td><td>0.00*</td><td><b>42</b></td><td>0.01*</td><td><b>42</b></td><td>0.01*</td><td><b>42</b></td><td>0.37*</td><td><b>42</b></td><td>0.60*</td><td>-</td><td>-</td><td>57</td><td>0.00</td></tr><tr><td>monk3</td><td><b>6</b></td><td>0.00*</td><td><b>6</b></td><td>0.00*</td><td><b>6</b></td><td>0.00*</td><td><b>6</b></td><td>0.00*</td><td><b>6</b></td><td>0.00*</td><td><b>6</b></td><td>0.32*</td><td><b>6</b></td><td>0.41*</td><td>-</td><td>-</td><td>7</td><td>0.00</td></tr><tr><td>primary-tumor</td><td><b>46</b></td><td>0.00*</td><td><b>46</b></td><td>0.01*</td><td><b>46</b></td><td>0.00*</td><td><b>46</b></td><td>0.12*</td><td><b>46</b></td><td>0.02*</td><td><b>46</b></td><td>2.0*</td><td><b>46</b></td><td>0.95*</td><td><b>46</b></td><td>2722</td><td>53</td><td>0.00</td></tr><tr><td>seismic_bumps</td><td><b>160</b></td><td>0.28*</td><td><b>160</b></td><td>1.1*</td><td><b>160</b></td><td>0.84*</td><td><b>160</b></td><td>5.3*</td><td><b>160</b></td><td>4.1*</td><td><b>160</b></td><td>7.3*</td><td><b>160</b></td><td>7.1*</td><td>-</td><td>-</td><td>170</td><td>0.01</td></tr><tr><td>soybean</td><td><b>29</b></td><td>0.01*</td><td><b>29</b></td><td>0.02*</td><td><b>29</b></td><td>0.01*</td><td><b>29</b></td><td>0.23*</td><td><b>29</b></td><td>0.17*</td><td><b>29</b></td><td>2.3*</td><td><b>29</b></td><td>2.4*</td><td>31</td><td>3098</td><td>47</td><td>0.00</td></tr><tr><td>tic-tac-toe</td><td><b>216</b></td><td>0.01*</td><td><b>216</b></td><td>0.02*</td><td><b>216</b></td><td>0.01*</td><td><b>216</b></td><td>0.11*</td><td><b>216</b></td><td>0.10*</td><td><b>216</b></td><td>1.8*</td><td><b>216</b></td><td>2.6*</td><td>232</td><td>1794</td><td>236</td><td>0.00</td></tr><tr><td>vote</td><td><b>12</b></td><td>0.02*</td><td><b>12</b></td><td>0.02*</td><td><b>12</b></td><td>0.02*</td><td><b>12</b></td><td>0.29*</td><td><b>12</b></td><td>0.32*</td><td><b>12</b></td><td>2.6*</td><td><b>12</b></td><td>2.7*</td><td>13</td><td>2763</td><td>14</td><td>0.00</td></tr><tr><td>winequality-red</td><td><b>8</b></td><td>0.02*</td><td><b>8</b></td><td>0.10*</td><td><b>8</b></td><td>0.11*</td><td><b>8</b></td><td>0.37*</td><td><b>8</b></td><td>0.23*</td><td><b>8</b></td><td>1.2*</td><td><b>8</b></td><td>3.5*</td><td>-</td><td>-</td><td>9</td><td>0.00</td></tr><tr><td>yeast</td><td><b>403</b></td><td>0.07*</td><td><b>403</b></td><td>0.34*</td><td><b>403</b></td><td>0.10*</td><td><b>403</b></td><td>6.1*</td><td><b>403</b></td><td>0.66*</td><td><b>403</b></td><td>7.7*</td><td><b>403</b></td><td>1.6*</td><td>434</td><td>2683</td><td>418</td><td>0.00</td></tr></tbody></table>

<table><caption>Table 14: Comparison with state of the art: $m \ge 100$, depth 3</caption><thead><tr><th rowspan="2"></th><th colspan="2">Blossom</th><th colspan="2">Murtree</th><th colspan="2">Murtree<sup>P</sup></th><th colspan="2">DL8.5</th><th colspan="2">DL8.5<sup>P</sup></th><th colspan="2">CP</th><th colspan="2">CP<sup>P</sup></th><th colspan="2">binOCT</th><th colspan="2">CART</th></tr><tr><th>error</th><th>cpu</th><th>error</th><th>cpu</th><th>error</th><th>cpu</th><th>error</th><th>cpu</th><th>error</th><th>cpu</th><th>error</th><th>cpu</th><th>error</th><th>cpu</th><th>error</th><th>cpu</th><th>error</th><th>cpu</th></tr></thead><tbody><tr><td>audiology</td><td><b>5</b></td><td>0.06*</td><td><b>5</b></td><td>0.13*</td><td><b>5</b></td><td>0.06*</td><td><b>5</b></td><td>4.1*</td><td><b>5</b></td><td>0.85*</td><td><b>5</b></td><td>9.1*</td><td><b>5</b></td><td>5.0*</td><td>6</td><td>508</td><td>6</td><td>0.00</td></tr><tr><td>australian-credit</td><td><b>73</b></td><td>0.14*</td><td><b>73</b></td><td>0.35*</td><td><b>73</b></td><td>0.12*</td><td><b>73</b></td><td>9.7*</td><td><b>73</b></td><td>1.8*</td><td><b>73</b></td><td>14*</td><td><b>73</b></td><td>4.6*</td><td>87</td><td>192</td><td>87</td><td>0.00</td></tr><tr><td>bank conv</td><td><b>428</b></td><td>9.9*</td><td><b>428</b></td><td>16*</td><td><b>428</b></td><td>15*</td><td><b>428</b></td><td>112*</td><td><b>428</b></td><td>71*</td><td><b>428</b></td><td>73*</td><td><b>428</b></td><td>63*</td><td>-</td><td>-</td><td>438</td><td>0.02</td></tr><tr><td>biogeg</td><td><b>164</b></td><td>5.4*</td><td><b>164</b></td><td>12*</td><td><b>164</b></td><td>12*</td><td><b>164</b></td><td>141*</td><td><b>164</b></td><td>98*</td><td><b>164</b></td><td>90*</td><td><b>164</b></td><td>103*</td><td>-</td><td>-</td><td>184</td><td>0.01</td></tr><tr><td>breast-wisconsin</td><td><b>15</b></td><td>0.05*</td><td><b>15</b></td><td>0.20*</td><td><b>15</b></td><td>0.07*</td><td><b>15</b></td><td>5.6*</td><td><b>15</b></td><td>0.76*</td><td><b>15</b></td><td>11*</td><td><b>15</b></td><td>2.0*</td><td>18</td><td>1858</td><td>26</td><td>0.00</td></tr><tr><td>default_credit</td><td><b>5327</b></td><td>232*</td><td><b>5327</b></td><td>451*</td><td><b>5327</b></td><td>450*</td><td><b>5327</b></td><td>1730*</td><td><b>5327</b></td><td>1389*</td><td><b>5327</b></td><td>510*</td><td><b>5327</b></td><td>462*</td><td>-</td><td>-</td><td>5349</td><td>0.48</td></tr><tr><td>diabetes</td><td><b>162</b></td><td>0.09*</td><td><b>162</b></td><td>0.37*</td><td><b>162</b></td><td>0.12*</td><td><b>162</b></td><td>10*</td><td><b>162</b></td><td>1.00*</td><td><b>162</b></td><td>12*</td><td><b>162</b></td><td>4.6*</td><td>165</td><td>3501</td><td>177</td><td>0.00</td></tr><tr><td>forest-fires</td><td><b>193</b></td><td>20*</td><td><b>193</b></td><td>9.6*</td><td><b>193</b></td><td>4.3*</td><td>-</td><td>-</td><td><b>193</b></td><td>301*</td><td><b>193</b></td><td>198</td><td>2836*</td><td>193</td><td>198</td><td>3501</td><td>198</td><td>0.01</td></tr><tr><td>german-credit</td><td><b>236</b></td><td>0.26*</td><td><b>236</b></td><td>0.38*</td><td><b>236</b></td><td>0.20*</td><td><b>236</b></td><td>9.4*</td><td><b>236</b></td><td>3.1*</td><td><b>236</b></td><td>13*</td><td><b>236</b></td><td>6.9*</td><td>244</td><td>2329</td><td>251</td><td>0.00</td></tr><tr><td>handposture</td><td><b>7645</b></td><td>181</td><td><b>7645</b></td><td>1134</td><td><b>7645</b></td><td>1110</td><td>10461</td><td>&gt;1h</td><td>10461</td><td>&gt;1h</td><td>8432</td><td>&gt;1h</td><td>8432</td><td>&gt;1h</td><td>-</td><td>-</td><td>8382</td><td>22</td></tr><tr><td>ionosphere</td><td><b>22</b></td><td>3.8*</td><td><b>22</b></td><td>12*</td><td><b>22</b></td><td>2.6*</td><td><b>22</b></td><td>397*</td><td><b>22</b></td><td>50*</td><td><b>22</b></td><td>460*</td><td><b>22</b></td><td>69*</td><td>27</td><td>3268</td><td>29</td><td>0.01</td></tr><tr><td>letter</td><td><b>369</b></td><td>10*</td><td><b>369</b></td><td>34*</td><td><b>369</b></td><td>11*</td><td><b>369</b></td><td>462*</td><td><b>369</b></td><td>44*</td><td><b>369</b></td><td>158*</td><td><b>369</b></td><td>19*</td><td>813</td><td>0.00</td><td>677</td><td>0.17</td></tr><tr><td>mnist_0</td><td><b>2557</b></td><td>1994*</td><td><b>2557</b></td><td>568*</td><td><b>2557</b></td><td>597*</td><td>3366</td><td>&gt;1h</td><td>3294</td><td>&gt;1h</td><td><b>2557</b></td><td>&gt;1h</td><td><b>2557</b></td><td>&gt;1h</td><td>-</td><td>-</td><td>3329</td><td>2.5</td></tr><tr><td>mushroom</td><td><b>8</b></td><td>0.79*</td><td><b>8</b></td><td>0.53*</td><td><b>8</b></td><td>0.40*</td><td><b>8</b></td><td>6.8*</td><td><b>8</b></td><td>3.8*</td><td><b>8</b></td><td>8.4*</td><td><b>8</b></td><td>5.6*</td><td>180</td><td>2728</td><td>280</td><td>0.02</td></tr><tr><td>pendigits</td><td><b>47</b></td><td>3.3*</td><td><b>47</b></td><td>11*</td><td><b>47</b></td><td>3.4*</td><td><b>47</b></td><td>126*</td><td><b>47</b></td><td>13*</td><td><b>47</b></td><td>70*</td><td><b>47</b></td><td>12*</td><td>477</td><td>2663</td><td>51</td><td>0.05</td></tr><tr><td>segment</td><td><b>0</b></td><td>0.03*</td><td><b>0</b></td><td>0.13*</td><td><b>0</b></td><td>0.04*</td><td><b>0</b></td><td>2.0*</td><td><b>0</b></td><td>0.27*</td><td><b>0</b></td><td>4.1*</td><td><b>0</b></td><td>1.8*</td><td>4</td><td>2865</td><td>5</td><td>0.01</td></tr><tr><td>spambase</td><td><b>694</b></td><td>11*</td><td><b>694</b></td><td>38*</td><td><b>694</b></td><td>35*</td><td><b>694</b></td><td>291*</td><td><b>694</b></td><td>286*</td><td><b>694</b></td><td>203*</td><td><b>694</b></td><td>211*</td><td>-</td><td>-</td><td>704</td><td>0.05</td></tr><tr><td>splice-1</td><td><b>224</b></td><td>9.8*</td><td><b>224</b></td><td>5.3*</td><td><b>224</b></td><td>4.8*</td><td><b>224</b></td><td>108*</td><td><b>224</b></td><td>90*</td><td><b>224</b></td><td>173*</td><td><b>224</b></td><td>145*</td><td>453</td><td>3502</td><td>279</td><td>0.03</td></tr><tr><td>Statlog.satellite</td><td><b>187</b></td><td>79*</td><td><b>187</b></td><td>118*</td><td><b>187</b></td><td>116*</td><td><b>187</b></td><td>998*</td><td><b>187</b></td><td>905*</td><td><b>187</b></td><td>703*</td><td><b>187</b></td><td>865*</td><td>-</td><td>-</td><td>345</td><td>0.08</td></tr><tr><td>Statlog.shuttle</td><td><b>0</b></td><td>6.7*</td><td><b>0</b></td><td>81*</td><td><b>0</b></td><td>70*</td><td><b>1</b></td><td>&gt;1h</td><td>1</td><td>&gt;1h</td><td><b>0</b></td><td>39*</td><td><b>0</b></td><td>39*</td><td>-</td><td>-</td><td>58</td><td>1.7</td></tr><tr><td>surgical-deepnet</td><td><b>2512</b></td><td>953</td><td><b>2512</b></td><td>3523</td><td>2524</td><td>605</td><td>-</td><td>-</td><td>2768</td><td>&gt;1h</td><td><b>2512</b></td><td>&gt;1h</td><td><b>2512</b></td><td>&gt;1h</td><td>-</td><td>-</td><td>2924</td><td>5.7</td></tr><tr><td>taiwan_binarised</td><td><b>5326</b></td><td>48*</td><td><b>5326</b></td><td>45*</td><td><b>5326</b></td><td>35*</td><td><b>5326</b></td><td>511*</td><td><b>5326</b></td><td>328*</td><td><b>5326</b></td><td>190*</td><td><b>5326</b></td><td>176*</td><td>6636</td><td>0.00</td><td>5346</td><td>0.26</td></tr><tr><td>titanic</td><td><b>143</b></td><td>6.7*</td><td><b>143</b></td><td>11*</td><td><b>143</b></td><td>9.6*</td><td><b>143</b></td><td>135*</td><td><b>143</b></td><td>107*</td><td><b>143</b></td><td>173*</td><td><b>143</b></td><td>182*</td><td>150</td><td>3362</td><td>148</td><td>0.01</td></tr><tr><td>vehicle</td><td><b>26</b></td><td>0.93*</td><td><b>26</b></td><td>2.2*</td><td><b>26</b></td><td>0.58*</td><td><b>26</b></td><td>63*</td><td><b>26</b></td><td>6.5*</td><td><b>26</b></td><td>66*</td><td><b>26</b></td><td>11*</td><td>42</td><td>3374</td><td>66</td><td>0.01</td></tr><tr><td>weather-aus</td><td><b>1756</b></td><td>14</td><td><b>1756</b></td><td>611</td><td><b>1756</b></td><td>687</td><td>-</td><td>-</td><td>-</td><td>-</td><td><b>1756</b></td><td>&gt;1h</td><td>-</td><td>-</td><td>-</td><td>-</td><td>1761</td><td>20</td></tr><tr><td>wine1</td><td><b>43</b></td><td>16*</td><td><b>43</b></td><td>9.0*</td><td><b>43</b></td><td>2.0*</td><td>-</td><td>-</td><td><b>43</b></td><td>200*</td><td><b>43</b></td><td>&gt;1h</td><td><b>43</b></td><td>703*</td><td>44</td><td>3507</td><td>45</td><td>0.00</td></tr><tr><td>wine2</td><td><b>49</b></td><td>17*</td><td><b>49</b></td><td>5.8*</td><td><b>49</b></td><td>1.5*</td><td>-</td><td>-</td><td><b>49</b></td><td>189*</td><td><b>49</b></td><td>&gt;1h</td><td><b>49</b></td><td>680*</td><td>57</td><td>3207</td><td>52</td><td>0.00</td></tr><tr><td>wine3</td><td><b>33</b></td><td>16*</td><td><b>33</b></td><td>8.4*</td><td><b>33</b></td><td>2.3*</td><td>-</td><td>-</td><td><b>33</b></td><td>228*</td><td><b>33</b></td><td>&gt;1h</td><td><b>33</b></td><td>649*</td><td>35</td><td>2814</td><td>35</td><td>0.00</td></tr></tbody></table>
<table><caption>Table 15: Comparison with state of the art: $m < 100$, depth 4</caption><thead><tr><th rowspan="2"></th><th colspan="2">Blossom</th><th colspan="2">Murtree</th><th colspan="2">Murtree<sup>P</sup></th><th colspan="2">DL8.5</th><th colspan="2">DL8.5<sup>P</sup></th><th colspan="2">CP</th><th colspan="2">CP<sup>P</sup></th><th colspan="2">binOCT</th><th colspan="2">CART</th></tr><tr><th>error</th><th>cpu</th><th>error</th><th>cpu</th><th>error</th><th>cpu</th><th>error</th><th>cpu</th><th>error</th><th>cpu</th><th>error</th><th>cpu</th><th>error</th><th>cpu</th><th>error</th><th>cpu</th><th>error</th><th>cpu</th></tr></thead><tbody><tr><td>adult_discretized</td><td>4609</td><td>14*</td><td>4609</td><td>30*</td><td>4609</td><td>15*</td><td>4609</td><td>271*</td><td>4609</td><td>93*</td><td>4609</td><td>246*</td><td>4609</td><td>156*</td><td>5659</td><td>3392</td><td>5022</td><td>0.06</td></tr><tr><td>anneal</td><td>91</td><td>1.5*</td><td>91</td><td>5.0*</td><td>91</td><td>1.5*</td><td>91</td><td>102*</td><td>91</td><td>9.6*</td><td>91</td><td>193*</td><td>91</td><td>30*</td><td>108</td><td>2954</td><td>135</td><td>0.00</td></tr><tr><td>balance-scale</td><td>48</td><td>0.04*</td><td>48</td><td>0.05*</td><td>48</td><td>0.05*</td><td>48</td><td>0.22*</td><td>48</td><td>0.16*</td><td>48</td><td>1.8*</td><td>48</td><td>2.2*</td><td>-</td><td>-</td><td>49</td><td>0.00</td></tr><tr><td>banknote</td><td>13</td><td>0.08*</td><td>13</td><td>0.27*</td><td>13</td><td>0.22*</td><td>13</td><td>0.78*</td><td>13</td><td>0.59*</td><td>13</td><td>4.2*</td><td>13</td><td>2.9*</td><td>-</td><td>-</td><td>38</td><td>0.00</td></tr><tr><td>breast-cancer</td><td>16</td><td>9.6*</td><td>16</td><td>2.9*</td><td>16</td><td>2.7*</td><td>16</td><td>28*</td><td>16</td><td>30*</td><td>16</td><td>219*</td><td>16</td><td>241*</td><td>22</td><td>2746</td><td>21</td><td>0.00</td></tr><tr><td>car</td><td>136</td><td>0.19*</td><td>136</td><td>0.16*</td><td>136</td><td>0.16*</td><td>136</td><td>0.36*</td><td>136</td><td>0.38*</td><td>136</td><td>2.8*</td><td>136</td><td>3.3*</td><td>178</td><td>871</td><td>178</td><td>0.00</td></tr><tr><td>car_evaluation</td><td>130</td><td>0.02*</td><td>130</td><td>0.07*</td><td>130</td><td>0.06*</td><td>130</td><td>0.13*</td><td>130</td><td>0.07*</td><td>130</td><td>1.3*</td><td>130</td><td>2.1*</td><td>-</td><td>-</td><td>130</td><td>0.00</td></tr><tr><td>chess</td><td>0</td><td>0.00*</td><td>0</td><td>0.00*</td><td>0</td><td>0.00*</td><td>0</td><td>0.00*</td><td>0</td><td>0.00*</td><td>0</td><td>0.07*</td><td>0</td><td>0.14*</td><td>-</td><td>-</td><td>0</td><td>0.00</td></tr><tr><td>compas_discretized</td><td>1954</td><td>0.07*</td><td>1954</td><td>1.0*</td><td>1954</td><td>0.19*</td><td>1954</td><td>3.5*</td><td>1954</td><td>0.45*</td><td>1954</td><td>6.3*</td><td>1954</td><td>2.2*</td><td>1991</td><td>3390</td><td>1997</td><td>0.01</td></tr><tr><td>heart-cleveland</td><td>25</td><td>3.1*</td><td>25</td><td>4.8*</td><td>25</td><td>1.1*</td><td>25</td><td>154*</td><td>25</td><td>17*</td><td>25</td><td>391*</td><td>25</td><td>47*</td><td>37</td><td>2750</td><td>38</td><td>0.00</td></tr><tr><td>hepatitis</td><td>3</td><td>0.32*</td><td>3</td><td>0.73*</td><td>3</td><td>0.14*</td><td>3</td><td>28*</td><td>3</td><td>1.2*</td><td>3</td><td>70*</td><td>3</td><td>8.4*</td><td>11</td><td>510</td><td>12</td><td>0.00</td></tr><tr><td>HTRU_2</td><td>385</td><td>74*</td><td>385</td><td>122*</td><td>385</td><td>101*</td><td>385</td><td>450*</td><td>385</td><td>276*</td><td>385</td><td>295*</td><td>385</td><td>253*</td><td>-</td><td>-</td><td>409</td><td>0.05</td></tr><tr><td>hypothyroid</td><td>53</td><td>2.9*</td><td>53</td><td>16*</td><td>53</td><td>3.4*</td><td>53</td><td>181*</td><td>53</td><td>12*</td><td>53</td><td>254*</td><td>53</td><td>24*</td><td>55</td><td>3071</td><td>53</td><td>0.01</td></tr><tr><td>IndiansDiabetes</td><td>149</td><td>0.90*</td><td>149</td><td>1.3*</td><td>149</td><td>1.3*</td><td>149</td><td>7.3*</td><td>149</td><td>6.6*</td><td>149</td><td>16*</td><td>149</td><td>16*</td><td>-</td><td>-</td><td>166</td><td>0.00</td></tr><tr><td>iris</td><td>1</td><td>0.00*</td><td>1</td><td>0.00*</td><td>1</td><td>0.00*</td><td>1</td><td>0.00*</td><td>1</td><td>0.00*</td><td>1</td><td>0.92*</td><td>1</td><td>0.05*</td><td>-</td><td>-</td><td>1</td><td>0.00</td></tr><tr><td>kr-vs-kp</td><td>144</td><td>2.8*</td><td>144</td><td>6.9*</td><td>144</td><td>0.93*</td><td>144</td><td>88*</td><td>144</td><td>3.6*</td><td>144</td><td>141*</td><td>144</td><td>15*</td><td>189</td><td>2850</td><td>189</td><td>0.01</td></tr><tr><td>lymph</td><td>3</td><td>0.74*</td><td>3</td><td>0.63*</td><td>3</td><td>0.25*</td><td>3</td><td>14*</td><td>3</td><td>3.0*</td><td>3</td><td>64*</td><td>3</td><td>19*</td><td>7</td><td>2987</td><td>10</td><td>0.00</td></tr><tr><td>magic04</td><td>3112</td><td>232*</td><td>3112</td><td>328*</td><td>3112</td><td>308*</td><td>3112</td><td>1296*</td><td>3112</td><td>1021*</td><td>3112</td><td>800*</td><td>3112</td><td>701*</td><td>-</td><td>-</td><td>3350</td><td>0.07</td></tr><tr><td>messidor</td><td>332</td><td>21*</td><td>332</td><td>27*</td><td>332</td><td>25*</td><td>332</td><td>245*</td><td>332</td><td>219*</td><td>332</td><td>269*</td><td>332</td><td>318*</td><td>-</td><td>-</td><td>364</td><td>0.00</td></tr><tr><td>monk1</td><td>2</td><td>0.00*</td><td>2</td><td>0.01*</td><td>2</td><td>0.01*</td><td>2</td><td>0.01*</td><td>2</td><td>0.01*</td><td>2</td><td>1.5*</td><td>2</td><td>0.93*</td><td>-</td><td>-</td><td>11</td><td>0.00</td></tr><tr><td>monk2</td><td>31</td><td>0.01*</td><td>31</td><td>0.01*</td><td>31</td><td>0.01*</td><td>31</td><td>0.04*</td><td>31</td><td>0.03*</td><td>31</td><td>2.1*</td><td>31</td><td>0.39*</td><td>-</td><td>-</td><td>50</td><td>0.00</td></tr><tr><td>monk3</td><td>4</td><td>0.00*</td><td>4</td><td>0.01*</td><td>4</td><td>0.01*</td><td>4</td><td>0.01*</td><td>4</td><td>0.01*</td><td>4</td><td>1.0*</td><td>4</td><td>1.1*</td><td>-</td><td>-</td><td>5</td><td>0.00</td></tr><tr><td>primary-tumor</td><td>34</td><td>0.03*</td><td>34</td><td>0.11*</td><td>34</td><td>0.03*</td><td>34</td><td>2.0*</td><td>34</td><td>0.13*</td><td>34</td><td>5.6*</td><td>34</td><td>2.2*</td><td>38</td><td>3132</td><td>44</td><td>0.00</td></tr><tr><td>seismic_bumps</td><td>148</td><td>22*</td><td>148</td><td>56*</td><td>148</td><td>44*</td><td>148</td><td>290*</td><td>148</td><td>175*</td><td>148</td><td>303*</td><td>148</td><td>307*</td><td>-</td><td>-</td><td>158</td><td>0.01</td></tr><tr><td>soybean</td><td>14</td><td>0.62*</td><td>14</td><td>0.46*</td><td>14</td><td>0.31*</td><td>14</td><td>5.1*</td><td>14</td><td>2.8*</td><td>14</td><td>22*</td><td>14</td><td>15*</td><td>22</td><td>2906</td><td>32</td><td>0.00</td></tr><tr><td>tic-tac-toe</td><td>137</td><td>0.38*</td><td>137</td><td>0.26*</td><td>137</td><td>0.23*</td><td>137</td><td>1.8*</td><td>137</td><td>1.4*</td><td>137</td><td>7.2*</td><td>137</td><td>6.5*</td><td>162</td><td>2511</td><td>150</td><td>0.00</td></tr><tr><td>vote</td><td>5</td><td>1.2*</td><td>5</td><td>0.50*</td><td>5</td><td>0.48*</td><td>5</td><td>7.6*</td><td>5</td><td>6.8*</td><td>5</td><td>21*</td><td>5</td><td>26*</td><td>12</td><td>3311</td><td>8</td><td>0.00</td></tr><tr><td>winequality-red</td><td>4</td><td>0.62*</td><td>4</td><td>1.2*</td><td>4</td><td>0.94*</td><td>4</td><td>4.3*</td><td>4</td><td>2.4*</td><td>4</td><td>12*</td><td>4</td><td>11*</td><td>-</td><td>-</td><td>8</td><td>0.00</td></tr><tr><td>yeast</td><td>366</td><td>3.4*</td><td>366</td><td>18*</td><td>366</td><td>2.9*</td><td>366</td><td>257*</td><td>366</td><td>21*</td><td>366</td><td>386*</td><td>366</td><td>34*</td><td>438</td><td>888</td><td>394</td><td>0.01</td></tr></tbody></table>

<table><caption>Table 16: Comparison with state of the art: $m \ge 100$, depth 4</caption><thead><tr><th rowspan="2"></th><th colspan="2">Blossom</th><th colspan="2">Murtree</th><th colspan="2">Murtree<sup>P</sup></th><th colspan="2">DL8.5</th><th colspan="2">DL8.5<sup>P</sup></th><th colspan="2">CP</th><th colspan="2">CP<sup>P</sup></th><th colspan="2">binOCT</th><th colspan="2">CART</th></tr><tr><th>error</th><th>cpu</th><th>error</th><th>cpu</th><th>error</th><th>cpu</th><th>error</th><th>cpu</th><th>error</th><th>cpu</th><th>error</th><th>cpu</th><th>error</th><th>cpu</th><th>error</th><th>cpu</th><th>error</th><th>cpu</th></tr></thead><tbody><tr><td>audiology</td><td>1</td><td>4.0*</td><td>1</td><td>6.4*</td><td>1</td><td>1.6*</td><td>1</td><td>128*</td><td>1</td><td>20*</td><td>1</td><td>773*</td><td>1</td><td>113*</td><td>2</td><td>2687</td><td>3</td><td>0.00</td></tr><tr><td>australian-credit</td><td>56</td><td>10*</td><td>56</td><td>24*</td><td>56</td><td>4.7*</td><td>56</td><td>470*</td><td>56</td><td>77*</td><td>56</td><td>1170*</td><td>56</td><td>179*</td><td>83</td><td>3258</td><td>74</td><td>0.00</td></tr><tr><td>bank conv</td><td>392</td><td>1963*</td><td>392</td><td>1651*</td><td>392</td><td>1621*</td><td>-</td><td>-</td><td>404</td><td>≥1h</td><td>392</td><td>≥1h</td><td>392</td><td>≥1h</td><td>-</td><td>-</td><td>408</td><td>0.04</td></tr><tr><td>biodeg</td><td>128</td><td>1511*</td><td>128</td><td>1436*</td><td>128</td><td>1323*</td><td>-</td><td>-</td><td>-</td><td>-</td><td>129</td><td>≥1h</td><td>129</td><td>≥1h</td><td>-</td><td>-</td><td>148</td><td>0.01</td></tr><tr><td>breast-wisconsin</td><td>7</td><td>3.1*</td><td>7</td><td>9.3*</td><td>7</td><td>1.8*</td><td>7</td><td>245*</td><td>7</td><td>24*</td><td>7</td><td>662*</td><td>7</td><td>58*</td><td>15</td><td>3460</td><td>16</td><td>0.00</td></tr><tr><td>default_credit</td><td>5270</td><td>209</td><td>5270</td><td>430</td><td>5270</td><td>430</td><td>5306</td><td>≥1h</td><td>5306</td><td>≥1h</td><td>5270</td><td>≥1h</td><td>5270</td><td>≥1h</td><td>-</td><td>-</td><td>5306</td><td>0.69</td></tr><tr><td>diabetes</td><td>137</td><td>5.7*</td><td>137</td><td>22*</td><td>137</td><td>3.5*</td><td>137</td><td>550*</td><td>137</td><td>35*</td><td>137</td><td>1001*</td><td>137</td><td>73*</td><td>180</td><td>2663</td><td>166</td><td>0.00</td></tr><tr><td>forest-fires</td><td>173</td><td>15</td><td>171</td><td>2907*</td><td>171</td><td>879*</td><td>-</td><td>-</td><td>171</td><td>≥1h</td><td>179</td><td>≥1h</td><td>173</td><td>≥1h</td><td>196</td><td>3356</td><td>186</td><td>0.01</td></tr><tr><td>german-credit</td><td>204</td><td>28*</td><td>204</td><td>27*</td><td>204</td><td>11*</td><td>204</td><td>423*</td><td>204</td><td>200*</td><td>204</td><td>1008*</td><td>204</td><td>453*</td><td>236</td><td>3306</td><td>231</td><td>0.00</td></tr><tr><td>hand_posture</td><td>4896</td><td>976</td><td>5778</td><td>1432</td><td>5778</td><td>1368</td><td>11021</td><td>≥1h</td><td>11021</td><td>≥1h</td><td>16265</td><td>≥1h</td><td>16265</td><td>≥1h</td><td>-</td><td>-</td><td>6098</td><td>27</td></tr><tr><td>ionosphere</td><td>7</td><td>730*</td><td>7</td><td>1683*</td><td>7</td><td>233*</td><td>-</td><td>-</td><td>7</td><td>≥1h</td><td>8</td><td>≥1h</td><td>8</td><td>≥1h</td><td>24</td><td>751</td><td>27</td><td>0.01</td></tr><tr><td>letter</td><td>261</td><td>1185*</td><td>261</td><td>2956*</td><td>261</td><td>540*</td><td>335</td><td>≥1h</td><td>261</td><td>2517*</td><td>261</td><td>≥1h</td><td>261</td><td>2076*</td><td>813</td><td>0.00</td><td>462</td><td>0.20</td></tr><tr><td>mnist_0</td><td>2173</td><td>2158</td><td>1951</td><td>3542</td><td>2077</td><td>3152</td><td>3319</td><td>≥1h</td><td>3294</td><td>≥1h</td><td>5923</td><td>≥1h</td><td>5923</td><td>≥1h</td><td>-</td><td>-</td><td>2311</td><td>3.8</td></tr><tr><td>mushroom</td><td>0</td><td>0.00*</td><td>0</td><td>0.03*</td><td>0</td><td>0.02*</td><td>0</td><td>41*</td><td>0</td><td>25*</td><td>0</td><td>0.07*</td><td>0</td><td>0.29*</td><td>192</td><td>3354</td><td>4</td><td>0.02</td></tr><tr><td>pendigits</td><td>13</td><td>230*</td><td>13</td><td>833*</td><td>13</td><td>129*</td><td>-</td><td>-</td><td>13</td><td>704*</td><td>14</td><td>≥1h</td><td>13</td><td>923*</td><td>780</td><td>0.00</td><td>25</td><td>0.07</td></tr><tr><td>segment</td><td>0</td><td>0.00*</td><td>0</td><td>0.02*</td><td>0</td><td>0.01*</td><td>0</td><td>1.6*</td><td>0</td><td>0.20*</td><td>0</td><td>2.5*</td><td>0</td><td>0.99*</td><td>1</td><td>3501</td><td>1</td><td>0.01</td></tr><tr><td>spambase</td><td>590</td><td>7.7</td><td>590</td><td>3295*</td><td>590</td><td>3117*</td><td>-</td><td>-</td><td>-</td><td>-</td><td>590</td><td>≥1h</td><td>590</td><td>≥1h</td><td>-</td><td>-</td><td>624</td><td>0.06</td></tr><tr><td>splice-1</td><td>141</td><td>3241*</td><td>141</td><td>644*</td><td>141</td><td>525*</td><td>-</td><td>-</td><td>212</td><td>≥1h</td><td>141</td><td>≥1h</td><td>141</td><td>≥1h</td><td>568</td><td>3416</td><td>141</td><td>0.03</td></tr><tr><td>Statlogsatellite</td><td>111</td><td>3571</td><td>116</td><td>1306</td><td>116</td><td>1322</td><td>-</td><td>-</td><td>187</td><td>≥1h</td><td>136</td><td>≥1h</td><td>136</td><td>≥1h</td><td>-</td><td>-</td><td>204</td><td>0.08</td></tr><tr><td>Statlog shuttle</td><td>0</td><td>0.64*</td><td>0</td><td>41*</td><td>0</td><td>41*</td><td>1</td><td>≥1h</td><td>2</td><td>≥1h</td><td>0</td><td>42*</td><td>0</td><td>30*</td><td>-</td><td>-</td><td>36</td><td>2.4</td></tr><tr><td>surgical-deepnet</td><td>2269</td><td>49</td><td>2506</td><td>489</td><td>2506</td><td>498</td><td>-</td><td>-</td><td>2767</td><td>≥1h</td><td>3690</td><td>≥1h</td><td>3690</td><td>≥1h</td><td>-</td><td>-</td><td>2704</td><td>6.2</td></tr><tr><td>taiwan_binarised</td><td>5273</td><td>6.2</td><td>5273</td><td>37</td><td>5273</td><td>34</td><td>5307</td><td>≥1h</td><td>5307</td><td>≥1h</td><td>5273</td><td>≥1h</td><td>5273</td><td>≥1h</td><td>6521</td><td>75</td><td>5306</td><td>0.27</td></tr><tr><td>titanic</td><td>119</td><td>1604*</td><td>119</td><td>2104*</td><td>119</td><td>1874*</td><td>-</td><td>-</td><td>-</td><td>-</td><td>119</td><td>≥1h</td><td>119</td><td>≥1h</td><td>135</td><td>3501</td><td>134</td><td>0.01</td></tr><tr><td>vehicle</td><td>12</td><td>71*</td><td>12</td><td>172*</td><td>12</td><td>26*</td><td>-</td><td>-</td><td>12</td><td>427*</td><td>12</td><td>≥1h</td><td>12</td><td>919*</td><td>30</td><td>3410</td><td>28</td><td>0.01</td></tr><tr><td>weather-aus</td><td>1749</td><td>2525</td><td>1750</td><td>1243</td><td>1750</td><td>1252</td><td>-</td><td>-</td><td>-</td><td>-</td><td>1752</td><td>≥1h</td><td>-</td><td>-</td><td>-</td><td>-</td><td>1761</td><td>20</td></tr><tr><td>wine1</td><td>37</td><td>1674</td><td>37</td><td>1831*</td><td>37</td><td>265*</td><td>-</td><td>-</td><td>-</td><td>-</td><td>39</td><td>≥1h</td><td>39</td><td>≥1h</td><td>45</td><td>3506</td><td>42</td><td>0.01</td></tr><tr><td>wine2</td><td>43</td><td>17</td><td>43</td><td>1833*</td><td>43</td><td>218*</td><td>-</td><td>-</td><td>-</td><td>-</td><td>46</td><td>≥1h</td><td>43</td><td>≥1h</td><td>57</td><td>3232</td><td>47</td><td>0.01</td></tr><tr><td>wine3</td><td>28</td><td>33</td><td>28</td><td>2537*</td><td>28</td><td>320*</td><td>-</td><td>-</td><td>-</td><td>-</td><td>30</td><td>≥1h</td><td>30</td><td>≥1h</td><td>32</td><td>3388</td><td>32</td><td>0.01</td></tr></tbody></table>
<table><caption>Table 17: Comparison with state of the art: $m < 100$, depth 5</caption><thead><tr><th rowspan="2"></th><th colspan="2">Blossom</th><th colspan="2">Murtree</th><th colspan="2">Murtree<sup>P</sup></th><th colspan="2">DL8.5</th><th colspan="2">DL8.5<sup>P</sup></th><th colspan="2">CP</th><th colspan="2">CP<sup>P</sup></th><th colspan="2">binOCT</th><th colspan="2">CART</th></tr><tr><th>error</th><th>cpu</th><th>error</th><th>cpu</th><th>error</th><th>cpu</th><th>error</th><th>cpu</th><th>error</th><th>cpu</th><th>error</th><th>cpu</th><th>error</th><th>cpu</th><th>error</th><th>cpu</th><th>error</th><th>cpu</th></tr></thead><tbody><tr><td>adult_discretized</td><td>4423</td><td>725*</td><td>4423</td><td>794*</td><td>4423</td><td>420*</td><td>4442</td><td>&ge;1h</td><td>4423</td><td>2184*</td><td>4423</td><td>&ge;1h</td><td>4423</td><td>&ge;1h</td><td>7157</td><td>20</td><td>4728</td><td>0.08</td></tr><tr><td>anneal</td><td>70</td><td>44*</td><td>70</td><td>148*</td><td>70</td><td>22*</td><td>-</td><td>-</td><td>70</td><td>156*</td><td>75</td><td>&ge;1h</td><td>70</td><td>790*</td><td>101</td><td>2995</td><td>123</td><td>0.00</td></tr><tr><td>balance-scale</td><td>45</td><td>0.46*</td><td>45</td><td>0.44*</td><td>45</td><td>0.40*</td><td>45</td><td>1.0*</td><td>45</td><td>0.76*</td><td>45</td><td>7.9*</td><td>45</td><td>6.3*</td><td>-</td><td>-</td><td>49</td><td>0.00</td></tr><tr><td>banknote</td><td>3</td><td>0.88*</td><td>3</td><td>2.2*</td><td>3</td><td>1.4*</td><td>3</td><td>3.9*</td><td>3</td><td>2.2*</td><td>3</td><td>34*</td><td>3</td><td>27*</td><td>-</td><td>-</td><td>15</td><td>0.00</td></tr><tr><td>breast-cancer</td><td>6</td><td>725*</td><td>6</td><td>72*</td><td>6</td><td>72*</td><td>6</td><td>438*</td><td>6</td><td>478*</td><td>6</td><td>&ge;1h</td><td>6</td><td>&ge;1h</td><td>14</td><td>2894</td><td>16</td><td>0.00</td></tr><tr><td>car</td><td>86</td><td>2.4*</td><td>86</td><td>1.2*</td><td>86</td><td>1.2*</td><td>86</td><td>2.7*</td><td>86</td><td>2.5*</td><td>86</td><td>21*</td><td>86</td><td>27*</td><td>138</td><td>3379</td><td>106</td><td>0.01</td></tr><tr><td>car_evaluation</td><td>90</td><td>0.13*</td><td>90</td><td>0.37*</td><td>90</td><td>0.18*</td><td>90</td><td>0.49*</td><td>90</td><td>0.15*</td><td>90</td><td>4.9*</td><td>90</td><td>3.7*</td><td>-</td><td>-</td><td>116</td><td>0.00</td></tr><tr><td>chess</td><td>0</td><td>0.00*</td><td>0</td><td>0.00*</td><td>0</td><td>0.00*</td><td>0</td><td>0.00*</td><td>0</td><td>0.00*</td><td>0</td><td>0.08*</td><td>0</td><td>0.04*</td><td>-</td><td>-</td><td>0</td><td>0.00</td></tr><tr><td>compas_discretized</td><td>1919</td><td>1.1*</td><td>1919</td><td>11*</td><td>1919</td><td>1.7*</td><td>1919</td><td>26*</td><td>1919</td><td>3.3*</td><td>1919</td><td>77*</td><td>1919</td><td>20*</td><td>1952</td><td>3153</td><td>1968</td><td>0.01</td></tr><tr><td>heart-cleveland</td><td>7</td><td>93*</td><td>7</td><td>101*</td><td>7</td><td>17*</td><td>-</td><td>-</td><td>7</td><td>236*</td><td>7</td><td>&ge;1h</td><td>7</td><td>1731*</td><td>26</td><td>3288</td><td>26</td><td>0.00</td></tr><tr><td>hepatitis</td><td>0</td><td>0.05*</td><td>0</td><td>0.18*</td><td>0</td><td>0.05*</td><td>0</td><td>71*</td><td>0</td><td>1.8*</td><td>0</td><td>12*</td><td>0</td><td>3.8*</td><td>6</td><td>3026</td><td>8</td><td>0.00</td></tr><tr><td>HTRU_2</td><td>361</td><td>98</td><td>361</td><td>2724*</td><td>361</td><td>2302*</td><td>369</td><td>&ge;1h</td><td>362</td><td>&ge;1h</td><td>361</td><td>&ge;1h</td><td>361</td><td>&ge;1h</td><td>-</td><td>-</td><td>394</td><td>0.06</td></tr><tr><td>hypothyroid</td><td>44</td><td>87*</td><td>44</td><td>343*</td><td>44</td><td>50*</td><td>-</td><td>-</td><td>44</td><td>172*</td><td>45</td><td>&ge;1h</td><td>44</td><td>684*</td><td>64</td><td>3324</td><td>50</td><td>0.01</td></tr><tr><td>IndiansDiabetes</td><td>125</td><td>30*</td><td>125</td><td>19*</td><td>125</td><td>17*</td><td>125</td><td>125*</td><td>125</td><td>122*</td><td>125</td><td>410*</td><td>125</td><td>375*</td><td>-</td><td>-</td><td>162</td><td>0.00</td></tr><tr><td>iris</td><td>1</td><td>0.00*</td><td>1</td><td>0.00*</td><td>1</td><td>0.00*</td><td>1</td><td>0.01*</td><td>1</td><td>0.00*</td><td>1</td><td>1.2*</td><td>1</td><td>0.06*</td><td>-</td><td>-</td><td>1</td><td>0.00</td></tr><tr><td>kr-vs-kp</td><td>81</td><td>65*</td><td>81</td><td>150*</td><td>81</td><td>13*</td><td>-</td><td>-</td><td>81</td><td>37*</td><td>81</td><td>&ge;1h</td><td>81</td><td>399*</td><td>189</td><td>3502</td><td>189</td><td>0.01</td></tr><tr><td>lymph</td><td>0</td><td>0.00*</td><td>0</td><td>0.00*</td><td>0</td><td>0.00*</td><td>0</td><td>14*</td><td>0</td><td>2.6*</td><td>0</td><td>2.7*</td><td>0</td><td>2.8*</td><td>7</td><td>3380</td><td>4</td><td>0.00</td></tr><tr><td>magic04</td><td>2882</td><td>756</td><td>2882</td><td>873</td><td>831</td><td>831</td><td>2910</td><td>&ge;1h</td><td>2880</td><td>&ge;1h</td><td>2882</td><td>&ge;1h</td><td>2882</td><td>&ge;1h</td><td>-</td><td>-</td><td>3179</td><td>0.11</td></tr><tr><td>messidor</td><td>281</td><td>1522*</td><td>281</td><td>855*</td><td>281</td><td>790*</td><td>-</td><td>-</td><td>281</td><td>&ge;1h</td><td>292</td><td>&ge;1h</td><td>292</td><td>&ge;1h</td><td>-</td><td>-</td><td>345</td><td>0.00</td></tr><tr><td>monk1</td><td>0</td><td>0.00*</td><td>0</td><td>0.00*</td><td>0</td><td>0.00*</td><td>0</td><td>0.00*</td><td>0</td><td>0.00*</td><td>0</td><td>0.23*</td><td>0</td><td>0.10*</td><td>-</td><td>-</td><td>9</td><td>0.00</td></tr><tr><td>monk2</td><td>15</td><td>0.05*</td><td>15</td><td>0.05*</td><td>15</td><td>0.05*</td><td>15</td><td>0.09*</td><td>15</td><td>0.13*</td><td>15</td><td>2.8*</td><td>15</td><td>2.9*</td><td>-</td><td>-</td><td>32</td><td>0.00</td></tr><tr><td>monk3</td><td>2</td><td>0.03*</td><td>2</td><td>0.03*</td><td>2</td><td>0.02*</td><td>2</td><td>0.03*</td><td>2</td><td>0.02*</td><td>2</td><td>2.2*</td><td>2</td><td>2.7*</td><td>-</td><td>-</td><td>5</td><td>0.00</td></tr><tr><td>primary-tumor</td><td>26</td><td>0.38*</td><td>26</td><td>1.5*</td><td>26</td><td>0.23*</td><td>26</td><td>24*</td><td>26</td><td>0.41*</td><td>26</td><td>103*</td><td>26</td><td>9.2*</td><td>34</td><td>3255</td><td>35</td><td>0.00</td></tr><tr><td>seismic_bumps</td><td>132</td><td>1533*</td><td>132</td><td>1617*</td><td>132</td><td>1166*</td><td>-</td><td>-</td><td>133</td><td>&ge;1h</td><td>134</td><td>&ge;1h</td><td>134</td><td>&ge;1h</td><td>-</td><td>-</td><td>151</td><td>0.01</td></tr><tr><td>soybean</td><td>8</td><td>20*</td><td>8</td><td>7.6*</td><td>8</td><td>4.5*</td><td>8</td><td>63*</td><td>8</td><td>31*</td><td>8</td><td>752*</td><td>8</td><td>412*</td><td>14</td><td>3178</td><td>23</td><td>0.00</td></tr><tr><td>tic-tac-toe</td><td>63</td><td>10*</td><td>63</td><td>2.3*</td><td>63</td><td>2.3*</td><td>63</td><td>14*</td><td>63</td><td>11*</td><td>63</td><td>89*</td><td>63</td><td>110*</td><td>125</td><td>3052</td><td>78</td><td>0.00</td></tr><tr><td>vote</td><td>1</td><td>24*</td><td>1</td><td>6.1*</td><td>1</td><td>5.8*</td><td>1</td><td>45*</td><td>1</td><td>37*</td><td>1</td><td>522*</td><td>1</td><td>599*</td><td>8</td><td>1319</td><td>6</td><td>0.00</td></tr><tr><td>winequality-red</td><td>3</td><td>16*</td><td>3</td><td>18*</td><td>3</td><td>11*</td><td>3</td><td>39*</td><td>3</td><td>18*</td><td>3</td><td>232*</td><td>3</td><td>204*</td><td>-</td><td>-</td><td>6</td><td>0.00</td></tr><tr><td>yeast</td><td>313</td><td>139*</td><td>313</td><td>558*</td><td>313</td><td>53*</td><td>-</td><td>-</td><td>313</td><td>412*</td><td>315</td><td>&ge;1h</td><td>313</td><td>1120*</td><td>376</td><td>3456</td><td>367</td><td>0.01</td></tr></tbody></table>

<table><caption>Table 18: Comparison with state of the art: $m \ge 100$, depth 5</caption><thead><tr><th rowspan="2"></th><th colspan="2">Blossom</th><th colspan="2">Murtree</th><th colspan="2">Murtree<sup>P</sup></th><th colspan="2">DL8.5</th><th colspan="2">DL8.5<sup>P</sup></th><th colspan="2">CP</th><th colspan="2">CP<sup>P</sup></th><th colspan="2">binOCT</th><th colspan="2">CART</th></tr><tr><th>error</th><th>cpu</th><th>error</th><th>cpu</th><th>error</th><th>cpu</th><th>error</th><th>cpu</th><th>error</th><th>cpu</th><th>error</th><th>cpu</th><th>error</th><th>cpu</th><th>error</th><th>cpu</th><th>error</th><th>cpu</th></tr></thead><tbody><tr><td>audiology</td><td>0</td><td>0.00*</td><td>0</td><td>0.02*</td><td>0</td><td>0.01*</td><td>0</td><td>0.05*</td><td>0</td><td>0.02*</td><td>0</td><td>7.0*</td><td>0</td><td>3.8*</td><td>1</td><td>3083</td><td>2</td><td>0.00</td></tr><tr><td>australian-credit</td><td>39</td><td>658*</td><td>39</td><td>872*</td><td>39</td><td>116*</td><td>-</td><td>-</td><td>39</td><td>1779*</td><td>40</td><td>&ge;1h</td><td>40</td><td>&ge;1h</td><td>72</td><td>3282</td><td>64</td><td>0.00</td></tr><tr><td>bank conv</td><td>340</td><td>1662</td><td>340</td><td>1636</td><td>340</td><td>1449</td><td>-</td><td>-</td><td>404</td><td>&ge;1h</td><td>521</td><td>&ge;1h</td><td>521</td><td>&ge;1h</td><td>-</td><td>-</td><td>379</td><td>0.04</td></tr><tr><td>biodeg</td><td>88</td><td>268</td><td>88</td><td>1141</td><td>88</td><td>1030</td><td>-</td><td>-</td><td>-</td><td>-</td><td>356</td><td>&ge;1h</td><td>356</td><td>&ge;1h</td><td>-</td><td>-</td><td>127</td><td>0.01</td></tr><tr><td>breast-wisconsin</td><td>0</td><td>20*</td><td>0</td><td>72*</td><td>0</td><td>9.1*</td><td>-</td><td>-</td><td>0</td><td>83*</td><td>1</td><td>&ge;1h</td><td>0</td><td>471*</td><td>16</td><td>3105</td><td>13</td><td>0.00</td></tr><tr><td>default\credit</td><td>5181</td><td>3202</td><td>5251</td><td>3121</td><td>5251</td><td>3130</td><td>5334</td><td>&ge;1h</td><td>5334</td><td>&ge;1h</td><td>6636</td><td>&ge;1h</td><td>6636</td><td>&ge;1h</td><td>-</td><td>-</td><td>5273</td><td>1.0</td></tr><tr><td>diabetes</td><td>106</td><td>312*</td><td>106</td><td>920*</td><td>106</td><td>78*</td><td>-</td><td>-</td><td>106</td><td>974*</td><td>107</td><td>&ge;1h</td><td>106</td><td>2841*</td><td>160</td><td>3501</td><td>141</td><td>0.00</td></tr><tr><td>forest-fires</td><td>156</td><td>777</td><td>149</td><td>2977</td><td>149</td><td>857</td><td>-</td><td>-</td><td>172</td><td>177</td><td>172</td><td>&ge;1h</td><td>172</td><td>&ge;1h</td><td>207</td><td>3386</td><td>177</td><td>0.01</td></tr><tr><td>german-credit</td><td>161</td><td>2741*</td><td>161</td><td>973*</td><td>161</td><td>318*</td><td>-</td><td>-</td><td>161</td><td>&ge;1h</td><td>161</td><td>&ge;1h</td><td>161</td><td>&ge;1h</td><td>221</td><td>3504</td><td>209</td><td>0.01</td></tr><tr><td>hand\posture</td><td>3154</td><td>56</td><td>4482</td><td>1297</td><td>4482</td><td>1218</td><td>11736</td><td>&ge;1h</td><td>11736</td><td>&ge;1h</td><td>16265</td><td>&ge;1h</td><td>16265</td><td>&ge;1h</td><td>-</td><td>-</td><td>3377</td><td>42</td></tr><tr><td>ionosphere</td><td>0</td><td>506*</td><td>0</td><td>1340*</td><td>0</td><td>192*</td><td>-</td><td>-</td><td>-</td><td>-</td><td>4</td><td>&ge;1h</td><td>2</td><td>&ge;1h</td><td>25</td><td>3386</td><td>17</td><td>0.01</td></tr><tr><td>letter</td><td>168</td><td>3082</td><td>190</td><td>549</td><td>168</td><td>2091</td><td>352</td><td>&ge;1h</td><td>260</td><td>&ge;1h</td><td>813</td><td>&ge;1h</td><td>201</td><td>&ge;1h</td><td>813</td><td>0.00</td><td>335</td><td>0.32</td></tr><tr><td>mnist_0</td><td>1714</td><td>284</td><td>2066</td><td>2149</td><td>2066</td><td>2013</td><td>3319</td><td>&ge;1h</td><td>3319</td><td>&ge;1h</td><td>5923</td><td>&ge;1h</td><td>5923</td><td>&ge;1h</td><td>-</td><td>-</td><td>2021</td><td>4.5</td></tr><tr><td>mushroom</td><td>0</td><td>0.00*</td><td>0</td><td>0.03*</td><td>0</td><td>0.02*</td><td>0</td><td>36*</td><td>0</td><td>21*</td><td>0</td><td>0.10*</td><td>0</td><td>0.56*</td><td>1930</td><td>19</td><td>3</td><td>0.03</td></tr><tr><td>pendigits</td><td>0</td><td>284*</td><td>0</td><td>1295*</td><td>0</td><td>196*</td><td>-</td><td>-</td><td>2</td><td>&ge;1h</td><td>780</td><td>&ge;1h</td><td>0</td><td>3010*</td><td>751</td><td>30</td><td>11</td><td>0.07</td></tr><tr><td>segment</td><td>0</td><td>0.00*</td><td>0</td><td>0.02*</td><td>0</td><td>0.01*</td><td>0</td><td>1.0*</td><td>0</td><td>0.15*</td><td>0</td><td>2.0*</td><td>0</td><td>0.26*</td><td>41</td><td>2839</td><td>1</td><td>0.01</td></tr><tr><td>spambase</td><td>501</td><td>219</td><td>501</td><td>2340</td><td>501</td><td>2150</td><td>-</td><td>-</td><td>615</td><td>&ge;1h</td><td>1813</td><td>&ge;1h</td><td>1813</td><td>&ge;1h</td><td>-</td><td>-</td><td>571</td><td>0.05</td></tr><tr><td>splice-1</td><td>10</td><td>24</td><td>100</td><td>3308</td><td>100</td><td>2808</td><td>-</td><td>-</td><td>561</td><td>&ge;1h</td><td>1535</td><td>&ge;1h</td><td>1535</td><td>&ge;1h</td><td>814</td><td>16</td><td>117</td><td>0.04</td></tr><tr><td>Statlog\satellite</td><td>71</td><td>279</td><td>98</td><td>638</td><td>98</td><td>604</td><td>-</td><td>-</td><td>187</td><td>&ge;1h</td><td>1072</td><td>&ge;1h</td><td>1072</td><td>&ge;1h</td><td>-</td><td>-</td><td>128</td><td>0.13</td></tr><tr><td>Statlog\shuttle</td><td>0</td><td>0.06*</td><td>0</td><td>39*</td><td>0</td><td>38*</td><td>1</td><td>&ge;1h</td><td>1</td><td>&ge;1h</td><td>0</td><td>34*</td><td>0</td><td>23*</td><td>-</td><td>-</td><td>10</td><td>2.8</td></tr><tr><td>surgical-deepnet</td><td>2131</td><td>2168</td><td>2337</td><td>400</td><td>2337</td><td>381</td><td>-</td><td>-</td><td>2767</td><td>&ge;1h</td><td>3690</td><td>&ge;1h</td><td>3690</td><td>&ge;1h</td><td>-</td><td>-</td><td>2245</td><td>8.4</td></tr><tr><td>taiwan\binarised</td><td>5200</td><td>105</td><td>5261</td><td>38</td><td>5261</td><td>32</td><td>5412</td><td>&ge;1h</td><td>5412</td><td>&ge;1h</td><td>6636</td><td>&ge;1h</td><td>6636</td><td>&ge;1h</td><td>6636</td><td>0.00</td><td>5280</td><td>0.37</td></tr><tr><td>titanic</td><td>95</td><td>1428</td><td>95</td><td>1371</td><td>95</td><td>1074</td><td>-</td><td>-</td><td>-</td><td>-</td><td>342</td><td>&ge;1h</td><td>342</td><td>&ge;1h</td><td>149</td><td>3505</td><td>130</td><td>0.01</td></tr><tr><td>vehicle</td><td>1</td><td>690</td><td>1</td><td>1540</td><td>1</td><td>912*</td><td>-</td><td>-</td><td>-</td><td>-</td><td>218</td><td>&ge;1h</td><td>3</td><td>&ge;1h</td><td>85</td><td>3502</td><td>23</td><td>0.01</td></tr><tr><td>weather\aus</td><td>1735</td><td>419</td><td>1735</td><td>1907</td><td>1735</td><td>1980</td><td>-</td><td>-</td><td>-</td><td>-</td><td>1761</td><td>&ge;1h</td><td>-</td><td>-</td><td>-</td><td>-</td><td>1751</td><td>26</td></tr><tr><td>wine1</td><td>33</td><td>1154</td><td>33</td><td>287</td><td>33</td><td>76</td><td>-</td><td>-</td><td>-</td><td>-</td><td>38</td><td>&ge;1h</td><td>36</td><td>&ge;1h</td><td>46</td><td>2910</td><td>39</td><td>0.01</td></tr><tr><td>wine2</td><td>39</td><td>411</td><td>37</td><td>3400</td><td>37</td><td>438</td><td>-</td><td>-</td><td>-</td><td>-</td><td>42</td><td>&ge;1h</td><td>40</td><td>&ge;1h</td><td>50</td><td>3197</td><td>44</td><td>0.01</td></tr><tr><td>wine3</td><td>25</td><td>17</td><td>25</td><td>25</td><td>23</td><td>971</td><td>-</td><td>-</td><td>-</td><td>-</td><td>28</td><td>&ge;1h</td><td>27</td><td>&ge;1h</td><td>37</td><td>3288</td><td>30</td><td>0.01</td></tr></tbody></table>
<table><caption>Table 19: Comparison with state of the art: $m < 100$, depth 7</caption><thead><tr><th rowspan="2"></th><th colspan="2">Blossom</th><th colspan="2">Murtree</th><th colspan="2">Murtree<sup>P</sup></th><th colspan="2">DL8.5</th><th colspan="2">DL8.5<sup>P</sup></th><th colspan="2">CP</th><th colspan="2">CP<sup>P</sup></th><th colspan="2">binOCT</th><th colspan="2">CART</th></tr><tr><th>error</th><th>cpu</th><th>error</th><th>cpu</th><th>error</th><th>cpu</th><th>error</th><th>cpu</th><th>error</th><th>cpu</th><th>error</th><th>cpu</th><th>error</th><th>cpu</th><th>error</th><th>cpu</th><th>error</th><th>cpu</th></tr></thead><tbody><tr><td>adult_discretized</td><td>4191</td><td>534</td><td>4294</td><td>2016</td><td>4204</td><td>397</td><td>4998</td><td>≥1h</td><td>4539</td><td>≥1h</td><td>7511</td><td>≥1h</td><td>7511</td><td>≥1h</td><td>7511</td><td>0.00</td><td>4481</td><td>0.09</td></tr><tr><td>anneal</td><td>41</td><td>3036</td><td>50</td><td>836</td><td>36</td><td>1579*</td><td>-</td><td>-</td><td>-</td><td>-</td><td>187</td><td>≥1h</td><td>187</td><td>≥1h</td><td>106</td><td>3386</td><td>96</td><td>0.00</td></tr><tr><td>balance-scale</td><td>29</td><td>37*</td><td>29</td><td>17*</td><td>29</td><td>16*</td><td>29</td><td>10*</td><td>29</td><td>8.6*</td><td>29</td><td>228*</td><td>29</td><td>279*</td><td>-</td><td>-</td><td>49</td><td>0.00</td></tr><tr><td>banknote</td><td>2</td><td>0.00*</td><td>2</td><td>69*</td><td>2</td><td>0.01*</td><td>2</td><td>80*</td><td>2</td><td>0.01*</td><td>2</td><td>≥1h</td><td>2</td><td>0.12*</td><td>-</td><td>-</td><td>5</td><td>0.00</td></tr><tr><td>breast-cancer</td><td>0</td><td>1007*</td><td>0</td><td>150*</td><td>0</td><td>146*</td><td>0</td><td>450*</td><td>0</td><td>523*</td><td>1</td><td>≥1h</td><td>1</td><td>≥1h</td><td>19</td><td>3313</td><td>8</td><td>0.00</td></tr><tr><td>car</td><td>11</td><td>231*</td><td>11</td><td>27*</td><td>11</td><td>25*</td><td>11</td><td>16*</td><td>11</td><td>17*</td><td>11</td><td>1678*</td><td>11</td><td>1978*</td><td>80</td><td>3495</td><td>50</td><td>0.00</td></tr><tr><td>car_evaluation</td><td>80</td><td>0.00*</td><td>80</td><td>7.4*</td><td>80</td><td>0.00*</td><td>80</td><td>4.2*</td><td>80</td><td>0.01*</td><td>80</td><td>123*</td><td>80</td><td>0.16*</td><td>-</td><td>-</td><td>80</td><td>0.00</td></tr><tr><td>chess</td><td>0</td><td>0.00*</td><td>0</td><td>0.00*</td><td>0</td><td>0.00*</td><td>0</td><td>0.00*</td><td>0</td><td>0.00*</td><td>0</td><td>0.13*</td><td>0</td><td>0.08*</td><td>-</td><td>-</td><td>0</td><td>0.00</td></tr><tr><td>compas_discretized</td><td>1852</td><td>198*</td><td>1852</td><td>569*</td><td>1852</td><td>37*</td><td>1852</td><td>575*</td><td>1852</td><td>34*</td><td>1857</td><td>≥1h</td><td>1852</td><td>2014*</td><td>1940</td><td>3504</td><td>1941</td><td>0.01</td></tr><tr><td>heart-cleveland</td><td>0</td><td>0.00*</td><td>0</td><td>0.04*</td><td>0</td><td>0.02*</td><td>-</td><td>-</td><td>0</td><td>174*</td><td>0</td><td>3.0*</td><td>0</td><td>2.7*</td><td>17</td><td>3368</td><td>6</td><td>0.01</td></tr><tr><td>hepatitis</td><td>0</td><td>0.00*</td><td>0</td><td>0.01*</td><td>0</td><td>0.00*</td><td>0</td><td>8.9*</td><td>0</td><td>0.46*</td><td>0</td><td>0.49*</td><td>0</td><td>0.56*</td><td>1</td><td>3436</td><td>1</td><td>0.00</td></tr><tr><td>HTRU_2</td><td>297</td><td>3334</td><td>293</td><td>2992</td><td>293</td><td>1737</td><td>601</td><td>≥1h</td><td>599</td><td>≥1h</td><td>1639</td><td>≥1h</td><td>1639</td><td>≥1h</td><td>-</td><td>-</td><td>352</td><td>0.08</td></tr><tr><td>hypothyroid</td><td>22</td><td>3478</td><td>23</td><td>590</td><td>22</td><td>2548*</td><td>-</td><td>-</td><td>24</td><td>≥1h</td><td>277</td><td>≥1h</td><td>23</td><td>≥1h</td><td>277</td><td>274</td><td>42</td><td>0.01</td></tr><tr><td>IndiansDiabetes</td><td>44</td><td>3343</td><td>44</td><td>1355*</td><td>44</td><td>1138*</td><td>-</td><td>-</td><td>44</td><td>≥1h</td><td>268</td><td>≥1h</td><td>268</td><td>≥1h</td><td>-</td><td>-</td><td>113</td><td>0.00</td></tr><tr><td>iris</td><td>1</td><td>0.00*</td><td>1</td><td>0.00*</td><td>1</td><td>0.00*</td><td>1</td><td>0.01*</td><td>1</td><td>0.00*</td><td>1</td><td>2.6*</td><td>1</td><td>0.07*</td><td>-</td><td>-</td><td>1</td><td>0.00</td></tr><tr><td>kr-vs-kp</td><td>18</td><td>2550</td><td>21</td><td>2051</td><td>17</td><td>1063*</td><td>-</td><td>-</td><td>17</td><td>1733*</td><td>37</td><td>≥1h</td><td>34</td><td>≥1h</td><td>1096</td><td>43</td><td>103</td><td>0.01</td></tr><tr><td>lymph</td><td>0</td><td>0.00*</td><td>0</td><td>0.00*</td><td>0</td><td>0.00*</td><td>0</td><td>0.01*</td><td>0</td><td>0.00*</td><td>0</td><td>0.24*</td><td>0</td><td>0.32*</td><td>1</td><td>3431</td><td>0</td><td>0.00</td></tr><tr><td>magic04</td><td>2488</td><td>2773</td><td>2851</td><td>1512</td><td>2851</td><td>1414</td><td>3140</td><td>≥1h</td><td>3129</td><td>≥1h</td><td>6688</td><td>≥1h</td><td>6688</td><td>≥1h</td><td>-</td><td>-</td><td>2768</td><td>0.11</td></tr><tr><td>messidor</td><td>179</td><td>2456</td><td>203</td><td>1842</td><td>203</td><td>1354</td><td>-</td><td>-</td><td>248</td><td>≥1h</td><td>540</td><td>≥1h</td><td>540</td><td>≥1h</td><td>-</td><td>-</td><td>305</td><td>0.01</td></tr><tr><td>monk1</td><td>0</td><td>0.00*</td><td>0</td><td>0.00*</td><td>0</td><td>0.00*</td><td>0</td><td>0.00*</td><td>0</td><td>0.00*</td><td>0</td><td>0.17*</td><td>0</td><td>0.08*</td><td>-</td><td>-</td><td>8</td><td>0.00</td></tr><tr><td>monk2</td><td>0</td><td>0.00*</td><td>0</td><td>0.02*</td><td>0</td><td>0.02*</td><td>0</td><td>0.00*</td><td>0</td><td>0.00*</td><td>0</td><td>0.78*</td><td>0</td><td>0.30*</td><td>-</td><td>-</td><td>5</td><td>0.00</td></tr><tr><td>monk3</td><td>0</td><td>0.00*</td><td>0</td><td>0.00*</td><td>0</td><td>0.00*</td><td>0</td><td>0.00*</td><td>0</td><td>0.00*</td><td>0</td><td>0.45*</td><td>0</td><td>0.09*</td><td>-</td><td>-</td><td>2</td><td>0.00</td></tr><tr><td>primary-tumor</td><td>16</td><td>18*</td><td>16</td><td>162*</td><td>16</td><td>2.1*</td><td>16</td><td>458*</td><td>16</td><td>0.94*</td><td>16</td><td>≥1h</td><td>16</td><td>410*</td><td>24</td><td>3432</td><td>26</td><td>0.00</td></tr><tr><td>seismic_bumps</td><td>76</td><td>2389</td><td>97</td><td>193</td><td>82</td><td>3565</td><td>-</td><td>-</td><td>129</td><td>≥1h</td><td>170</td><td>≥1h</td><td>170</td><td>≥1h</td><td>-</td><td>-</td><td>137</td><td>0.01</td></tr><tr><td>soybean</td><td>2</td><td>19*</td><td>2</td><td>1108*</td><td>2</td><td>6.9*</td><td>-</td><td>-</td><td>2</td><td>164*</td><td>3</td><td>≥1h</td><td>3</td><td>≥1h</td><td>13</td><td>1579</td><td>11</td><td>0.00</td></tr><tr><td>tic-tac-toe</td><td>0</td><td>32*</td><td>0</td><td>8.4*</td><td>0</td><td>8.2*</td><td>0</td><td>29*</td><td>0</td><td>33*</td><td>0</td><td>764*</td><td>0</td><td>761*</td><td>46</td><td>3449</td><td>22</td><td>0.00</td></tr><tr><td>vote</td><td>0</td><td>0.00*</td><td>0</td><td>0.00*</td><td>0</td><td>0.01*</td><td>0</td><td>0.17*</td><td>0</td><td>0.14*</td><td>0</td><td>3.2*</td><td>0</td><td>3.7*</td><td>2</td><td>3348</td><td>2</td><td>0.00</td></tr><tr><td>winequality-red</td><td>2</td><td>0.01*</td><td>2</td><td>1131*</td><td>2</td><td>0.02*</td><td>-</td><td>-</td><td>2</td><td>0.04*</td><td>10</td><td>≥1h</td><td>2</td><td>0.93*</td><td>-</td><td>-</td><td>4</td><td>0.00</td></tr><tr><td>yeast</td><td>182</td><td>3558</td><td>222</td><td>1088</td><td>165</td><td>2224</td><td>-</td><td>-</td><td>260</td><td>≥1h</td><td>463</td><td>≥1h</td><td>215</td><td>≥1h</td><td>455</td><td>1968</td><td>306</td><td>0.02</td></tr></tbody></table>

<table><caption>Table 20: Comparison with state of the art: $m \ge 100$, depth 7</caption><thead><tr><th rowspan="2"></th><th colspan="2">Blossom</th><th colspan="2">Murtree</th><th colspan="2">Murtree<sup>P</sup></th><th colspan="2">DL8.5</th><th colspan="2">DL8.5<sup>P</sup></th><th colspan="2">CP</th><th colspan="2">CP<sup>P</sup></th><th colspan="2">binOCT</th><th colspan="2">CART</th></tr><tr><th>error</th><th>cpu</th><th>error</th><th>cpu</th><th>error</th><th>cpu</th><th>error</th><th>cpu</th><th>error</th><th>cpu</th><th>error</th><th>cpu</th><th>error</th><th>cpu</th><th>error</th><th>cpu</th><th>error</th><th>cpu</th></tr></thead><tbody><tr><td>audiology</td><td>0</td><td>0.00*</td><td>0</td><td>0.01*</td><td>0</td><td>0.00*</td><td>0</td><td>0.00*</td><td>0</td><td>0.00*</td><td>0</td><td>0.18*</td><td>0</td><td>0.25*</td><td>3</td><td>2177</td><td>0</td><td>0.00</td></tr><tr><td>australian-credit</td><td>0</td><td>101*</td><td>0</td><td>126*</td><td>0</td><td>30*</td><td>-</td><td>-</td><td>3</td><td>≥1h</td><td>296</td><td>≥1h</td><td>296</td><td>≥1h</td><td>85</td><td>3320</td><td>43</td><td>0.01</td></tr><tr><td>bank conv</td><td>220</td><td>1642</td><td>319</td><td>1174</td><td>319</td><td>1090</td><td>-</td><td>-</td><td>405</td><td>≥1h</td><td>521</td><td>≥1h</td><td>521</td><td>≥1h</td><td>-</td><td>-</td><td>303</td><td>0.06</td></tr><tr><td>biodeg</td><td>26</td><td>2775</td><td>95</td><td>876</td><td>71</td><td>3544</td><td>-</td><td>-</td><td>-</td><td>-</td><td>356</td><td>≥1h</td><td>356</td><td>≥1h</td><td>-</td><td>-</td><td>86</td><td>0.02</td></tr><tr><td>breast-wisconsin</td><td>0</td><td>0.02*</td><td>0</td><td>0.09*</td><td>0</td><td>0.02*</td><td>-</td><td>-</td><td>0</td><td>38*</td><td>0</td><td>2805*</td><td>0</td><td>111*</td><td>12</td><td>3502</td><td>4</td><td>0.00</td></tr><tr><td>default\credit</td><td>4935</td><td>222</td><td>5237</td><td>223</td><td>5237</td><td>222</td><td>5412</td><td>≥1h</td><td>5412</td><td>≥1h</td><td>6636</td><td>≥1h</td><td>6636</td><td>≥1h</td><td>-</td><td>-</td><td>5153</td><td>1.0</td></tr><tr><td>diabetes</td><td>21</td><td>827</td><td>81</td><td>2000</td><td>12</td><td>498</td><td>-</td><td>-</td><td>86</td><td>≥1h</td><td>268</td><td>≥1h</td><td>268</td><td>≥1h</td><td>179</td><td>1988</td><td>100</td><td>0.01</td></tr><tr><td>forest-fires</td><td>146</td><td>125</td><td>139</td><td>2254</td><td>138</td><td>2715</td><td>-</td><td>-</td><td>-</td><td>-</td><td>247</td><td>≥1h</td><td>247</td><td>≥1h</td><td>270</td><td>0.00</td><td>161</td><td>0.02</td></tr><tr><td>german-credit</td><td>56</td><td>1192</td><td>87</td><td>341</td><td>86</td><td>2385</td><td>-</td><td>-</td><td>171</td><td>≥1h</td><td>300</td><td>≥1h</td><td>300</td><td>≥1h</td><td>246</td><td>2598</td><td>150</td><td>0.01</td></tr><tr><td>hand\posture</td><td>749</td><td>2684</td><td>1418</td><td>461</td><td>418</td><td>413</td><td>14236</td><td>≥1h</td><td>14236</td><td>≥1h</td><td>16265</td><td>≥1h</td><td>16265</td><td>≥1h</td><td>-</td><td>-</td><td>962</td><td>78</td></tr><tr><td>ionosphere</td><td>0</td><td>0.07*</td><td>0</td><td>0.37*</td><td>0</td><td>0.10*</td><td>-</td><td>-</td><td>0</td><td>63*</td><td>0</td><td>566*</td><td>0</td><td>53*</td><td>61</td><td>213</td><td>7</td><td>0.01</td></tr><tr><td>letter</td><td>68</td><td>177</td><td>131</td><td>86</td><td>66</td><td>1473</td><td>488</td><td>≥1h</td><td>324</td><td>≥1h</td><td>813</td><td>≥1h</td><td>813</td><td>≥1h</td><td>-</td><td>-</td><td>153</td><td>0.31</td></tr><tr><td>mnist_0</td><td>1107</td><td>2895</td><td>1601</td><td>964</td><td>1601</td><td>948</td><td>3296</td><td>≥1h</td><td>3364</td><td>≥1h</td><td>5923</td><td>≥1h</td><td>5923</td><td>≥1h</td><td>-</td><td>-</td><td>1323</td><td>8.5</td></tr><tr><td>mushroom</td><td>0</td><td>0.00*</td><td>0</td><td>0.02*</td><td>0</td><td>0.03*</td><td>0</td><td>10*</td><td>0</td><td>6.6*</td><td>0</td><td>0.15*</td><td>0</td><td>0.35*</td><td>4208</td><td>0.00</td><td>0</td><td>0.03</td></tr><tr><td>pendigits</td><td>0</td><td>0.00*</td><td>0</td><td>0.15*</td><td>0</td><td>0.06*</td><td>-</td><td>-</td><td>0</td><td>1125*</td><td>0</td><td>8.1*</td><td>0</td><td>2.3*</td><td>780</td><td>0.00</td><td>1</td><td>0.07</td></tr><tr><td>segment</td><td>0</td><td>0.00*</td><td>0</td><td>0.02*</td><td>0</td><td>0.01*</td><td>0</td><td>0.23*</td><td>0</td><td>0.06*</td><td>0</td><td>0.28*</td><td>0</td><td>0.21*</td><td>330</td><td>0.00</td><td>0</td><td>0.01</td></tr><tr><td>spambase</td><td>352</td><td>3562</td><td>495</td><td>2265</td><td>495</td><td>2185</td><td>-</td><td>-</td><td>966</td><td>≥1h</td><td>1813</td><td>≥1h</td><td>1813</td><td>≥1h</td><td>-</td><td>-</td><td>462</td><td>0.08</td></tr><tr><td>splice-1</td><td>29</td><td>3484</td><td>47</td><td>881</td><td>47</td><td>775</td><td>-</td><td>-</td><td>575</td><td>≥1h</td><td>1535</td><td>≥1h</td><td>1535</td><td>≥1h</td><td>1655</td><td>0.00</td><td>58</td><td>0.05</td></tr><tr><td>Statlog\satellite</td><td>14</td><td>2428</td><td>89</td><td>2540</td><td>89</td><td>2419</td><td>-</td><td>-</td><td>185</td><td>≥1h</td><td>1072</td><td>≥1h</td><td>1072</td><td>≥1h</td><td>-</td><td>-</td><td>41</td><td>0.12</td></tr><tr><td>Statlog\shuttle</td><td>0</td><td>0.04*</td><td>0</td><td>42*</td><td>0</td><td>40*</td><td>0</td><td>3163*</td><td>0</td><td>2500*</td><td>0</td><td>14*</td><td>0</td><td>12*</td><td>-</td><td>-</td><td>4</td><td>2.8</td></tr><tr><td>surgical-deepnet</td><td>1647</td><td>1248</td><td>1890</td><td>655</td><td>1885</td><td>3540</td><td>-</td><td>-</td><td>2767</td><td>≥1h</td><td>3690</td><td>≥1h</td><td>3690</td><td>≥1h</td><td>-</td><td>-</td><td>1871</td><td>9.9</td></tr><tr><td>taiwan\binarised</td><td>4896</td><td>1958</td><td>5189</td><td>3125</td><td>5186</td><td>2596</td><td>5412</td><td>≥1h</td><td>5412</td><td>≥1h</td><td>6636</td><td>≥1h</td><td>6636</td><td>≥1h</td><td>-</td><td>-</td><td>5161</td><td>0.58</td></tr><tr><td>titanic</td><td>72</td><td>442</td><td>97</td><td>149</td><td>97</td><td>141</td><td>-</td><td>-</td><td>-</td><td>-</td><td>342</td><td>≥1h</td><td>342</td><td>≥1h</td><td>342</td><td>0.00</td><td>111</td><td>0.01</td></tr><tr><td>vehicle</td><td>0</td><td>0.09*</td><td>0</td><td>0.47*</td><td>0</td><td>0.14*</td><td>-</td><td>-</td><td>0</td><td>90*</td><td>0</td><td>1178*</td><td>0</td><td>88*</td><td>210</td><td>25</td><td>4</td><td>0.01</td></tr><tr><td>weather\aus</td><td>1685</td><td>2048</td><td>1724</td><td>3257</td><td>1724</td><td>3415</td><td>-</td><td>-</td><td>-</td><td>-</td><td>1761</td><td>≥1h</td><td>-</td><td>-</td><td>-</td><td>-</td><td>1721</td><td>27</td></tr><tr><td>wine1</td><td>28</td><td>892</td><td>28</td><td>325</td><td>27</td><td>2628</td><td>-</td><td>-</td><td>40</td><td>≥1h</td><td>36</td><td>≥1h</td><td>35</td><td>≥1h</td><td>57</td><td>122</td><td>33</td><td>0.01</td></tr><tr><td>wine2</td><td>31</td><td>28</td><td>31</td><td>25</td><td>30</td><td>1011</td><td>-</td><td>-</td><td>-</td><td>-</td><td>35</td><td>≥1h</td><td>32</td><td>≥1h</td><td>71</td><td>0.00</td><td>38</td><td>0.01</td></tr><tr><td>wine3</td><td>21</td><td>524</td><td>20</td><td>2925</td><td>17</td><td>2248</td><td>-</td><td>-</td><td>-</td><td>-</td><td>24</td><td>≥1h</td><td>23</td><td>≥1h</td><td>47</td><td>142</td><td>24</td><td>0.01</td></tr></tbody></table>