35 - Decision trees: choosing a question with Gini and entropy

You know the game of twenty questions: you have to guess an object by asking questions answered with yes or no. Whoever plays well does not ask at random: the first question is the one that splits the possibilities roughly in half ("is it a living thing?"), and the next one depends on the answer. A decision tree is exactly a game of twenty questions learned from data: a sequence of tests on the features ("petal length ≤ 2.45?") that leads to a leaf with the prediction.

The interesting point is how the right question is chosen. You need a way to measure how "mixed" a group of examples is, and how much a question reduces the disorder. That measure is called impurity, and we will see two: the Gini index and entropy.

Anatomy of a tree

• Node: a point of the tree where a question about a feature is asked (for example "petal width ≤ 0.8?"). The question is a comparison with a threshold.
• Root: the first node, at the top, where all the examples arrive.
• Branch: the outcome of a question (yes/no). The examples follow the right branch.
• Leaf: a final node, with no questions, that holds the prediction (the most frequent class among the examples that arrive there).
• Depth: the maximum number of questions separating the root from a leaf.
• Recursion: building a tree means building smaller trees on the two subsets, and so on, until a stopping criterion says enough.

The six entries are a vocabulary but also a sequence: the root receives all the examples, each node splits them with a threshold, the branches lead to the leaves, and the depth measures how many questions are needed at most. The word that explains all the rest is "recursion": a tree is a node with two smaller trees below it, and that is why the code further down is a function that calls itself.

Measuring disorder: Gini and entropy

Consider a node that contains examples of K classes, with p_k the fraction of examples of class k. A node is pure if it contains a single class. The two most widely used measures:

Gini(node)     = 1 − Σ_k p_k²

Entropy(node)  = − Σ_k p_k · log₂(p_k)        (with 0·log 0 = 0)

The intuition behind Gini: if you draw two examples at random (with replacement) from the node, Σ p_k² is the probability that they have the same class; 1 minus that is the probability that they differ. A pure node gives 0; two classes at 50% give 0.5, the maximum for two classes. Entropy, already met in information theory, measures the average surprise: 0 for a pure node, 1 bit for two equiprobable classes.

import numpy as np

def gini(y):
    if len(y) == 0:
        return 0.0
    p = np.bincount(y) / len(y)
    return 1.0 - (p ** 2).sum()

def entropia(y):
    if len(y) == 0:
        return 0.0
    p = np.bincount(y) / len(y)
    p = p[p > 0]
    return float(-(p * np.log2(p)).sum()) + 0.0

for nome, y in [("pure 10/0", np.array([0] * 10)),
                ("90/10", np.array([0] * 9 + [1])),
                ("70/30", np.array([0] * 7 + [1] * 3)),
                ("50/50", np.array([0] * 5 + [1] * 5))]:
    print("%-10s Gini %.3f   Entropy %.3f" % (nome, gini(y), entropia(y)))

pure 10/0  Gini 0.000   Entropy 0.000
90/10      Gini 0.180   Entropy 0.469
70/30      Gini 0.420   Entropy 0.881
50/50      Gini 0.500   Entropy 1.000

What the code does. np.bincount(y) counts how many times each class appears (non-negative integers), and dividing by len(y) gives the frequencies p_k. gini applies 1 − Σp²; entropia discards the zero probabilities (p[p > 0], because 0·log 0 is not defined numerically and by convention equals 0) and applies −Σp·log₂p. The four test nodes run from pure to perfectly mixed: for the 70/30 node you read Gini 0.420 (= 1 − 0.49 − 0.09) and entropy 0.881.

The two measures have a very similar trend: zero on the pure node, maximum on the 50/50 one. In practice the two criteria often produce similar trees, but not always: the exercise below shows a case in which they choose different roots. Gini does not require the logarithm, so it costs a little less to compute; scikit-learn uses gini as its default criterion.

What a question is worth: the impurity reduction

A question splits a parent node of n examples into two children, left (n_L examples) and right (n_R). The impurity of the children must be weighted by their size, otherwise a tiny but pure child would fool the measure. The gain is:

Δ = I(parent) − ( n_L/n · I(left) + n_R/n · I(right) )

With entropy as I, this Δ is called information gain. A worked example by hand: a node with 10 examples, 6 of class A and 4 of class B. A question sends 5 examples all of A to the left, and the other 5 (1 of A and 4 of B) to the right.

