Decision trees

Every classifier of the linear section, binary or multiclass, scores an input by a weighted sum of its features. A weighted sum cannot express an interaction, a rule in which the effect of one feature depends on the value of another: “a high income lowers the risk of default, unless the debt is also high”. The kernels note added interactions through a feature map, but the kernel has to be chosen, the cost grows with the square of the sample size, and the inputs must be numbers on comparable scales. Tabular data are rarely like that: they mix counts, money, categories and missing entries. A decision tree handles all of this with the simplest possible building block, a yes-or-no question about one feature, and it builds interactions by asking the next question only on one side of the previous answer.

Notation. The training set is $(x_i, y_i)$, $i = 1, \dots, n$, with $x_i \in \mathbb R^d$ and $x_{ij}$ its $j$-th feature. A node is a set $S$ of training indices; a split $(j, t)$ sends $i \in S$ to the left child $S_\ell = \{i \in S : x_{ij} \le t\}$ or to the right child $S_r = S \setminus S_\ell$. In classification with $K$ classes, $p_k = \frac{1}{|S|} \sum_{i \in S} [y_i = k]$ is the share of class $k$ in the node. $H(S)$ is an impurity: a number that is zero when the node is pure. The leaves $S_1, \dots, S_J$ of a tree partition the input space into regions $A_1, \dots, A_J$.

What a tree computes#

A tree is a sequence of questions $x_j \le t$. An input starts at the root, goes left or right according to the answer, and repeats until it reaches a leaf, which returns a constant: the mean target of its training points for regression, the majority class or the vector of class shares for classification. Each leaf is the set of inputs that answer a fixed list of questions, a box with sides parallel to the axes, so the tree is a piecewise-constant function

$$f(x) = \sum_{m=1}^{J} c_m \, [x \in A_m] ,$$

where $c_m$ is the value of leaf $m$. Read differently, this is a linear model over $J$ indicator features: the tree first constructs the features $[x \in A_m]$ from the data and then fits one weight per feature. A path from the root to a leaf is a conjunction, ”$x_1 > 0.44$ and $x_2 > 0.485$”, which is exactly the kind of interaction a weighted sum lacks.

Figure

A decision tree and its partition of the plane

The figure grows such a tree on 18 points. The two classes swap sides with $x_1$: on the left, class 1 sits at small $x_2$; on the right, at large $x_2$. No line separates them, and no weighted sum of $x_1$ and $x_2$ describes them. The tree needs three questions:

1. The root asks about $x_1$, which leaves 8 points on the left, 2 of them class 1, and 10 on the right, 7 of them class 1.
2. The left node asks $x_2 \le 0.315$.
3. The right node asks $x_2 \le 0.485$, a different threshold on the same feature.
4. Four pure leaves remain, and the effect of $x_2$ reverses between the two halves.

Two properties follow from the form of the questions. A tree only compares each feature with thresholds, so it is unchanged by any increasing transformation of a feature: taking logarithms of an income, or standardizing it, gives the same tree. And every boundary is a staircase of axis-parallel segments, so a boundary along a diagonal, which one linear classifier draws exactly, costs a tree many leaves. Splits on linear combinations $\langle w, x \rangle \le t$ exist but are rarely used: their weights are hard to optimize by a discrete search, and they lose both the invariance and the readability (Hastie, Tibshirani and Friedman, 2009, Section 9.2.4).

How good is a split?#

A split is good if its children are purer than the parent. The impurity of a node is best defined as the loss of the best constant prediction in it,

$$H(S) = \min_{c} \frac{1}{|S|} \sum_{i \in S} L(y_i, c) ,$$

and the gain of a split is the drop of the size-weighted impurity:

$$\Delta(j, t) = H(S) - \frac{|S_\ell|}{|S|} H(S_\ell) - \frac{|S_r|}{|S|} H(S_r) .$$

Different losses give the familiar criteria.

• Regression, squared error. The best constant is the mean $\bar y_S$, and $H(S) = \frac{1}{|S|} \sum_{i \in S} (y_i - \bar y_S)^2$ is the variance of the targets in the node. For the six targets $1, 2, 3, 7, 8, 9$, the variance is $58/6 = 9.67$; the split between 3 and 7 leaves two nodes with variance $2/3$ each, a gain of $9.0$. With absolute error the best constant is the median and the impurity is the mean absolute deviation from it, the same pairing of loss and summary as in the conditional expectation note.
• Classification, log-loss. Predict a distribution $c = (c_1, \dots, c_K)$ for every point of the node and pay $-\log c_{y_i}$. The average loss is $-\sum_k p_k \log c_k$, the cross-entropy between the class shares and $c$, which is smallest at $c = p$. The impurity is therefore the entropy $H(S) = -\sum_k p_k \log p_k$ of the class shares, the expected surprise of the entropy note, and the gain is the information gain of ID3 (Quinlan, 1986).
• Classification, squared error on one-hot labels (the Brier score). For each class $k$ the indicator $[y_i = k]$ is a 0/1 variable with mean $p_k$; the best constant for it is $p_k$, and its mean squared deviation is $p_k(1 - p_k)$, the variance of a Bernoulli variable. Summing over classes gives the Gini index of CART (Breiman et al., 1984):

