06 - Decision Trees and Random Forest

A decision tree is a sequence of yes/no questions about the measurements ("does the nodule have a radius greater than 14?") that ends in a prediction, and it is the only model in this series that you can print and hand to a person who knows no statistics. It has, however, two defects that explain everything else: left to grow it memorises the training set, and changing a few examples is enough to make the tree look different. The remedy for the second, averaging many different trees, is the random forest. This article builds a tree with a hand computation and compares it with scikit-learn, shows with a measurement where it overfits and how it is pruned, explains why a forest works with experiments on the number of trees and on the choice of features, and warns about the limits of feature importance. You need chapters 04 (bias and variance, where bagging has already appeared) and 05 (cross-validation).

The examples use scikit-learn 1.9.0 and numpy 2.4.6, with the Breast Cancer dataset (569 examples, 30 measurements) and with synthetic data with a fixed seed; the outputs are identical across two runs.

How a tree grows

The algorithm is greedy: it starts from a node with all the examples, looks for the question "measurement ≤ threshold" that best separates the classes, splits into two children and repeats in each. The textbook by James, Witten, Hastie and Tibshirani (An Introduction to Statistical Learning) calls it recursive binary splitting (section 8.1.1) and applies it to classification problems in section 8.1.2. "Best" is measured with the impurity of a node: the lower it is, the more the node contains a single class. With p_k the fraction of examples of class k in the node, the Gini index is 1 − Σ p_k² and the entropy is −Σ p_k log₂ p_k (in bits). For two classes, a 50/50 node has Gini 0.5 and entropy 1; a pure node has both at 0. The textbook observes that the two indices are numerically very similar. A split is evaluated with the weighted mean of the impurities of the children, and the threshold that minimises it is chosen.

Worked exercise: the best threshold for a single feature

Ten examples with a measurement x from 1 to 10, labels 0,0,0,1,0,1,1,1,1,0 (five per class). For each threshold halfway between two consecutive values the examples are split, the Gini of the two children is computed and averaged with weights; then the result is compared with that of DecisionTreeClassifier(max_depth=1). By hand: for threshold 3.5 the left child (x = 1, 2, 3) is pure, with Gini 0; the right one has 7 examples, 5 of class 1 and 2 of class 0, so Gini 1 − (5/7)² − (2/7)² = 0.4082; the weighted mean is (3·0 + 7·0.4082)/10 = 0.2857.

import numpy as np
from sklearn.tree import DecisionTreeClassifier

x = np.array([1, 2, 3, 4, 5, 6, 7, 8, 9, 10], dtype=float)
y = np.array([0, 0, 0, 1, 0, 1, 1, 1, 1, 0])           # 5 and 5; a single feature

def gini(y):
    p = np.bincount(y, minlength=2) / len(y)
    return 1 - np.sum(p ** 2)

def entropy(y):
    p = np.bincount(y, minlength=2) / len(y)
    p = p[p > 0]
    return -np.sum(p * np.log2(p))

print("impurity of the root: Gini =", round(gini(y), 4), " entropy =", round(entropy(y), 4))
best = None
for t in (x[:-1] + x[1:]) / 2:                          # thresholds halfway between consecutive values
    left, right = y[x <= t], y[x > t]
    weighted = (len(left) * gini(left) + len(right) * gini(right)) / len(y)
    if best is None or weighted < best[1]:
        best = (t, weighted)
    print(f"threshold {t:4.1f}: weighted Gini of the children = {weighted:.4f}")
print("best threshold by hand:", best[0], " impurity reduction:", round(gini(y) - best[1], 4))

tree = DecisionTreeClassifier(max_depth=1, random_state=0).fit(x[:, None], y)
print("threshold chosen by sklearn:", tree.tree_.threshold[0], " impurity of root and children:", tree.tree_.impurity.round(4).tolist())

# Output:
# impurity of the root: Gini = 0.5  entropy = 1.0
# threshold  1.5: weighted Gini of the children = 0.4444
# threshold  2.5: weighted Gini of the children = 0.3750
# threshold  3.5: weighted Gini of the children = 0.2857
# threshold  4.5: weighted Gini of the children = 0.4167
# threshold  5.5: weighted Gini of the children = 0.3200
# threshold  6.5: weighted Gini of the children = 0.4167
# threshold  7.5: weighted Gini of the children = 0.4762
# threshold  8.5: weighted Gini of the children = 0.5000
# threshold  9.5: weighted Gini of the children = 0.4444
# best threshold by hand: 3.5  impurity reduction: 0.2143
# threshold chosen by sklearn: 3.5  impurity of root and children: [0.5, 0.0, 0.4082]

Of the nine thresholds, 3.5 gives the lowest weighted Gini (0.2857), with an impurity reduction of 0.2143 relative to the root; scikit-learn chooses the same threshold and reports the same impurities, 0.5 for the root, 0.0 and 0.4082 for the children. Threshold 5.5 is second (0.3200). The method does not guarantee the optimal tree, because each choice looks only at the current step; this is why two trees trained on slightly different samples can be very different.

