Machine Learning · Module 9 of 26 · 10 concepts · about 19 min

Decision Trees

A model that is a nested sequence of yes/no questions — how each question gets chosen, and why an unpruned tree memorises its training set perfectly.

At work: Models made of yes/no questions: easy to explain to a loan officer, and the building block of today's strongest models for tables.

The tree model: nodes, splits and leaves

What it is

A decision tree is a binary tree in which every internal node holds a test of the form feature <= threshold, and every leaf holds a prediction: a class distribution for classification, a mean for regression. Predicting means walking from the root to a leaf, answering one test per level.

Why it matters

It is the only mainstream model whose full decision procedure can be read aloud, which makes it the natural baseline whenever someone has to explain a prediction. It is also the base learner for random forests and gradient boosting, so this structure is the atom of the next two modules.

In the real world: A loan decision as a flowchart: income over ₹50,000? Existing loans? Missed payments? Each path ends in approve or decline.

Visual example

DecisionTreeClassifier(max_depth=2)

One tree, written as the table of its nodes. Prediction is a walk down the go left if true column until a leaf.

Root

(every row starts here)

Leaf predictions

(the class proportion in that leaf)

tree_ — 5 nodes

	test	n	left	prediction
0	radius <= 16.8	455	1 / 4	-
1	concave <= 0.14	289	2 / 3	-
2	leaf	271	-	benign (0.99)
3	leaf	18	-	malignant (0.72)
4	leaf	166	-	malignant (0.95)

radius=15.0, concave=0.20

node 0 true -> node 1 false -> node 3

predict_proba -> [0.28, 0.72], from 18 training rows

Where node 3's probability comes from

18 training rows reached node 3: 5 benign, 13 malignant

predict_proba = 13/18 = 0.72 — literally the leaf's class proportion

n = 18 out of 455, so this probability rests on 4% of the data

Why this matters

A leaf's prediction is just a count of the training rows that fell into it. That is why a deep tree's confident probabilities are untrustworthy: its leaves hold two or three rows each.

Common misconception

Wrong idea: predict_proba from a tree is a calibrated probability.

Correct idea: it is the class fraction of one leaf's training rows. A pure leaf reports 1.00 whether it held 300 rows or 3.

1Start at the rootNode 0 tests one feature against one threshold.
2Answer and descendTrue goes left, false goes right; one test per level.
3Stop at a leafThe leaf's stored training distribution is the prediction.

from sklearn.tree import DecisionTreeClassifier, export_text

tree = DecisionTreeClassifier(max_depth=3, random_state=0).fit(X_train, y_train)
print(export_text(tree, feature_names=list(feature_names)))
# |--- worst radius <= 16.80
# |   |--- worst concave points <= 0.14
# |   |   |--- class: 1
# |   |--- class: 0

tree.tree_.node_count          # how many nodes it actually grew
tree.get_depth(), tree.get_n_leaves()

Reading a tree's printed rules as an explanation of the *problem* rather than of the *fit*. Two trees grown on 95% overlapping data can pick entirely different root features and produce near-identical accuracy — the rules are one of many equally good descriptions, not the discovered truth.

Gini impurity and entropy

What it is

Both measure how mixed a node's labels are. For a binary node with positive fraction p, Gini is 2p(1-p) and entropy is -p log2(p) - (1-p) log2(1-p). Both are 0 at a pure node (p = 0 or p = 1) and maximal at p = 0.5.

Why it matters

The split search needs a single number for 'how bad is this node', and this is it. Every split a tree makes is chosen to reduce this number as much as possible, so the impurity function *is* the tree's objective.

In the real world: How a tree decides that “missed payments” separates good and bad borrowers better than “city” does.

Visual example

Split criteria

Gini and entropy as functions of the class-1 fraction p. Same zeros, same peak at 0.5, different heights — which is why they rarely disagree.

EntropyGini — 2p(1-p)Misclassification rate

A node with 30 rows, 24 of class 1

p = 24/30 = 0.8

gini = 2 x 0.8 x 0.2 = 0.32

entropy = -(0.8 log2 0.8 + 0.2 log2 0.2) = 0.722

misclassification = 1 - 0.8 = 0.2 — flat-sided, so it cannot rank splits well

Why this matters

The dashed misclassification curve is straight-sided, so two candidate splits often score identically on it and the search has nothing to choose between them. Gini and entropy are strictly concave, so they always prefer the purer split — that concavity is exactly why they are used instead.

Common misconception

Wrong idea: entropy and Gini are different objectives that produce different trees.

