Decision Trees

A decision tree is a supervised model that makes predictions by asking a sequence of yes/no questions about the input features, learning the questions themselves from data. This lesson builds the model from the bottom up: the recursive splitting algorithm, the two impurity measures (entropy and Gini), information gain as the splitting criterion, why unconstrained trees overfit dramatically, the four levers used to prune them (max depth, minimum samples per leaf and split, cost-complexity pruning), the connection to the bias-variance tradeoff, and — the killer feature — why a single fitted tree can be read by a non-ML stakeholder as a short story about the data.

Learning Objectives

1. Describe the recursive partitioning algorithm that builds a decision tree, including the base case and the recursive case, and explain why it must terminate.
2. Compute the entropy and the Gini impurity of a node from its class proportions, and explain both the information-theoretic and the probability-of-misclassification interpretations.
3. Compute the information gain of a candidate split, choose the split with the highest gain, and work through a numeric example with real class counts.
4. Explain why an unconstrained tree always reaches 100% training accuracy, and connect that fact to the bias-variance decomposition.
5. Apply the four pruning levers — max_depth, min_samples_split, min_samples_leaf, and cost-complexity pruning (ccp_alpha) — and choose appropriate values for a given dataset size.
6. Read a fitted tree as a set of if/else rules, list features by importance, and explain to a non-technical stakeholder why a single decision path is interpretable.

1. The Recursive Partitioning Idea

A decision tree is built by repeatedly cutting the training set into two (or more) subsets, each cut chosen to make the resulting subsets "purer" than the parent. A pure node contains only one class; an impure node contains a mix.

              [all 100 customers]
              refund?  (no/yes)
              /                \
   refund = no (70)         refund = yes (30)
   marital?                  class=?
   /          \              /         \
single (40) married (30)  single (15) married (15)
class=?      class=?      class=A     class=A
   |            |            |            |
class=B       class=A      class=A      class=A

Figure above is the classic iris-style sketch: every internal node asks one question about a feature, every leaf carries a class label, and the path from the root to a leaf is the rule the model applies to a new example.

Algorithmically, fitting a tree is two functions calling each other:

def build(node, data):
    if stopping_criterion(node, data):
        node.label = majority_class(data)
        return node
    feature, threshold = best_split(data)        # maximise information gain
    node.question = (feature, threshold)
    left  = build(new_node(), data[data.feature <= threshold])
    right = build(new_node(), data[data.feature >  threshold])
    node.left, node.right = left, right
    return node

The recursion bottoms out when a stopping criterion fires — every leaf then holds a single class label (the majority class in that leaf) and a count distribution. Termination is guaranteed because each split strictly reduces the number of rows in every non-empty child node, and that number is bounded below by one.

The two questions to settle before any tree can be built are:

1. How is "purity" measured? — answered by entropy or Gini impurity, Section 2.
2. How is the best feature/threshold chosen? — answered by information gain, Section 3.

2. Impurity: Entropy and Gini

A node is pure if every example in it has the same class. The impurity of a node with class proportions $(p_1, p_2, \ldots, p_K)$ is a number in $[0, 1]$ that is $0$ when one class has probability 1 and reaches its maximum when all classes are equiprobable. Two functions satisfy that contract.

2.1 Entropy

The Shannon entropy of a node with class proportions $(p_1, \ldots, p_K)$ is

with the convention $0 \log_2 0 = 0$. Entropy is the expected number of bits needed to encode the class of a randomly drawn example from the node when the encoding is optimal for that node's class distribution. A pure node needs zero bits — you already know the answer — so $H = 0$. A two-class node with $p = (0.5, 0.5)$ needs exactly one bit, so $H = 1$.

For a binary classification node, the entropy as a function of $p$ (the proportion of class 1) traces out a clean curve:

The maximum is at $p = 0.5$, and the function is symmetric around it.

2.2 Gini impurity

The Gini impurity of a node with class proportions $(p_1, \ldots, p_K)$ is

