Decision Tree

A decision tree predicts by asking a sequence of simple questions about its input, such as “is pixel 12 brighter than 0.4?”, and following the answers down a tree until it reaches a leaf, which holds the prediction. Trees are learned from labelled examples by splitting the training set again and again, each time on the question that best separates the labels. They are fast, need no feature scaling, and can be read by a person, and they are the building block of boosting and of random forests. In computer vision they appear inside detectors and feature extractors: the Viola–Jones face detector chains single-node trees on rectangle features, FAST compiles a learned tree into its corner test, and forests of trees predicted edge masks and labelled pixels in land-cover maps.

This article covers the classification and regression tree (CART) algorithm as Murphy (§18.1) and scikit-learn’s user guide describe it, the impurity measures, cost-complexity pruning, ID3 and C4.5 in outline, what scikit-learn 1.7.2’s DecisionTreeClassifier computes as read in its source, and an example on synthetic image patches: a tree written in NumPy checked split for split against scikit-learn, trees on raw pixels against a tree on one engineered feature, how much trees change between resamples of the training set, and the pruning path. The Machine Learning hub uses tree depth as its example of capacity, and Boosting uses single-split trees (stumps) as weak learners; this article does not repeat their examples.

Problem

Given $n$ training examples $(\mathbf{x}_i, y_i)$ with $\mathbf{x}_i \in \mathbb{R}^D$ (for example the $D = 64$ pixels of an $8 \times 8$ patch) and a class label or a real-valued target $y_i$, learn a function that predicts $y$ for new inputs. A decision tree restricts that function to be piecewise constant on a partition of the input space into axis-aligned boxes, one per leaf, with the boxes defined by the threshold tests on the path from the root (Murphy, §18.1.1). Choosing the best such partition is a hard combinatorial problem: finding the optimal partitioning of the data is NP-complete, as Murphy (§18.1.2) states, citing Hyafil and Rivest (1976). Practical algorithms therefore grow the tree greedily, one node at a time.

Inputs and Outputs

• Input: a training matrix of $n$ examples by $D$ features, real-valued (and, in implementations that support them, categorical), the labels or targets, and the stopping and pruning settings.
• Output: a binary tree. Each internal node holds a feature index $d$ and a threshold $t$ and sends an input left if $x_d \le t$ and right otherwise; each leaf holds a prediction. For regression the leaf value is the mean target of the training examples in the leaf (Murphy, Eq. 18.3); for classification the leaf holds the distribution of class labels among them (§18.1.1), and the predicted class is the most frequent one. scikit-learn’s predict_proba returns that fraction of training samples of each class in the leaf, and predict the class with the highest probability, the lowest class index among ties (user guide §1.10.1).

Intuition

Think of sorting image patches into two piles by hand with a ruler and a list of yes/no questions. The first question should split the patches into two groups that are each as pure as possible, mostly one class. Then each group is treated as a new, smaller problem with the same procedure, until every group is pure or too small to split further. Each question looks at one feature at a time, so in the space of features every boundary the tree draws is parallel to an axis, and a boundary that is diagonal in that space can only be approximated by a staircase of many small steps. Murphy (§18.1.1, footnote) notes that deep enough trees can approximate decision boundaries of complex shape piecewise, but this may need a lot of data. The example below shows how many steps a diagonal rule in pixel space costs.

Algorithm

CART grows a tree top down (Murphy, §18.1.2; user guide §1.10.7):

1. Put all training examples at the root.
2. At a node with example set $Q$, stop and make the node a leaf if a stopping rule applies: the node is pure, it has too few examples, or the tree has reached its maximum depth.
3. Otherwise, for every feature $j$, sort the node’s values of $x_j$ and consider every threshold between consecutive distinct values. Each candidate $(j, t)$ splits $Q$ into $Q_L = \{x_j \le t\}$ and $Q_R$.
4. Score each candidate by the size-weighted impurity of the two children and choose the candidate with the lowest score, which is the one with the largest impurity decrease.
5. Split, and apply steps 2–5 to each child.
6. Optionally, prune the grown tree back (below).

Murphy (§18.1.2) takes the sorted unique values of a feature as its thresholds, with $x_j \le t$; scikit-learn places each threshold at the midpoint between two consecutive distinct values (below). Apart from Murphy’s largest value, which leaves the right side empty, both give the same splits of the training set. For categorical features, Murphy describes binary splits that test whether the feature equals each of its values, and multi-way splits as an alternative that may fragment the data.

Because the search is greedy, a split that is useless on its own but useful in combination is never chosen. Murphy (§18.1.3) gives the XOR problem as the example: neither feature alone has any predictive power, so top-down growing would make no split at all. The user guide (§1.10) lists XOR, parity and multiplexer problems as concepts that trees do not express easily.

Mathematical Formulation

Let node $m$ hold $n_m$ examples and let $p_{mk}$ be the fraction of them in class $k$. A candidate split $\theta = (j, t)$ is scored by

$$G(Q_m, \theta) = \frac{n_m^{L}}{n_m} H(Q_m^{L}(\theta)) + \frac{n_m^{R}}{n_m} H(Q_m^{R}(\theta)), \qquad \theta^* = \arg\min_\theta G(Q_m, \theta),$$

