A decision tree is a flowchart that writes itself: at every step it picks the feature and threshold that make the child regions purer, measured by Gini or entropy. Many such trees, each a little different, vote into a random forest.
Every internal node tests one feature against one threshold; every leaf predicts. Choosing the branch at each node traces a path from the root to a decision — and cuts the feature space into rectangles along the way.
age < 30? → income > 50k? → approve02 / SCORE THE MIX
Impurity is the thing splits reduce.
Gini = 1 − Σ p² answers “how often would a random label guess be wrong here?”; entropy = −Σ p log2 p measures disorder in bits. Both are 0 at a pure node and maximum at an even mix.
6 cats / 4 dogs: Gini 0.48 · entropy 0.97103 / MANY TREES, ONE VOTE
A forest averages decorrelated trees.
Bagging gives each tree a bootstrap sample; feature randomization gives each split a random subset of columns. The trees disagree in different places, so their majority vote cancels much of the noise a single deep tree would memorize.
bootstrap ≈ 63% · features √p · majority vote
MENTAL MODEL IN ONE SENTENCE
A tree is a flowchart that chooses its own questions: score how mixed each candidate split’s children would be, take the question that reduces the mix the most, and repeat — while a forest is many such flowcharts, each trained on a slightly different world, voting.
By the end you will be able to compute Gini and entropy by hand, score a candidate split with information gain, pick stopping rules instead of letting a tree memorize the noise, and explain exactly why bagging plus feature subsampling makes a forest work.
01
ASK YES-OR-NO
A tree is a flowchart that learns its own questions.
Rows are samples, columns are features, one column is the target. Instead of fitting a curve, a tree keeps asking simple yes/no questions until the answers point at a prediction.
Imagine a spreadsheet of loan applications. Each row is an applicant; the columns are age, income, credit score. A decision tree learns rules like “age < 30? if yes, income > 50k? if yes, approve”. Every question tests one feature against one threshold. The end of each path is a leaf, and the leaf’s prediction is whatever class was most common among the training rows that landed there.
To classify a new row you start at the root and follow the answers down — one comparison per level. Along the way the questions divide the feature space into rectangles, one rectangle per leaf. Constraints like x ≤ 2.3 and y > −1 stack up into a box, which is why tree boundaries are always axis-aligned staircases.
A learned tree for loan approval. Internal nodes are questions about one feature; leaves are predictions. Follow the answers to classify a new applicant.
So where do the questions come from? Nobody hands the tree a list. It tries every feature and every threshold, scores how cleanly each one separates the classes, and keeps the best. Repeat inside each child, and the flowchart assembles itself.
02
HOW MIXED IS IT?
Purity is a number. Put a score on the mix.
Before a tree can choose a question, it needs to say how mixed a set of labels is. Two scores do the job: Gini impurity and entropy. Lower is better, and pure is zero.
Take a node holding 10 animals: 6 cats and 4 dogs. If you had to label a random animal using only those proportions, you would be wrong fairly often. Gini impurity is exactly that expected error rate:
Gini(S) = 1 − Σ_k p_k²
plain English: 1 minus the sum of squared class proportions —
the chance a randomly chosen sample would be mislabeled
by a coin flip weighted by the node's own class mix.
Both numbers are positive — the node is mixed — and both would be exactly 0 if all ten animals were cats. That is the property the tree exploits: a split is good when its children score lower than their parent.
Entropy comes from information theory and measures the same disorder in bits. A fair coin is 1 bit; a pure node carries 0 bits of uncertainty:
Entropy(S) = − Σ_k p_k · log2(p_k)
plain English: the average surprise, in bits, when you learn a
random sample's class. Fair coin = 1 bit, pure = 0 bits.
The impurity console
Type any class mix and read both impurity scores computed from your counts — every substitution is shown.
n = 10
p = (0.60, 0.40, 0.00)
Gini = 1 − (0.60² + 0.40²)
= 1 − (0.360 + 0.160)
= 0.4800
Entropy = −(0.60·log2 0.60 + 0.40·log2 0.40)
= −(-0.4422 + -0.5288)
= 0.9710 bits
log2 used above: log2 0.60 = -0.7370, log2 0.40 = -1.3219
Both scores are 0 exactly when one class owns
the node, and maximal for an even mix.
Gini is an expected misclassification rate; entropy is measured in bits of information. The tree only ever compares scores of the same kind, so either one works — the reference implementation offers both.
Class mix
Gini
Entropy (bits)
Pure: A A A A
0.0000
0.0000
Balanced: A A B B
0.5000
1.0000
Imbalanced: A A A B
0.3750
0.8113
Three classes: A A B C
0.6250
1.5000
Uniform 4-class
0.7500
2.0000
Values from the lesson’s reference implementation. Notice both scores hit 0 only at a pure node, and both are largest at an even mix — four classes even need 2 bits.
Quick check
A node contains 8 dogs and 2 cats. What is its Gini impurity?
03
THE BEST QUESTION
Score every split. Keep the one that helps most.
Information gain is the drop in impurity a question buys you, measured on the children and weighted by their sizes. The greedy tree takes the biggest drop at every node.
A node’s impurity tells you how mixed it is. A split sends the samples left or right, and the children are usually purer than the parent. Information gain is how much purer, on average:
IG(S, split) = Impurity(S) − [ (n_L/n)·Impurity(S_L) + (n_R/n)·Impurity(S_R) ]
plain English: the parent's mix minus the mix its two children
have on average, with each child weighted by its share of
the samples. Bigger gain = the question separated the classes
more cleanly.
Worked check: three questions, one winner (Gini and entropy)
Feature B isolates the cats in one clean child and splits a 50/50 mix of dogs and birds in the other; both criteria crown it. Note how the weighted average means a pure child only counts in proportion to its size — making one sample happy is worth almost nothing.
The split picker
Slide a cut across one feature and watch the gain change. The chosen line is solid; the best cut of all is dashed. All numbers come from the visible counts.
On the wavy bands a single horizontal cut already reaches gain ≈ 0.38; on the disk the best cut barely clears 0.06. When one question cannot separate the classes, the tree must ask more.
Both children landed on the same impurity by coincidence of these counts — the tree does not care. It only compares the weighted result with the parent, and 0.12 of Gini bought here means the split is kept if no better question exists.
Quick check
Parent: 10 points, 6 of class A and 4 of class B (Gini 0.48). Which candidate split has the larger information gain?
04
GROW, THEN STOP
The same question, asked again inside each child.
Splitting is recursive: pick the best question for the current set, cut it in two, then repeat inside each child. Recursion needs base cases — and that is what stopping rules are.
Training a tree is a loop with a very short body. At a node, try every feature and every threshold between adjacent distinct values; score each candidate with information gain; keep the winner; send the rows left and right; call the same procedure on each side. A node becomes a leaf when it is pure, when no question improves things, or when a stopping rule says enough.
For each feature, sort its values and test every midpoint between consecutive values as a threshold.
Compute the information gain for each candidate threshold.
Split on the (feature, threshold) pair with the highest gain — rows with value ≤ threshold go left.
Recurse on both children; stop when a node is pure, has no useful split, or a rule below fires.
Grow the tree, one question at a time
Each click takes the leaf with the best question available and splits it. Watch the weighted impurity fall and the tinted rectangles get purer.
leaves 1
train accuracy 70.3% (majority vote per leaf)
weighted leaf Gini 0.4175
root: one region, no questions asked.
Greedy splitting never revisits an earlier choice, and the tree keeps asking as long as a question pays. Stopping rules are what keep that enthusiasm in check.
Without a stopping rule, this loop runs until every leaf is pure — often one training row per leaf. That tree is a perfect memorizer of the data it saw and a poor predictor of anything new. Pre-pruning prevents the problem by refusing to grow:
Rule
What it does
Library name
Max depth
Stop when the path has asked enough questions.
max_depth=3 in scikit-learn
Min samples to split
Do not split a node with fewer than k rows.
min_samples_split
Min samples per leaf
Every child must keep at least k rows.
min_samples_leaf=5
Min gain
Stop when the best question improves impurity by less than δ.
min_impurity_decrease
Max leaves
Cap the total number of rectangles.
max_leaf_nodes
05
DEPTH & PRUNING
Depth is the tree’s complexity dial.
Each extra level can carve another rectangle. Early on that buys real structure; later it buys memorized noise. Pruning is how a grown tree gives the noise back.
A depth-1 tree is a single yes/no cut — one feature, one threshold, two predictions. Depth 10 can make up to 2¹⁰ = 1,024 leaves. In the language of bias and variance: a shallow tree has high bias (it underfits — it cannot bend enough to follow the real pattern), while a very deep tree has high variance (it overfits — resample the data a little and its rectangles move a lot, because it is fitting individual points).
The reference implementation’s depth sweep on a 3-class 2D dataset (160 train rows, 40 test rows) makes the tradeoff visible. The gap column is our addition: train accuracy minus test accuracy is the warning light.
Max depth
Train accuracy
Test accuracy
Gap
1
0.5312
0.4750
0.0562
2
0.6750
0.6250
0.0500
3
0.8438
0.8250
0.0188
5
0.9563
0.8250
0.1313
10
1.0000
0.8500
0.1500
None
1.0000
0.8500
0.1500
Reference run, seed 42. Note the honest shape of this particular run: test accuracy never falls, but the gains stall after depth 3 while train accuracy climbs to a perfect 1.0000 — the 0.15 gap is pure memorization. On smaller, noisier data the test curve bends down too; the lab below shows that case.
Depth and the overfitting curve
A noisy disk: 84 training points, 37 test points. Slide the depth and compare the shading (the model) with the two accuracy curves.
depth leaves train test
1 2 60.7% 64.9%
2 4 71.4% 75.7%
3 7 79.8% 83.8%
4 8 85.7% 94.6% ← best test
5 10 85.7% 94.6%
6 13 90.5% 83.8%
7 16 91.7% 81.1%
8 18 91.7% 73.0%
At depth 4: train 85.7%, test 94.6%.
Close to the sweet spot: test accuracy is near its peak.
This toy dataset also illustrates the honest limit of the story: deeper is not always worse — it is worse once the extra splits can only fit noise. The test curve is the judge.
Worked check: cost-complexity pruning in numbers
Score(T) = error(T) + α · (number of leaves)
big tree: 10 leaves, validation error 0.10
α = 0.02 → 0.10 + 0.02·10 = 0.30
α = 0.005 → 0.10 + 0.005·10 = 0.15
pruned subtree: 4 leaves, validation error 0.13
α = 0.02 → 0.13 + 0.02·4 = 0.21 (prune: 0.21 < 0.30)
α = 0.005 → 0.13 + 0.005·4 = 0.15 (tie — the extra leaves are free)
plain English: pay one α per leaf in exchange for lower error.
Raise α and the tree prefers fewer, bigger leaves; set α = 0
and nothing is ever pruned.
scikit-learn exposes this knob as ccp_alpha and finds the α path for you. Grow the tree fully, then walk α upward, trimming the subtree whose loss of accuracy is smaller than the penalty it removes. Reduced-error pruning is the simpler cousin: delete a subtree whenever validation error does not get worse.
Quick check
A depth-12 tree scores 100% on training data and 76% on held-out data; a depth-3 tree scores 84% and 82%. What is the best reading?
06
DECORRELATED TREES
Many mediocre trees beat one confident tree.
A single tree is jumpy: change a few rows and the splits move. A random forest trains many trees on different random views of the data and lets them vote.
In the reference stability demo, five trees trained on slightly different resamples scored 0.975, 0.925, 0.925, 0.925 and 0.950 on their test splits — while five 30-tree forests on the same splits scored 0.975, 0.950, 0.950, 1.000 and 0.950. Five trials is far too few to claim a precise variance reduction, but the pattern is the point: the forest never did worse than the single tree and never produced the weakest result. Averaging stabilizes.
Bagging (bootstrap aggregating) is the first source of diversity. Each tree gets its own random sample drawn with replacement, the same size as the original. Some rows appear several times; some never appear.
How often does a row get picked? (the 63.2% rule)
One draw misses a given row with probability 1 − 1/n.
n draws miss it with probability (1 − 1/n)^n, which approaches
1/e ≈ 0.3679 as n grows. So the chance a row appears in a
bootstrap sample is about 1 − 0.3679 = 63.2%.
numeric checks:
n = 10 → 0.9^10 = 0.3487 → in-bag 65.1%
n = 100 → 0.99^100 = 0.3660 → in-bag 63.4%
n = 1000 → 0.999^1000 = 0.3677 → in-bag 63.2%
The ~37% left out are the out-of-bag rows — a free validation
set attached to every tree.
The second source is feature randomization: at every split, a tree may only consider a random subset of the columns — typically √p for classification and p/3 for regression. With 16 features, each split sees about 4; with 100, about 10. Without it, every tree would grab the same dominant feature first and make the same mistakes.
The random forest vote
One tree memorizes the flipped labels. Many trees, each on its own bootstrap sample and a random feature per split, vote — and the noisy patches dissolve. All numbers recomputed live.
single tree (depth 8) train 91.7% test 73.0%
forest (15 trees) train 94.0% test 86.5%
tree 1 bootstrap: 54 of 84 distinct rows in bag
(64.3%; theory says ≈ 63.2%)
votes on the first test point:
A 9 · B 6
majority wins; the shading shows how close the vote was.
Full-depth trees overfit individually — that is why each tree is grown deep without pruning, then averaged. On this toy data the depth-4 single tree still edges the forest; a forest buys you a strong answer without having to find the perfect depth yourself.
Why decorrelation is the whole trick
Simplified model: T trees, each with variance σ², and every
pair of trees correlated by ρ. The average's variance is
Var(average) = ρ·σ² + (1 − ρ)·σ²/T
plain English: the first term is the mistake all trees share —
averaging cannot remove it. The second term shrinks 1/T. So
averaging pays only when ρ is small.
numeric checks (σ² = 1):
ρ = 1.00, T = 10 → 1.00 + 0 = 1.000 (identical trees: no help)
ρ = 0.20, T = 10 → 0.20 + 0.08 = 0.280
ρ = 0.05, T = 10 → 0.05 + 0.095 = 0.145
ρ = 0.05, T = 100 → 0.05 + 0.0095 = 0.0595 (diminishing returns)
Bagging lowers ρ by giving each tree different data; feature subsampling lowers it by making them ask different questions. Both leave the trees’ bias roughly intact — they are still deep, flexible trees — and attack variance only. That is why a forest of fully grown trees resists overfitting even though each member overfits on its own.
07
WHAT THE FOREST LEARNED
The forest tells you which columns it leaned on.
Every impurity decrease happens at a named feature. Sum those decreases and you have MDI importance. Shuffle a column and measure the damage and you have permutation importance — the more honest of the two.
Mean Decrease in Impurity (MDI) is free with the forest you just trained. Each time a split on feature j reduces impurity, credit that feature with the decrease, scaled by the share of samples that reached the node:
importance(j) = Σ over all nodes that split on j:
(samples at the node / total samples) × impurity decrease
plain English: features that split big, mixed nodes early — when
there is the most impurity to remove — collect the most credit.
Scores are normalized to sum to 1.
Worked check: MDI by hand, then the real forest
Toy forest with 200 training rows:
node A uses feature j: 100/200 samples, decrease 0.50 → 0.50·0.50 = 0.25
node B uses feature j: 50/200 samples, decrease 0.20 → 0.25·0.20 = 0.05
importance(j) = 0.25 + 0.05 = 0.30 before normalization
Reference run, 50 trees, depth 5, four features:
feature MDI permutation
important_1 0.4348 0.312
important_2 0.4807 0.295
noise_1 0.0354 0.008
noise_2 0.0491 0.004
total MDI = 1.0000 (normalized); permutation does not have to
sum to 1 — each value is an accuracy drop.
Both methods agree here: the two real signals carry ~92% of the MDI and the noise columns almost nothing. That is the easy case. The danger is a feature with many distinct values — one unique value per row can be split off into a leaf by itself, which looks like a big impurity decrease and pure memorization.
Feature importance, two ways
MDI is computed while the forest trains; permutation importance re-measures accuracy after shuffling one column. Compare them, then add the row-ID column.
important_10.435
important_20.481
noise_10.035
noise_20.049
Reference run (MDI) plus an illustrative permutation rerun: 50 trees, depth 5. Target = important_1 + important_2 > 0; features 3 and 4 are pure noise. Both methods agree on this easy case.
MDI(feature) = Σ over the nodes that use it:
(samples at node / total samples) × impurity decrease
numeric check:
node 100/200 samples, decrease 0.50 → 0.25
node 50/200 samples, decrease 0.20 → 0.05
total for that feature: 0.30
Fast, but every extra split point is another
chance to look useful — so high-cardinality
columns get inflated scores.
Importance is not causality. A shuffled-together pair of features can each look weak, and a leaked column can look strongest of all.
Permutation importance and out-of-bag error
Permutation importance:
real accuracy 0.910
shuffle feature j 0.620
importance(j) = 0.910 − 0.620 = 0.290
Repeat the shuffle 5–10 times, report mean ± spread. No retraining.
Out-of-bag (OOB) error:
each bootstrap keeps ≈ 63.2% of rows, so ≈ 36.8% are left out
n = 200 rows, 50 trees → each row is out-of-bag in ≈ 0.368·50 ≈ 18 trees
predict each row by majority vote of only those trees, then score
— a validation set you never had to set aside.
OOB error is why forests are hard to misconfigure: you get a generalization estimate while training, without carving out a validation split. Use it to compare forest settings, but still keep a final untouched test set for the number you report.
Quick check
A customer-ID column is added to the feature set. MDI gives it 55% importance; permutation importance gives it 0.001. What happened?
Feature (reference run)
MDI
Permutation (illustrative)
important_1 (real signal)
0.4348
0.312
important_2 (real signal)
0.4807
0.295
noise_1 (pure noise)
0.0354
0.008
noise_2 (pure noise)
0.0491
0.004
08
CHECK YOURSELF
Five questions. Then the terms worth keeping.
Answer before you look. The Gini arithmetic and the bagging questions are exactly what comes up when you reach for a forest in a real project.
0 / 5 answered · 0 correct
01What does Gini impurity measure at a decision tree node?
02Why do tree-based models often beat neural networks on tabular data?
03A random forest uses bootstrap samples AND random feature subsets at each split. Why both?
04A node contains 8 dogs and 2 cats. What is its Gini impurity?
05MDI (Mean Decrease in Impurity) feature importance is biased toward which kind of feature?
Key terms, demystified
Click a card to swap the lazy description for what it actually means.
Exercises from the lesson
Four short problems. Try first; a worked answer is one click away.
Train a single decision tree on a 2D dataset with 3 classes. Draw the decision boundaries at max_depth=2 and max_depth=10, and explain the difference.Show one worked answer
Depth 2 can make at most 2² = 4 leaves, so the boundary is a few axis-aligned rectangles — in the reference run it scored 0.675 on train and 0.625 on test: underfitting. Depth 10 scored 1.000 on train but only 0.850 on test: the extra rectangles carve out individual training points, including their noise. Draw both and you see the shallow tree miss structure while the deep tree grows skinny rectangles around single samples — the classic overfitting picture.
Implement variance reduction for regression trees. On y = x·sin(x) + noise, explain why the prediction is a staircase, not a smooth curve.Show one worked answer
Variance reduction = Var(parent) − weighted average of the children's variances; the leaf then predicts the mean of its targets. Numeric check: values [1, 2, 3, 4] have mean 2.5 and variance 1.25. Split [1, 2] | [3, 4]: child variances are 0.25 each, weighted average 0.25, so reduction = 1.00. Both children now predict a constant (1.5 and 3.5), which is exactly why the fitted curve is piecewise constant — a staircase. More depth adds more steps. In the reference run train MSE fell from 0.3259 at depth 1 to 0.0681 at depth 3 and 0.0031 at depth 10, while test MSE bottomed at 0.0433 at depth 5 and then rose to 0.0599 at depth 10: the staircase started tracing the noise.
Build random forests with 1, 5, 10, 50 and 200 trees. Plot train and test accuracy against the number of trees. What shape do you expect and why?Show one worked answer
Expect test accuracy to rise quickly, then plateau with small wiggles — never a systematic fall. Variance of the average is ρσ² + (1−ρ)σ²/T, which falls toward ρσ² as T grows; adding trees does not increase bias. In the reference run (60 test points) test accuracy went 0.8667 → 0.9500 → 0.9500 → 0.8833 → 0.9500 for 1, 5, 10, 50 and 100 trees: the 0.8833 at 50 is 4 extra test points and reflects test-set noise, not a real decline. Bumping to 200 often costs compute for no measurable gain.
Compare Gini and entropy as split criteria on five datasets. Measure accuracy and depth. Why do the trees look almost identical?Show one worked answer
Both criteria are 0 exactly when a node is pure, both are maximized by a uniform mix, and both are concave in the class probabilities — so they rank nearly every candidate split the same way. In the reference run the test accuracies were 0.8250/0.8000 at depth 3, 0.8250/0.8500 at depth 5 and 0.8500/0.9000 at depth 10 for Gini/entropy: each gap is 1–2 examples on a 40-point test set. Entropy costs a log per evaluation; Gini is a couple of multiplications. Use Gini unless you have a specific reason.
Terms this lesson borrows from later lessons (or outside)
You do not need to master these here. Each one gets a proper treatment in its own lesson; the one-line meaning is enough to keep reading. Orange dotted underlines in the prose point back to this list.
entropy — The information-theory measure of uncertainty in a distribution, in bits. This lesson uses it as one of two node impurity scores. (Phase 1 · Lesson 09)
probability distribution — How likely each outcome is. Every node's class mix is a little distribution, and impurity is a function of its probabilities. (Phase 1 · Lesson 06)
expected value — The average outcome weighted by probability. Gini is literally an expected misclassification rate. (Phase 1 · Lesson 06)
bias–variance tradeoff — Underfitting (too simple, high bias) versus overfitting (too flexible, high variance). Depth is the tree's main dial on that tradeoff. (Phase 2 · Lesson 10)
ensemble method — Combining many models into one predictor. Random forests average in parallel; boosting builds sequentially. (Phase 2 · Lesson 11)
cross-validation — Splitting data into rotating train/validation folds to estimate generalization. It is the honest way to choose a depth or pruning strength. (Phase 2 · Lesson 09)
KEEP GOING
A picture is a start. Practice is the rest.
This lesson is a port of an open course. Everything here traces back to it — and the next step is running the code yourself.
Lesson text adapted from AI Engineering from Scratch (Phase 02, Lesson 04) and the vendored reference implementation (trees.py, seed 42). The split picker, tree builder, depth playground, forest vote simulator, feature-importance board and impurity console are original to this page, as are the worked exercise answers and the added numeric checks. Every lab runs in your browser.