Decision Trees

Recursively split on the feature threshold that most reduces impurity (Gini or entropy).

18 min read1206 wordscore26 viewsupdated 2026-10-07

Definition

A decision tree predicts by asking a sequence of yes/no questions about single features — is xj≤tx_j \le t? or is Outlook = Sunny? — until it reaches a leaf, which outputs the majority class (classification) or the mean target (regression) of the training points that ended there.

At a glance

Task
Classification and regression
Input → output
xx → the prediction stored in the leaf xx falls into
Learns
a feature and threshold per internal node; a value (or class distribution) per leaf
Split criterion
entropy / information gain (ID3, C4.5), Gini impurity (CART), variance / MSE (regression)
Training
greedy, top-down; about O(d nlog⁡n)O(d\,n\log n) per level with pre-sorted features
Prediction
O(depth)O(\text{depth}) comparisons
Hyperparameters
max depth, min samples per split / leaf, criterion, pruning strength α
Assumes
nothing about distributions; decision boundaries are axis-aligned

The problem

Many real decisions look like rules: if income < 30k and debt > 10k, then high risk. A linear model cannot express thresholds and interactions like this without hand-made features. We want a model that discovers such rules from data — and that a person can read and audit.

Anatomy of a tree

Vocabulary

Root node
the first question; it sees the whole training set
Internal node
a question feature ≤\le threshold? (numeric) or feature = value? (categorical)
Branch
one answer to a node's question; it routes a subset of the data to a child
Leaf
a node with no question; it stores the prediction
Depth
number of questions on the longest root-to-leaf path
Rule
the conjunction of answers along one root-to-leaf path

Definition

A pure node contains training points of only one class. Its impurity is 0 by every measure — there is nothing left to separate — so a pure node always becomes a leaf. The whole algorithm is a search for questions that make the children purer than their parent.

Measuring impurity

To pick a question we need a number that says how mixed a node is. Let pcp_c be the fraction of points in node SS that belong to class cc. Three measures are used; all are 0 for a pure node and largest for an even mix.

H(S)=−∑cpclog⁡2pcH(S)=-\sum_{c}p_c\log_2 p_c
H(S)H(S)
entropy of node S, in bits
pcp_c
fraction of class cc in SS (with 0log⁡0=00\log 0 = 0)

Entropy is the average number of bits needed to encode the class of a random point from the node. For two classes it ranges from 0 (pure) to 1 bit (50/50); with KK classes the maximum is log⁡2K\log_2 K. Example: 9 Yes and 5 No gives H=−914log⁡2914−514log⁡2514=0.940H=-\tfrac{9}{14}\log_2\tfrac{9}{14}-\tfrac{5}{14}\log_2\tfrac{5}{14}=0.940 bits.

G(S)=1−∑cpc2=∑cpc(1−pc)G(S)=1-\sum_{c}p_c^2=\sum_c p_c(1-p_c)
G(S)G(S)
Gini impurity of node S

Gini impurity is the probability that two points drawn at random (with replacement) from the node have different classes — equivalently, the error rate if you labelled points randomly according to pp. It ranges from 0 to 1−1/K1-1/K (0.5 for two classes). Same 9/5 node: G=1−(0.6432+0.3572)=0.459G=1-(0.643^2+0.357^2)=0.459.

Misclassification error E(S)=1−max⁡cpcE(S)=1-\max_c p_c is the error of predicting the majority. It is what we ultimately care about, but it is a poor splitting criterion: it is piecewise linear, so many splits that clearly improve purity leave it unchanged.

00.510 · pure Bp = fraction of class A in the nodepure A · 1drag the handle · impurity of a 2-class node
● entropy 0.881
H = −Σ p log₂ p
● gini 0.420
G = 1 − Σ p²
● misclassification 0.300
E = 1 − max p

node: 6 A / 14 B · mixed