where $H$ is the impurity (user guide §1.10.7; Murphy, Eq. 18.5). For classification the two common impurities are

$$H_{\text{Gini}}(Q_m) = \sum_k p_{mk}(1 - p_{mk}) = 1 - \sum_k p_{mk}^2, \qquad H_{\text{entropy}}(Q_m) = -\sum_k p_{mk} \log p_{mk}.$$

Murphy (§18.1.2) reads the Gini index as an expected error rate: $p_{mk}$ is the probability that a random example in the node belongs to class $k$, and $1 - p_{mk}$ the probability that it would be misclassified. Both impurities are zero for a pure node. Dollár and Zitnick (2013, §2.1) write the same criterion as an information gain to be maximized,

$$I_m = H(Q_m) - \sum_{s \in \{L, R\}} \frac{|Q_m^s|}{|Q_m|} H(Q_m^s),$$

with the Shannon entropy or the Gini impurity as $H$; with the entropy, $I_m$ is the information gain that ID3 uses (FAST’s article writes it with counts for its three-way split). For regression, $H$ is the variance of the targets in the node, $H(Q_m) = \frac{1}{n_m}\sum_{y \in Q_m}(y - \bar y_m)^2$, and the leaf predicts $\bar y_m$ (Murphy, Eq. 18.6; Dollár and Zitnick, §2.1; user guide §1.10.7.2, which also lists the Poisson deviance and the absolute error, whose leaves predict the median).

scikit-learn’s user guide (§1.10.7.1) shows why the entropy criterion is natural for probabilistic prediction: because the predicted probabilities are constant within a leaf, the log loss of the tree on its training set equals the sum over leaves of the leaf entropies weighted by $n_m / n$, so minimizing the weighted entropy of the leaves minimizes the training log loss.

Weighted impurity decrease. scikit-learn reports the improvement of a split at node $t$ as

$$\Delta(t) = \frac{N_t}{N}\left( H_t - \frac{N_{t}^{R}}{N_t} H_{t}^{R} - \frac{N_{t}^{L}}{N_t} H_{t}^{L} \right),$$

with $N$ the total number of training samples (_criterion.pyx, impurity_improvement). Summing $\Delta(t)$ over the internal nodes that use feature $k$ and normalizing over features gives feature_importances_, the “Gini importance” of its docstring; Murphy (§18.6.1, Eq. 18.57) gives the CART book’s version of this measure as the sum of the reductions in cost at the nodes that use the feature.

Cost-complexity pruning. A fully grown tree fits its training set exactly when there is no label noise (Murphy, §18.1.3), and usually overfits. The two remedies Murphy names are to stop growing early by a heuristic (too few examples at a node, a maximum depth) or to grow the tree fully and then prune it back by merging subtrees into their parent. Minimal cost-complexity pruning, which scikit-learn’s user guide (§1.10.9) attributes to Chapter 3 of the CART book, scores a subtree $T$ by

$$R_\alpha(T) = R(T) + \alpha |\widetilde{T}|,$$

where $|\widetilde{T}|$ is the number of leaves and $R(T)$ is traditionally the total misclassification rate of the leaves; scikit-learn uses the total sample-weighted impurity of the leaves instead. For a node $t$ and the branch $T_t$ below it, the two costs $R(t) + \alpha$ and $R(T_t) + \alpha|\widetilde{T_t}|$ are equal at the node’s effective $\alpha$. As _tree.pyx computes it, with $R(t) = (N_t/N) H_t$,

$$\alpha_{\text{eff}}(t) = \frac{R(t) - R(T_t)}{|\widetilde{T_t}| - 1}.$$

The internal node with the smallest $\alpha_{\text{eff}}$ is the weakest link; it is collapsed into a leaf, the values of its ancestors are updated, and the process repeats until only the root is left. The sequence of effective alphas and of the total leaf impurity after each collapse is the pruning path. Fitting with ccp_alpha $= a$ keeps pruning while the smallest $\alpha_{\text{eff}}$ is at most $a$. scikit-learn leaves the choice of $\alpha$ to the user, for example by cross-validation over the path’s alphas.

Parameters

scikit-learn 1.7.2’s DecisionTreeClassifier has these defaults (from the installed signature): criterion="gini", splitter="best", max_depth=None, min_samples_split=2, min_samples_leaf=1, min_weight_fraction_leaf=0.0, max_features=None, random_state=None, max_leaf_nodes=None, min_impurity_decrease=0.0, class_weight=None, ccp_alpha=0.0 and monotonic_cst=None. DecisionTreeRegressor has the same settings with criterion="squared_error" and no class_weight.