For a regression problem the leaves contain the mean of the values of the examples that reach them, and the impurity becomes the squared error inside the node: the threshold is chosen that minimises the sum of the squared errors of the two children. The splitting rule is the same, only the measure changes.

Why a tree overfits, and pruning

A tree with no limits keeps splitting until every leaf is pure: on the training set the error is zero, and the cost is leaves that describe the noise. The listing shows the accuracy on training and test sets (30% of the data, 171 examples) as the maximum depth grows, and then cost-complexity pruning: a cost error + α·(number of leaves) is defined, and for each α there is an optimal subtree; cost_complexity_pruning_path computes the sequence of the α at which it changes, and the α is chosen with cross-validation on the training set alone.

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

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)
print(f"{'depth':>11} | {'leaves':>6} | {'train accuracy':>17} | test accuracy")
for d in (1, 2, 3, 5, 8, None):
    t = DecisionTreeClassifier(max_depth=d, random_state=0).fit(Xtr, ytr)
    print(f"{str(d):>11} | {t.get_n_leaves():6d} | {t.score(Xtr, ytr):17.3f} | {t.score(Xte, yte):.3f}")

# cost-complexity pruning: the sequence of alpha comes from the full tree
path = DecisionTreeClassifier(random_state=0).cost_complexity_pruning_path(Xtr, ytr)
alphas = np.unique(path.ccp_alphas.round(6))
gs = GridSearchCV(DecisionTreeClassifier(random_state=0), {"ccp_alpha": alphas},
                  cv=StratifiedKFold(5, shuffle=True, random_state=0)).fit(Xtr, ytr)
t = gs.best_estimator_
print(f"candidate alphas: {len(alphas)}; chosen by CV: {gs.best_params_['ccp_alpha']:.5f}; leaves={t.get_n_leaves()}; "
      f"train={t.score(Xtr, ytr):.3f} test={t.score(Xte, yte):.3f}")

# Output:
#       depth | leaves |    train accuracy | test accuracy
#           1 |      2 |             0.932 | 0.889
#           2 |      4 |             0.942 | 0.906
#           3 |      8 |             0.980 | 0.901
#           5 |     15 |             0.997 | 0.912
#           8 |     16 |             1.000 | 0.906
#        None |     16 |             1.000 | 0.906
# candidate alphas: 12; chosen by CV: 0.01959; leaves=5; train=0.972 test=0.918

With depth 1 the tree has 2 leaves and a test accuracy of 0.889; at depth 5 it has 15 with a test accuracy of 0.912; from depth 8 onwards the tree is complete with 16 leaves, training 1.000 and test 0.906. Here the complete tree has only 16 leaves because the classes are well separated, but the sign of overfitting is visible: the training accuracy rises to 1.000 while the test accuracy stops around 0.91. Pruning with α chosen by validation (0.01959) leaves 5 leaves, with training 0.972 and test 0.918: a much simpler tree that does not lose on the test set. Do not exaggerate the differences: 0.918 and 0.906 on 171 examples are two examples apart, and both values are compatible with the same real quality. The advantage of the pruned tree lies more in readability than in the score.

From instability to the forest

A single tree has little bias and a lot of variance, exactly the case in which averaging helps (chapter 04). The random forest combines two ideas. The first is bagging: each tree is trained on a sample drawn with replacement from the training set (bootstrap), which contains on average about 63% of the distinct examples, because the probability that an example is never drawn in n draws is (1 − 1/n)ⁿ, which tends to 0.368. The second is the random choice of features: at each split the tree considers only a subset of m measurements chosen at random, typically m ≈ √p for classification, and the textbook (section 8.2.2) explains why: if one measurement is very strong, all the trees would use it at the top and would be similar to each other, whereas averaging highly correlated trees reduces the variance little. The scikit-learn documentation indicates max_features="sqrt" as an empirically good value for classification, and max_features=None, all the features, is equivalent to the bagging of trees.

The examples left out of a tree's sample (about 37%) are free test examples for that tree: the out-of-bag (OOB) prediction of each example is the mean of the trees that did not see it, and the accuracy of those predictions is an estimate of the test error without cross-validation (textbook, section 8.2.1). The listing uses a synthetic problem with noise on the labels (10%), 20 measurements of which 5 informative and 5 redundant.

import numpy as np
from sklearn.datasets import make_classification
from sklearn.ensemble import RandomForestClassifier
from sklearn.model_selection import StratifiedKFold, cross_val_score
from sklearn.tree import DecisionTreeClassifier

X, y = make_classification(n_samples=1000, n_features=20, n_informative=5, n_redundant=5,
                           flip_y=0.1, class_sep=1.0, random_state=0)
cv = StratifiedKFold(5, shuffle=True, random_state=0)
def cvm(m): return cross_val_score(m, X, y, cv=cv).mean()

print("a single unbounded tree:", round(cvm(DecisionTreeClassifier(random_state=0)), 3))
for n in (1, 10, 50, 200):
    print(f"forest, {n:3d} trees (max_features='sqrt'):", round(cvm(RandomForestClassifier(n_estimators=n, random_state=0)), 3))