fig.Drag p. All three are 0 at the edges (pure nodes) and peak at p = ½. Entropy and Gini are strictly concave, so any split that changes the class mix lowers their weighted average; misclassification error is flat on each side of ½ and often does not move.

Information gain: scoring a split

A split sends the parent's points into children S1,…,SmS_1,\dots,S_m. We score it by how much impurity it removes, weighting each child by its share of the points — a tiny pure child should not count as much as a large one.

IG(S,A)=H(S)−∑v∈values(A)∣Sv∣∣S∣ H(Sv)\text{IG}(S,A)=H(S)-\sum_{v\in\text{values}(A)}\frac{|S_v|}{|S|}\,H(S_v)
AA
the attribute (or threshold test) being split on
SvS_v
subset of SS where AA takes value vv
∣Sv∣∣S∣\tfrac{|S_v|}{|S|}
weight: fraction of the parent's points sent to that child

The second term is the weighted child entropy (the "remainder"). Information gain is how many bits of uncertainty about the label the question removes, on average. With Gini, the same recipe gives the Gini decrease G(S)−∑v∣Sv∣∣S∣G(Sv)G(S)-\sum_v \tfrac{|S_v|}{|S|}G(S_v). The greedy rule is simply: pick the split with the largest gain.

Worked example: should we play tennis?

The classic dataset from Quinlan's ID3 paper: 14 days, four categorical features, and whether tennis was played. 9 days are Yes and 5 are No, so the root entropy is H(S)=0.940H(S)=0.940 bits.

DayOutlookTempHumidityWindPlay
1SunnyHotHighWeakNo
2SunnyHotHighStrongNo
3OvercastHotHighWeakYes
4RainMildHighWeakYes
5RainCoolNormalWeakYes
6RainCoolNormalStrongNo
7OvercastCoolNormalStrongYes
8SunnyMildHighWeakNo
9SunnyCoolNormalWeakYes
10RainMildNormalWeakYes
11SunnyMildNormalStrongYes
12OvercastMildHighStrongYes
13OvercastHotNormalWeakYes
14RainMildHighStrongNo
Play-tennis data (Quinlan, 1986). Highlighted: the 5 Sunny days, which the tree will split again.

Gain of Outlook at the root

  1. 1Split by value: Sunny 2 Yes / 3 No, Overcast 4 Yes / 0 No, Rain 3 Yes / 2 No.
  2. 2Child entropies: H(Sunny)=H(Rain)=−25log⁡225−35log⁡235=0.971H(\text{Sunny})=H(\text{Rain})=-\tfrac25\log_2\tfrac25-\tfrac35\log_2\tfrac35=0.971; H(Overcast)=0H(\text{Overcast})=0 — a pure node.
  3. 3Weighted child entropy: 514(0.971)+414(0)+514(0.971)=0.694\tfrac{5}{14}(0.971)+\tfrac{4}{14}(0)+\tfrac{5}{14}(0.971)=0.694.
  4. 4Information gain: 0.940−0.694=0.2470.940-0.694=0.247 bits.
AttributeChildren (Yes/No)Weighted entropyInformation gainGini decrease
OutlookSunny 2/3 · Overcast 4/0 · Rain 3/20.6940.2470.116
HumidityHigh 3/4 · Normal 6/10.7890.1520.092
WindWeak 6/2 · Strong 3/30.8920.0480.031
TempHot 2/2 · Mild 4/2 · Cool 3/10.9110.0290.019
Every attribute scored at the root. Outlook wins on both criteria; Temperature barely helps.

So the root asks about Outlook. The Overcast branch is pure and becomes a Yes leaf. The other two branches recurse on their own subsets, with Outlook removed from the candidates:

The recursion

