0x60Lesson 7 of 11

Decision trees and ensembles

Split data with Gini impurity, see why single trees overfit, and combine many trees into random forests and gradient boosting.

25 min 5-question quiz 2 code exercises

By the end of this lesson you can

Compute Gini impurity and choose the best split
Explain why deep trees overfit
Compare bagging (random forests) and boosting

A decision tree asks a series of yes/no questions - “income below 40k?”, “missed a payment?” - and each leaf gives a prediction. It’s easy to read, needs no feature scaling, and handles mixed data well.

To grow a tree, at each node we pick the question that makes the groups as pure as possible. For classification, purity is often measured by Gini impurity:

G = 1 - \sum_{k} p_k^2

where $p_k$ is the share of class $k$ in the node. A pure node has $G = 0$ ; a 50/50 split of two classes has $G = 0.5$ . The best split minimizes the size-weighted Gini of the two children.

Many trees beat one

Grown deep, a tree can carve out a leaf for nearly every training example - classic overfitting. Ensembles fix this by combining many trees:

Random forests (Breiman, 2001) train hundreds of deep trees, each on a random bootstrap sample of the data and random subsets of features, then vote or average. Their individual errors cancel out (bagging reduces variance).
Gradient boosting trains small trees one after another, each fitting the errors the previous ones left. Libraries like XGBoost and LightGBM are often the strongest choice for tabular data.

Try it

Bagging or boosting?

Sort each statement.

0 of 5 sortedScore 0/0

“Trees are trained independently, so they can be trained in parallel”
“Each new tree corrects the mistakes of the trees before it”
“Mainly reduces variance by averaging many deep trees”
“Uses a learning rate to shrink each tree’s contribution”
“Works well with almost no tuning”

gini.py

1from collections import Counter
2def gini(labels):
3    return 1 - sum((count / len(labels)) ** 2 for count in Counter(labels).values())
4print(gini(["yes"] * 4), gini(["yes", "no"] * 2), round(gini(["a", "b", "c"]), 3))

Output

0.0 0.5 0.667

Key takeaways

Trees split on the question that most reduces impurity, such as Gini $1 - \sum p_k^2$ .
Deep single trees overfit; limit depth or use ensembles.
Random forests average independent trees; gradient boosting adds trees that fix earlier errors.

Lesson quiz

5 questions · pass with 4 correct · up to 50 XP

Passing this quiz completes the lesson and keeps your streak going. Questions you miss come back in review sessions later.

Practice: write Python

Write Python in the editor and run it against sample inputs. Python runs locally in your browser using a WebAssembly runtime.

Exercise 1

Find the best split

+25 XP

Each line is value label. For every threshold halfway between consecutive distinct sorted values, split into value <= t and value > t, and compute the size-weighted Gini of the two sides. Print the best threshold and its weighted Gini as best split: x <= T (gini G) (T with :g, G 3 decimals; the smallest threshold wins ties).

Income and default

main.py

Loading editor…

Python runs in a sandboxed browser worker with a 60 second time limit. Its runtime loads from the Pyodide CDN; your code stays in this browser.

Exercise 2

Ensemble majority vote

+25 XP

Each line holds one tree’s predictions for the same examples (space-separated labels). Print the majority vote for each example (alphabetically first on ties), space-separated, then agreement: P% - the average share of trees agreeing with the vote (whole percent).

Five trees

main.py

Loading editor…

Python runs in a sandboxed browser worker with a 60 second time limit. Its runtime loads from the Pyodide CDN; your code stays in this browser.

Questions about this lesson

Stuck? Ask. Figured something out? Share it. Explaining is one of the best ways to learn.

Loading posts…