• criterion: "gini", "entropy" or "log_loss". The last two map to the same class (_classes.py, CRITERIA_CLF), and its logarithm is base 2 (_utils.pyx defines log(x) as $\ln x / \ln 2$), so scikit-learn’s entropies are in bits.
• max_depth, min_samples_split, min_samples_leaf, max_leaf_nodes, min_impurity_decrease: stopping rules (pre-pruning). With the defaults, a tree grows until every leaf is pure or cannot be split. A node becomes a leaf if its depth reaches max_depth, it has fewer than min_samples_split samples or fewer than 2 * min_samples_leaf, its impurity is at most the float64 machine epsilon, or the best split’s improvement plus that epsilon is below min_impurity_decrease (_tree.pyx, depth-first builder). With max_leaf_nodes set, the tree grows best-first instead of depth-first (docstring). The user guide (§1.10.5) suggests starting with max_depth=3 and trying min_samples_leaf=5, and notes that the number of samples needed to populate the tree doubles with each extra level.
• ccp_alpha: the cost-complexity parameter above (post-pruning); cost_complexity_pruning_path(X, y) returns the alphas and impurities of the whole path.
• max_features and splitter: the number of features examined at each split, and "random" to choose the best of random thresholds. Both inject randomness. Dollár and Zitnick (2013, §2.2) describe this kind of randomness: forests are diversified by subsampling the data for each tree or the features and splits at each node, and in effect trade the accuracy of each tree for the diversity of the ensemble.
• random_state: even with splitter="best" and all features, the features are visited in a random order at every split, and when several splits give exactly the same improvement, the first one visited is kept (docstring; _splitter.pyx, where the best split is replaced only on a strictly larger improvement). Equal improvements are common, because the impurity depends only on how many examples of each class go to each side; the example below finds them at 67 of the 159 internal nodes of one tree. Fixing random_state makes a fit repeatable; changing it can give a different tree that is just as good on the training set.

Complexity

The user guide (§1.10.4) gives a construction cost of $O(n_{\text{samples}} n_{\text{features}} \log n_{\text{samples}})$ for a balanced tree and a query time of $O(\log n_{\text{samples}})$. It adds that the cost at each node, searching all features after sorting, is $O(n_{\text{features}} n_{\text{samples}} \log n_{\text{samples}})$ and that summing over all nodes gives $O(n_{\text{features}} n_{\text{samples}}^2 \log n_{\text{samples}})$ in total. Prediction is one comparison per level; in our reading, this is why trees suit the per-pixel or per-window tests of detectors. scikit-learn stores the training matrix as float32 and copies data that are not in that format (§1.10.5).

Implementation

scikit-learn 1.7.2. The user guide (§1.10.6) calls its tree “an optimized version of the CART algorithm” and notes that it does not support categorical variables. Read in the source, the classifier differs from CART as Murphy and the user guide describe it, or fixes what they leave open, in these ways:

• Thresholds. _splitter.pyx sorts the float32 values of a feature at the node, skips positions where two consecutive values differ by at most FEATURE_THRESHOLD $= 10^{-7}$, and sets the threshold to v_prev / 2.0 + v / 2.0 (a sum of halves, to avoid overflow), falling back to v_prev if the midpoint rounds to v. An input goes left if $x_j \le t$.
• Ties are broken by the random order of features described under Parameters.
• Missing values are supported with splitter="best": at each threshold the splitter tries sending all missing values left and all right, and also the split that separates missing from non-missing values (user guide §1.10.8). CART’s surrogate splits, backup variables that mimic the chosen split when its feature is missing (Murphy, §18.1.4), are not implemented.
• Pruning uses the sample-weighted impurity rather than the misclassification rate that the user guide calls traditional, collapses one node per step, taking the lowest node index where several share the smallest $\alpha_{\text{eff}}$ (_tree.pyx), and leaves the choice of $\alpha$ to the user (above).

Example. The script below works on synthetic $8 \times 8$ grayscale patches with an exactly known label. Each patch has a random brightness offset $c$, a vertical step edge whose signed height $s$ makes the left half brighter by $s/2$ and the right half darker by $s/2$, and independent pixel noise, all three drawn from $\mathcal{N}(0, 1)$. The label is 1 if the mean of the left half (columns 0–3) exceeds the mean of the right half (columns 4–7), computed on the noisy patch itself, so the rule is exact and the Bayes error is zero. In pixel space the rule is a single hyperplane with weight $+1/32$ on the 32 left pixels and $-1/32$ on the 32 right pixels: oblique to every axis. On the engineered feature $d = \text{left mean} - \text{right mean}$ it is one threshold at zero. The offset $c$ cancels in $d$ but not in any single pixel, so no single pixel decides the label. Each data seed (0–4) draws 2,000 training and 5,000 test patches. The script has four parts:

• (a) A CART written in NumPy (exhaustive search over all 64 pixels and every midpoint, with scikit-learn’s threshold rule, Gini or entropy in bits) is grown alongside DecisionTreeClassifier(random_state=0) on seed 0. At every node it checks that scikit-learn’s split is one of the splits our search finds optimal, following scikit-learn’s choice where several tie, and it compares node sizes, leaf status, node impurities and feature importances.
• (b) Fully grown trees on the 64 pixels against a tree on $d$ alone, for both criteria and five seeds.
• (c) Instability: 50 trees, each fitted to a bootstrap resample (2,000 draws with replacement) of the training set, for fully grown pixel trees, depth-1 pixel trees and fully grown trees on $d$. The measure is the mean pairwise disagreement: the fraction of test patches on which two of the 50 trees predict different labels, averaged over all 1,225 pairs.
• (d) cost_complexity_pruning_path against our own weakest-link computation on the node impurities and sizes of (a).

