Decision trees

The big idea

Think of the game twenty questions. "Is it alive?" "Does it fly?" Each answer cuts the possibilities, and a good player asks the question that cuts them most. A decision treeA model that predicts by asking a sequence of yes-or-no questions about the features, following one branch per answer until it reaches a leaf that holds the prediction. plays this game with your data: "Is income above 40,000?" "Is the debt ratio below 0.3?" Each question sends an example left or right until it lands in a leafAn end node of a decision tree. It holds a prediction: the majority class, or the average target, of the training examples that reached it., and the leaf's answer is the prediction.

Trees are popular because you can read them. A loan officer can follow the path and see exactly why an application was declined. They also handle numbers and categories without scaling, and capture interactions ("high income matters only if debt is low") automatically. Their weakness is that a tree allowed to keep asking questions will memorise the training data, noise included.

How it works

Step 1: A tree is a set of nested questions

Each internal node tests one feature against one threshold. Below is a depth-2 tree learned from 300 noisy points of two classes (the code is further down). Follow the glowing path for a new point with x1 = 1.6 and x2 = -0.3.

Every question is about one feature, so every split is a straight line parallel to an axis. A tree carves the feature space into rectangles, one per leaf:

Step 2: Measure how mixed a group is

To choose a question, the tree needs a score for how mixed the labels in a node are. Gini impurityThe probability that two examples drawn at random (with replacement) from a node have different labels: 1 minus the sum of squared class proportions. is the usual one:

where p_k is the share of class k in the node. A pure node scores 0. A 50/50 node scores 0.5, the worst possible for two classes. EntropyA measure of uncertainty in bits: minus the sum of p log2 p over classes. 0 for a pure node, 1 for a 50/50 binary node., from information theory ( Information theory for ML ), is the alternative: minus the sum of p_k log2 p_k. The two almost always pick the same splits; Gini is slightly cheaper to compute.

Worked example: a node with 6 "yes" and 4 "no" has Gini 1 - (0.6^2 + 0.4^2) = 1 - 0.52 = 0.48 (entropy 0.971 bits).

Step 3: Choose the split that reduces impurity most

For every feature and every threshold between two sorted values, the tree computes the impurity of the two children, weighted by their sizes, and keeps the split with the lowest result. Splitting our 10 examples into 5 "yes" on the left and 1 "yes" plus 4 "no" on the right gives children with Gini 0 and 1 - (0.2^2 + 0.8^2) = 0.32. Weighted: 0.5 x 0 + 0.5 x 0.32 = 0.16, down from 0.48. That reduction, 0.32, is the split's gainThe drop in impurity from a parent node to the size-weighted impurity of its children. With entropy it is called information gain..

The tree then repeats the search inside each child. This greedy, one-split-at-a-time algorithm is called CARTClassification and Regression Trees: the standard greedy algorithm that grows binary trees by choosing the impurity-minimising split at each node.. It never reconsiders earlier splits, which makes it fast but not optimal.

For regression the same search minimises the variance (squared error) of the target in each child, and a leaf predicts the mean of its training targets.

Step 4: Stop before it memorises

Left alone, the tree keeps splitting until every leaf is pure, even if a leaf holds a single noisy point. Training accuracy reaches 100 percent; test accuracy drops. Two remedies:

• Pre-pruning (stop early): limit max_depth, require min_samples_leaf (say 20 examples per leaf), or require a minimum gain to split.
• Post-pruning: grow the full tree, then cut back branches whose gain does not justify their size. Cost-complexity pruningPruning that removes subtrees whose impurity reduction is smaller than a penalty alpha times their number of leaves; alpha is chosen by cross-validation. adds a penalty alpha per leaf and picks alpha by cross-validation.

Try it

Try this:

1. Step the depth from 0 to 3. Which feature does the first split use, and why does it cut the two moons roughly in half?
2. Keep going to depth 10. Watch the tiny rectangles appear around single points. What happens to training accuracy, and what happens to test accuracy?
3. Switch between Gini and entropy at depth 3. How much do the splits change?

Going deeper

Code: impurity, depth and pruning

import numpy as np
from sklearn.datasets import make_moons
from sklearn.model_selection import GridSearchCV, train_test_split
from sklearn.tree import DecisionTreeClassifier, export_text

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))