Gini(parent)   = 1 − (0.6² + 0.4²)  = 1 − 0.52  = 0.48
Gini(left)     = 1 − (1² + 0²)      = 0
Gini(right)    = 1 − (0.2² + 0.8²)  = 1 − 0.68  = 0.32
Weighted impurity = 5/10 · 0 + 5/10 · 0.32 = 0.16
Δ = 0.48 − 0.16 = 0.32

The code that follows computes the same thing for Gini and entropy with a small peso function that applies the weighted average. You can see that with entropy the gain is 0.610 and with Gini 0.320: the absolute numbers are not comparable between criteria, but the order of the questions (which one is better) usually coincides.

Among all the possible questions, the one with maximum Δ is chosen. Let us verify the calculation with code:

padre = np.array([0] * 6 + [1] * 4)
sx = np.array([0] * 5)
dx = np.array([0] * 1 + [1] * 4)
peso = lambda f, a, b: len(a) / len(padre) * f(a) + len(b) / len(padre) * f(b)
print("Gini:    parent %.3f  weighted children %.3f  gain %.3f" % (gini(padre), peso(gini, sx, dx), gini(padre) - peso(gini, sx, dx)))
print("Entropy: parent %.3f  weighted children %.3f  gain %.3f" % (entropia(padre), peso(entropia, sx, dx), entropia(padre) - peso(entropia, sx, dx)))

Gini:    parent 0.480  weighted children 0.160  gain 0.320
Entropy: parent 0.971  weighted children 0.361  gain 0.610

The output confirms the calculation by hand: with Gini the parent is worth 0.480 and the weighted children 0.160, so the gain is 0.320. With entropy the values are 0.971, 0.361 and 0.610. In both cases the question removes about two thirds of the parent's impurity, but the numbers are on different scales and are not compared across measures. In the exercise that follows you will see that even the order of the questions can change.

QUESTION A - "does it come from the product chat?"
   yes (60):  60 information ,  0 bug
   no  (40):  20 information , 20 bug

QUESTION B - "does it contain an attachment?"
   no  (90):  80 information , 10 bug
   yes (10):   0 information , 10 bug

The algorithm: greedy and recursive search

The standard method (CART, Classification And Regression Trees) is greedy: at each node it tries all the features and, for each numeric feature, all the candidate thresholds (the midpoints between consecutive sorted values), chooses the (feature, threshold) pair with maximum Δ, splits, and repeats on each child. It stops when the node is pure, or reaches a maximum depth, or has too few examples. The leaf predicts the majority class of its examples.

"Greedy" means that the best choice now does not guarantee the best tree overall: finding the optimal tree is a computationally intractable problem, and we fall back on this heuristic, which works well in practice.

Implementation by hand

We build the tree on Iris (150 flowers, 4 measurements, 3 species) with only two pieces: migliore_divisione, which tries every (feature, threshold) pair and keeps the one with the highest gain, and costruisci, which applies it recursively down to a maximum depth. The result is compared with DecisionTreeClassifier, with the same criterion and depth.

from sklearn.datasets import load_iris
from sklearn.model_selection import train_test_split
from sklearn.tree import DecisionTreeClassifier, export_text

def migliore_divisione(X, y, impurita):
    n, d = X.shape
    migliore = (None, None, 0.0)                     # (feature, threshold, gain)
    base = impurita(y)
    for j in range(d):
        valori = np.unique(X[:, j])
        for s in (valori[:-1] + valori[1:]) / 2:     # midpoints between consecutive values
            sx = X[:, j] <= s
            nl = sx.sum()
            guadagno = base - (nl / n * impurita(y[sx]) + (n - nl) / n * impurita(y[~sx]))
            if guadagno > migliore[2] + 1e-12:
                migliore = (j, s, guadagno)
    return migliore

def costruisci(X, y, impurita, profondita=0, max_prof=3, min_campioni=2):
    if profondita >= max_prof or len(y) < min_campioni or impurita(y) == 0:
        return {"foglia": int(np.bincount(y).argmax())}
    j, s, g = migliore_divisione(X, y, impurita)
    if j is None:
        return {"foglia": int(np.bincount(y).argmax())}
    sx = X[:, j] <= s
    return {"feature": j, "soglia": s,
            "sx": costruisci(X[sx], y[sx], impurita, profondita + 1, max_prof, min_campioni),
            "dx": costruisci(X[~sx], y[~sx], impurita, profondita + 1, max_prof, min_campioni)}