The probability-of-misclassification interpretation is the cleanest: if you predict by drawing a class label from the node's empirical distribution and the true label is also drawn independently from the same distribution, then $G(p)$ is the probability that the two draws disagree. Equivalently, $G(p)$ is twice the variance of a Bernoulli trial with success probability $p_k$ in a $K$-category setting.

For binary classification with class-1 proportion $p$:

The maximum is $0.5$ at $p = 0.5$, half the entropy maximum. Both curves have the same shape, but Gini is slightly cheaper to compute (no logarithm) and is the default in scikit-learn's DecisionTreeClassifier.

2.3 Side-by-side

The two impurity measures agree on the ranking of splits more than 98% of the time on real datasets. The choice is rarely load-bearing; pick entropy if you care about the information-theoretic story, Gini if you care about speed.

3. Information Gain and the Best Split

Information gain (IG) is the reduction in impurity achieved by splitting a parent node $P$ into children $C_1, C_2, \ldots, C_m$. For a binary split with impurity $I(\cdot)$ and child weights $w_j = |C_j| / |P|$:

The greedy algorithm at every node evaluates every (feature, threshold) pair, computes the resulting IG, and splits on the pair with the largest gain. Ties are broken arbitrarily. With $d$ features and $n$ examples, the per-node cost is $O(d \cdot n)$ (sort each feature once and sweep thresholds); the total cost across the tree is bounded by $O(d \cdot n \cdot h)$ where $h$ is the eventual depth, and $h$ is bounded by $n$ in the worst case.

The same algebra works for both entropy and Gini:

Note that the gain is always non-negative for any split that produces children at least as pure as the parent, and the gain is bounded above by $I(P)$ itself — splitting can at most drive the children's impurity to zero.

A subtle but important caveat: information gain is biased towards features with many distinct values, because a high-cardinality feature can always find a threshold that isolates a single example and yields a large apparent gain. The standard fix is the gain ratio used by Quinlan's C4.5, which divides IG by the split's intrinsic information content; scikit-learn does not implement gain ratio directly but the bias is mitigated by min_samples_leaf and other stopping rules.

4. A Worked Numeric Split

Consider a parent node $P$ with $n = 10$ examples split into two classes: 6 positives and 4 negatives. Two candidate splits are on the table.

Split A — feature refund at threshold "no":

Split B — feature marital at threshold "single":

Compute Gini impurity for each node, then the gain for each split.

Parent $P$: $G(P) = 1 - (0.6^2 + 0.4^2) = 1 - 0.52 = 0.48$.

Split A:

• $G(C_1) = 1 - (0.8^2 + 0.2^2) = 1 - 0.68 = 0.32$
• $G(C_2) = 1 - (0.4^2 + 0.6^2) = 1 - 0.52 = 0.48$
• Weighted children: $w_1 G(C_1) + w_2 G(C_2) = 0.5 \cdot 0.32 + 0.5 \cdot 0.48 = 0.40$
• $\text{IG}_A = 0.48 - 0.40 = 0.08$

Split B:

• $G(C_1) = 1 - (0.5^2 + 0.5^2) = 1 - 0.50 = 0.50$
• $G(C_2) = 1 - (0.75^2 + 0.25^2) = 1 - 0.625 = 0.375$
• Weighted children: $(6/10) \cdot 0.50 + (4/10) \cdot 0.375 = 0.30 + 0.15 = 0.45$
• $\text{IG}_B = 0.48 - 0.45 = 0.03$

The greedy algorithm picks Split A because $\text{IG}_A = 0.08 > 0.03 = \text{IG}_B$. Both splits reduce impurity, but Split A does so more sharply. Repeat the same evaluation at every other (feature, threshold) pair, pick the maximum, recurse into the children, and stop when a stopping rule fires.

The same procedure with entropy produces the same ordering for this example:

• $H(P) = -[0.6 \log_2 0.6 + 0.4 \log_2 0.4] \approx 0.971$
• $H(C_1^A) = -[0.8 \log_2 0.8 + 0.2 \log_2 0.2] \approx 0.722$
• $H(C_2^A) = -[0.4 \log_2 0.4 + 0.6 \log_2 0.6] \approx 0.971$
• $\text{IG}_A^{\text{entropy}} = 0.971 - (0.5 \cdot 0.722 + 0.5 \cdot 0.971) \approx 0.125$