Correct idea: they are two smooth concave curves with the same shape and the same zeros. Swapping one for the other typically moves accuracy by a fraction of a point.

import numpy as np

def gini(p):
    return 2 * p * (1 - p)

def entropy(p):
    p = np.clip(p, 1e-12, 1 - 1e-12)
    return -(p * np.log2(p) + (1 - p) * np.log2(1 - p))

for p in [0.0, 0.1, 0.3, 0.5]:
    print(p, round(gini(p), 3), round(entropy(p), 3))
# 0.5 -> gini 0.5, entropy 1.0 (both at their maximum)

DecisionTreeClassifier(criterion="entropy")   # the alternative to the default 'gini'

Expecting criterion="entropy" to change anything much. The two curves have the same shape and the same zeros, so they agree on the great majority of splits; entropy is slightly more sensitive near the pure ends and marginally slower to compute. Depth and leaf-size limits change a tree's behaviour by orders of magnitude more than the criterion does.

Practise it: The Best Single-Feature Split, by Gini

Information gain and the greedy split search

What it is

The gain of a split is the parent's impurity minus the *weighted* average impurity of the two children: gain = I(parent) - (n_L/n) I(L) - (n_R/n) I(R). At every node the tree evaluates every feature at every candidate threshold and takes the split with the largest gain.

Why it matters

This is the whole learning algorithm. Understanding it as a local, one-step-at-a-time maximisation explains both why fitting a tree is fast and why the resulting tree is not the best possible tree — the greedy choice at the root is never revisited.

In the real world: The tree picks the single most useful question first, like which plan a customer is on, when predicting churn.

Visual example

Information gain

One split, scored: the parent's impurity minus the row-weighted impurity of the two children it produces.

parent node — 455 rows

class 0	class 1	p	gini
169	286	0.629	0.467

best split at the root: radius <= 16.8

children after the split

	class 0	class 1	p	gini
left	18	271	0.938	0.117
right	151	15	0.09	0.164

The gain, arithmetic in full

parent gini = 2 x 0.629 x 0.371 = 0.467

weights: 289/455 = 0.635 left, 166/455 = 0.365 right

weighted child gini = 0.635 x 0.117 + 0.365 x 0.164 = 0.134

gain = 0.467 - 0.134 = 0.333 — the largest of every (feature, threshold) pair tried

Why this matters

The weighting is the part people drop. A split that carves off 3 pure rows and leaves 452 mixed ones has tiny weighted gain, which is precisely why the criterion does not chase such splits.

Common misconception

Wrong idea: the best split is the one whose children are purest.

Correct idea: it is the one with the best size-weighted purity. A perfectly pure child holding 1% of the rows barely moves the objective.

1Sort per featureCandidate thresholds are the midpoints between consecutive distinct values.
2Score every candidateCompute the weighted child impurity for each, in one pass per feature.
3Take the best and recurseNever reconsidered: the choice is greedy and final.

import numpy as np

y_node = np.array([1]*24 + [0]*6)           # 30 rows, p = 0.8
left, right = y_node[:18], y_node[18:]      # a candidate split: 18 | 12

def gini(y):
    p = y.mean()
    return 2 * p * (1 - p)

n = len(y_node)
gain = gini(y_node) - (len(left)/n) * gini(left) - (len(right)/n) * gini(right)
round(gain, 4)                              # 0.12

tree = DecisionTreeClassifier(max_depth=1).fit(X_train, y_train)
tree.tree_.impurity[:3]                     # parent, then the two children

Believing a greedy tree finds the optimal set of rules. It cannot: a pair of features that is only informative *jointly* (classic XOR) yields zero gain for either feature alone, so a depth-1 search finds nothing useful and may never recover. Finding the optimal tree is NP-hard, which is why ensembles exist.

Regression trees: variance reduction

What it is

The same algorithm with the impurity swapped. A node's impurity is the variance (mean squared error) of its target values, a leaf predicts the mean of its rows, and a split is scored by how much weighted variance it removes. criterion="squared_error" is the default; "absolute_error" uses the median instead and is robust but much slower.

Why it matters

It makes the tree a general-purpose model rather than a classifier trick, and it is the exact object gradient boosting fits to residuals in the next module but one — every GBM, even for classification, is a sum of regression trees.

In the real world: Predicting delivery time by splitting on distance, then time of day, then weather.

Visual example

DecisionTreeRegressor

A depth-3 regression tree fitting a sine wave: a staircase of leaf means, flat outside the training range.

True f(x) = sin(x)Tree prediction

One leaf, one number

leaf covering 3.6 <= x < 5.6 holds the rows near the trough

its prediction is their mean y = -0.86, for every x in that interval