# Impurity of a node and of one candidate split, by hand
y = np.array([1] * 6 + [0] * 4)             # 6 yes, 4 no
left, right = y[:5], y[5:]                  # split: 5 yes | 1 yes + 4 no
w = [len(left) / len(y), len(right) / len(y)]
print(f"parent gini {gini(y):.3f}, entropy {entropy(y):.3f}")
print(f"split  gini {w[0] * gini(left) + w[1] * gini(right):.3f} (left {gini(left):.2f}, right {gini(right):.2f})")

# Depth vs train and test accuracy on noisy two-moons data
X, y = make_moons(n_samples=600, noise=0.3, random_state=0)
Xtr, Xte, ytr, yte = train_test_split(X, y, test_size=0.5, random_state=0)
print("\ndepth  leaves  train  test")
for d in [1, 2, 3, 5, 8, None]:
    t = DecisionTreeClassifier(max_depth=d, random_state=0).fit(Xtr, ytr)
    print(f"{str(d):>5}  {t.get_n_leaves():>6}  {t.score(Xtr, ytr):.3f}  {t.score(Xte, yte):.3f}")

# Cost-complexity pruning: choose alpha by 5-fold cross-validation on the training set
alphas = DecisionTreeClassifier(random_state=0).cost_complexity_pruning_path(Xtr, ytr).ccp_alphas[:-1]
cv = GridSearchCV(DecisionTreeClassifier(random_state=0), {"ccp_alpha": alphas}, cv=5).fit(Xtr, ytr)
best, t = cv.best_params_["ccp_alpha"], cv.best_estimator_
print(f"\npruned: alpha {best:.4f}, leaves {t.get_n_leaves()}, test {t.score(Xte, yte):.3f}")

print("\n" + export_text(DecisionTreeClassifier(max_depth=2, random_state=0).fit(Xtr, ytr), feature_names=["x1", "x2"]))

parent gini 0.480, entropy 0.971
split  gini 0.160 (left 0.00, right 0.32)

depth  leaves  train  test
    1       2  0.810  0.787
    2       4  0.923  0.867
    3       7  0.923  0.867
    5      16  0.953  0.870
    8      27  0.987  0.863
 None      32  1.000  0.857

pruned: alpha 0.0032, leaves 17, test 0.863

|--- x2 <= 0.12
|   |--- x1 <= -0.54
|   |   |--- class: 0
|   |--- x1 >  -0.54
|   |   |--- class: 1
|--- x2 >  0.12
|   |--- x1 <= 1.39
|   |   |--- class: 0
|   |--- x1 >  1.39
|   |   |--- class: 1

The depth table is the overfitting story in numbers. Depth 2 already reaches 86.7 percent test accuracy with 4 leaves. The unlimited tree has 32 leaves, 100 percent training accuracy and 85.7 percent test accuracy: the extra leaves memorised noise. Cost-complexity pruning chosen by cross-validation cuts it to 17 leaves with 86.3 percent. On this data a simple depth limit does as well as pruning; both beat the unlimited tree.

The printed rules at the end are the whole depth-2 model: four lines anyone can audit, which is the main reason trees are still used on their own.

Why trees are unstable

Change a few training points and the root split can move, which changes everything below it. This high variance is the price of greedy, axis-aligned splits. It is also the opening for the next two lessons: averaging many different trees ( Bagging and random forests ) or adding many small ones in sequence ( Boosting: AdaBoost to gradient boosting ) keeps the strengths and cancels much of the variance.

Practical properties

• No feature scaling needed: a split on income works the same in dollars or thousands.
• Categories can be split as groups of values (some libraries do this natively); otherwise one-hot encode them.
• Missing values can be routed down a learned default branch in many implementations.
• Diagonal boundaries need many staircase splits, so a tree is a poor fit when the true boundary is a slanted line.

Trade-offs

Common mistakes

• Leaving max_depth unlimited and trusting a 100 percent training accuracy.
• Reading a deep tree's structure as truth: a slightly different sample would give a different tree.
• Treating label-encoded categories (red = 0, green = 1, blue = 2) as ordered numbers and splitting on "colour less than 1.5".
• Scaling or normalizing features for a tree and expecting it to help; splits are unaffected.
• Choosing the pruning strength on the test set instead of by cross-validation.

In the wild

Shallow decision trees appear wherever a decision must be explained: credit and insurance rules, clinical triage checklists and customer-support routing are often written as small trees, sometimes learned from data and then reviewed by experts. Deep trees are rarely deployed alone. Instead they are the building block of random forests and gradient boosted trees (XGBoost, LightGBM, CatBoost), which you will meet in the rest of this module and which dominate tabular-data problems.

Check yourself

Recap