Unit 7 · Decision Trees — COMP328: Fundamentals of Machine Learning

01 Learning Outcomes

Knowledge

Describe the structure of a decision tree in terms of root node, internal nodes, branches, and leaves.
Explain how entropy measures the impurity of a set of labelled examples.
Explain how information gain is used to select the best split at each node.
Distinguish between Gini impurity and entropy as splitting criteria.
Describe why an unconstrained tree overfits and how pruning and stopping rules control complexity.

Skills

Compute entropy and information gain by hand for a small dataset.
Trace the decision path a new example takes through a trained tree.
Train, tune, and evaluate a DecisionTreeClassifier with scikit-learn.
Choose sensible values for max_depth, min_samples_leaf, and criterion.
Extract human-readable decision rules and feature importances from a fitted model.

Professional Competencies

Communicate a tree's decisions to a non-technical stakeholder.
Recognise when interpretability matters more than a small gain in accuracy.
Identify sources of bias in tree-based models (imbalance, proxy features, unstable splits).
Document model choices and limitations honestly in a report.

02 Why This Unit Matters

Every algorithm you meet later in COMP328 — random forests, gradient boosting, and even some deep architectures — is built on ideas introduced here. A decision tree is the simplest model that can learn non-linear boundaries, and it does so with a rule you can read aloud. That combination makes it the natural bridge between the linear models of Module 2 and the ensemble and neural methods that follow.

Big idea

A decision tree builds a model by asking a sequence of yes/no questions about the features. Each question is chosen to make the resulting groups as pure as possible — as close to a single class as possible.

Where you have already met this

In Unit 6 you learned precision, recall, and cross-validation. This unit puts those tools to work immediately: a tree is easy to grow, but deciding whether it is useful still depends on the evaluation discipline from Unit 6.

Common misconception

"A tree that fits the training data perfectly is a good tree." Usually the opposite is true. An unconstrained tree can memorise noise, producing a brittle model that generalises poorly — the bias–variance trade-off from Unit 6 in its most visible form.

03 Reading Roadmap

Work through the eight tutorials in order. Tutorials t-03 and t-04 contain the mathematical core of the unit — do not skip the hand calculations there, as they are what make the scikit-learn API feel obvious rather than magical.

t-01

Anatomy of a Decision Tree

Root nodes, internal nodes, branches, and leaves — the vocabulary of tree models.

t-02

How a Tree Makes a Prediction

Decision paths, axis-aligned splits, and recursive partitioning of feature space.

t-03

Entropy: Measuring Disorder

Impurity, the entropy formula, and a full hand calculation on a small dataset.

t-04

Information Gain

Scoring candidate splits, comparing entropy with Gini impurity, and the greedy search.

t-05

Growing, Stopping & Pruning

Recursion, stopping criteria, overfitting, and cost-complexity pruning.

t-06

Building Trees in scikit-learn

DecisionTreeClassifier, plot_tree, hyperparameters, and cross-validation.

t-07

Reading and Explaining a Tree

Feature importance, rule extraction, and talking about a model with stakeholders.

t-08

Strengths, Limits and Fairness

Instability, axis-aligned bias, class imbalance, and the ethics of automated decisions.

04 Topics & Key Concepts

Unit 7 syllabus topics mapped to tutorials and outcomes
Topic	What you will be able to do	Tutorials
Tree structure	Identify nodes, branches, and leaves, and describe a tree as a set of nested if–then rules.	t-01, t-02
Entropy	Compute the entropy of a labelled set and interpret it as a measure of disorder.	t-03
Information gain	Score candidate splits and select the feature that reduces impurity the most.	t-04, t-05
Interpretability	Extract rules and feature importances, and explain a prediction to a non-specialist.	t-07, t-08
Practical modelling	Fit, tune, prune, and evaluate a decision tree end to end.	t-05, t-06

Terms you must be able to define

