Home / MLP / Week 9

Week 9 · Decision trees and ensembles

Official syllabus line: Decision Trees, Ensemble Learning and Random Forests

About 90 minEnd Term material (see exam radar)BSCS2008 · Ashish Tendulkar

Before you start: MLP weeks 2 and 6 (cross-validation, classification metrics). MLT week 7 (entropy, Gini, information gain) and week 11 (bagging).

Watch first: the animated story of this weekAbout 1-2 minutes of real 3D animation with a friendly voice. Pause any time.

Read the words of the video

Imagine playing twenty questions to guess an object. A decision tree works similarly, asking simple yes or no questions one by one. For example, 'Is the petal shorter than two point four five centimetres?' or 'Is it wider than one point seven five centimetres?' It keeps asking until it knows the answer.
A single decision tree is easy to understand, but it can be a bit 'jumpy'. Small changes in our data might lead to a completely different tree. It also tends to 'memorise' the training information too well. To fix this, we create a 'committee of trees', combining many trees through voting or averaging their predictions.
A clear glass cube holds ten shimmering spheres, five red and five blue. A glowing divider slides in, splitting the cube into two sections. The spheres instantly reconfigure: one section has four red and one blue, the other has one red and four blue. An overhead camera with subtle zoom reveals the much cleaner separation. Bright lab lighting.
For your exams, remember that increasing 'minimum samples per leaf' reduces overfitting. Ensembles like voting or random forests are powerful, especially 'soft voting' with probabilities. Also, 'feature importances' tell us which factors truly matter. You've learned to build and tame trees, and combine them into smart committees. Great job!

The one-minute story

Think of it like this

A decision tree is the game of twenty questions turned into code: "Is the petal shorter than 2.45 cm? ... Is the petal wider than 1.75 cm?..." scikit-learn builds the questions automatically, always choosing the question that leaves the cleanest groups.

One tree is easy to read but jumpy: change a few training flowers and you may get a different tree, and left alone it memorises the training set. The cure is a committee of trees:

ask many different classifiers and let them vote (voting),
or train many trees on different random samples and average (bagging and the famous random forest).

This week: grow and tame a tree, then build the committees.

By the end of this week you can:

train and read a DecisionTreeClassifier, and control overfitting with its hyperparameters;
explain the CART cost and Gini vs entropy;
use VotingClassifier (hard and soft), BaggingClassifier (with out-of-bag score), and RandomForestClassifier;
read feature_importances_.

Words you need

Node / leaf - a question box / a final answer box.
Gini impurity - $1-\sum p_k^2$ ; 0 for a pure node.
CART - the greedy algorithm scikit-learn uses to build binary trees.
Ensemble - several models combined.
Hard / soft voting - majority of the votes / average of the predicted probabilities.
Bagging / pasting - training on samples drawn with / without replacement.
Out-of-bag (OOB) - the training examples a given tree did not see.
Feature importance - how much each feature reduced impurity, summed over the tree.

Idea 1: A decision tree in scikit-learn

We use the iris flowers, keeping petal length and width only, with a depth limit of 2:

from sklearn.tree import DecisionTreeClassifier, export_text
tree = DecisionTreeClassifier(max_depth=2, random_state=42).fit(X_petal, y)
print(export_text(tree, feature_names=["petal_len", "petal_wid"]))

|--- petal_len <= 2.45
|   |--- class: 0
|--- petal_len >  2.45
|   |--- petal_wid <= 1.75
|   |   |--- class: 1
|   |--- petal_wid >  1.75
|   |   |--- class: 2

Three leaves, depth 2. The first question already separates class 0 (setosa) perfectly. The root's Gini is $1-(\frac13)^2\cdot3=0.667$ , the largest possible for 3 equal classes.

predict(X) gives the leaf's majority class.
predict_proba(X) gives the class fractions in the leaf: for a flower with petal $(5,1.5)$ the answer was [0, 0.907, 0.093], because the leaf it lands in holds 49 class-1 and 5 class-2 training flowers ( $49/54=0.907$ ).
feature_importances_ $=[0.562,\,0.438]$ (non-negative, sum to 1): how much each feature contributed to reducing impurity.
get_depth(), get_n_leaves().