Sunny (5 days)
H=0.971H=0.971. Humidity: High 0/3, Normal 2/0 — both children pure, gain =0.971=0.971 (the maximum possible). Temp gains 0.571, Wind 0.020. → split on Humidity.
Rain (5 days)
H=0.971H=0.971. Wind: Weak 3/0, Strong 0/2 — both pure, gain =0.971=0.971. Temp and Humidity each gain only 0.020. → split on Wind.
Result
5 leaves, all pure, using 3 of the 4 features. Temperature is never asked.
▸ decision tree · ID3 on play-tennisstep 1/24
? H=0.94dots = the 14 days · ● Yes ● No
#OutlookTempHumidityWindPlay
1SunnyHotHighWeakNo
2SunnyHotHighStrongNo
3OvercastHotHighWeakYes
4RainMildHighWeakYes
5RainCoolNormalWeakYes
6RainCoolNormalStrongNo
7OvercastCoolNormalStrongYes
8SunnyMildHighWeakNo
9SunnyCoolNormalWeakYes
10RainMildNormalWeakYes
11SunnyMildNormalStrongYes
12OvercastMildHighStrongYes
13OvercastHotNormalWeakYes
14RainMildHighStrongNo
rows in node 14H(node) 0.940nodes 0
  1. 1id3(S, attrs):
  2. 2 if S is pure: return leaf
  3. 3 H(S) ← −Σ p log₂ p
  4. 4 for each attribute A:
  5. 5 gain(A) ← H(S) − Σ |Sᵥ|/|S|·H(Sᵥ)
  6. 6 split on A* = argmax gain
  7. 7 for each value v: id3(Sᵥ, attrs − A*)

Root: 14 days (9 Yes / 5 No). H = −9/14·log₂(9/14) − 5/14·log₂(5/14) = 0.940 bits.

fig.The tree growing from the table. Each dot is one day. At every node, each attribute is tried as a dashed preview split (its table column lights up in the branch colours) and scored by information gain; the winner becomes the node and the dots flow into its branches. Pure branches turn into leaves. Finally a new day — Sunny, Cool, High humidity, Strong wind — walks down to a No leaf.

Read off the rules: if Outlook = Overcast → play; if Sunny and Humidity = Normal → play; if Rain and Wind = Weak → play; otherwise don't. Each one is a root-to-leaf path.

Numeric features: choosing a threshold

For a numeric feature the question is xj≤tx_j\le t. Only thresholds between consecutive sorted values can change the split, so CART sorts the values and tries every midpoint — n−1n-1 candidates per feature — keeping the one with the best gain. With pre-sorting, one feature is scanned in O(n)O(n) by moving points from right to left one at a time and updating class counts.

hours studied · ● passed ● failed · drag the splitleft: x ≤ 2.35right: x > 2.35012345678910information gain at every candidate threshold (midpoints)0.2650.447best: x ≤ 4.40
parent: 9 pass / 7 fail · H = 0.989
left 0 pass / 3 fail · H = 0.000 pure
right 9 pass / 4 fail · H = 0.890
weighted = 3/16·0.000 + 13/16·0.890 = 0.724
gain = 0.989 − 0.724 = 0.265
fig.16 students, hours studied → passed or failed. Drag the split or switch criterion. The best threshold is x ≤ 4.40 (gain 0.447); x ≤ 5.75 makes the right child pure but scores lower (0.438), because its left child stays badly mixed.

The algorithm, step by step

Grow(node)

  1. 1Stop? If the node is pure, has fewer than min_samples_split points, or is at max_depth, make it a leaf: predict the majority class (and store the class proportions).
  2. 2Search. For every feature and every candidate threshold (or category), compute the weighted child impurity.
  3. 3Choose. Keep the split with the largest impurity decrease. If even the best one decreases impurity by less than min_impurity_decrease, make a leaf instead.
  4. 4Recurse on each child with the subset of points routed to it.
▸ decision tree · CARTstep 1/48
?
depth 0nodes 1best score —
  1. 1grow(node):
  2. 2 if pure or depth = max: leaf
  3. 3 for each feature f, threshold t:
  4. 4 score ← weighted Gini(L, R)
  5. 5 split on best (f, t)
  6. 6 grow(L); grow(R)