It ran with NumPy 2.3.5 and scikit-learn 1.7.2 under Python 3.13, with BLAS and OpenMP threads set to one, in about 17 seconds; two runs gave identical output. The NumPy tree is written from the behaviour described above, not copied from scikit-learn’s code.

import os
for v in ("OMP_NUM_THREADS", "OPENBLAS_NUM_THREADS", "MKL_NUM_THREADS"):
    os.environ[v] = "1"
import numpy as np
from sklearn.tree import DecisionTreeClassifier

P, N_TR, N_TE, B = 8, 2000, 5000, 50
FT = np.float32(1e-7)                 # scikit-learn's FEATURE_THRESHOLD
EPS = np.finfo(np.float64).eps

def make_patches(n, rng):
    """8x8 patches: brightness offset c, vertical step edge of signed height s, pixel noise.
    Label 1 iff the left-half mean exceeds the right-half mean (an exact rule of the patch)."""
    c = rng.normal(0, 1, (n, 1, 1))
    s = rng.normal(0, 1, (n, 1, 1))
    step = np.where(np.arange(P) < P // 2, 0.5, -0.5)[None, None, :]
    X = c + s * step + rng.normal(0, 1, (n, P, P))
    d = X[:, :, :P // 2].mean(axis=(1, 2)) - X[:, :, P // 2:].mean(axis=(1, 2))
    return X.reshape(n, P * P), d, (d > 0).astype(np.int64)

def data(seed):
    rng = np.random.default_rng(seed)
    return make_patches(N_TR, rng), make_patches(N_TE, rng)

def impurity(n0, n1, crit):
    n = n0 + n1
    p0, p1 = n0 / n, n1 / n
    if crit == "gini":
        return 1.0 - (p0 * p0 + p1 * p1)
    with np.errstate(divide="ignore", invalid="ignore"):   # entropy in bits, 0 log 0 = 0
        return -(np.where(p0 > 0, p0 * np.log2(p0), 0.0) + np.where(p1 > 0, p1 * np.log2(p1), 0.0))

def best_splits(Xf, y, idx, crit):
    """Exhaustive CART search at one node: every feature, every midpoint between distinct
    sorted values. Returns the best weighted child impurity n_L*H_L + n_R*H_R and every
    (feature, threshold) that attains it (ties)."""
    n, n1 = len(idx), int(y[idx].sum())
    best, ties = np.inf, []
    for j in range(Xf.shape[1]):
        o = np.argsort(Xf[idx, j], kind="stable")
        v, ys = Xf[idx, j][o], y[idx][o]
        if v[-1] <= v[0] + FT:                            # constant feature
            continue
        nL = np.arange(1, n)
        L1 = np.cumsum(ys)[:-1]
        cost = nL * impurity(nL - L1, L1, crit) + (n - nL) * impurity(n - nL - (n1 - L1), n1 - L1, crit)
        cost[~(v[1:] > v[:-1] + FT)] = np.inf             # no split between (near-)equal values
        thr = v[:-1].astype(np.float64) / 2.0 + v[1:].astype(np.float64) / 2.0
        thr = np.where(thr == v[1:], v[:-1].astype(np.float64), thr)
        m = cost.min()
        if m < best - 1e-9:
            best, ties = m, []
        if m <= best + 1e-9:
            ties += [(j, float(t)) for t in thr[cost <= best + 1e-9]]
    return best, ties

def check_against_sklearn(X, y, crit):
    """Grow our CART alongside scikit-learn's tree. At every node, check that sklearn's split
    is one of our optimal splits (where several tie, follow sklearn's choice), that node sizes
    and impurities agree, and accumulate the weighted impurity decrease per feature."""
    Xf = X.astype(np.float32)                             # trees store X as float32
    clf = DecisionTreeClassifier(criterion=crit, random_state=0).fit(X, y)
    T, N = clf.tree_, len(y)
    ok_split = ok_size = ok_leaf = True
    n_tied, max_dimp = 0, 0.0
    imp_node, n_node = {}, {}
    importance = np.zeros(X.shape[1])
    stack = [(0, np.arange(N))]
    while stack:
        k, idx = stack.pop()
        n1 = int(y[idx].sum()); H = float(impurity(len(idx) - n1, n1, crit))
        imp_node[k], n_node[k] = H, len(idx)
        max_dimp = max(max_dimp, abs(H - T.impurity[k]))
        ok_size &= len(idx) == T.n_node_samples[k]
        leaf_sk = T.children_left[k] == -1
        leaf_my = H <= EPS or len(idx) < 2
        ok_leaf &= leaf_sk == leaf_my
        if leaf_sk or leaf_my:
            continue
        best, ties = best_splits(Xf, y, idx, crit)
        f, t = int(T.feature[k]), float(T.threshold[k])
        ok_split &= (f, t) in ties
        n_tied += len(ties) > 1
        go_left = Xf[idx, f].astype(np.float64) <= t
        L, R = idx[go_left], idx[~go_left]
        HL = float(impurity(len(L) - y[L].sum(), y[L].sum(), crit))
        HR = float(impurity(len(R) - y[R].sum(), y[R].sum(), crit))
        importance[f] += len(idx) / N * (H - len(L) / len(idx) * HL - len(R) / len(idx) * HR)
        stack += [(T.children_right[k], R), (T.children_left[k], L)]
    importance /= importance.sum()
    return clf, dict(nodes=len(imp_node), sk_nodes=T.node_count, ok_split=ok_split, ok_size=ok_size,
                     ok_leaf=ok_leaf, n_tied=n_tied, max_dimp=max_dimp,
                     max_dfi=np.abs(importance - clf.feature_importances_).max()), (imp_node, n_node, T)

def weakest_link_path(imp_node, n_node, T):
    """CART's weakest-link pruning on our node impurities and sizes: repeatedly collapse the
    internal node with the smallest (R(t) - R(T_t)) / (|leaves(T_t)| - 1), R = n_t/N * H_t.
    Ties go to the lowest node id, as in scikit-learn."""
    N = n_node[0]
    r = {k: n_node[k] / N * imp_node[k] for k in imp_node}
    pruned = set()
    def branch(k):                                         # (R of the branch's leaves, leaf count)
        if T.children_left[k] == -1 or k in pruned:
            return r[k], 1
        a, b = branch(T.children_left[k]), branch(T.children_right[k])
        return a[0] + b[0], a[1] + b[1]
    def internal(k):
        if T.children_left[k] == -1 or k in pruned:
            return []
        return [k] + internal(T.children_left[k]) + internal(T.children_right[k])
    alphas, imps = [0.0], [branch(0)[0]]
    while internal(0):
        cand = sorted(internal(0))
        g = [(r[k] - branch(k)[0]) / (branch(k)[1] - 1) for k in cand]
        gmin = min(g)
        k = cand[next(i for i, gi in enumerate(g) if gi <= gmin + 1e-15)]
        pruned.add(k)
        alphas.append(gmin); imps.append(branch(0)[0])
    return np.array(alphas), np.array(imps)

def disagreement(preds):
    """Mean fraction of test patches on which two trees of the ensemble disagree, over all pairs."""
    Bn = preds.shape[0]; k = preds.sum(axis=0)
    return float((k * (Bn - k)).sum() / (preds.shape[1] * Bn * (Bn - 1) / 2))

# ---------------- data checks ----------------
print("data: per seed, class-1 share (train, test), min |d| (train, test), sign(float32 d) == label")
for seed in range(5):
    (Xtr, dtr, ytr), (Xte, dte, yte) = data(seed)
    sgn = all(np.array_equal((d.astype(np.float32) > 0).astype(int), yy) for d, yy in ((dtr, ytr), (dte, yte)))
    print(f"  seed {seed}: {ytr.mean():.4f} {yte.mean():.4f}  {np.abs(dtr).min():.2e} {np.abs(dte).min():.2e}  {sgn}")
(Xtr, dtr, ytr), _ = data(0)
corr = [np.corrcoef(Xtr[:, j], ytr)[0, 1] for j in range(P * P)]
print(f"  seed 0: correlation of single pixels with the label, left half {min(corr[j] for j in range(64) if j % 8 < 4):.3f}"
      f" to {max(corr[j] for j in range(64) if j % 8 < 4):.3f}, right half {min(corr[j] for j in range(64) if j % 8 >= 4):.3f}"
      f" to {max(corr[j] for j in range(64) if j % 8 >= 4):.3f}")

# ---------------- (a) our CART against scikit-learn, (d) pruning path ----------------
print("\n(a) NumPy CART against DecisionTreeClassifier(random_state=0), seed 0, 64 pixel features")
print("(d) cost_complexity_pruning_path against our weakest-link computation")
for crit in ("gini", "entropy"):
    clf, s, (imp_node, n_node, T) = check_against_sklearn(Xtr, ytr, crit)
    print(f"  {crit:7s}: nodes {s['nodes']} (sklearn {s['sk_nodes']}), every sklearn split optimal for us {s['ok_split']},"
          f" nodes with tied optima {s['n_tied']}, sizes equal {s['ok_size']}, leaves equal {s['ok_leaf']},"
          f" max |impurity diff| {s['max_dimp']:.1e}, max |importance diff| {s['max_dfi']:.1e}")
    path = clf.cost_complexity_pruning_path(Xtr, ytr)
    a_my, i_my = weakest_link_path(imp_node, n_node, T)
    same = len(a_my) == len(path.ccp_alphas)
    da = np.abs(a_my - path.ccp_alphas).max() if same else np.nan
    di = np.abs(i_my - path.impurities).max() if same else np.nan
    print(f"           pruning path: {len(path.ccp_alphas)} alphas (ours {len(a_my)}), max |alpha diff| {da:.1e},"
          f" max |impurity diff| {di:.1e}, largest alpha {path.ccp_alphas[-1]:.6f}")

# ---------------- (b) pixels against the difference feature ----------------
print("\n(b) fully grown trees (random_state=0): leaves, train error, test error")
print("    seed  crit     pixels: leaves train  test     difference: leaves train  test")
for seed in range(5):
    (Xtr, dtr, ytr), (Xte, dte, yte) = data(seed)
    for crit in ("gini", "entropy"):
        row = []
        for Ftr, Fte in ((Xtr, Xte), (dtr[:, None], dte[:, None])):
            t = DecisionTreeClassifier(criterion=crit, random_state=0).fit(Ftr, ytr)
            row += [t.get_n_leaves(), 1 - t.score(Ftr, ytr), 1 - t.score(Fte, yte)]
        print(f"    {seed}     {crit:7s}  {row[0]:6d} {row[1]:.4f} {row[2]:.4f}         {row[3]:6d} {row[4]:.4f} {row[5]:.4f}")

# ---------------- (c) instability under bootstrap resampling ----------------
print(f"\n(c) {B} trees on bootstrap resamples (Gini, random_state=0): mean pairwise disagreement on the"
      " test patches, mean single-tree test error")
print("    seed  pixels deep        pixels depth 1     difference deep")
for seed in range(5):
    (Xtr, dtr, ytr), (Xte, dte, yte) = data(seed)
    rng = np.random.default_rng(1000 + seed)
    boots = [rng.integers(0, N_TR, N_TR) for _ in range(B)]
    out = []
    for Ftr, Fte, depth in ((Xtr, Xte, None), (Xtr, Xte, 1), (dtr[:, None], dte[:, None], None)):
        preds = np.array([DecisionTreeClassifier(max_depth=depth, random_state=0).fit(Ftr[b], ytr[b]).predict(Fte)
                          for b in boots])
        out += [disagreement(preds), (preds != yte).mean()]
    print(f"    {seed}     {out[0]:.4f} {out[1]:.4f}      {out[2]:.4f} {out[3]:.4f}      {out[4]:.4f} {out[5]:.4f}")

Output:

data: per seed, class-1 share (train, test), min |d| (train, test), sign(float32 d) == label
  seed 0: 0.4880 0.5014  2.83e-04 1.34e-05  True
  seed 1: 0.5095 0.5026  1.61e-04 2.25e-04  True
  seed 2: 0.5145 0.4960  7.21e-04 2.39e-04  True
  seed 3: 0.5040 0.5072  3.15e-04 8.71e-05  True
  seed 4: 0.5030 0.5142  2.75e-04 1.28e-04  True
  seed 0: correlation of single pixels with the label, left half 0.239 to 0.279, right half -0.316 to -0.272

(a) NumPy CART against DecisionTreeClassifier(random_state=0), seed 0, 64 pixel features
(d) cost_complexity_pruning_path against our weakest-link computation
  gini   : nodes 319 (sklearn 319), every sklearn split optimal for us True, nodes with tied optima 67, sizes equal True, leaves equal True, max |impurity diff| 2.2e-16, max |importance diff| 1.8e-16
           pruning path: 129 alphas (ours 129), max |alpha diff| 1.7e-16, max |impurity diff| 1.7e-16, largest alpha 0.045360
  entropy: nodes 295 (sklearn 295), every sklearn split optimal for us True, nodes with tied optima 56, sizes equal True, leaves equal True, max |impurity diff| 2.2e-16, max |importance diff| 2.5e-16
           pruning path: 131 alphas (ours 131), max |alpha diff| 1.7e-16, max |impurity diff| 2.2e-16, largest alpha 0.066574

(b) fully grown trees (random_state=0): leaves, train error, test error
    seed  crit     pixels: leaves train  test     difference: leaves train  test
    0     gini        160 0.0000 0.2556              2 0.0000 0.0006
    0     entropy     148 0.0000 0.2504              2 0.0000 0.0006
    1     gini        163 0.0000 0.2530              2 0.0000 0.0002
    1     entropy     150 0.0000 0.2378              2 0.0000 0.0002
    2     gini        172 0.0000 0.2498              2 0.0000 0.0000
    2     entropy     137 0.0000 0.2388              2 0.0000 0.0000
    3     gini        174 0.0000 0.2380              2 0.0000 0.0004
    3     entropy     138 0.0000 0.2450              2 0.0000 0.0004
    4     gini        167 0.0000 0.2548              2 0.0000 0.0002
    4     entropy     144 0.0000 0.2366              2 0.0000 0.0002

(c) 50 trees on bootstrap resamples (Gini, random_state=0): mean pairwise disagreement on the test patches, mean single-tree test error
    seed  pixels deep        pixels depth 1     difference deep
    0     0.3422 0.2648      0.3042 0.3986      0.0005 0.0005
    1     0.3380 0.2592      0.3432 0.3951      0.0004 0.0004
    2     0.3382 0.2583      0.4342 0.3898      0.0003 0.0002
    3     0.3379 0.2592      0.4391 0.3945      0.0005 0.0006
    4     0.3414 0.2635      0.3214 0.3991      0.0001 0.0002

Data and checks. The data checks held: the classes are balanced (48.8–51.5% of each set in class 1), no patch lies exactly on the rule’s boundary (the smallest $|d|$ is $1.3 \times 10^{-5}$), and every label is reproduced by the sign of $d$ in float32, the precision the trees see. Single pixels correlate with the label at only 0.24–0.32 in absolute value, positively in the left half and negatively in the right. Every planned check held:

• In (a), for both criteria, our tree has the same 319 (Gini) or 295 (entropy) nodes as scikit-learn’s, every split scikit-learn chose is one our exhaustive search finds optimal, node sizes and leaves agree, and impurities and feature importances agree to $2.5 \times 10^{-16}$ at most.
• In (d), the two pruning paths have the same length (129 and 131 alphas) and agree to $1.7 \times 10^{-16}$ in alpha and $2.2 \times 10^{-16}$ in impurity.
• Every fully grown tree in (b) has zero training error, and every tree on $d$ has exactly 2 leaves: one split at the gap around zero separates the training set perfectly.

The count of nodes with tied optima, 67 of the 159 internal nodes of the Gini tree and 56 of the 147 of the entropy tree, shows that ties are not rare even on continuous pixel values. When two splits send the same numbers of each class to each side, they have the same impurity whatever their features and thresholds; in our reading, most such ties arise deep in the tree, where nodes hold a few examples and many pixels can isolate the same one or two of them (the output does not show where the tied nodes lie). At these nodes the split scikit-learn returns can depend on random_state, and so can every split below them. The pruning path has fewer steps than the tree has internal nodes because collapsing a node removes all the internal nodes beneath it in one step. The largest alpha, 0.045 for Gini and 0.067 for entropy, is the penalty per leaf at which the whole tree is pruned to its root.

Pixels against one good feature (b). A fully grown tree on pixels needs 137–174 leaves to fit 2,000 training patches and still misclassifies 23.7–25.6% of the test patches, in every seed and for both criteria. The tree on $d$ uses one split and misclassifies at most 3 of 5,000 test patches (0.0000–0.0006): a test patch can be wrong only if its $d$ falls in the gap between the two training values on either side of zero, where the midpoint threshold may put it on the wrong side. The planned predictions held: the pixel trees have at least 50 leaves (H1 i) and a test error of at least 0.05 (H1 ii), the trees on $d$ have a test error of at most 0.005 (H1 iii), and the pixel error is at least ten times the other in every row (H1 iv), the smallest ratio being 0.2504/0.0006 ≈ 417 (seed 0, entropy; in seed 2 the tree on $d$ made no test error). In every seed the entropy trees have fewer leaves than the Gini trees (137–150 against 160–174); the test errors of the two criteria differ by at most 0.0182, with entropy lower in four seeds and Gini in seed 3. In our reading, the pixel trees fail for the reason the Intuition section gives: each split cuts along one of 64 axes, so a hyperplane with 64 equal-magnitude weights becomes a staircase whose steps are placed by the training examples near the boundary, and each split leaves fewer examples to place the next step. The comparison is the point of image features: a tree, like any classifier built from axis-aligned tests, is only as good as the coordinates it is given. Dollár and Zitnick (2013, §2.1) list a split on the difference of two features, $x_{k_1} - x_{k_2} < \tau$, beside the single-feature stump as a common, efficient choice; a test on a difference is oblique in the original coordinates.

Instability (c). Fully grown pixel trees fitted to different bootstrap resamples disagree on 33.8–34.2% of the test patches, while trees on $d$ disagree on at most 0.05%. Both of these predictions held: deep pixel trees disagree on at least 5% (H2 c), and trees on $d$ on at most 0.5% and less than both pixel conditions (H2 b). The expectation from the batch’s planning research, large disagreement for deep trees and small for depth 1, tested as deep pixel trees disagreeing more than depth-1 pixel trees (H2 a), failed in seeds 1, 2 and 3 and held in seeds 0 and 4: depth-1 trees disagree on 30.4–43.9% of the test patches, more than the deep trees in three seeds. The plan for this example recorded before the pilot, as the drafter’s reasoning, that “a depth-1 tree on pixels picks one of 64 near-equivalent pixels, and resamples may pick different pixels with different predictions, so (a) may fail”. In our reading, this explains the failure: by construction every pixel in a half has the same distribution, so a stump’s best pixel on one resample has no reason to be best on the next, and two stumps on different pixels disagree on many patches. The output does not show which pixels the stumps chose. The deep pixel trees fitted to resamples also have a higher mean test error (0.258–0.265) than the Gini tree fitted to the full training set in (b) (0.238–0.256), in every seed, and the depth-1 trees err on 39.0–39.9% of the test patches on average. In our reading, the three conditions together show that instability here comes from the representation as much as from the depth: with a feature that carries the rule, even a fully grown tree hardly changes between resamples.

This instability is what Murphy (§18.1.5) describes: small changes to the training data can change the tree a lot, because an error at the top changes everything below it, and omitting a single data point can give a very different decision surface. Murphy (§18.2) calls trees high-variance estimators, and averaging many trees grown on resampled data (bagging) or with random feature subsets (random forests) turns that instability into an advantage (§18.3–18.4).

Process. The script was run as piloted, with no change after the pilot, and the output shown is the first run. Before the pilot, a script that prints only the checks, the data properties and the base results of this example was run to set the tolerances of the checks; it printed the node counts of the seed-0 pixel trees, which give their leaf counts (160 and 148), before the hypotheses were written, so the leaf-count part of H1 is an illustration for seed 0. The example departs from the batch plan’s entry for it in seven ways, all fixed before the pilot: (1) the plan’s data line reads “continuous features, so no ties”, but different splits that send the same numbers of each class to each side tie, so the split-for-split check was designed for ties (scikit-learn’s split must be among our optimal splits, and our recursion follows scikit-learn’s choice where several tie); (2) the noise model was specified as an offset, a step and pixel noise, all $\mathcal{N}(0, 1)$, with the label computed on the noisy patch; (3) part (a) also compares node sizes, impurities and feature importances; (4) parts (b) and (d) run both criteria and part (c) Gini only; (5) parts (b) and (c) run five data seeds and parts (a) and (d) seed 0; (6) part (c) adds the tree on $d$ as a third condition, prints the mean single-tree test error, and defines disagreement as the mean over all pairs of trees; (7) part (d) computes the weakest-link path on our own impurities and node sizes, breaking ties toward the lowest node index as scikit-learn does.

Properties and Behavior

Murphy (§18.1.5) lists the reasons trees are popular: they are easy to interpret; they handle mixed discrete and continuous inputs; they are insensitive to monotone transformations of the inputs, because the split points depend only on the ranking of the values, so the data need no standardization; they perform automatic variable selection; they are relatively robust to outliers; they are fast to fit and scale well to large data sets; and they can handle missing input features. The user guide (§1.10) adds that they handle multi-output problems, and that predictions are piecewise constant, neither smooth nor continuous, so trees are poor at extrapolation.

• Exact fit. A tree grown until its leaves are pure reaches zero training error whenever no two identical inputs carry different labels; the example shows this in every row of (b).
• Axis-aligned boundaries. Every boundary is a union of faces of axis-aligned boxes. A rule that is oblique in the given features costs many leaves and generalizes poorly, as the pixel trees in (b) show, while an engineered feature that carries the rule makes the tree small and exact.
• Local constancy. The prediction is constant inside each leaf’s box. The Machine Learning hub explains, after Goodfellow, Bengio and Courville (§5.11.2), why methods that rely only on this kind of smoothness, decision trees among them, need roughly one example per region they distinguish, which in high dimensions is too many (the curse of dimensionality); the same reasoning applies to k-nearest neighbours.
• Instability. Small changes in the data can change the tree’s structure and predictions substantially (Murphy, §18.1.5; user guide §1.10), as part (c) shows.
• Greedy and not optimal. Each split is the best one locally. The user guide (§1.10) notes that greedy algorithms cannot guarantee a globally optimal tree, and Murphy (§18.1.3) notes that growing fully and then pruning can partly overcome the greediness of top-down growth.

Limitations

• Accuracy. Murphy (§18.1.5) calls the main disadvantage that trees do not predict very accurately compared with other kinds of model, in part because of the greedy construction.
• Overfitting. Without pruning or stopping rules, trees fit noise; the Machine Learning hub’s depth sweep shows the training error going to zero while the test error rises. The user guide (§1.10.5) notes that trees tend to overfit on data with many features and suggests dimensionality reduction beforehand. General remedies are in Regularization.
• Class imbalance. The user guide (§1.10) warns that trees are biased toward dominant classes and recommends balancing the data, preferably by sample weights (§1.10.5).
• Raw pixels. On images, a single pixel rarely carries the label, and the boundaries are oblique in pixel space, as in the example. Vision systems that use trees therefore feed them computed features, such as rectangle sums, pixel differences or descriptors, and use many trees together.

Variants

• ID3 and C4.5. As scikit-learn’s user guide (§1.10.6) describes them, ID3 (Quinlan, 1986) grows a multiway tree, choosing at each node the categorical feature with the largest information gain, and C4.5 (Quinlan, 1993), its successor, removes the restriction to categorical features by discretizing numerical ones into intervals, converts the tree into a set of if-then rules and prunes those rules. The same section says CART (Breiman, Friedman, Olshen and Stone, 1984) is very similar to C4.5 but supports numerical targets (regression) and does not compute rule sets, and that C5.0 is Quinlan’s later, proprietary release. FAST learns a ternary tree by ID3 over the states of its circle pixels, as its article describes.
• Regression trees predict a constant per leaf and split by variance reduction (above). They are the weak learners of gradient boosting, described in Boosting.
• Decision stumps are trees with one split. Boosting combines many of them, and the Viola–Jones article describes the detector’s thresholded rectangle features as single-node decision trees.
• Soft decision trees. Murphy (§18.1.2) mentions replacing each hard split by a binary logistic regression, so that for a fixed structure the tree can be fitted by gradient-based optimization; he calls this a differentiable or soft decision tree.
• Ensembles of trees. Bagging and random forests average many trees fitted to resampled data or with random features at each node (Murphy, §18.3–18.4), and boosting adds trees fitted one after another. Dollár and Zitnick (2013) extended random forests to structured outputs, predicting a whole local edge mask per patch, as Edge Detection describes; Facial Landmark Detection describes forests trained to regress landmark offsets.