Trees need no feature scaling (each question compares one feature to a threshold) and handle numeric and (encoded) categorical features.

Idea 2: How the tree is grown (CART)

At each node, CART tries every feature $k$ and every threshold $t_k$ and picks the pair that minimises the cost

J(k,t_k)=\frac{m_{\text{left}}}{m}\,G_{\text{left}}+\frac{m_{\text{right}}}{m}\,G_{\text{right}}

(the size-weighted impurity of the two children). It splits, then recurses on each child, greedily: it never looks ahead or goes back, so the result is good, not provably optimal.

criterion="gini" is the default; "entropy" is the alternative. They give almost identical trees; Gini is slightly faster, entropy slightly more balanced.
Growth stops when a node is pure, or when a stopping rule (a hyperparameter) applies.

Solved example: 1. A CART cost by hand

Question. A node holds 10 examples (5 class A, 5 class B). A split gives left $(4A,1B)$ and right $(1A,4B)$ . Compute the Gini cost. Compare with the unsplit node.

Solution. $G_{\text{left}}=1-(0.8^2+0.2^2)=0.32$ and $G_{\text{right}}=0.32$ . Cost $=\frac5{10}(0.32)+\frac5{10}(0.32)=\mathbf{0.32}$ . The parent's impurity is $0.5$ , so the split lowers it by $0.18$ . CART picks the split with the smallest cost.

Idea 3: Taming a tree

An unrestricted tree keeps splitting until every leaf is pure, so it fits the training set perfectly (on the iris petal data it grew to depth 5 with 8 leaves, 99.3% training accuracy). That memorising is overfitting: on the "two moons" data (500 noisy points, 70/30 split):

Tree	Train acc.	Test acc.
default (unrestricted)	1.000	0.853
`min_samples_leaf=5`	0.949	0.873

Perfect on training, worse on test. The regularising hyperparameters: each one limits the tree, so increasing a min_* value or decreasing a max_* value regularises:

Hyperparameter	Default	Effect
`max_depth`	`None`	stop at this depth ( $\downarrow$ = simpler)
`min_samples_split`	2	a node needs at least this many examples to be split ( $\uparrow$ = simpler)
`min_samples_leaf`	1	each leaf must hold at least this many ( $\uparrow$ = simpler)
`max_leaf_nodes`	`None`	cap on the number of leaves
`max_features`	`None`	features considered at each split
`criterion`	`'gini'`	`'gini'` or `'entropy'`

DecisionTreeRegressor works the same way but chooses splits that minimise the mean squared error, and each leaf predicts the mean of its training targets (so predictions are a staircase).

Weaknesses. Trees make axis-aligned splits (a diagonal boundary needs many steps), and they are unstable: tiny changes in the data, or rotating the data, can produce a very different tree. That instability is exactly what ensembles average away.

Idea 4: Voting classifiers

Train several different classifiers on the same data and combine them:

from sklearn.ensemble import VotingClassifier
vote = VotingClassifier([("lr", LogisticRegression()),
                         ("rf", RandomForestClassifier(random_state=42)),
                         ("svc", SVC(random_state=42))], voting="hard")

Hard voting: each model casts one vote for a class; the majority wins.
Soft voting: average the predicted probabilities and pick the highest. Needs every model to have predict_proba (so SVC(probability=True)). It usually does better, because very confident models speak louder.

On the moons data: LogisticRegression 0.860, random forest 0.907, SVC 0.907, hard voting 0.913, soft voting 0.933: the committee beats each member. It works best when members are diverse and make different mistakes.

Idea 5: Bagging, pasting and out-of-bag evaluation

Use the same algorithm many times, each on a different random subset of the training data:

from sklearn.ensemble import BaggingClassifier
bag = BaggingClassifier(DecisionTreeClassifier(), n_estimators=300,
                        max_samples=100, bootstrap=True,
                        oob_score=True, random_state=42)