(Entropy gives the same split A as winner — the IG magnitudes differ between Gini and entropy, but the ranking almost always matches.)

5. Why Unconstrained Trees Overfit

A decision tree built with no stopping rule will, by induction on the recursion, eventually reach a state where every leaf contains examples of a single class. That is because the recursion only terminates when a stopping criterion fires; without one, the algorithm keeps splitting until each leaf has fewer than two distinct labels, which means it can drive training accuracy to exactly 100%.

The way that happens is a vivid example of overfitting. Suppose the dataset has $n$ examples and $d$ features. A tree grown until every leaf is pure has at most $n$ leaves (one per example in the degenerate case) and a depth of at most $n$. Such a tree has memorised the training set: every training point falls into a leaf by itself and is classified correctly. Its training error is zero.

The cost is paid on held-out data. Each of those single-example leaves makes a prediction using only that one training point — there is no statistical basis for the prediction. Worse, the splits near the leaves were chosen to separate specific training examples from their neighbours, so the tree has fitted noise rather than signal. On test data the same splits fail to separate new examples, accuracy drops sharply, and the model has high variance — different resamples of the training data produce wildly different trees.

A useful diagnostic: if a single tree can reach 100% training accuracy but its test accuracy is much lower, the gap is the overfitting gap, and the fix is almost always one of the four pruning levers in the next section.

6. Pruning: Four Levers

scikit-learn's DecisionTreeClassifier exposes four parameters that limit tree complexity. Each lever targets a different aspect of the recursion.

6.1 max_depth

Setting max_depth = k stops any branch from extending beyond $k$ levels. A small tree has high bias (it can only ask $k$ questions per prediction) but low variance (the same $k$ questions are robust to resampling). For a dataset with $n \approx 10{,}000$ and a moderate number of features, max_depth in $[3, 10]$ is a reasonable starting range; deeper than that the variance starts to bite.

6.2 min_samples_split

Setting min_samples_split = m forbids any split on a node with fewer than $m$ examples. This prevents the tree from creating tiny near-leaf nodes that have fitted noise. A value of 2 (the default) allows any split; values of 5 to 20 are common regularisers on medium datasets.

6.3 min_samples_leaf

Setting min_samples_leaf = m requires every leaf to contain at least $m$ training examples. This is a stronger condition than min_samples_split because it constrains the children, not just the parent. It directly addresses the overfitting failure mode in Section 5 — leaves with a single example memorise that example, leaves with $m$ examples must summarise them.

6.4 Pre-pruning vs post-pruning

max_depth, min_samples_split, and min_samples_leaf are pre-pruning levers — they stop the tree from growing in the first place. The alternative is post-pruning: grow the tree fully, then collapse subtrees back into their parent if doing so does not hurt validation performance. The classic post-pruning method is cost-complexity pruning, covered next.

7. Cost-Complexity Pruning

Cost-complexity pruning (Breiman, Friedman, Olshen, Stone — the CART book, 1984) is the most principled post-pruning method. The idea is to find a sequence of subtrees $T_0 \supset T_1 \supset T_2 \supset \cdots$ where $T_0$ is the fully grown tree and each subsequent $T_{k+1}$ is obtained from $T_k$ by collapsing the subtree whose removal causes the smallest increase in training error per removed leaf.

The scoring function for a subtree $T \subseteq T_0$ is

where $R(T)$ is the tree's misclassification rate on the training set, $|T|$ is the number of leaves in $T$, and $\alpha \geq 0$ is a complexity parameter. For each $\alpha$ there is a unique smallest subtree that minimises $R_\alpha$. The path of optimal subtrees as $\alpha$ increases is the pruning path.

DecisionTreeClassifier.cost_complexity_pruning_path(X, y) returns the sequence $(\alpha_k, T_k)$; picking the $\alpha$ that minimises validation score (or that yields the smallest gap between train and validation accuracy) gives the right-sized tree for the data.