Root: 40 points (20 A / 20 B), Gini = 1 − (0.50² + 0.50²) = 0.500.

fig.CART on 2-D points: at every node it scores thresholds on both features by weighted Gini and keeps the lowest. Each split carves an axis-aligned rectangle, so the decision regions are boxes. Root: Gini 0.50 → 0.31 after the first split.

This is greedy: each split is the best one now, not necessarily the best for the final tree — finding the optimal tree is NP-hard. Greedy works well in practice, and ensembles fix most of its weaknesses.

Regression trees

For a numeric target, a leaf predicts the mean of its points, and impurity is their variance (mean squared error around that mean). The split criterion becomes variance reduction:

Δ=Var⁡(S)−∣L∣∣S∣Var⁡(L)−∣R∣∣S∣Var⁡(R)\Delta=\operatorname{Var}(S)-\frac{|L|}{|S|}\operatorname{Var}(L)-\frac{|R|}{|S|}\operatorname{Var}(R)
SplitLeft mean (var)Right mean (var)Weighted varReduction
x ≤ 1.55.00 (0.00)14.80 (58.16)48.4713.34
x ≤ 2.55.50 (0.25)17.00 (48.50)32.4229.39
x ≤ 3.55.33 (0.22)21.00 (0.67)0.4461.36
x ≤ 4.59.00 (40.50)21.50 (0.25)27.0834.72
x ≤ 5.511.60 (59.44)21.00 (0.00)49.5312.27
Six points: x=1…6x=1\ldots6, y=5,6,5,20,22,21y = 5, 6, 5, 20, 22, 21. Parent mean 13.17, variance 61.81. Splitting at 3.5 removes 99% of the variance.

The fitted function is a step function: constant within each leaf. More depth means more, narrower steps.

Overfitting and pruning

Left alone, a tree keeps splitting until every leaf is pure — 100% training accuracy, with the last splits fitting noise. Two remedies:

Controlling complexity

Pre-pruning
stop early: max_depth, min_samples_leaf, min_samples_split, max_leaf_nodes, min_impurity_decrease. Cheap, but may stop before a split that would have enabled a great one below it.
Post-pruning
grow the full tree, then cut back subtrees that don't pay for themselves on held-out data.
Rα(T)=R(T)+α ∣T∣R_\alpha(T)=R(T)+\alpha\,|T|
R(T)R(T)
training error (or impurity) of tree T
∣T∣|T|
number of leaves
α\alpha
price per leaf; larger α → smaller tree

Cost-complexity pruning (CART) charges α\alpha per leaf. As α\alpha grows from 0, the subtree whose removal costs the least error per leaf saved is pruned first, giving a nested sequence of ever-smaller trees. Pick α\alpha by cross-validation — scikit-learn exposes it as ccp_alpha.

In code