bag.fit(X_train, y_train)
bag.oob_score_

bootstrap=True (the default) samples with replacement: that is bagging. bootstrap=False samples without replacement: pasting.
n_estimators default is 10; max_samples is how many examples each model sees.
Any classifier with fit/predict can be the base estimator (trees, k-NN, logistic regression, SVC...); if none is given a decision tree is used.
Each ensemble prediction is a majority vote (or average of probabilities if available).
Out-of-bag evaluation: each model never saw about 37% of the training examples; oob_score=True tests every example only with the models that did not train on it, giving a free validation estimate in oob_score_. On moons: OOB 0.926, close to the real test accuracy (0.92): a trustworthy estimate with no hold-out set.
Compared with a single tree, bagging has about the same bias but lower variance. (Pasting: test accuracy 0.913 here.)
Trees can be trained in parallel: n_jobs=-1.

Idea 6: Random forests

A random forest is bagged decision trees plus random feature selection at every split, so the trees differ more:

from sklearn.ensemble import RandomForestClassifier
rf = RandomForestClassifier(n_estimators=300, random_state=42, oob_score=True).fit(X_train, y_train)

n_estimators=100 by default; max_features="sqrt" by default (the square root of the number of features are considered at each split); bootstrap=True; plus all the tree hyperparameters. Moons: test accuracy 0.907, OOB 0.894.
Extra-Trees (ExtraTreesClassifier) go further: random thresholds too, and bootstrap=False by default; faster, more bias, less variance.
Feature importances. rf.feature_importances_ averages each feature's impurity reduction over all trees and sums to 1. On the breast-cancer data the top three were worst perimeter (0.143), worst area (0.128) and worst concave points (0.119). A great tool for finding which features matter.

Solved examples

Solved example: 1. Which hyperparameter change reduces overfitting?

Question. For a decision tree, which changes reduce overfitting? (a) larger max_depth (b) larger min_samples_leaf (c) smaller max_leaf_nodes (d) smaller min_samples_split.

Solution. Restrictions regularise. (b) and (c) reduce overfitting. (a) lets the tree grow deeper and (d) lets nodes split more easily: both increase overfitting.

Solved example: 2. Hard vs soft voting

Question. Three classifiers give class-1 probabilities $0.9,\,0.4,\,0.45$ for one example. What do hard and soft voting predict?

Solution. Hard: votes for class 1 are $1,\,0,\,0$ (0.9 is above 0.5; 0.4 and 0.45 are below), so class 0 wins 2 to 1. Soft: mean probability $=\frac{0.9+0.4+0.45}3=0.583>0.5$ , so class 1. The confident first model carries the soft vote.

Solved example: 3. Reading oob_score_

Question. A bagging classifier has oob_score_=0.91 and test accuracy 0.90. What does it tell you?

Solution. The OOB estimate and the test accuracy agree, so the OOB score is a reliable stand-in for a validation set, and the ensemble should generalise at about 90 to 91%.

Your turn

Your turn: 1. Gini

A node has 30 examples: 20 class A, 10 class B. Compute its Gini impurity.

Need a hint?

$1-\sum p_k^2$ .

Show the full solution

$p_A=\frac23$ , $p_B=\frac13$ . $G=1-(\frac49+\frac19)=\frac49=\mathbf{0.444}$ .

Your turn: 2. Predict proba

A leaf holds 12 training examples: 9 of class 0 and 3 of class 1. What does predict_proba give for a test point landing there?

Need a hint?

Class fractions.

Show the full solution

$[\,9/12,\,3/12\,]=[0.75,\,0.25]$ .

Your turn: 3. Pick the setting

Which is the correct way to train pasting with 50 trees, each on 80 examples, from BaggingClassifier?

Need a hint?

Pasting means sampling without replacement.

Show the full solution

BaggingClassifier(DecisionTreeClassifier(), n_estimators=50, max_samples=80, bootstrap=False).