Two practical notes:

1. $\alpha = 0$ corresponds to $T_0$ — the fully grown, fully overfit tree. Setting ccp_alpha = 0 in fit() reproduces $T_0$.
2. Choosing $\alpha$ is done by cross-validation. The library exposes the path; the engineer picks the elbow.

Cost-complexity pruning is more expensive than pre-pruning (the full tree must be grown before anything is collapsed) but tends to give slightly better trees on small datasets where the bias of pre-pruning is visible.

8. Reading a Tree: Interpretability as the Killer Feature

The reason decision trees keep their place in the ML toolbox despite being dominated in accuracy by gradient-boosted forests and neural networks is interpretability. A fitted tree is a piece of literal logic — a sequence of if/else rules — that a non-ML stakeholder can read aloud. The model does not need an explanation engine, an attention map, or a SHAP plot; the explanation is the model.

8.1 A single decision path

Suppose a tree has been fit on a loan-default dataset and a particular applicant receives the path:

if income_k > 80:                          # first question
    if debt_ratio <= 0.30:                 # second question
        if age_years > 25:                 # third question
            class = "no default"           # leaf
        else:
            class = "default"
    else:
        class = "default"
else:
    class = "default"

A loan officer can read this and disagree with it, trust it, or ask why age_years > 25 appears in the rule — and the answer is "because in the training data, 91% of young, high-income, low-debt applicants defaulted, which seems suspicious and may indicate a confound we should investigate."

8.2 Feature importance

For a fitted tree, the importance of feature $j$ is

where the sum is over every internal node $t$ that splits on feature $j$, $w_t$ is the fraction of training examples that reach node $t$, and $\Delta I(t)$ is the impurity reduction at node $t$. The importances sum to 1 across all features. scikit-learn exposes them as model.feature_importances_ after fitting.

A feature with high importance is one that the tree relied on heavily to separate classes; a feature with importance 0 is one the tree never used. This is a quick way to communicate "which signals does the model think matter" to a stakeholder.

8.3 What trees cannot tell you

Two honest limitations:

1. Single-path reasoning hides interactions. A path reads like a series of independent decisions, but the tree implicitly learns interactions ("high income is good only if debt is low"). When the rules get long, the story gets harder to follow.
2. A single tree is unstable. Small changes in the training data can produce a very different tree, and the rules the tree prints out can shift. A random forest of 500 trees is more accurate but harder to read than any one of them. The interpretability argument applies cleanly to a single tree and only approximately to ensembles.

9. Bias-Variance Connection

The pruning levers are a knob on the bias-variance tradeoff:

• No pruning → low training error, high variance. The tree is a $k$-nearest-neighbour memoriser with one neighbour per leaf.
• Aggressive pruning → high training error, low variance. The tree underfits and approaches a stump that always predicts the majority class.

The decomposition of expected prediction error at a fixed test point $x$ is

where $\sigma^2$ is irreducible noise. A tree's bias decreases with depth (the model can fit more complex patterns) and its variance increases with depth (the model is sensitive to the specific training set). The optimal depth minimises their sum.

Pre-pruning levers (max_depth, min_samples_leaf) increase bias to decrease variance. Cost-complexity pruning is the post-pruning analogue of the same tradeoff: the $\alpha$ knob shifts the operating point along the same curve. Cross-validation estimates the right operating point.

A practical recipe:

1. Start with max_depth = None (full tree), min_samples_leaf = 1. This overfits; expect training accuracy near 100% and validation accuracy noticeably lower.
2. Use validation_curve to plot train and validation accuracy against max_depth in $[1, 2, \ldots, 20]$. Pick the depth where the validation curve peaks and the two curves are closest.
3. Re-run with min_samples_leaf in $[1, 2, 5, 10, 20, 50]$ at the chosen depth. Pick the leaf size that maximises validation score.
4. (Optional) Fit cost_complexity_pruning_path on the training set, then cross-validate over the returned $\alpha$ values.