$$H_{\text{Gini}}(S) = \sum_{k=1}^{K} p_k (1 - p_k) = 1 - \sum_{k=1}^{K} p_k^2 .$$

• Classification, 0–1 loss. The best constant is the majority class, and $H(S) = 1 - \max_k p_k$, the misclassification rate of the node.

Why not split by the misclassification rate, the quantity we finally care about? Because it is too coarse. Take a node with 8 points of each class and two candidate splits: A gives children with class counts $(7, 3)$ and $(1, 5)$, B gives $(8, 4)$ and $(0, 4)$. Both make 4 mistakes, so the misclassification rate falls from $0.5$ to $0.25$ for both. B produces a pure node that needs no further splits, and both smooth criteria see it: the weighted Gini index is $0.367$ for A and $0.333$ for B, the weighted entropy $0.795$ and $0.689$ bits. The misclassification rate is also piecewise linear in the shares, so many splits tie, and a split can have zero gain in misclassification while it sets up a perfect split one level down. Gini and entropy are strictly concave in $p$, so the gain is strictly positive whenever the children’s class shares differ from the parent’s; in practice they choose nearly the same trees (Hastie, Tibshirani and Friedman, 2009, Section 9.2.3, makes the same comparison).

For two classes the Gini index is $2p(1 - p)$, twice the variance of the 0/1 label. A classification tree grown by Gini is therefore the regression tree on the 0/1 labels, and its leaf values $p$ are estimated probabilities of class 1.

Greedy split search and its cost#

Finding the binary tree that identifies every training point with the smallest expected number of tests, that is, with the smallest sum of root-to-leaf path lengths, is NP-complete (Hyafil and Rivest, 1976), so every practical algorithm is greedy: choose the best split of the root, then recurse into each child, never revisiting a decision. For one node and one feature, sort the $|S|$ values; the candidate thresholds are the midpoints between consecutive distinct values, at most $|S| - 1$ of them. Going through them in order, moving one point at a time from the right child to the left, the class counts (or the sums $\sum y_i$ and $\sum y_i^2$ for regression) are updated in constant time, and so is the gain. A node therefore costs $O(d \, |S| \log |S|)$ for sorting and $O(d \, |S|)$ for the sweep. The nodes at one depth partition the training set, so one level of the tree costs $O(d \, n \log n)$, and a tree of depth $D$ costs $O(D \, d \, n \log n)$; sorting every feature once at the start and keeping the order when the data are split removes the repeated sorting.

Greediness has a price. On the XOR pattern, four points with class 1 at $(0, 1)$ and $(1, 0)$ and class 0 at $(0, 0)$ and $(1, 1)$, every single split leaves one point of each class on each side: the gain of every root split is zero, although two levels of splits classify the four points perfectly. A greedy algorithm that refuses splits without gain never starts; one that accepts them finds the tree. For large datasets, libraries replace the exact search by a histogram: each feature is binned once into at most a few hundred bins, and only bin boundaries are tried. Building the histogram of a node still touches each of its points once, $O(d \, |S|)$, but the sorting disappears and the sweep over thresholds costs $O(d \, B)$ for $B$ bins instead of $O(d \, |S|)$; after the one-off binning, a tree of depth $D$ costs $O(D \, d \, n)$. The boosting libraries of the gradient boosting note are built on this.

When to stop: stopping rules and pruning#

Grown until every leaf is pure, a tree fits any training set without errors, one leaf per point if necessary, and it generalizes badly. Two remedies exist.

Stopping rules end the recursion early: a maximal depth, a minimal number of points per leaf or per split, a maximal number of leaves, a minimal gain. They are cheap, and they are what libraries offer first. Their weakness is the XOR problem in another guise: a split that looks useless can enable a useful one below it, and a gain threshold stops too early (Hastie, Tibshirani and Friedman, 2009, Section 9.2.2).

Pruning grows a large tree $T_0$ first and then cuts it back. Cost-complexity pruning (Breiman et al., 1984) charges every leaf a price $\alpha \ge 0$:

$$C_\alpha(T) = R(T) + \alpha \, |T| ,$$

where $R(T)$ is the training loss of a subtree $T \subseteq T_0$ (the summed impurity of its leaves, weighted by their sizes, or the number of training errors) and $|T|$ its number of leaves. For each $\alpha$ there is a unique smallest subtree minimizing $C_\alpha$, and as $\alpha$ grows the minimizers form a nested sequence from $T_0$ down to the root alone. The sequence is found by weakest-link pruning. For an internal node $s$ with subtree $T_s$, collapsing $s$ into a leaf raises the loss from $R(T_s)$ to $R(s)$ and removes $|T_s| - 1$ leaves, so it pays off once

$$\alpha \ge g(s) = \frac{R(s) - R(T_s)}{|T_s| - 1} .$$

The node with the smallest $g(s)$ is collapsed first, then $g$ is recomputed, and so on. A toy example, counting training errors: node $s$ would make 6 errors as a leaf and makes 2 with its subtree of 4 leaves, so $g(s) = (6 - 2)/3 = 1.33$; node $u$ would make 3 errors as a leaf and makes 1 with its 2 leaves, so $g(u) = (3 - 1)/1 = 2$. Raising $\alpha$ past $1.33$ prunes $s$ first, past $2$ prunes $u$. The value of $\alpha$ itself is chosen by cross-validation, as in the validation note. On the breast cancer data (398 training and 171 test points, 30 features), the fully grown tree has 16 leaves, depth 6 and training accuracy 1.0, and reaches $0.906$ on the test set; cost-complexity pruning with $\alpha = 0.0088$ chosen by 5-fold cross-validation keeps 6 leaves and depth 4, with training accuracy $0.977$ and test accuracy $0.918$.

$C_\alpha$ has the shape of every regularized objective in this course: a training loss plus a penalty on complexity, here the number of leaves instead of a norm of the weights as in the regularization note.

Categorical features and missing values#

Categorical features. A feature with $q$ unordered levels, such as a city, has no thresholds. The natural binary split sends a subset of the levels left, and there are $2^{q-1} - 1$ such subsets, too many to try for large $q$. For two classes there is a shortcut: order the levels by their share of class 1 and try only the $q - 1$ splits that respect this order; the best of them is the best of all subsets for Gini and entropy, and the same holds for squared error with the levels ordered by their mean target (Breiman et al., 1984; Fisher, 1958; Hastie, Tibshirani and Friedman, 2009, Section 9.2.4). In a toy example with four levels of 10 points each and 2, 8, 3 and 7 positives, the 7 subset splits are matched by the 3 ordered ones: in the order A, C, D, B, the second ordered split, $\{A, C\}$ against $\{B, D\}$, has the smallest weighted Gini index, $0.375$, the same as the best of all 7. Two cautions. With many classes no such shortcut exists. And a feature with many levels offers many ways to split, so it can fit noise. Ordering the levels by the training targets is not leakage: it is part of the split search, like choosing a threshold, and it finds the same split as trying all subsets. The danger is overfitting, which pruning and validation control. Leakage, the problem the data note warns about, needs a label that the fit must not see: a held-out label, or a point’s own label inside a feature, as when each level is replaced by its mean target computed over all points, including the point itself. CatBoost’s ordered target statistics, in the gradient boosting note, are designed to avoid that. One-hot encoding needs many splits to isolate a group of levels. The subset split is a property of the method, not of every library: scikit-learn’s DecisionTreeClassifier, used in the Code section, accepts only numbers, so categories must be encoded first, while scikit-learn’s HistGradientBoostingClassifier (with categorical_features), LightGBM and CatBoost split on categories directly.

Missing values. Trees offer several ways to keep rows with missing entries (Hastie, Tibshirani and Friedman, 2009, Section 9.2.4):

• treat “missing” as a level of its own (for categorical features), so the tree can learn that missingness itself predicts the target;
• surrogate splits (CART): at each node, rank the splits on other features by how well they reproduce the chosen split, and send a point whose feature is missing down the best surrogate it has;
• a learned direction: compute the gain of each threshold twice, with all missing values sent left and with all sent right, and keep the better; prediction follows the stored direction. XGBoost does this (Chen and Guestrin, 2016, Section 3.4), and so does scikit-learn’s DecisionTreeClassifier.
• C4.5 sends a point with a missing value down both branches with weights proportional to the branch sizes and averages the predictions.

On the breast cancer split above, hiding 30% of the values of the root feature in both the training and the test set leaves a working tree with test accuracy $0.947$ against $0.918$ with complete data; the difference is within the variation of a single tree from sample to sample, which is the subject of the next section.