def prevedi_uno(nodo, x):
    while "foglia" not in nodo:
        nodo = nodo["sx"] if x[nodo["feature"]] <= nodo["soglia"] else nodo["dx"]
    return nodo["foglia"]

Xi, yi = load_iris(return_X_y=True)
Xtr, Xte, ytr, yte = train_test_split(Xi, yi, test_size=0.3, stratify=yi, random_state=0)

albero = costruisci(Xtr, ytr, gini, max_prof=3)
pred = np.array([prevedi_uno(albero, x) for x in Xte])
sk = DecisionTreeClassifier(criterion="gini", max_depth=3, random_state=0).fit(Xtr, ytr)

print("hand-made root:  feature %d, threshold %.3f" % (albero["feature"], albero["soglia"]))
print("sklearn root:    feature %d, threshold %.3f" % (sk.tree_.feature[0], sk.tree_.threshold[0]))
print("accuracy by hand %.3f   sklearn %.3f" % ((pred == yte).mean(), sk.score(Xte, yte)))
print()
print(export_text(sk, feature_names=["sepal_length", "sepal_width", "petal_length", "petal_width"]))

hand-made root:  feature 2, threshold 2.350
sklearn root:    feature 3, threshold 0.800
accuracy by hand 0.956   sklearn 0.956

|--- petal_width <= 0.80
|   |--- class: 0
|--- petal_width >  0.80
|   |--- petal_width <= 1.75
|   |   |--- petal_length <= 4.95
|   |   |   |--- class: 1
|   |   |--- petal_length >  4.95
|   |   |   |--- class: 1
|   |--- petal_width >  1.75
|   |   |--- petal_length <= 4.85
|   |   |   |--- class: 2
|   |   |--- petal_length >  4.85
|   |   |   |--- class: 2

What the code does. migliore_divisione runs through all the features j; for each one it takes the sorted distinct values (np.unique) and proposes as thresholds the midpoints between consecutive values: a threshold halfway between two neighboring values separates the examples in a way different from every other. For each threshold it computes the boolean mask sx of the examples on the left and the weighted gain. It keeps the best. costruisci is recursive: if it has reached the maximum depth, has few examples, or the node is already pure (zero impurity) it returns a leaf with the most frequent class (np.bincount(y).argmax()); otherwise it finds the best split and calls itself on the two subsets. prevedi_uno descends the tree from the root following the thresholds down to a leaf. The tree is a nested dictionary: no classes, no dependencies.

An instructive detail: the hand-made root uses feature 2 (petal length, threshold 2.35), the scikit-learn one feature 3 (petal width, threshold 0.80). It is not an error: both isolate class 0 perfectly, so they have the same gain, and the first one found wins. In scikit-learn the features are examined in random order at each split, and the documentation of DecisionTreeClassifier warns that with identical gains the chosen split may vary; fixing random_state makes the behavior deterministic. The test accuracy is identical (0.956).

Also look at the two leaves at the bottom of each branch of the printed tree: under "petal_width ≤ 1.75" the split on "petal_length ≤ 4.95" produces two leaves of the same class 1, and under the other branch two leaves of class 2. That question does not change any prediction, but it reduces the impurity (it separates a few examples of another class), and this is why the greedy algorithm chooses it anyway. A tree can therefore contain splits that are of no use for prediction: pruning, further below, eliminates many of them.

The tree can be read as a set of "if... then..." rules: it is its strength compared with almost all other models, and it matters a lot when you have to explain a decision to a person or an auditor.

The main trap: a deep tree memorizes

If you do not stop it, a tree keeps splitting until every leaf is pure, that is until it has memorized the training set. We see it on the Breast Cancer dataset (569 cases, 30 features) by growing the depth:

from sklearn.datasets import load_breast_cancer

Xb, yb = load_breast_cancer(return_X_y=True)
Xbt, Xbe, ybt, ybe = train_test_split(Xb, yb, test_size=0.3, stratify=yb, random_state=0)