8 leaves at depth 3, so the whole function is 8 horizontal segments

Why this matters

The staircase is not a drawing convention — it is exactly what the model is. Every 'smooth' behaviour a tree ensemble shows later comes from averaging many differently-placed staircases.

Common misconception

Wrong idea: a deeper tree would eventually fit the curve smoothly and keep going past x = 10.

Correct idea: depth adds steps, never slope. Beyond the training range the last leaf's mean is the answer for all time.

from sklearn.tree import DecisionTreeRegressor
from sklearn.model_selection import cross_val_score

reg = DecisionTreeRegressor(max_depth=4, min_samples_leaf=20, random_state=0)
cross_val_score(reg, X, y, cv=5, scoring="neg_mean_absolute_error").mean()

reg.fit(X, y)
np.unique(reg.predict(X)).size    # at most n_leaves distinct values — it is piecewise constant

Expecting a regression tree to extrapolate. Every prediction is the mean of some leaf's training rows, so the model is a staircase bounded by the training target range: feed it an x beyond anything it saw and it returns the nearest edge leaf's mean, flat forever. A linear model extrapolates (sometimes wrongly); a tree simply cannot.

Depth, overfitting and the validation curve

What it is

Depth is the tree's capacity knob. A depth-1 stump underfits badly; an unconstrained tree grows until every leaf is pure, which for most datasets means 100% training accuracy and leaves holding one or two rows.

Why it matters

Trees are the clearest demonstration in the whole syllabus of the bias-variance decomposition in action, because a single integer moves you smoothly from one extreme to the other and you can watch the two error curves separate.

In the real world: A tree that asks 30 questions memorises individual customers; one that asks 5 generalises to new ones.

Visual example

max_depth

Training accuracy climbs to a perfect 1.000 and stays there. Validation accuracy peaks at depth 4 and then decays — that gap is variance.

Training accuracyValidation accuracy

Reading the two curves

depth 1: train 0.879, val 0.872 — gap 0.007. Both low: bias.

depth 4: train 0.978, val 0.935 — the best validation score

depth 12: train 1.000, val 0.912 — gap 0.088. Train is perfect and useless.

the model to ship is the depth-4 one, not the depth-12 one

Why this matters

The two curves only ever answer different questions. Training accuracy tells you whether the model *can* fit these rows; only the validation curve tells you whether that fit means anything, and it turns downward while the other is still improving.

Common misconception

Wrong idea: a tree that reaches 100% training accuracy has learnt the problem.

Correct idea: it has learnt these rows. Perfect training accuracy is the signature of leaves holding one row each, and is a warning, not an achievement.

1GrowEach extra level lets the tree carve finer regions of feature space.
2DivergePast depth 4 the extra regions fit noise, so only training accuracy benefits.
3Pick the peakChoose depth by the validation curve's maximum, never by the training curve.

from sklearn.model_selection import validation_curve

depths = [1, 2, 3, 4, 6, 8, 12, 16, None]
train, val = validation_curve(
    DecisionTreeClassifier(random_state=0), X, y,
    param_name="max_depth", param_range=depths[:-1],
    cv=5, scoring="accuracy", n_jobs=-1,
)
train.mean(axis=1).round(3)   # climbs to 1.000
val.mean(axis=1).round(3)     # peaks, then falls back

Tuning max_depth and stopping there. min_samples_leaf is usually the more effective control, because it limits capacity where the overfitting actually happens — in the tiny leaves at the bottom — rather than uniformly across the tree. A max_depth=12 tree with min_samples_leaf=20 is a very different and usually much better model than max_depth=12 alone.

Pruning: pre-pruning vs cost-complexity pruning

What it is

Pre-pruning stops growth early with max_depth, min_samples_split, min_samples_leaf, max_leaf_nodes or min_impurity_decrease. Post-pruning grows the tree fully, then removes subtrees: ccp_alpha penalises the tree's leaf count, minimising total_impurity + alpha * n_leaves.

Why it matters

Pre-pruning is greedy and can stop too early — it will refuse a split with low immediate gain even when that split enables an excellent one below it. Post-pruning sees the whole tree before deciding, so it can keep exactly those subtrees that paid off.

In the real world: Trimming a credit tree to a few clear rules that a loan officer can apply and explain.

Visual example

Cost-complexity pruning

Post-pruning collapses subtrees whose purity gain is worth less than alpha per leaf it costs.

fully grown tree

leaves	depth	train acc	val acc
43	7	1	0.912

ccp_alpha = 0.0043

pruned tree

leaves	depth	train acc	val acc
9	4	0.974	0.942