Trees are unstable and overfit#

The greedy construction makes a tree a high-variance estimator. A small change in the data can change the root split, and every split below inherits the change (Hastie, Tibshirani and Friedman, 2009, Section 9.2.4). Trees grown on two random halves of the same breast cancer training set split the root on different features (worst perimeter and mean concave points), and they disagree on 10.5% of the test points. Depth controls the effect:

Figure

Trees of growing depth on two samples

The fully grown tree has zero training error and the worst test error of the three, and the gap between the two trees, grown on samples from the same distribution, is almost four times that of the stump. A deep tree has small bias, since it can follow any function, and large variance, since it follows the noise of its sample. The next note makes “small bias, large variance” precise, and the two notes after it turn the instability into an advantage.

What changed#

	Linear classifier	Decision tree
Model	$\operatorname{sign}\langle w, x \rangle$	$\sum_m c_m [x \in A_m]$, boxes from axis-aligned splits
Interactions	must be added by hand	built by branching
Features	numeric, scaled	any monotone scale; categories and missing values in the split rule (library support varies)
Training	convex loss, gradient methods	greedy search over splits, $O(D \, d \, n \log n)$
Complexity control	norm penalty	depth, leaf size, cost-complexity pruning
Typical failure	bias: boundary too simple	variance: unstable, overfits

Limitations#

• High variance. A single tree changes a lot with the training sample, and its interpretation changes with it.
• Piecewise constant. Predictions are not smooth, and outside the range of the training data they are constant: a tree cannot extrapolate a trend.
• Axis-aligned. A diagonal boundary or an additive effect spread over many features needs many splits; ESL notes that a tree has no special way of representing additive structure (Hastie, Tibshirani and Friedman, 2009, Section 9.2.4).
• Greedy. The tree found is not the best tree of its size, and patterns that pay off only after two splits, like XOR, can be missed.

What you should remember#

• A tree partitions the inputs into boxes by questions $x_j \le t$ and predicts a constant per box; paths are conjunctions, so trees model interactions.
• Impurity is the loss of the best constant in a node: variance for squared error, entropy for log-loss, Gini $\sum_k p_k(1 - p_k)$ for the Brier score, $1 - \max_k p_k$ for 0–1 loss.
• Gini is the expected error of labelling the node’s points at random with the class shares; for two classes it is twice the variance of the 0/1 label.
• Splits are chosen greedily by gain; one level costs $O(d \, n \log n)$; the optimal tree is NP-hard.
• Cost-complexity pruning minimizes $R(T) + \alpha |T|$; weakest-link pruning gives the nested sequence; $\alpha$ comes from cross-validation.
• Categorical levels ordered by target share or mean give the optimal binary split for two classes and regression; missing values go to a separate level, a surrogate split or a learned direction.
• Deep trees: low bias, high variance; small changes in the data change the tree.

Code#

Impurities and the two candidate splits, Gini as random labelling, a categorical feature, pruning, instability and missing values:

import numpy as np
from itertools import combinations
from sklearn.datasets import load_breast_cancer
from sklearn.model_selection import train_test_split, GridSearchCV
from sklearn.tree import DecisionTreeClassifier

# impurities of a node from its class counts, and the weighted impurity of a split
def error(c): return 1 - max(c) / sum(c)
def gini(c): return 1 - sum((k / sum(c)) ** 2 for k in c)
def entropy(c): return -sum(k / sum(c) * np.log2(k / sum(c)) for k in c if k)
def after(children, H): return sum(sum(c) * H(c) for c in children) / sum(sum(c) for c in children)
A, B = [(7, 3), (1, 5)], [(8, 4), (0, 4)]             # two splits of a node with 8 + 8 points
for H in (error, gini, entropy):
    print(H.__name__, round(H((8, 8)), 3), round(after(A, H), 3), round(after(B, H), 3))
# error 0.5 0.25 0.25 | gini 0.5 0.367 0.333 | entropy 1.0 0.795 0.689

# Gini as the error of random labelling: draw each label from the node's class shares
rng = np.random.default_rng(0)
labels = np.repeat([0, 1, 2], [6, 3, 1])
draws = rng.choice(labels, size=(100_000, labels.size))
print(round(gini((6, 3, 1)), 3), round(float((draws != labels).mean()), 3))   # 0.54 0.539

# a categorical feature with 4 levels: all 2^(q-1) - 1 = 7 subset splits against the 3 splits in the order of mean target
pos = {'A': 2, 'B': 8, 'C': 3, 'D': 7}                 # positives out of 10 per level
def subset_gini(left):
    l = sum(pos[c] for c in left); r = sum(pos.values()) - l
    return after([(l, 10 * len(left) - l), (r, 10 * (4 - len(left)) - r)], gini)