Your turn: 4. Count

A random forest has n_estimators=200. How many DecisionTreeClassifiers does it contain, and does each see all the training rows?

Need a hint?

Think of bootstrap sampling.

Show the full solution

200 trees. Each is trained on a bootstrap sample (the same size, drawn with replacement, so about 63% distinct rows), not on all rows exactly once.

Your turn: 5. True or false

(a) Trees need scaled features. (b) feature_importances_ sums to 1. (c) Soft voting requires predict_proba. (d) A deeper tree always generalises better.

Need a hint?

Check each lesson point.

Show the full solution

(a) False. (b) True. (c) True. (d) False: deeper trees overfit.

Exam radar

MLP Quiz 2 and the End Term: "Suppose you want to use BaggingClassifier; which estimators can be the base estimator?" (any classifier), "advantages of ensemble methods", "which options give the largest regularisation (lowest overfitting)" for trees and forests, "predict the class for this test point from the code given", oob_score, hard vs soft voting, RandomForest hyperparameter grid counts ("how many unique combinations of hyperparameters are in this grid?"), and feature_importances_.

From MLT (the theory partner): decision trees in 24 End Term papers, entropy in 19, random forests in 12, bagging in 14.

Watch out - real exam trap

Soft voting needs predict_proba; SVC needs probability=True.
BaggingClassifier has bootstrap=True (bagging); bootstrap=False is pasting.
Regularise a tree by raising min_samples_* or lowering max_depth / max_leaf_nodes.
Random forest $\ne$ bagged trees only: it also randomises the features per split.
Trees do not need scaling; k-NN, SVM and linear models do.
The default BaggingClassifier has 10 estimators; the default forest has 100.

Quick quiz

Which change makes a decision tree LESS likely to overfit?

increase max_depth
increase min_samples_leaf
decrease min_samples_leaf
grow it until every leaf is pure

Requiring more samples per leaf limits how finely the tree can partition the data.

What does soft voting average?

the predicted classes
the predicted probabilities
the feature importances
the training errors

Soft voting averages predict_proba outputs and picks the class with the largest mean.

In BaggingClassifier, bootstrap=False means...

no randomness at all
the samples are drawn without replacement (pasting)
the trees share the same data exactly
out-of-bag scoring is faster

Without replacement is called pasting; with replacement is bagging.

Select all TRUE statements about random forests. (select all that apply)

Each split considers only a random subset of features.
feature_importances_ sums to 1.
They require feature scaling.
They always have exactly 10 trees.

Trees do not need scaling, and the default n_estimators is 100.

Recap

Remember this

CART: greedily minimise $\frac{m_L}mG_L+\frac{m_R}mG_R$ (Gini default, entropy option). predict_proba = leaf class fractions. Trees: no scaling, axis-aligned, unstable.
Unrestricted tree overfits. Regularise with max_depth $\downarrow$ , min_samples_leaf $\uparrow$ , min_samples_split $\uparrow$ , max_leaf_nodes $\downarrow$ .
Voting: hard (majority) or soft (mean probabilities, usually better). Bagging (bootstrap=True) vs pasting (False); OOB score $\approx$ validation.
Random forest = bagged trees + random features per split (max_features="sqrt"); feature_importances_ sums to 1.

Formulas to keep

Gini $=1-\sum p_k^2$ ; entropy $=-\sum p_k\log_2p_k$ ; cost $=\frac{m_L}mG_L+\frac{m_R}mG_R$
Defaults: tree criterion="gini", max_depth=None, min_samples_leaf=1; BaggingClassifier(n_estimators=10, bootstrap=True); RandomForestClassifier(n_estimators=100, max_features="sqrt")
OOB fraction $\approx0.37$ per tree; oob_score=True $\to$ oob_score_

Connected weeks (learn them together)

MLT week 7 - k-NN and decision trees: Decision trees: the theory, then the code.

Practise with real exam questions

These come straight from past papers (with the real figures and the official answer key). Open 53 real questions on this week All End Term papers