for prof in (1, 2, 3, 5, 8, None):
    t = DecisionTreeClassifier(max_depth=prof, random_state=0).fit(Xbt, ybt)
    print("max_depth=%-4s leaves %3d   train %.3f   test %.3f" % (
        prof, t.get_n_leaves(), t.score(Xbt, ybt), t.score(Xbe, ybe)))

max_depth=1    leaves   2   train 0.932   test 0.889
max_depth=2    leaves   4   train 0.942   test 0.906
max_depth=3    leaves   8   train 0.980   test 0.901
max_depth=5    leaves  15   train 0.997   test 0.912
max_depth=8    leaves  16   train 1.000   test 0.906
max_depth=None leaves  16   train 1.000   test 0.906

What the code does: it loads Breast Cancer (569 patients, 30 measurements from cell images, benign/malignant label), splits in a stratified way and trains trees with increasing maximum depth; max_depth=None means no limit. get_n_leaves() counts the leaves, a direct measure of complexity.

Without a depth limit the training accuracy is 1.000 and the tree reaches 16 leaves: it has a rule for almost every case. The test, however, does not improve: with only 4 leaves (depth 2) it scores 0.906, like the full tree. On this dataset the extra complexity buys nothing. The hyperparameters that control complexity are max_depth, min_samples_leaf (minimum number of examples per leaf), min_samples_split and ccp_alpha (post-hoc pruning that eliminates branches whose gain does not justify the complexity). They are chosen with cross-validation.

Trap: noise columns and dirty labels

When the data have noisy labels (annotation errors, ambiguous cases), an unlimited tree is not content with what is explainable: it keeps splitting until it isolates the errors too, and to do so it needs any column with thresholds to try, even one that contains no information. We build a controlled case: three informative features, 15% of the labels wrong, and we compare the tree with and without ten columns of pure noise.

from sklearn.datasets import make_classification

Xi3, yi3 = make_classification(n_samples=1000, n_features=3, n_informative=3, n_redundant=0,
                               n_clusters_per_class=1, flip_y=0.15, shuffle=False, random_state=0)
rng = np.random.default_rng(0)
Xn = np.hstack([Xi3, rng.normal(size=(1000, 10))])           # 3 real columns + 10 noise columns
Xt, Xe, yt, ye = train_test_split(Xn, yi3, test_size=0.3, stratify=yi3, random_state=0)

for nome, cols in (("3 informative", slice(0, 3)), ("3 informative + 10 noise", slice(0, 13))):
    t = DecisionTreeClassifier(random_state=0).fit(Xt[:, cols], yt)
    imp = t.feature_importances_
    print("%-26s leaves %3d  train %.3f  test %.3f  importance given to noise: %.3f" % (
        nome, t.get_n_leaves(), t.score(Xt[:, cols], yt), t.score(Xe[:, cols], ye),
        imp[3:].sum() if imp.size > 3 else 0.0))

3 informative              leaves  96  train 1.000  test 0.830  importance given to noise: 0.000
3 informative + 10 noise   leaves  72  train 1.000  test 0.797  importance given to noise: 0.212

What the code does: make_classification with shuffle=False keeps the 3 informative columns in first position, so we can know which they are. flip_y=0.15 flips 15% of the labels. Ten columns of Gaussian noise are added with np.hstack. For each configuration an unlimited tree is trained and the importance of the noise columns is summed (imp[3:].sum()): feature_importances_ is the total impurity reduction attributed to each feature, normalized to sum 1.

In both cases the tree reaches 1.000 on the training set with dozens of leaves: it is memorizing the wrong labels. With the noise columns available the tree attributes to them 21.2% of the total importance and the test drops from 0.830 to 0.797 (a single 70/30 split and a single seed, so the difference is an indication, not a measurement). Note that in the Breast Cancer dataset from before, where the real features separate the classes well, the noise would not have been used: the problem shows up when the data are dirty. This is why the feature importance computed on the training set (mean impurity) must be read with caution; the more robust alternative is the permutation importance computed on validation data.

Instability: small changes in the data, different trees

Trees are high-variance models. If you train the same algorithm on slightly different samples of the same population, you get even very different trees. Try with five resamplings of the training set (drawing with replacement):

