A1 · Supervised Machine Learning in Depth

Decision Trees

A decision tree predicts by asking a sequence of feature-threshold questions, from the root to a leaf. CART builds it greedily: at each node it chooses the split that most reduces impurity, measured by Gini impurity or entropy (information gain) for classification, or variance for regression. Trees grow until a stopping rule, and pruning removes branches that don't improve validation performance.

18 min Advanced Jump to the activity

What you need: The earlier topics of this module, and its prerequisites.

Definition

How would you guess an animal in five yes-or-no questions?

A decision tree predicts by asking a sequence of feature-threshold questions, from the root to a leaf. CART builds it greedily: at each node it chooses the split that most reduces impurity, measured by Gini impurity or entropy (information gain) for classification, or variance for regression. Trees grow until a stopping rule, and pruning removes branches that don't improve validation performance.

In simple words

At each step, ask the question that splits the group into the purest halves: 'Is the tumour radius above 16?' might send nearly all malignant cases one way. Gini measures mixedness: 0 means everyone in the group has the same label. A tree that keeps splitting until every leaf is pure has memorised the training data.

Why it matters

Trees handle mixed feature types, need no scaling, capture interactions and can be read as rules. They are also the building blocks of random forests and gradient boosting, the strongest methods for tabular data.

Key terms

Root, internal node and leaf
The first split, the splits below it, and the end nodes that give predictions.
Gini impurity
1 − Σpₖ²: the chance of mislabelling a random item if labelled by the node's class mix.
Entropy and information gain
Entropy −Σpₖ log₂pₖ measures disorder; information gain is its reduction after a split.
Pre-pruning
Stopping growth early with limits such as max_depth or min_samples_leaf.
Cost-complexity pruning
Growing a full tree, then removing branches whose gain does not justify their size (ccp_alpha).
Regression tree
A tree whose leaves predict the average target of the training rows that reach them.

Explained in detail

Choosing splits with numbers

Imagine 10 loan applicants, 6 who repaid and 4 who did not. The root's Gini impurity is 1 − (0.6² + 0.4²) = 0.48. Splitting on "income above ₹30,000" sends 5 applicants left (5 repaid, 0 defaulted, Gini 0) and 5 right (1 repaid, 4 defaulted, Gini 1 − (0.2² + 0.8²) = 0.32). The weighted impurity after the split is 0.5 × 0 + 0.5 × 0.32 = 0.16, a reduction of 0.32. The algorithm tries every feature and threshold, picks the largest reduction, and repeats on each child until a stopping rule is met. Regression trees use the reduction in variance or squared error instead, and each leaf predicts the mean of its rows.

Controlling a tree's complexity

HyperparameterEffectTypical range
max_depthLimits the number of questions on any path3 to 15
min_samples_leafEach leaf must contain at least this many rows5 to 100
min_samples_splitA node needs this many rows to be split10 to 200
max_featuresNumber of features considered at each splitsqrt(p) for forests
ccp_alphaStrength of post-pruningChosen by cross-validation

Trees capture interactions and non-linear patterns automatically, need no scaling and handle mixed feature types, which is why they underpin the most successful tabular methods: random forests and gradient boosting. Their weaknesses are high variance, where a small change in data can change the root split and the whole tree, and axis-aligned splits that approximate diagonal boundaries with staircases. Feature importance from trees, based on total impurity reduction, is biased towards features with many unique values; permutation importance on validation data is more reliable. For explanation, a shallow tree of depth 3 or 4 can be printed and read as plain if-then rules, which makes it popular in medicine and policy.

A familiar scenario is a hospital triage rule: "If oxygen saturation is below 92 per cent, admit; otherwise, if the patient is over 65 and has a fever, observe; otherwise, discharge with advice." Such rules can be learned as a decision tree from past cases and then reviewed by doctors line by line. Banks use similar shallow trees for credit decisions because each refusal can be traced to specific conditions. When accuracy matters more than readability, the same trees become the building blocks of random forests and gradient boosting.