Decision node (internal node): A node that tests a condition on a single feature and routes each example to one of its children.
Leaf node: A terminal node that holds the prediction — a class label for classification, or a numeric value for regression.
Impurity: A measure of how mixed the class labels are within a node. A node containing only one class has impurity zero.
Entropy: An impurity measure from information theory: H(S) = −Σ pᵢ log₂ pᵢ, where pᵢ is the proportion of class i in set S.
Information gain: The reduction in entropy achieved by splitting a set on a particular feature: IG(S, A) = H(S) − Σ (|Sᵥ| / |S|) · H(Sᵥ).
Gini impurity: An alternative impurity measure, Gini(S) = 1 − Σ pᵢ², which is cheaper to compute and usually gives similar trees.
Pruning: Removing branches that add little predictive value, typically to reduce overfitting. Cost-complexity pruning is the standard approach in scikit-learn.
Feature importance: The total weighted impurity reduction contributed by a feature across all nodes that split on it.

05 Worked Example: Choosing the First Split

Suppose we want to predict whether a student passes COMP328 from two binary features. We have eight past students:

Training set: 8 students, 5 passed / 3 failed
Student	Studied ≥ 5 h/week	Attended ≥ 80% of labs	Passed
1	Yes	Yes	Yes
2	Yes	Yes	Yes
3	Yes	No	Yes
4	Yes	No	Yes
5	Yes	No	No
6	No	Yes	No
7	No	No	No
8	No	Yes	Yes

Step-by-step

Entropy of the root node. Five of eight students passed, so p(Pass) = 5/8 and p(Fail) = 3/8.

H(S) = −(5/8)·log₂(5/8) − (3/8)·log₂(3/8)
     = 0.4238 + 0.5306
     ≈ 0.954 bits

Try splitting on "Studied ≥ 5 h/week".
The Yes branch has 5 students (4 pass, 1 fail): H = 0.722 bits.
The No branch has 3 students (1 pass, 2 fail): H = 0.918 bits.
```
Weighted entropy = (5/8)(0.722) + (3/8)(0.918) = 0.796 bits
Information gain = 0.954 − 0.796 = 0.159 bits
```
Try splitting on "Attended ≥ 80% of labs".
The Yes branch has 4 students (3 pass, 1 fail): H = 0.811 bits.
The No branch has 4 students (2 pass, 2 fail): H = 1.000 bits.
```
Weighted entropy = (4/8)(0.811) + (4/8)(1.000) = 0.906 bits
Information gain = 0.954 − 0.906 = 0.048 bits
```
Choose the better split. "Studied ≥ 5 h/week" has the higher information gain (0.159 vs 0.048 bits), so it becomes the root node. The algorithm then recurses on each branch, choosing the best remaining feature for each subset.

Check your understanding

Notice that the root split does not produce pure leaves — the Yes branch still contains one failing student. That is expected: a tree grows until its stopping criteria are met, not until every node is pure.

06 Learning Activities

Activity 7.1 — Grow the tree by hand

Using the eight-student dataset above, continue the recursion for the Studied = Yes branch (students 1–5). Compute the information gain of splitting that subset on "Attended ≥ 80% of labs" and decide whether the tree would stop there. Show all entropy calculations to three decimal places.

Activity 7.2 — Trace a decision path

Take the tree you produced in Activity 7.1. A new student studied 6 hours per week and attended 85% of labs. Write out the sequence of node tests the student passes through and state the predicted label and the leaf's class distribution.

Activity 7.3 — Compare impurity criteria

Repeat the root-split calculation using Gini impurity instead of entropy. Does the winning feature change? Record both sets of scores in a table and write two sentences explaining the result.

Notebook

u07-decision-trees.ipynb Guided notebook — load a dataset, fit trees at several depths, plot the tree, and compare training vs validation accuracy. Open

The core of the notebook is a short, readable scikit-learn workflow:

from sklearn.tree import DecisionTreeClassifier, plot_tree
from sklearn.model_selection import cross_val_score

clf = DecisionTreeClassifier(
    criterion="entropy",   # or "gini"
    max_depth=3,           # controls overfitting
    min_samples_leaf=5,    # smooths the leaves
    random_state=42,
)