print("forest, 200 trees, max_features=None (= pure bagging):",
      round(cvm(RandomForestClassifier(n_estimators=200, max_features=None, random_state=0)), 3))
rf = RandomForestClassifier(n_estimators=200, oob_score=True, random_state=0).fit(X, y)
print("OOB estimate of the 200-tree forest:", round(rf.oob_score_, 3))

# Output:
# a single unbounded tree: 0.842
# forest,   1 trees (max_features='sqrt'): 0.843
# forest,  10 trees (max_features='sqrt'): 0.911
# forest,  50 trees (max_features='sqrt'): 0.92
# forest, 200 trees (max_features='sqrt'): 0.923
# forest, 200 trees, max_features=None (= pure bagging): 0.906
# OOB estimate of the 200-tree forest: 0.922

A tree with no limits reaches 0.842 in 5-fold cross-validation; a forest with a single tree does practically the same (0.843), as it should. With 10 trees you get to 0.911, with 50 to 0.920, with 200 to 0.923: the gain is quick at the start and then flattens, and in this experiment adding trees does not worsen the result, but it costs computing and prediction time. Pure bagging, with 200 trees and all the features at each split, obtains 0.906: the random choice of features adds about 1.7 points above bagging in this experiment, because it decorrelates the trees. The OOB estimate of the 200-tree forest is 0.922, practically that of cross-validation (0.923), and it is obtained from a single training. These are results on a single synthetic dataset: they do not set a rule, but they show the mechanism.

Feature importance, and why to trust it little

A forest returns for each feature an impurity importance (feature_importances_): how much, on average, the splits on that feature reduce the impurity. It is free but, warns the scikit-learn documentation, it is computed on the training set and is strongly biased in favour of features with many distinct values, typically continuous numeric ones. The alternative is permutation importance: the values of one feature are shuffled in the test set and the drop in accuracy is measured. We build a case in which the answer is known: three informative features and one column of pure noise, continuous.

import numpy as np
from sklearn.datasets import make_classification
from sklearn.ensemble import RandomForestClassifier
from sklearn.inspection import permutation_importance
from sklearn.model_selection import train_test_split

X, y = make_classification(n_samples=1500, n_features=3, n_informative=3, n_redundant=0,
                           n_clusters_per_class=1, flip_y=0.15, random_state=0)
noise = np.random.default_rng(0).standard_normal((len(y), 1))       # one column of pure noise, continuous
X = np.hstack([X, noise])                                           # index 3 = noise
Xtr, Xte, ytr, yte = train_test_split(X, y, test_size=0.3, random_state=0)
rf = RandomForestClassifier(n_estimators=200, min_samples_leaf=1, random_state=0).fit(Xtr, ytr)
print("train:", round(rf.score(Xtr, ytr), 3), " test:", round(rf.score(Xte, yte), 3))
print("impurity importance (features 0,1,2 and noise):", rf.feature_importances_.round(3).tolist())
pi = permutation_importance(rf, Xte, yte, n_repeats=20, random_state=0)
print("permutation importance on the test set:        ", pi.importances_mean.round(3).tolist())

# Output:
# train: 1.0  test: 0.891
# impurity importance (features 0,1,2 and noise): [0.12, 0.684, 0.106, 0.089]
# permutation importance on the test set:         [0.011, 0.388, 0.029, 0.007]

The forest is perfect on the training set (1.000) and reaches 0.891 on the test set. The impurity importance assigns to the noise column 0.089, almost as much as to feature 2 (0.106) and to feature 0 (0.120): reading it, you would conclude that the noise matters. The permutation importance on the test set gives the noise 0.007, practically zero, and recognises that feature 1 weighs far more than all the others (0.388). The difference arises from the fact that impurities are measured on the training set, where the noise was used to split the examples, whereas permutations are evaluated on data the model has not seen. The documentation also warns that this importance describes how much the feature serves a particular model and not its intrinsic value, and that it makes sense only if the model is good on the test data.

When not to use trees and forests

• You need to extrapolate beyond the range of the data: a tree predicts a constant in the last leaf, so a rising trend is flattened outside the range of the training set.
• You need a model that can be explained step by step: a forest of 200 trees cannot be read, and the single pruned tree keeps readability at the cost of a little accuracy.
• The relationship is truly linear with many noisy measurements: a linear model with a penalty (chapter 02) is simpler and more stable.

The three items are different limits of the same aspect: trees approximate with constant pieces. They do it very well where there are thresholds and interactions, and badly where there is continuity and trend. Boosting, which builds trees in sequence instead of in parallel, is another family and is not covered in this article.

What you can do now

You can compute by hand the split of a node with Gini and entropy and check it with scikit-learn, recognise the overfitting of a tree from the two errors and prune it with α chosen by validation, explain why the forest reduces the variance with bagging and random features, estimate its error with the OOB, and use permutation importance in place of impurity importance. The next chapter changes the idea of separation: instead of thresholds, a maximum margin between the classes, with 07 - Support Vector Machines and the kernel trick.

The same series also includes: 03 - Logistic Regression and Binary Classification, 11 - Metrics and ML Model Evaluation and 12 - ML Deployment in Production: Serving and Monitoring.