Decision Trees

A decision tree classifies by asking a sequence of simple questions — petal length ≤ 2.45? income > 5,000? — walking from root to leaf. Formalized in the 1980s (CART: Breiman et al., 1984; ID3/C4.5: Quinlan, 1986/1993), trees read like flowcharts a domain expert can audit, handle mixed feature types without scaling, and are the building block of the ensembles (random forests, gradient boosting) that dominate tabular ML today.

A depth-2 tree on iris: two thresholds on petal measurements already separate the species almost perfectly — and you can read why directly from the picture.

How a tree is grown

Trees are built greedily, top-down (CART): at each node, try every feature and every threshold, and pick the split that makes the two children purest; recurse until a stopping rule fires.

Measuring impurity

For a node with class proportions \(p_1, \dots, p_k\):

Gini impurity (CART's default) — the probability that two random draws from the node disagree:

Entropy (ID3 family) — information-theoretic uncertainty:

Both are 0 for a pure node and maximal for a 50/50 mix; in practice they choose nearly identical splits (Gini is slightly cheaper — no logarithm).

A candidate split \(S\) of node \(N\) into children \(L, R\) is scored by impurity decrease (with entropy, called information gain):

For regression trees, impurity is simply the variance of the target in the node — the mean squared error (MSE) — and each leaf predicts the mean of its samples.

GROW(node):
    if stopping rule (depth, min samples, purity): make leaf
    for each feature j, each threshold t:
        score split x_j ≤ t by impurity decrease Δ
    apply best split; GROW(left); GROW(right)

Greedy means no lookahead: the tree never reconsiders a split that would pay off two levels later (XOR-like patterns can defeat it). Ensembles compensate.

Overfitting: the tree's chronic disease

Grown without limits, a tree keeps splitting until leaves are pure — happily isolating every noisy point in its own leaf. Trees are low-bias, high-variance learners: tiny changes in data can produce a completely different tree.

The unlimited tree (left) carves rectangular islands around individual noise points; max_depth=4 (right) captures the real structure. Note the axis-aligned, "staircase" boundaries — trees split one feature at a time.

Controlling complexity (all are bias–variance knobs for cross-validation):

• Pre-pruning: max_depth, min_samples_split, min_samples_leaf, min_impurity_decrease;
• Post-pruning: grow fully, then cut back branches that don't earn their complexity — cost-complexity pruning minimizes \(\text{error} + \alpha \cdot \#\text{leaves}\) (ccp_alpha), the tree version of regularization.

from sklearn.tree import DecisionTreeClassifier

tree = DecisionTreeClassifier(max_depth=4, min_samples_leaf=5, random_state=0)
tree.fit(X_train, y_train)          # no scaling needed!
tree.feature_importances_           # impurity-based importances (sum to 1)

Practical profile

Impurity, on one node

Gini for a node is \(1 - \sum_c p_c^2\) — the probability that two points drawn from it disagree. Take a node with 6 of class A and 4 of class B:

Now score two candidate splits. The rule is the weighted impurity of the children:

Split 2 divides the node perfectly in half and achieves nothing: both children have the same class mix as the parent, so the gain is exactly zero. A split is only worth making when it changes the proportions, which is the whole content of the greedy criterion.

CART tries every feature and every threshold, scores each one this way, and keeps the best. Then it recurses. Watch it happen:

Class materials

References

• Quinlan, J. R. "Induction of Decision Trees." Machine Learning 1 (1986). DOI

The full course bibliography is on the references page.

Quiz