clf.fit(X_train, y_train)

print("CV accuracy:", cross_val_score(clf, X_train, y_train, cv=5).mean())
plot_tree(clf, feature_names=feature_names, class_names=["Fail", "Pass"])

Watch the depth

Run the notebook once with max_depth=None and once with max_depth=3. Compare training accuracy with cross-validated accuracy. The gap you see in the unconstrained tree is overfitting.

07 Self-Check

Answer these before moving on. If any feel uncertain, revisit the linked tutorial.

08 Assessment Activities

3%

Quiz 7 · Decision Trees

12 questions covering tree structure, entropy calculations, information gain, pruning, and interpretability. Unlimited attempts; highest score counts.

10%

Assignment 3 · Classification Analysis

Train and evaluate a decision tree on a real dataset. Report your split strategy, hyperparameter choices, evaluation metrics, and the decision rules your final model learned.

Quiz 7 Decision Trees — 12 questions, auto-graded Due end of week 7
Assignment 3 Classification Analysis — decision tree component Due week 8
Capstone Decision tree baseline for your capstone problem End of course

Tip for Assignment 3

Always report a baseline alongside your tuned model. A single-split tree (a "decision stump") is a strong, honest baseline and makes the value of additional depth easy to see.

09 Summary

What you should take away

A decision tree partitions feature space with a sequence of axis-aligned splits, producing a model that can be read as a set of if–then rules.
Entropy quantifies node impurity; information gain quantifies how much a candidate split reduces that impurity.
The tree grows greedily: at each node it picks the split with the highest information gain, then recurses. This is fast, but not guaranteed to be globally optimal.
Unconstrained trees overfit. Control complexity with max_depth, min_samples_leaf, and pruning, and always validate with cross-validation.
Interpretability is the tree's defining strength — and it carries a responsibility to check for bias and to communicate limitations clearly.

Next up

Unit 8, Random Forests, fixes the tree's biggest weakness — instability — by averaging many trees. Everything you learned here about entropy and splitting carries directly into the ensemble methods.

Decision Trees

01 Learning Outcomes

Knowledge

Skills

Professional Competencies

02 Why This Unit Matters

Big idea

Where you have already met this

Common misconception

03 Reading Roadmap

Anatomy of a Decision Tree

How a Tree Makes a Prediction

Entropy: Measuring Disorder

Information Gain

Growing, Stopping & Pruning

Building Trees in scikit-learn

Reading and Explaining a Tree

Strengths, Limits and Fairness

04 Topics & Key Concepts

Terms you must be able to define

05 Worked Example: Choosing the First Split

Step-by-step

Check your understanding

06 Learning Activities

Activity 7.1 — Grow the tree by hand

Activity 7.2 — Trace a decision path

Activity 7.3 — Compare impurity criteria

Notebook

Watch the depth

07 Self-Check

Quick check — 3 questions

08 Assessment Activities

Quiz 7 · Decision Trees

Assignment 3 · Classification Analysis

Tip for Assignment 3

09 Summary

What you should take away

Next up

Ready to grow your first tree?

Student	Studied ≥ 5 h/week	Attended ≥ 80% of labs	Passed
1	Yes	Yes	Yes
2	Yes	Yes	Yes
3	Yes	No	Yes
4	Yes	No	Yes
5	Yes	No	No
6	No	Yes	No
7	No	No	No
8	No	Yes	Yes

Student	Studied ≥ 5 h/week	Attended ≥ 80% of labs	Passed
1	Yes	Yes	Yes
2	Yes	Yes	Yes
3	Yes	No	Yes
4	Yes	No	Yes
5	Yes	No	No
6	No	Yes	No
7	No	No	No
8	No	Yes	Yes

Student	Studied ≥ 5 h/week	Attended ≥ 80% of labs	Passed
1	Yes	Yes	Yes
2	Yes	Yes	Yes
3	Yes	No	Yes
4	Yes	No	Yes
5	Yes	No	No
6	No	Yes	No
7	No	No	No
8	No	Yes	Yes