nomi = load_breast_cancer().feature_names
for seed in range(5):
    r = np.random.default_rng(seed)
    idx = r.integers(0, len(Xbt), size=len(Xbt))
    t = DecisionTreeClassifier(max_depth=3, random_state=0).fit(Xbt[idx], ybt[idx])
    print("sample %d: root = %-22s threshold %.3f   test %.3f" % (
        seed, nomi[t.tree_.feature[0]], t.tree_.threshold[0], t.score(Xbe, ybe)))

sample 0: root = worst perimeter        threshold 110.050   test 0.906
sample 1: root = worst perimeter        threshold 106.100   test 0.912
sample 2: root = worst concave points   threshold 0.115   test 0.906
sample 3: root = worst radius           threshold 16.815   test 0.947
sample 4: root = worst radius           threshold 17.005   test 0.936

The root changes from sample to sample: "worst perimeter" in two cases, "worst concave points" in one, "worst radius" in two, with different thresholds, and the test accuracy oscillates between 0.906 and 0.947. None of these features is "wrong" (they are all highly correlated with each other), but the structure you read from the tree depends on the sample you have in hand. This instability is the defect that in Random Forest we turn into an advantage: if a single tree is unstable, the average of many different trees is not.

Trade-offs

• Pros: interpretable, they require no scaling or normalization, they handle numeric and categorical features (with encoding), they capture interactions and nonlinearities without you specifying them, they are fast to use at prediction time.
• Cons: easy overfitting, high variance, "staircase" boundaries orthogonal to the axes (a diagonal requires many steps), in regression they do not extrapolate beyond the range seen in training (they predict piecewise constants).
• Gini or entropy? In practice the difference is small. Start from the default (Gini) and change only if validation justifies it.

The advantages and disadvantages come from the same choice: a tree is a set of explicit rules, therefore readable and with no need to prepare the data, but each rule is a rigid threshold on a single feature, and this makes it unstable and prone to memorizing. The scikit-learn documentation says that the cost of a prediction is logarithmic in the number of training examples and that trees are not suited to extrapolation, because their predictions are piecewise constant.

Real-world pitfalls

• Training accuracy of 1.0 is a symptom of overfitting, not a success.
• Imbalanced classes: pure leaves of the majority class dominate. Use class_weight="balanced" and evaluate with recall and precision.
• Identifier columns left in the dataset (id, email address, unique timestamp): the tree exploits them to memorize. Remove them.
• Thresholds on production data that has a different distribution from the training data: the tree has no "softness", a value just past the threshold changes branch.
• Reading too much into a single tree: its structure is unstable, it is not a "law" about the phenomenon.

The five pitfalls share one cause: the tree does exactly what you ask of it, that is reduce the impurity on the training set, and it does so even when the only way is to use an identifier, a wrong label or a chance threshold. So none of these pitfalls produces an error or a warning: you find them only by looking at the test, the permutation importance and the stability across samples.

Trees for regression: variance reduction

So far the tree predicted a class. To predict a number the structure is identical: what changes are the criterion with which the split is chosen and the value in the leaves. Instead of Gini or entropy you use the reduction of the sum of squared deviations (SSE, equivalent to reducing the variance): a split is good if the values in each child are closer to their own mean than the values of the parent are to the parent's mean. The leaf predicts the mean of the values that arrive there, which is the value that minimizes the squared error in that leaf (the mean is the value that minimizes the sum of squared deviations, the same argument as the centroid in K-Means).

from sklearn.tree import DecisionTreeRegressor

rng = np.random.default_rng(0)
x_r = np.sort(rng.uniform(0, 6, 120))
y_r = np.sin(x_r) + rng.normal(0, 0.3, 120)                           # noisy sine wave

def best_regression_split(x, y):
    best_threshold, best_sse = None, np.inf
    for threshold in (x[:-1] + x[1:]) / 2:                             # midpoints between consecutive values
        left, right = y[x <= threshold], y[x > threshold]
        sse = ((left - left.mean()) ** 2).sum() + ((right - right.mean()) ** 2).sum()
        if sse < best_sse:
            best_threshold, best_sse = threshold, sse
    return best_threshold, ((y - y.mean()) ** 2).sum() - best_sse     # threshold and SSE reduction