splits = [s for k in (1, 2) for s in combinations('ABCD', k) if k == 1 or 'A' in s]
best = min(splits, key=subset_gini)
order = sorted(pos, key=pos.get)
print(len(splits), best, round(subset_gini(best), 3), order, [round(subset_gini(order[:k]), 3) for k in (1, 2, 3)])
# 7 ('A', 'C') 0.375 ['A', 'C', 'D', 'B'] [0.44, 0.375, 0.44]

# breast cancer: a fully grown tree, then cost-complexity pruning with alpha chosen by 5-fold cross-validation
X, y = load_breast_cancer(return_X_y=True)
Xtr, Xte, ytr, yte = train_test_split(X, y, test_size=0.3, random_state=0, stratify=y)
full = DecisionTreeClassifier(random_state=0).fit(Xtr, ytr)
alphas = full.cost_complexity_pruning_path(Xtr, ytr).ccp_alphas
cv = GridSearchCV(DecisionTreeClassifier(random_state=0), {'ccp_alpha': alphas}, cv=5).fit(Xtr, ytr)
for t in (full, cv.best_estimator_):
    print(t.get_n_leaves(), t.get_depth(), round(t.score(Xtr, ytr), 3), round(t.score(Xte, yte), 3))
print(round(cv.best_params_['ccp_alpha'], 4))
# 16 6 1.0 0.906 | 6 4 0.977 0.918 | 0.0088

# instability: trees grown on two random halves of the training set
names = load_breast_cancer().feature_names
half = rng.permutation(len(ytr)); h1, h2 = half[: len(half) // 2], half[len(half) // 2:]
t1 = DecisionTreeClassifier(random_state=0).fit(Xtr[h1], ytr[h1])
t2 = DecisionTreeClassifier(random_state=0).fit(Xtr[h2], ytr[h2])
print(names[t1.tree_.feature[0]], '|', names[t2.tree_.feature[0]], round(float((t1.predict(Xte) != t2.predict(Xte)).mean()), 3))
# worst perimeter | mean concave points 0.105

# missing values: hide 30% of the root feature; each split learns which child the missing values go to
Xm = Xtr.copy(); Xm[rng.random(len(Xm)) < 0.3, full.tree_.feature[0]] = np.nan
Xtm = Xte.copy(); Xtm[rng.random(len(Xtm)) < 0.3, full.tree_.feature[0]] = np.nan
print(round(DecisionTreeClassifier(random_state=0, ccp_alpha=cv.best_params_['ccp_alpha']).fit(Xm, ytr).score(Xtm, yte), 3))   # 0.947

Next#

A deep tree fits its training set perfectly, and the figure above showed what that costs: a test error worse than that of a shallow tree, and two trees from the same distribution that disagree almost everywhere. “Flexible models overfit” is true but vague. The next note splits the expected test error of any learning method into three parts, noise, squared bias and variance, and uses the split to explain the choice of depth for trees, of $k$ for nearest neighbours and of $\lambda$ for ridge regression, and why averaging many trees should help.

References#

• L. Breiman, J. H. Friedman, R. A. Olshen, C. J. Stone. Classification and Regression Trees. Wadsworth, 1984 (CRC Press reprint). The Gini index, surrogate splits, cost-complexity pruning, the ordering of categorical levels for two classes.
• J. R. Quinlan. Induction of Decision Trees. Machine Learning, 1(1), 1986. ID3 and the information gain.
• L. Hyafil, R. L. Rivest. Constructing optimal binary decision trees is NP-complete. Information Processing Letters, 5(1), 1976.
• W. D. Fisher. On Grouping for Maximum Homogeneity. Journal of the American Statistical Association, 53(284), 1958. The ordering result for a quantitative target.
• T. Hastie, R. Tibshirani, J. Friedman. The Elements of Statistical Learning, 2nd ed. Springer, 2009. Section 9.2 (regression and classification trees, cost-complexity pruning, impurity measures and the interpretations of the Gini index, categorical predictors, missing values, instability).
• T. Chen, C. Guestrin. XGBoost: A Scalable Tree Boosting System. KDD, 2016. Section 3.4 (sparsity-aware split finding with a default direction).
• scikit-learn developers. Decision Trees, scikit-learn user guide: missing-value support and minimal cost-complexity pruning.
• E. Sokolov et al. Машинное обучение (HSE). Lecture notes, lecture 9: decision trees; practical session 9: decision trees.