python
1import numpy as np
2
3def entropy(y):
4 p = np.bincount(y) / len(y)
5 p = p[p > 0]
6 return -(p * np.log2(p)).sum()
7
8def gini(y):
9 p = np.bincount(y) / len(y)
10 return 1 - (p ** 2).sum()
11
12def best_split(X, y, impurity):
13 parent, best = impurity(y), (0.0, None, None) # (gain, feature, threshold)
14 for j in range(X.shape[1]):
15 v = np.unique(X[:, j])
16 for t in (v[:-1] + v[1:]) / 2: # midpoints
17 L = X[:, j] <= t
18 child = (L.sum() * impurity(y[L]) + (~L).sum() * impurity(y[~L])) / len(y)
19 if parent - child > best[0]:
20 best = (parent - child, j, t)
21 return best
22
23def grow(X, y, impurity=entropy, depth=0, max_depth=3, min_leaf=1):
24 gain, j, t = best_split(X, y, impurity)
25 if depth == max_depth or impurity(y) == 0 or j is None or len(y) < 2 * min_leaf:
26 return {"leaf": np.bincount(y).argmax(), "n": len(y)}
27 L = X[:, j] <= t
28 return {"feature": j, "threshold": t, "gain": gain,
29 "left": grow(X[L], y[L], impurity, depth + 1, max_depth, min_leaf),
30 "right": grow(X[~L], y[~L], impurity, depth + 1, max_depth, min_leaf)}
31
32def predict(node, x):
33 while "leaf" not in node:
34 node = node["left"] if x[node["feature"]] <= node["threshold"] else node["right"]
35 return node["leaf"]
From scratch: both criteria, numeric features, majority-class leaves.
python
1import pandas as pd
2from sklearn.tree import DecisionTreeClassifier, export_text
3
4df = pd.DataFrame({
5 "Outlook": "Sunny Sunny Overcast Rain Rain Rain Overcast Sunny Sunny Rain Sunny Overcast Overcast Rain".split(),
6 "Temp": "Hot Hot Hot Mild Cool Cool Cool Mild Cool Mild Mild Mild Hot Mild".split(),
7 "Humidity": "High High High High Normal Normal Normal High Normal Normal Normal High Normal High".split(),
8 "Wind": "Weak Strong Weak Weak Weak Strong Strong Weak Weak Weak Strong Strong Weak Strong".split(),
9 "Play": "No No Yes Yes Yes No Yes No Yes Yes Yes Yes Yes No".split(),
10})
11X = pd.get_dummies(df.drop(columns="Play"))
12tree = DecisionTreeClassifier(criterion="entropy", random_state=0).fit(X, df.Play)
13print(export_text(tree, feature_names=list(X.columns)))
14
15# Choosing the pruning strength on real data:
16# path = DecisionTreeClassifier().cost_complexity_pruning_path(X_train, y_train)
17# then cross-validate over path.ccp_alphas
The play-tennis tree with scikit-learn (one-hot features, entropy criterion) — and printed rules.

Use when

  • +Every prediction must be explainable — the path is a readable rule.
  • +Mixed numeric and categorical features; no scaling needed; thresholds and interactions found automatically.
  • +You need a fast baseline, or the building block for random forests and gradient boosting.

Avoid when

  • −You need accuracy from a single model: a deep tree overfits, a shallow one underfits.
  • −Stability matters: a small change in the data can produce a completely different tree.
  • −The true boundary is smooth or diagonal: axis-aligned splits approximate it with a staircase.
  • −You need to extrapolate: a regression tree can never predict outside the range of its training targets.

Where it's used

Medical triage & credit policy

Rules that must be audited and explained to regulators or patients.

Feature exploration

The first few splits reveal which variables matter most, and at which thresholds.

Business rules

Turn historical decisions into explicit if-then logic.

Inside ensembles

Random forests, XGBoost, LightGBM and CatBoost are all built from trees.

Check yourself

A node holds 8 points, 4 of each class. Its entropy and Gini impurity are…

Check yourself

A parent has entropy 1.0. A split sends 6 points to a pure child and 2 points to a 50/50 child. The information gain is…

Check yourself

Why does C4.5 use the gain ratio instead of raw information gain?

Check yourself

Which preprocessing does a decision tree require?

Remember

  • ✓Impurity measures how mixed a node is: entropy (bits), Gini, or variance for regression. A pure node has impurity 0 and becomes a leaf.
  • ✓Information gain = parent impurity − size-weighted child impurity; greedily split on the largest gain.
  • ✓Weighted child entropy equals the tree's training cross-entropy, so maximizing gain minimizes log-loss.
  • ✓Numeric features: try midpoints between sorted values. Categorical: one branch per value (ID3) or binary groupings (CART).
  • ✓Limit depth / leaf size or prune with cost-complexity α; use ensembles when you need accuracy.
← back to ML Algorithms roadmap