threshold, gain = best_regression_split(x_r, y_r)
sk = DecisionTreeRegressor(max_depth=1).fit(x_r[:, None], y_r)
print("by hand:      threshold %.4f   SSE reduction %.2f   leaf means %.4f and %.4f" % (
    threshold, gain, y_r[x_r <= threshold].mean(), y_r[x_r > threshold].mean()))
print("scikit-learn: threshold %.4f                         leaf means %.4f and %.4f" % (
    sk.tree_.threshold[0], sk.tree_.value[1, 0, 0], sk.tree_.value[2, 0, 0]))

x_grid = np.linspace(0, 6, 300)
print("\ndepth        leaves   error vs true function   training error")
for depth in (1, 2, 3, 5, 8, None):
    m = DecisionTreeRegressor(max_depth=depth, random_state=0).fit(x_r[:, None], y_r)
    print("%-9s   %5d   %22.4f   %14.4f" % (depth, m.get_n_leaves(), ((m.predict(x_grid[:, None]) - np.sin(x_grid)) ** 2).mean(), ((m.predict(x_r[:, None]) - y_r) ** 2).mean()))

by hand:      threshold 3.2412   SSE reduction 50.17   leaf means 0.5460 and -0.7487
scikit-learn: threshold 3.2412                         leaf means 0.5460 and -0.7487

depth        leaves   error vs true function   training error
1               2                   0.0907           0.1459
2               4                   0.0625           0.1160
3               8                   0.0333           0.0778
5              29                   0.0564           0.0509
8              87                   0.0971           0.0079
None          120                   0.1035           0.0000

What the code does. best_regression_split runs through the candidate thresholds (as for classification) and for each one computes the sum of squared deviations in the two children with respect to their respective means; it keeps the threshold that minimizes the sum, and also returns the reduction with respect to the parent (50.17). The split found by hand, 3.2412, coincides with scikit-learn's, and the leaf means (0.546 and −0.749) are the values the tree predicts: one constant for x ≤ 3.24 and another for x > 3.24.

Then the depth is increased and the error with respect to the true sine on the grid is measured (possible because the data are synthetic) together with the error on the training set. The profile is the usual one: the training error falls monotonically to zero (with 120 leaves the tree memorizes every point, noise included), while the error with respect to the true function has a minimum at depth 3 (0.033, with 8 leaves) and then rises again: 0.056 at depth 5, 0.097 at 8 and 0.104 without limit, almost the worst-case value, that is the variance of the noise (0.09) plus a little. The regression tree draws a step function, and with a few steps it approximates the smooth curve well; with too many, it chases the noise. It is the same compromise, with the same remedies (maximum depth, minimum leaves, pruning) and the same consequence: outside the range of the data it predicts a constant.

Cost-complexity pruning: choosing the size of the tree

Limiting the depth a priori is a coarse choice. A finer approach is to grow the full tree and then prune it. Cost-complexity pruning (CCP, Breiman et al. 1984) penalizes the number of leaves: for a parameter α ≥ 0 it minimizes SSE_tree + α·(number of leaves), or the analogue with impurity. With α = 0 you keep the full tree; increasing α you cut away, one after another, the branches whose contribution does not justify the complexity, and you obtain a nested sequence of ever smaller trees. Scikit-learn computes the exact sequence: the critical values of α at which the tree changes. Then α is chosen with cross-validation.

from sklearn.model_selection import cross_val_score

path = DecisionTreeClassifier(random_state=0).cost_complexity_pruning_path(Xbt, ybt)         # on the Breast Cancer training set
alphas = path.ccp_alphas
print("critical alpha values: %d, from the smallest %.5f to the largest %.4f" % (len(alphas), alphas[0], alphas[-1]))

print("alpha       leaves   train acc.   CV acc. (5 folds)   test acc.")
for alpha in sorted(set(np.round(np.quantile(alphas, [0, 0.5, 0.8, 0.9, 0.95, 0.98]), 5))):
    tree = DecisionTreeClassifier(random_state=0, ccp_alpha=alpha).fit(Xbt, ybt)
    cv = cross_val_score(DecisionTreeClassifier(random_state=0, ccp_alpha=alpha), Xbt, ybt, cv=5).mean()
    print("%-10g  %5d   %10.3f        %14.3f        %9.3f" % (alpha, tree.get_n_leaves(), tree.score(Xbt, ybt), cv, tree.score(Xbe, ybe)))