Should this subtree survive?

a subtree with 5 leaves reduces weighted impurity by 0.011 in total

collapsing it to one leaf saves 4 leaves, so the penalty saved is 4 x 0.0043 = 0.0172

0.0172 > 0.011, so the subtree is removed

34 leaves go, training accuracy falls 2.6 points, validation rises 3.0

Why this matters

The objective being minimised is impurity *plus* a per-leaf price. Raising alpha raises the price, so the whole nested sequence of pruned trees — from the full tree to the bare root — is generated by one scalar you can cross-validate over.

Common misconception

Wrong idea: pruning removes the nodes that were 'wrong'.

Correct idea: it removes the nodes that were not worth their complexity. Every pruned split had positive gain; it simply had less gain than alpha charges for a leaf.

path = DecisionTreeClassifier(random_state=0).cost_complexity_pruning_path(X_train, y_train)
alphas = path.ccp_alphas[:-1]            # drop the alpha that prunes to the root

from sklearn.model_selection import GridSearchCV
search = GridSearchCV(DecisionTreeClassifier(random_state=0),
                      {"ccp_alpha": alphas}, cv=5, scoring="roc_auc", n_jobs=-1)
search.fit(X_train, y_train)
search.best_params_                      # e.g. {'ccp_alpha': 0.0043}
search.best_estimator_.get_n_leaves()    # 9, down from 43 unpruned

Computing the ccp_alphas path on the whole dataset and then cross-validating over it. The path is fitted from the data, so it is a leak of exactly the kind the Pipeline concept warned about — compute the path inside each fold, or accept that the chosen alpha is mildly optimistic.

Feature importance from a single tree

What it is

tree.feature_importances_ is mean decrease in impurity: for each feature, the total weighted impurity reduction of every split that used it, normalised to sum to 1. A feature never split on gets exactly 0.

Why it matters

It is the cheapest available answer to 'which columns did this model actually use', and because it falls out of the fitting arithmetic it costs nothing to compute.

In the real world: Quickly seeing that “days since last login” drives the churn tree more than “age”.

Visual example

feature_importances_

Mean decrease in impurity, per feature. Note the two correlated radius columns: one takes nearly all the credit.

imp.sum()

always exactly 1.0

imp.sort_values(ascending=False)

feature	splits	impurity drop	importance
worst radius	3	0.248	0.612
worst concave pts	2	0.091	0.225
worst texture	2	0.045	0.111
mean radius	0	0	0
smoothness error	0	0	0

imp['mean radius']

0.0 — but corr(mean, worst radius) = 0.97

Zero importance means unused, not uninformative

How 0.612 is computed

worst radius was split on at nodes 0, 5 and 11

sum of (n_node / n_total) x impurity decrease over those three = 0.248

the same total over all features = 0.405

0.248 / 0.405 = 0.612

Why this matters

Importance is a report on what this fitted tree did, not a measurement of the features. Refit on a bootstrap sample and the ranking can reorder substantially — which is the problem the next module's permutation importance is built to reduce.

Common misconception

Wrong idea: feature importance measures how predictive each feature is.

Correct idea: it measures how much impurity this particular greedy tree removed using it. Correlated features cannibalise each other's scores.

import pandas as pd

imp = pd.Series(tree.feature_importances_, index=feature_names)
imp.sort_values(ascending=False).head(5)
imp.sum()                     # 1.0, always
(imp == 0).sum()              # how many columns the tree ignored entirely

Reading a zero as 'irrelevant'. Two strongly correlated features split the credit arbitrarily: the greedy search picks one at the root and the other then has no gain left to claim, so it scores 0 despite being equally predictive. Drop it on that evidence and accuracy is unchanged — but so would dropping the other have been.

Practise it: Permutation Importance, Averaged Honestly

Axis-aligned splits: what a tree cannot represent

What it is

Every test has the form feature <= threshold, so every decision boundary a tree can draw is made of segments perpendicular to a feature axis. A boundary that runs diagonally — x1 + x2 <= c — has to be approximated by a staircase of many splits.

Why it matters

It explains the single most common disappointment with trees: a problem a two-parameter logistic regression solves perfectly needs a depth-8 tree and still leaks near the boundary. It also explains why trees are completely indifferent to feature scaling but very sensitive to feature *rotation*.

In the real world: A tree struggles with “spend relative to income” unless you give it that ratio as its own column.

Visual example

Axis-aligned splits

Two classes separated by x1 + x2 = 0. A tree can only cut along the axes, so it approximates the diagonal with a staircase.