How it works

  1. For every feature and every candidate threshold, compute the weighted impurity of the two children.
  2. Choose the split with the largest impurity decrease.
  3. Recurse on each child until max_depth, min_samples_leaf or purity stops it.
  4. Prune: limit depth or use cost-complexity pruning (ccp_alpha) chosen by validation.

The maths

Gini impurity
Entropy and information gain
Share of class k in the node

A node holds 6 positives and 4 negatives. Gini = 1 − (0.6² + 0.4²) = 0.48. A split sends 5 positives and 1 negative left, and 1 positive and 3 negatives right.

Left:  1 − ((5/6)² + (1/6)²) = 0.278   (6 samples)
Right: 1 − ((1/4)² + (3/4)²) = 0.375   (4 samples)
Weighted = 0.6 × 0.278 + 0.4 × 0.375 = 0.317
Decrease = 0.48 − 0.317 = 0.163

In code

The Gini split above computed by hand, then a scikit-learn tree whose depth controls overfitting, with its top rules printed.

decision_tree.py
import numpy as np
from sklearn.datasets import load_breast_cancer
from sklearn.model_selection import train_test_split
from sklearn.tree import DecisionTreeClassifier, export_text

def gini(counts):
    p = np.array(counts) / sum(counts)
    return 1 - np.sum(p ** 2)

parent = gini([6, 4])
weighted = 0.6 * gini([5, 1]) + 0.4 * gini([1, 3])
print(f"Parent Gini {parent:.3f}, children {weighted:.3f}, decrease {parent - weighted:.3f}")

data = load_breast_cancer()
X_tr, X_te, y_tr, y_te = train_test_split(data.data, data.target, test_size=0.3, random_state=0)
print("depth  train acc  test acc  leaves")
for depth in [1, 2, 4, 8, None]:
    tree = DecisionTreeClassifier(max_depth=depth, random_state=0).fit(X_tr, y_tr)
    print(f"{str(depth):>5}  {tree.score(X_tr, y_tr):9.3f}  {tree.score(X_te, y_te):8.3f}  {tree.get_n_leaves():>6}")

small = DecisionTreeClassifier(max_depth=2, random_state=0).fit(X_tr, y_tr)
print(export_text(small, feature_names=list(data.feature_names)))

Output

Parent Gini 0.480, children 0.317, decrease 0.163
depth  train acc  test acc  leaves
    1      0.930     0.895       2
    2      0.960     0.947       4
    4      0.977     0.947      10
    8      1.000     0.912      19
 None      1.000     0.912      19
|--- worst concave points <= 0.14
|   |--- worst area <= 952.90
|   |   |--- class: 1
|   |--- worst area >  952.90
|   |   |--- class: 0
|--- worst concave points >  0.14
|   |--- area error <= 13.93
|   |   |--- class: 1
|   |--- area error >  13.93
|   |   |--- class: 0

Try it yourself

Compute Gini

Match each node's class counts to its Gini impurity.

  • 10 positives, 0 negatives
  • 5 positives, 5 negatives
  • 8 positives, 2 negatives
  • Three classes, equal shares

Common mistakes

  • Growing trees with no depth limit and trusting their training accuracy.
  • Reading the first split as the only important feature. Correlated features can swap places.
  • Expecting smooth predictions. Trees make step functions.

Check yourself

Question 1

1. Gini impurity of a pure node is…

Question 2

2. How does CART choose a split?

Question 3

3. Which reduces overfitting in a tree?

Summary

  • Trees split greedily to reduce Gini or entropy.
  • They need no scaling and read as rules.
  • Control depth or prune to avoid memorising the data.

Read it. Now try it yourself.

Open the interactive activity

Finished reading?

Sources: scikit-learn: Decision trees · James et al., An Introduction to Statistical Learning