Machine Learning Foundations / Core / 02.29
Decision trees and random forests
Models that ask yes-or-no questions, like a flowchart. One tree is easy to read. A crowd of trees is harder to fool.
14 min readFree
A model that asks questions
Think of the game Twenty Questions. Is it an animal? Does it fly? Is it bigger than a cat? Each answer cuts the choices down, until only one is left. A decision tree plays this game with your data.
The last lesson, ElasticNet Regularization, ended with models that ask yes-or-no questions. Here they are. A tree asks a short series of questions, and the answers lead to a prediction.
Key words
- Decision tree
- A model shaped like a flowchart of yes-or-no questions.
- Root
- The first question, at the top of the tree.
- Branch
- One answer to a question, leading to the next question.
- Leaf
- The end of a path. It holds the answer the tree gives.
- Split
- One question that sends the data down two branches.
- Impurity
- How mixed up a group is. A group that is all one kind has none.
- Bootstrap sample
- A new set made by drawing from the original, one item at a time, putting each back before the next draw.
- Random forest
- Many different trees whose answers are combined.
A tree is easy to explain to anyone. Scikit-learn lists this first among the advantages: trees are simple to understand and to interpret, and can be visualized.
A tree is a flowchart
Imagine a shop that wants to guess which visitors will buy. It knows two things about each person: visits per month, and minutes spent per visit. A tree for this might read: "Visits at most 3? If yes, ask about minutes. If no, ask something else." Follow the answers down to a leaf that says "buys" or "does not buy".
Root
The top question. The tree picks the question that sorts the data best.
Branches
Each yes or no leads to another question, or to a leaf. A tree can go several questions deep.
Leaf
The end. For a yes-or-no problem, the leaf gives the most common answer among the training examples that landed there.
How the tree picks a question
Which question goes first? The tree tries them all and keeps the one that makes the two groups cleanest: each group mostly one kind of person.
To score how mixed a group is, trees use impurity. The most common choice is Gini impurity. Wikipedia defines it as the probability that a randomly chosen element of a set would be mislabeled if it were labeled randomly and independently according to the distribution of labels in the set. It reaches its minimum (zero) when all cases in the node fall into a single target category.
In maths, add up the squares of each kind's share and take that away from 1. In words: the more one kind dominates, the smaller the impurity.
Here p with a small k is the share of kind k in the group. Scikit-learn writes the same measure as the sum of p times (1 minus p). Scikit-learn also lists entropy, a measure from information theory, as another common choice. It is used the same way: lower is cleaner.
- 1
1. Score the group before
Ten shoppers, five buy and five do not. Impurity: 1 minus 0.25 minus 0.25, which is 0.5. Maximum mixing.
- 2
2. Try a question
Say "visits at most 3?" sends 4 shoppers left, none of whom buy, and 6 shoppers right, of whom 5 buy.
- 3
3. Score each side
The left side is pure: 0. The right side: 1 minus (1/6 squared) minus (5/6 squared), which is about 0.28.
- 4
4. Weight by size
The right side holds 6 of the 10 shoppers, so it counts 60%: 0.6 times 0.28 is about 0.17. Add the left side's 0.
- 5
5. Compare
0.17 is much lower than 0.5, so this question helps a lot. The tree tries every question on every feature and keeps the lowest score.
Then it repeats the whole process inside each new group, and again inside those. Scikit-learn notes that practical tree-building uses a greedy approach, where locally optimal decisions are made at each node, and that such algorithms cannot guarantee to return the globally optimal decision tree. In plain words: the tree picks the best question right now, without planning ahead.
Trees that predict numbers
Trees work for numbers too. These are called regression trees. The questions are the same, but the leaf holds a number. Scikit-learn says the common scores for splits are Mean Squared Error (MSE), Poisson deviance and Mean Absolute Error (MAE), and that MSE sets the predicted value of terminal nodes to the learned mean value of the node.
So a leaf's answer is the average of the training values that reached it: three flats renting at 900, 1,000 and 1,100 give a leaf that says 1,000.
Depth and overfitting
A tree that keeps asking questions can end up with one leaf per training example. That tree gets the training data perfectly right, because it has memorised every row. This is overfitting, from the lesson on overfitting and underfitting: great on the data it has seen, poor on new data.
Scikit-learn says decision-tree learners can create over-complex trees that do not generalize the data well. Its cures are pruning, setting the minimum number of samples required at a leaf node, or setting the maximum depth of the tree. The last two are hyperparameters, settings you choose before training.
max depth
How many questions in a row the tree may ask. Small depth makes a simple tree. Scikit-learn says to use max_depth to control the size of the tree to prevent overfitting.
min samples per leaf
Every leaf must hold at least this many training examples, so no leaf rests on one lucky case. Scikit-learn suggests trying min_samples_leaf=5 as an initial value.
The trade
Too loose and the tree memorises. Too tight and it cannot learn the pattern. On the same page, scikit-learn warns that a large number will prevent the tree from learning the data.
Quick check
A tree scores 100% on its training data but only 70% on new data. What is the most likely cause, and a fix?
No scaling needed
Feature scaling puts columns on a similar range. Trees do not need it.
Scikit-learn lists it among the advantages: trees require little data preparation, where other techniques often require data normalization. The reason is how a tree asks questions. Every question looks at one column at a time and asks "is it above this line?" Stretching a column does not change the order of its values, so the same questions give the same groups.
Tip
Little preparation is not none: you still keep a test set and check your data for mistakes.
Worked example: grow a tree
Let us build a tree from scratch in plain Python. The data is made up: 80 shoppers with two numbers each, visits per month and minutes per visit. A shopper buys when the two numbers add up high enough, plus some random noise, because real people are not tidy. A seed fixes the random numbers, so the run repeats exactly.
import random
random.seed(3)
# Made-up shoppers: [visits per month, minutes per visit]; 1 = bought, 0 = did not.
def make(n):
rows = []
for _ in range(n):
visits = random.uniform(0, 10)
minutes = random.uniform(0, 10)
buys = visits + minutes + random.gauss(0, 2.0) > 10
rows.append(([round(visits, 1), round(minutes, 1)], int(buys)))
return rows
train, test = make(80), make(100)
NAMES = ["visits", "minutes"]
def gini(rows):
if not rows:
return 0.0
p = sum(label for _, label in rows) / len(rows)
return 1 - p * p - (1 - p) * (1 - p)
def best_split(rows, features):
best = None
for f in features:
for t in sorted({x[f] for x, _ in rows}):
left = [r for r in rows if r[0][f] <= t]
right = [r for r in rows if r[0][f] > t]
if not left or not right:
continue
score = (len(left) * gini(left) + len(right) * gini(right)) / len(rows)
if best is None or score < best[0]:
best = (score, f, t, left, right)
return best
def majority(rows):
return int(sum(label for _, label in rows) * 2 >= len(rows))
# pick: how many features each split may look at (2 = all, 1 = one chosen at random).
def build(rows, depth, pick=2):
features = random.sample([0, 1], pick)
split = best_split(rows, features)
if depth == 0 or gini(rows) == 0 or split is None:
return majority(rows)
_, f, t, left, right = split
l, r = build(left, depth - 1, pick), build(right, depth - 1, pick)
if l == r and not isinstance(l, tuple):
return l
return (f, t, l, r)
def predict(node, x):
while isinstance(node, tuple):
f, t, left, right = node
node = left if x[f] <= t else right
return node
def show(node, indent=""):
if not isinstance(node, tuple):
print(indent + "answer:", "buys" if node else "does not buy")
return
f, t, left, right = node
print(indent + "if", NAMES[f], "<=", t)
show(left, indent + " ")
print(indent + "else")
show(right, indent + " ")
print("Gini of all training rows:", round(gini(train), 3))
tree = build(train, 3)
show(tree)Output
Gini of all training rows: 0.495
if visits <= 3.5
if minutes <= 7.5
answer: does not buy
else
if visits <= 0.1
answer: does not buy
else
answer: buys
else
if minutes <= 4.1
if visits <= 8.6
answer: does not buy
else
answer: buys
else
answer: buysThe start
Gini of all 80 training rows is 0.495: nearly half buy and half do not, so the mix is close to the worst case of 0.5.
The root
The tree chose "visits at most 3.5" as its first question, because that split gave the lowest weighted Gini of all the questions it tried.
The odd branch
"Visits at most 0.1" slices off a tiny group. That is the tree chasing a few noisy rows. A larger minimum samples per leaf would stop it.
From one tree to a forest
One tree has two problems: it overfits, and a small change in the data can give a different tree. A famous fix is to ask a crowd. Think of guessing the number of sweets in a jar. Any one guess is poor, but the average of a hundred guesses is often close. Errors in different directions cancel out.
A random forest does this with trees. Wikipedia defines it as an ensemble learning method that works by creating a multitude of decision trees during training. For classification, the output is the class selected by most trees. For regression tasks, the output is the average of the predictions of the trees. Wikipedia adds that random forests correct for decision trees' habit of overfitting.
But if every tree saw the same data, they would all be the same tree, and a crowd of copies is no help. So a forest makes each tree different in two ways.
- 1
1. Bootstrap the rows
Scikit-learn says each tree is built from a sample drawn with replacement (a bootstrap sample) from the training set. Like drawing names from a hat and putting each back: some rows appear twice, some not at all.
- 2
2. Pick random columns
During the construction of each tree in the forest, a random subset of the features is considered. At each split, the tree may only choose from a few columns picked by chance.
- 3
3. Grow each tree
Every tree is grown on its own sample and its own column choices. Scikit-learn notes that random forests typically rely on deep trees that overfit individually.
- 4
4. Let them vote
Classification: the class most trees choose wins. Regression: average their numbers.
Scikit-learn gives the purpose of both sources of randomness: to decrease the variance of the forest estimator. Variance means how much the answer jumps around when the data changes.
Worked example: one tree against a forest
Now we test it. We grow three kinds of model: a depth-3 tree, a tree with no depth limit, and a forest of 15 trees. Each forest tree gets its own bootstrap sample and looks at one randomly chosen column at each split.
One test run could be luck, like one shuffle of a deck. So the code repeats the whole experiment on 20 fresh sets of shoppers and reports the average, plus the worst and best runs. This code continues from the lesson's earlier code: it reuses make, build and predict.
def accuracy(predictor, rows):
return sum(predictor(x) == y for x, y in rows) / len(rows)
def make_forest(rows, n_trees=15):
forest = []
for _ in range(n_trees):
sample = [random.choice(rows) for _ in rows] # bootstrap: draw with replacement
forest.append(build(sample, 20, pick=1)) # one random feature per split
return lambda x: int(sum(predict(t, x) for t in forest) * 2 > len(forest))
# One shuffle of the cards is luck, so repeat on 20 fresh sets of shoppers and average.
scores = {"tree depth 3": [], "tree no limit": [], "forest of 15": []}
for _ in range(20):
train, test = make(80), make(100)
shallow, deep, forest = build(train, 3), build(train, 20), make_forest(train)
scores["tree depth 3"].append(accuracy(lambda x: predict(shallow, x), test))
scores["tree no limit"].append(accuracy(lambda x: predict(deep, x), test))
scores["forest of 15"].append(accuracy(forest, test))
for name, vals in scores.items():
print(name, "average test accuracy", round(sum(vals) / len(vals), 3),
"worst", round(min(vals), 2), "best", round(max(vals), 2))Output
tree depth 3 average test accuracy 0.781 worst 0.66 best 0.87 tree no limit average test accuracy 0.789 worst 0.72 best 0.86 forest of 15 average test accuracy 0.815 worst 0.77 best 0.88
The averages
The forest scores 0.815 on average. The depth-3 tree scores 0.781 and the unlimited tree 0.789. The forest is ahead, by about three points.
The worst case
A single tree dropped to 0.66, while the forest never fell below 0.77. That steadiness is the variance falling.
The honest limit
The gain is modest: the data is small and noisy, and a forest cannot beat noise, only a tree's habit of chasing it.
Quick check
Why does a forest give each tree a different bootstrap sample and random columns?
Out-of-bag: a free test
A bootstrap sample leaves some rows out of each tree. Those left-out rows are a free test set for that tree. Scikit-learn says that when using bootstrap sampling the generalization error can be estimated on the left out or out-of-bag samples, and Wikipedia describes the out-of-bag error as the mean prediction error on each training sample, using only the trees that did not have it in their bootstrap sample.
Which columns mattered?
A forest can also tell you which columns it leaned on most. This is feature importance: a score per column.
Scikit-learn explains the usual way: it measures how much each column's splits lower the impurity, averaged over the trees. This is called the mean decrease in impurity, or MDI.
Here is the caution. Scikit-learn warns that impurity-based importances suffer from two flaws that can lead to misleading conclusions. First, they are computed on the training data, so they do not necessarily tell you which features matter for held-out data. Second, they favor high cardinality features, meaning columns with many different values, such as an ID number or a price to the cent.
Tip
Importance shows what the model used, not what causes the result. A column can score high because it happens to track something else. Use it to ask good questions, not to claim why.
What to remember
One tree
A flowchart of yes-or-no questions. Each split is picked to lower impurity, such as Gini. Leaves give a class, or the average for numbers. Easy to read, but it overfits and no scaling is needed.
Control it
Max depth and min samples per leaf are hyperparameters that keep a tree from memorising. Tune them on validation data.
A forest
Many trees, each on a bootstrap sample with random columns. Vote or average. Steadier than one tree, with a free out-of-bag check and feature importance, which needs a careful reading.
Next: gradient boosting, trees that fix each other's mistakes.
Sources
Last updated on 16 November 2026
Learn with me
Every lesson is free. I add new ones as I learn. Have a question, or want help with your own work? Book a short call.