critical alpha values: 12, from the smallest 0.00000 to the largest 0.3435
alpha       leaves   train acc.   CV acc. (5 folds)   test acc.
0              16        1.000                 0.925            0.906
0.00686         7        0.982                 0.937            0.918
0.02461         4        0.962                 0.930            0.901
0.02648         3        0.932                 0.930            0.889
0.1692          2        0.932                 0.905            0.889
0.2738          2        0.932                 0.905            0.889

What the code does. cost_complexity_pruning_path returns the 12 critical values of α for the full tree of the Breast Cancer training set; for six of them the pruned tree is trained and the number of leaves, the training accuracy, the mean of the 5-fold cross-validation (computed on the training set alone) and the test accuracy are reported. With α = 0 the tree has 16 leaves, training accuracy 1.000 (it memorizes), validation 0.925 and test 0.906. With α = 0.00686 the leaves drop to 7, training to 0.982 and validation rises to its maximum, 0.937: the test reaches 0.918. Pruning further, at 4 and 3 leaves the validation falls to 0.930 and at 2 leaves, the "stump", to 0.905.

The classic lesson can be read: the right complexity lies in the middle (here 7 leaves), the choice is made on cross-validation and not on the training set (which always grows with complexity), and the test confirms the direction (0.906 → 0.918; with 171 test examples a difference of 0.012 is two examples, so it is an indication and not a proof). Pruning is a principled way to find the right depth: a single continuous parameter α instead of combining maximum depth, minimum leaves and minimum samples per split.

Feature importance: two measures compared

A tree provides feature_importances_: the total impurity reduction brought by each feature, normalized. It is fast but it is computed on the training set, and is influenced by the structure of the tree. The alternative is the permutation importance (which you find again in Random Forest): one column of the test set is shuffled and the drop in accuracy is measured. The two measures answer different questions: the first "how much did the tree use this feature to build itself?", the second "how much is this feature needed to predict new data well?".

from sklearn.inspection import permutation_importance

shallow = DecisionTreeClassifier(random_state=0, max_depth=4).fit(Xbt, ybt)
impurity = shallow.feature_importances_
permutation = permutation_importance(shallow, Xbe, ybe, n_repeats=20, random_state=0).importances_mean
names = load_breast_cancer().feature_names

print("feature                     impurity importance   permutation importance (test)")
for j in np.argsort(-impurity)[:4]:
    print("%-26s   %14.3f           %20.3f" % (names[j], impurity[j], permutation[j]))
print("\nthe four features with the highest permutation importance:")
for j in np.argsort(-permutation)[:4]:
    print("%-26s   %14.3f           %20.3f" % (names[j], impurity[j], permutation[j]))

feature                     impurity importance   permutation importance (test)
worst perimeter                       0.816                          0.173
mean texture                          0.057                         -0.003
worst concave points                  0.043                          0.118
mean concave points                   0.020                         -0.006

the four features with the highest permutation importance:
worst perimeter                       0.816                          0.173
worst concave points                  0.043                          0.118
area error                            0.011                          0.110
worst compactness                     0.011                          0.041

What the code does. It trains a tree of depth 4 and compares the two importances. For impurity, worst perimeter dominates with 0.816: the tree built a large part of its impurity reduction on the root. By permutation the same feature weighs 0.173, that is shuffling it loses 17 points of accuracy on the test: it is the most important feature with this measure too, but the absolute value is very different (0.816 and 0.173 are on different scales and must not be compared directly).

The instructive comparison is on the others: mean texture has impurity importance 0.057 (second in the ranking) but permutation importance −0.003, that is shuffling it does not change the test accuracy: the tree used it to fit the training set but it is not needed to generalize. Conversely area error appears among the top four by permutation (0.110) without being among the first by impurity. It is the same warning seen with the noise columns: impurity importance measures the use the tree made of the feature, not its usefulness. To say which features really matter for the prediction you need permutation, computed on data not used for training, and with correlated features it must be read with caution (the importance is shared among "twin" features).

Categorical variables: ordinal or one-hot encoding?

