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 (MSE) of the target in the node, 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

Class materials

Quiz