Class 0Class 1True boundary x1 + x2 = 0Depth-3 tree boundary

Cost of the approximation

depth 3 -> 8 leaves -> 4 steps; each step leaves two wedges of error

logistic regression: 2 parameters, ~0.995 accuracy

depth-3 tree: 7 nodes, ~0.91 — it needs depth 8+ to close the gap

feature x1 + x2 added by hand: a depth-1 stump reaches ~1.0

Why this matters

Every extra step halves the remaining wedge, so the tree's error decays but never vanishes — you are paying exponentially many splits to imitate one addition. This is the strongest argument in the syllabus for engineering a feature rather than adding capacity.

Common misconception

Wrong idea: trees handle any boundary shape, given enough depth.

Correct idea: they approximate any shape with axis-parallel steps. A diagonal is the worst case, and no amount of feature scaling changes it, because a tree is invariant to monotone rescaling.

rng = np.random.default_rng(0)
X = rng.uniform(-3, 3, size=(600, 2))
y = (X[:, 0] + X[:, 1] > 0).astype(int)    # a perfect diagonal boundary

from sklearn.linear_model import LogisticRegression
cross_val_score(LogisticRegression(), X, y, cv=5).mean()            # ~0.995
cross_val_score(DecisionTreeClassifier(max_depth=3), X, y, cv=5).mean()   # ~0.91

# One rotated feature, and the tree is perfect again:
X_rot = np.c_[X[:, 0] + X[:, 1], X[:, 0] - X[:, 1]]
cross_val_score(DecisionTreeClassifier(max_depth=1), X_rot, y, cv=5).mean()  # ~1.0

Concluding the problem is nonlinear because the tree did badly on it. It is the opposite: the problem is *linear in a rotated basis*, which is the one easy case trees handle worst. Scaling will not help — a tree is invariant to monotone rescaling of any single feature — but a rotation or a sum feature will fix it completely.

What trees do and do not need from your preprocessing

What it is

A tree compares one feature to a threshold, so any monotone transform of a single feature — scaling, standardising, log, rank — leaves the tree identical. It needs no scaling, tolerates outliers in the features well, and handles mixed feature magnitudes natively. It still needs categorical encoding, and scikit-learn's implementation still needs missing values dealt with.

Why it matters

Half the preprocessing that is mandatory for KNN, SVM and regularised linear models is pure wasted effort for a tree. Knowing which half saves you building a pipeline that cannot help.

In the real world: Trees don't need scaled data, which makes them quick to try on messy business tables.

from sklearn.preprocessing import StandardScaler

a = DecisionTreeClassifier(random_state=0).fit(X_train, y_train)
b = DecisionTreeClassifier(random_state=0).fit(StandardScaler().fit_transform(X_train), y_train)
(a.predict(X_test) == b.predict(StandardScaler().fit(X_train).transform(X_test))).all()
# True — scaling changed nothing at all

# Categoricals still need encoding; HistGradientBoosting can take them natively:
from sklearn.ensemble import HistGradientBoostingClassifier
HistGradientBoostingClassifier(categorical_features="from_dtype")

Label-encoding a nominal category as 0..k-1 and feeding it to a tree. The threshold test now implies an order that does not exist, so city <= 3.5 groups cities by the arbitrary integers your encoder assigned. It often still scores acceptably, which is what makes it hard to notice — one-hot, target-encode, or use an implementation with real categorical support.

Practise it: A Pipeline That Does Not Leak, The Best Single-Feature Split, by Gini

Instability: why one tree is rarely the final answer

What it is

A single tree is a high-variance model. Resample the training rows slightly — a different CV fold, a bootstrap, one added row near a threshold — and the root split can change, which rewrites every node below it.

Why it matters

This is the exact property the next two modules are built on. Bagging averages many high-variance, low-bias trees to cancel their variance; boosting instead builds many high-bias shallow trees to cancel their bias. Neither makes sense until you accept that one tree's structure is largely noise.

In the real world: Retrain a single tree on next month's data and its rules may change completely, confusing the teams that rely on them.

from sklearn.utils import resample

roots = []
for seed in range(10):
    Xb, yb = resample(X_train, y_train, random_state=seed)
    t = DecisionTreeClassifier(max_depth=4, random_state=0).fit(Xb, yb)
    roots.append(feature_names[t.tree_.feature[0]])

set(roots)     # typically 3-4 different features chosen as the root split

Presenting one tree's rules to a stakeholder as 'the drivers of churn'. Refit on next month's data and the rules will look different while accuracy stays the same. If the explanation has to be stable, fit the tree many times and report what survives — or use an inherently stabler importance measure.