A tree works with numeric thresholds, so a categorical variable must be translated into numbers. Two choices. Ordinal encoding assigns an integer to each category (red = 0, green = 1...): a single column, but it imposes an order that does not exist. One-hot encoding creates a 0/1 column for each category: more columns, no invented order. For a tree the difference shows in the number of questions needed. We build a case in which 12 categories are associated with a class in an arbitrary way (5 "positive" categories, scattered at random among the codes) and we measure the accuracy with cross-validation, as the depth varies.

r = np.random.default_rng(1)
n = 2000
category = r.integers(0, 12, n)
positive = np.array([0, 1, 0, 0, 1, 0, 0, 1, 0, 1, 0, 0])             # which codes belong to the positive class (arbitrary)
y_cat = (positive[category] ^ (r.random(n) < 0.05)).astype(int)       # 5% of the labels flipped

encodings = {"ordinal (1 column)": category[:, None].astype(float), "one-hot (12 columns)": np.eye(12)[category]}
print("encoding                  depth        leaves   CV accuracy (5 folds)")
for name, features in encodings.items():
    for depth in (2, 4, None):
        tree = DecisionTreeClassifier(max_depth=depth, random_state=0)
        accuracy = cross_val_score(tree, features, y_cat, cv=5).mean()
        print("%-25s  %-10s  %6d   %.3f" % (name, depth, tree.fit(features, y_cat).get_n_leaves(), accuracy))

encoding                  depth        leaves   CV accuracy (5 folds)
ordinal (1 column)         2                4   0.719
ordinal (1 column)         4                6   0.791
ordinal (1 column)         None            12   0.944
one-hot (12 columns)       2                3   0.799
one-hot (12 columns)       4                5   0.944
one-hot (12 columns)       None            12   0.944

What the code does. It generates 2 000 examples with a categorical variable of 12 values and a label that depends on the category in an irregular way (with 5% noise), and trains trees with the two encodings. With the ordinal encoding and depth 2 the accuracy is 0.719, with depth 4 it rises to 0.791 and only without limit (12 leaves, one per code) does it reach 0.944. With one-hot, depth 4 and 5 leaves are enough to reach the same 0.944, and already at depth 2 you get 0.799, more than the ordinal at depth 4.

Why? The tree with the ordinal encoding can only split into "codes less than s" and "greater than s": to isolate a scattered set of codes (0, 2, 3, 5, 6, 8, 10, 11 against 1, 4, 7, 9) many consecutive thresholds are needed, hence many levels, and in real data this translates into many more examples needed and a risk of overfitting. With one-hot every question is "is it exactly this category?", and five questions isolate the five positive categories. The practical rule: for categories with no natural order use one-hot (or an algorithm that handles categories natively, such as LightGBM or HistGradientBoosting); ordinal makes sense only when the order really exists (sizes, levels). With many categories (hundreds), one-hot blows up the number of columns and you resort to groupings, target encoding (with great care about leakage) or models with native support.

Three things to try

Exercise 1. For the regression tree, add min_samples_leaf=10 and compare the error with respect to the true function with that of the unlimited tree: how much is a constraint on the leaves worth, as a regularizer? Exercise 2. In pruning, try choosing α with GridSearchCV over the 12 critical values: does the chosen α coincide with the one you identified by hand? Exercise 3. Repeat the categories experiment with 60 categories and a training set of 300 examples: does the difference between ordinal and one-hot encoding grow or shrink?

To practise on support-ticket triage there is an exercise skeleton in Python with three parts to complete: Gini and entropy with the 0·log 0 case, the weighted gain on the case where the two criteria choose different roots, and the gain ratio that dismantles the identifier column. The comments in the file are in Italian. As long as the points to complete are empty, it prints which exercises are missing.

What you can do now

You can compute Gini, entropy and the gain of a split by hand, you can write the greedy search that builds a tree and you can recognize when two legitimate criteria choose different roots. You can choose the complexity with pruning and cross-validation, you can read an impurity importance with suspicion and you know why a single tree changes with the data. In Random Forest we combine many unstable trees to obtain a stable model.

Sources

Previous lesson in the course: KNN: classifying by looking at neighbours (and the curse of dimensionality). Other lessons in the series that link to this one: Entropy, Cross-Entropy and KL Divergence: Why Loss Functions Are All the Same Thing, The ML project process: splits, data leakage and metrics that lie, Boosting: AdaBoost, Gradient Boosting and a note on XGBoost.