10. Implementation in scikit-learn

The library makes all of the above one short script. The default uses Gini impurity; switching to entropy is a parameter change.

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

#Load a small dataset; iris has 150 rows, 4 features, 3 classes.
X, y = load_iris(return_X_y=True)
X_tr, X_te, y_tr, y_te = train_test_split(X, y, test_size=0.25, random_state=0)

#Fit a depth-limited tree with a minimum leaf size; no single-leaf memorisation.
clf = DecisionTreeClassifier(
    criterion="gini",        # impurity measure
    max_depth=4,             # pre-pruning: limit the depth
    min_samples_leaf=5,      # pre-pruning: forbid tiny leaves
    random_state=0,
).fit(X_tr, y_tr)

print(f"train accuracy: {clf.score(X_tr, y_tr):.3f}")
print(f"test  accuracy: {clf.score(X_te, y_te):.3f}")

#Read the tree as text; this is the interpretability story.
print(export_text(clf, feature_names=["sepal length", "sepal width",
                                     "petal length", "petal width"]))

Typical output for this script (exact numbers depend on the split):

train accuracy: 0.973
test  accuracy: 0.974

The train and test accuracies are close, which is what pruning is supposed to achieve. With the defaults (max_depth=None, min_samples_leaf=1), training accuracy would climb to 100% and test accuracy would fall.

A second snippet shows feature importance:

import numpy as np
from sklearn.tree import DecisionTreeClassifier
from sklearn.datasets import load_iris

X, y = load_iris(return_X_y=True)
clf = DecisionTreeClassifier(max_depth=3, random_state=0).fit(X, y)

names = np.array(["sepal length", "sepal width", "petal length", "petal width"])
order = np.argsort(clf.feature_importances_)[::-1]
for i in order:
    print(f"{names[i]:>14s}: {clf.feature_importances_[i]:.3f}")

Output (typical):

    petal length: 0.563
     petal width: 0.413
    sepal length: 0.024
     sepal width: 0.000

petal length and petal width together account for ~98% of the impurity reduction — the tree has learned the classical iris story (petal measurements separate the species; sepal measurements add almost nothing).

A third snippet uses the cost-complexity path:

from sklearn.tree import DecisionTreeClassifier

clf = DecisionTreeClassifier(random_state=0)
path = clf.cost_complexity_pruning_path(X_tr, y_tr)
print("alphas:", path.ccp_alphas[:5], "...", path.ccp_alphas[-3:])

The ccp_alphas array contains the pruning path in increasing order; the rightmost $\alpha$ collapses the tree to a stump, the leftmost keeps the full tree. Cross-validation across this array selects the operating point.

Key Takeaways

• A decision tree is built by recursive partitioning: pick the (feature, threshold) with the largest information gain, split, recurse on each child, stop when a pruning rule fires. Termination is guaranteed because every split strictly reduces the number of examples in each non-empty child.
• Impurity is measured by entropy $H = -\sum p_k \log_2 p_k$ (expected bits to encode a class) or Gini $G = 1 - \sum p_k^2$ (probability of misclassification); both range over $[0, 1]$ with $0$ at purity and the maximum at equal class proportions.
• Information gain $\text{IG} = I(P) - \sum_j w_j I(C_j)$ ranks candidate splits; the greedy algorithm picks the maximum at every node. Gini and entropy give the same ranking on the vast majority of real-world splits.
• An unconstrained tree always reaches 100% training accuracy — every leaf can be made pure — but pays for it with high variance on held-out data; this is the canonical overfitting failure mode.
• The four pruning levers are max_depth (cap branch length), min_samples_split (forbid splitting small nodes), min_samples_leaf (force every leaf to summarise several examples), and ccp_alpha (post-pruning via cost-complexity). Cross-validation picks the values.
• The killer feature is interpretability: a single tree is a literal if/else program, feature_importances_ ranks signals by impurity reduction, and a single decision path can be read aloud to a non-ML stakeholder. This advantage disappears once you move to ensembles, where the interpretability argument applies only to the average behaviour rather than to any one tree.