Week 6: Decision Trees

From Linear Boundaries to Hierarchical Decisions

MPS311/439 - Machine Learning
Dr. Wei Xing
University of Sheffield
November 2025

Learning Outcomes

By the end of this lecture, you will be able to:

Core Learning Outcomes (MPS311 - Required for all students)

Advanced Learning Outcomes (MPS439 - Optional)

Table of Contents

  1. Introduction & Motivation
  2. What is a Decision Tree?
  3. Building a Tree: The Splitting Process
  4. Implementation in Python
  5. The Overfitting Problem
  6. Hyperparameter Tuning & Best Practices
  7. Real-World Example
  8. [OPTIONAL - MPS439] Beyond Single Trees: Ensemble Methods
  9. Summary & Looking Ahead

1. Introduction & Motivation

1.1 Where We Left Off

Last week, we explored Linear Discriminant Analysis (LDA) and Quadratic Discriminant Analysis (QDA). These methods make specific assumptions about our data:

Both methods work well when these assumptions hold. But what happens when our data doesn't fit these neat distributional assumptions?

1.2 The Challenge: When Linear Models Fail

Consider the classic XOR (exclusive OR) problem. We have two features and two classes arranged in a very specific pattern:

XOR Problem
Figure 1: The XOR problem - a classic example where linear classifiers fail. The four clusters cannot be separated by any straight line.

The problem: No single straight line can separate the blue points from the red points! Even though this pattern is conceptually simple (diagonal clustering), linear methods like logistic regression or LDA fail miserably.

Here's another challenging scenario - nested or circular boundaries:

Nested Boundaries
Figure 2: Nested class boundaries challenge linear methods. Class A (blue) forms an inner circle, while Class B (red) forms an outer ring.

Even QDA struggles here because the decision boundary isn't a simple quadratic curve - it's fundamentally about distance from the origin.

1.3 Thinking Like Humans: Hierarchical Decisions

Here's a key insight: Humans don't make decisions using linear combinations of features. Instead, we use hierarchical sequences of yes/no questions:

Example: Should I go for a run today?

  1. Is it raining?
    • Yes → Stay home
    • No → Continue to next question
  2. Is the temperature above 5°C?
    • Yes → Continue to next question
    • No → Too cold, stay home
  3. Is the temperature below 30°C?
    • Yes → Go running!
    • No → Too hot, stay home

Notice how this decision process naturally forms a tree structure. Each question is a node, and we follow different branches based on the answers until we reach a final decision (the leaves).

Other examples of tree-like thinking:

The key question: Can we teach machines to make decisions the same way?

The answer: Yes! That's exactly what decision trees do.

2. What is a Decision Tree?

2.1 The Core Idea

A decision tree is a flowchart-like structure where:

Think of it as a game of "20 questions" that the model plays with itself to arrive at a prediction.

2.2 Visual Introduction: A Simple Example

Let's look at a real decision tree trained on the famous Iris flower dataset:

Simple Tree Example
Figure 3: A decision tree (depth=3) for classifying Iris flowers. The tree asks questions about petal width and petal length to determine the species.

How to read this tree:

Each box (node) contains:

Color coding: The color intensity shows the majority class and how pure the node is. Darker colors mean more samples belong to the majority class.

Let's walk through an example:
Suppose we have a flower with petal width = 1.5 cm and petal length = 4.5 cm:

  1. Root node: Is petal width ≤ 0.8? → No (1.5 > 0.8), go right
  2. Right branch: Is petal width ≤ 1.75? → Yes (1.5 ≤ 1.75), go left
  3. Next node: Is petal length ≤ 4.95? → Yes (4.5 ≤ 4.95), go left
  4. Leaf node: Predict versicolor!

2.3 Formal Components

Let's define the key components more precisely:

Mathematical notation:

2.4 Key Advantages

Why are decision trees so popular in machine learning?

1. Interpretability 🔍

2. Non-linearity 🌊

3. No feature scaling needed 📏

4. Handles mixed data types 🎯

5. Implicit feature selection ✨

But (there's always a but!), trees have some serious drawbacks too - we'll discuss these later when we talk about overfitting.

3. Building a Tree: The Splitting Process

Now comes the crucial question: How do we actually build a decision tree?

3.1 The Greedy Recursive Algorithm

Decision trees are built using a greedy, recursive algorithm called CART (Classification and Regression Trees):

Algorithm (high-level):

1. Start with all training data at the root node
2. FOR each node (starting from the root):
   a. Find the "best" feature and threshold to split on
   b. Split the data into two child nodes based on this split
   c. Recursively apply steps 2a-2c to each child node
3. STOP when a stopping criterion is met

Key term: "Greedy" means we make the locally optimal choice at each step, without looking ahead. We choose the split that looks best right now, even though a different split might lead to a better overall tree. This is computationally efficient but doesn't guarantee the globally optimal tree.

3.2 What Makes a "Good" Split?

The critical question is: How do we measure the quality of a split?

Goal: We want splits that create pure child nodes.

Purity means:

Intuition: If we can split the data so that one child has mostly blues and the other has mostly reds, we've made progress! The more pure the children, the better the split.

3.3 Splitting Criterion 1: Gini Impurity

The Gini impurity measures how "mixed" a node is. It's the probability of misclassifying a randomly chosen element if we randomly label it according to the class distribution in the node.

Formula:

For a node NN containing samples from KK classes, where pip_i is the proportion of samples belonging to class ii:

Gini(N)=1−∑i=1Kpi2\text{Gini}(N) = 1 - \sum_{i=1}^{K} p_i^2

For binary classification (K=2K=2):

Gini(N)=1−p12−p22=2p1p2=2p1(1−p1)\text{Gini}(N) = 1 - p_1^2 - p_2^2 = 2p_1p_2 = 2p_1(1-p_1)

where p1p_1 is the proportion of class 1 samples.

Interpretation:

Example calculations:

  1. Pure node: 80 samples of Class A, 0 samples of Class B

    • p1=8080=1.0p_1 = \frac{80}{80} = 1.0, p2=080=0.0p_2 = \frac{0}{80} = 0.0
    • Gini=1−(1.02+0.02)=1−1=0\text{Gini} = 1 - (1.0^2 + 0.0^2) = 1 - 1 = 0 ✓ Perfect purity!

  2. Maximum impurity: 40 samples of Class A, 40 samples of Class B

    • p1=p2=0.5p_1 = p_2 = 0.5
    • Gini=1−(0.52+0.52)=1−0.5=0.5\text{Gini} = 1 - (0.5^2 + 0.5^2) = 1 - 0.5 = 0.5 ✗ Maximum impurity

  3. Moderate impurity: 60 samples of Class A, 20 samples of Class B

    • p1=0.75p_1 = 0.75, p2=0.25p_2 = 0.25
    • Gini=1−(0.752+0.252)=1−(0.5625+0.0625)=0.375\text{Gini} = 1 - (0.75^2 + 0.25^2) = 1 - (0.5625 + 0.0625) = 0.375

3.4 Splitting Criterion 2: Entropy & Information Gain

Entropy is an alternative measure borrowed from information theory. It measures the "disorder" or "uncertainty" in a node.

Formula:

Entropy(N)=−∑i=1Kpilog⁡2(pi)\text{Entropy}(N) = -\sum_{i=1}^{K} p_i \log_2(p_i)

Convention: 0log⁡2(0)=00 \log_2(0) = 0 (by limit definition)

Interpretation:

Information Gain measures how much a split reduces entropy:

IG(N,split)=Entropy(parent)−Weighted Entropy(children)\text{IG}(N, \text{split}) = \text{Entropy}(\text{parent}) - \text{Weighted Entropy}(\text{children})

where the weighted entropy is:

Weighted Entropy=∣Nleft∣∣N∣Entropy(Nleft)+∣Nright∣∣N∣Entropy(Nright)\text{Weighted Entropy} = \frac{|N_{\text{left}}|}{|N|} \text{Entropy}(N_{\text{left}}) + \frac{|N_{\text{right}}|}{|N|} \text{Entropy}(N_{\text{right}})

Example calculations (same nodes as before):

  1. Pure node: [80, 0]

    • Entropy=−(1.0×log⁡2(1.0)+0.0×log⁡2(0.0))=0\text{Entropy} = -(1.0 \times \log_2(1.0) + 0.0 \times \log_2(0.0)) = 0 ✓

  2. Maximum impurity: [40, 40]

    • Entropy=−(0.5×log⁡2(0.5)+0.5×log⁡2(0.5))\text{Entropy} = -(0.5 \times \log_2(0.5) + 0.5 \times \log_2(0.5))
    • =−(0.5×(−1)+0.5×(−1))=1.0= -(0.5 \times (-1) + 0.5 \times (-1)) = 1.0 bit

  3. Moderate impurity: [60, 20]

    • Entropy=−(0.75×log⁡2(0.75)+0.25×log⁡2(0.25))\text{Entropy} = -(0.75 \times \log_2(0.75) + 0.25 \times \log_2(0.25))
    • =−(0.75×(−0.415)+0.25×(−2))= -(0.75 \times (-0.415) + 0.25 \times (-2))
    • =−(−0.311−0.500)=0.811= -(-0.311 - 0.500) = 0.811 bits

3.5 Gini vs Entropy: Which to Use?

Let's visualize the difference between these two measures:

Gini vs Entropy
Figure 4: Comparison of Gini impurity and Entropy for binary classification as functions of class probability. Both curves are similar in shape, with maximum impurity at p=0.5.

Key observations:

  1. Both metrics have the same shape - they're monotonically related
  2. Both reach maximum at p=0.5p=0.5 (equal class probabilities)
  3. Both reach minimum at p=0p=0 or p=1p=1 (pure nodes)
  4. Entropy is slightly more "peaked" at the maximum

Practical differences:

When they differ: Entropy tends to produce slightly more balanced trees because it penalizes impurity more heavily. Gini tends to isolate the most frequent class in its own branch.

Recommendation: Start with Gini (default). Switch to entropy only if you have a specific reason or if experimentation shows it performs better on your data.

3.6 Weighted Impurity for Splits

When we split a node, we create two children of potentially different sizes. We need to account for this when evaluating split quality.

Weighted Gini impurity for a split:

Ginisplit=nleftnGini(Nleft)+nrightnGini(Nright)\text{Gini}_{\text{split}} = \frac{n_{\text{left}}}{n} \text{Gini}(N_{\text{left}}) + \frac{n_{\text{right}}}{n} \text{Gini}(N_{\text{right}})

where:

Goal: Choose the split that minimizes weighted impurity (or equivalently, maximizes information gain).

Example:

Parent node has 100 samples: [60 Class A, 40 Class B]

Consider split: "Feature X ≤ 5"

Weighted Gini:
Ginisplit=70100(0.408)+30100(0.444)=0.286+0.133=0.419\text{Gini}_{\text{split}} = \frac{70}{100}(0.408) + \frac{30}{100}(0.444) = 0.286 + 0.133 = 0.419

Gini reduction = 0.48−0.419=0.0610.48 - 0.419 = 0.061

This split reduces impurity, so it's helpful! We'd compare this to all other possible splits and choose the one with the largest reduction.

3.7 Stopping Criteria: When to Stop Growing?

The tree-building algorithm is recursive - it keeps splitting nodes into children. But when should we stop?

Common stopping criteria:

  1. Maximum depth reached (max_depth)

    • Stop if the tree has reached a specified depth
    • Example: max_depth=5 means maximum 5 levels from root to leaf

  2. Minimum samples for split (min_samples_split)

    • Stop if a node has too few samples to split
    • Example: min_samples_split=20 means don't split nodes with <20 samples

  3. Minimum samples per leaf (min_samples_leaf)

    • Stop if a split would create a child with too few samples
    • Example: min_samples_leaf=10 ensures every leaf has ≥10 samples

  4. Perfect purity achieved

    • Stop if all samples in a node belong to the same class
    • Gini = 0 or Entropy = 0

  5. No improvement in impurity (min_impurity_decrease)

    • Stop if splitting doesn't reduce impurity by at least a threshold
    • Example: min_impurity_decrease=0.01 requires significant splits

Without any stopping criteria, the tree grows until every leaf is pure (or has one sample). This leads to overfitting - we'll discuss this problem in detail later!

3.8 Worked Example: Building a Small Tree by Hand

Let's build a tiny decision tree manually to really understand the process.

Toy dataset (8 samples, 2 features, 2 classes):

Sample Feature 1 Feature 2 Class
1 2.5 3.0 A
2 3.0 3.5 A
3 1.5 2.0 A
4 5.0 4.0 B
5 5.5 4.5 B
6 6.0 5.0 B
7 4.0 3.0 B
8 3.5 2.5 A

Step 1: Root node impurity

All 8 samples: 4 Class A, 4 Class B
Gini(root)=1−(0.52+0.52)=0.5\text{Gini}(\text{root}) = 1 - (0.5^2 + 0.5^2) = 0.5

Step 2: Try all splits on Feature 1

Possible thresholds (midpoints between sorted values): 2.0, 2.75, 3.25, 3.75, 4.5, 5.25, 5.75

Let's try Feature 1 ≤ 3.0:

No need to check other splits - we found a perfect one!

Gini reduction = 0.5−0=0.50.5 - 0 = 0.5 (maximum possible)

Step 3: Create split

Our tree after one split:

                    [8 samples: 4A, 4B]
                    Feature 1 ≤ 3.0?
                    /              \
                 Yes               No
                  /                  \
        [4 samples: 4A, 0B]    [4 samples: 0A, 4B]
        Predict: A              Predict: B

Result: Both children are pure, so we stop! This tree achieves 100% accuracy on the training data with just one split.

Key insight: The CART algorithm would find this split by systematically trying every feature and every threshold, computing the weighted Gini for each, and selecting the best one.

4. Implementation in Python

Now let's see how to actually build and use decision trees with scikit-learn. The good news: sklearn handles all the complexity we just discussed!

4.1 Basic Workflow with sklearn

The standard machine learning workflow applies:

from sklearn.tree import DecisionTreeClassifier
from sklearn.model_selection import train_test_split

# 1. Load your data
# X = features, y = labels

# 2. Split into train/test sets
X_train, X_test, y_train, y_test = train_test_split(
    X, y, test_size=0.3, random_state=42
)

# 3. Create and train the tree
clf = DecisionTreeClassifier(max_depth=3, random_state=42)
clf.fit(X_train, y_train)

# 4. Make predictions
y_pred = clf.predict(X_test)

# 5. Evaluate
train_acc = clf.score(X_train, y_train)
test_acc = clf.score(X_test, y_test)
print(train_acc, test_acc)

Key parameters:

That's it! Just a few lines of code to train a decision tree.

4.2 Visualizing the Tree Structure

One of the best features of decision trees is that we can visualize them:

from sklearn.tree import plot_tree
import matplotlib.pyplot as plt

plt.figure(figsize=(20, 10))
plot_tree(clf, filled=True, feature_names=['f1', 'f2'])
plt.show()

How to interpret the visualization:

Each node shows:

Node colors: Darker color = higher purity (more samples from majority class)

4.3 Visualizing Decision Boundaries

For 2D data, we can visualize the decision regions:

Tree Decision Boundaries
Figure 5: Decision boundaries for shallow (depth=2) vs deep (depth=8) trees on a moons dataset. Notice how deeper trees create more complex, axis-aligned boundaries.

Key observations:

  1. Decision trees create axis-aligned boundaries (only horizontal/vertical splits)
  2. Deeper trees create more complex boundaries
  3. The boundary is piecewise constant within each region
  4. Each region corresponds to a leaf node

Code to generate this (for 2D data):

import numpy as np

# Create a mesh
h = 0.02
x_min, x_max = X[:, 0].min() - 0.5, X[:, 0].max() + 0.5
y_min, y_max = X[:, 1].min() - 0.5, X[:, 1].max() + 0.5
xx, yy = np.meshgrid(np.arange(x_min, x_max, h),
                     np.arange(y_min, y_max, h))

# Predict on mesh
Z = clf.predict(np.c_[xx.ravel(), yy.ravel()])
Z = Z.reshape(xx.shape)

# Plot
plt.contourf(xx, yy, Z, alpha=0.3)
plt.scatter(X[:, 0], X[:, 1], c=y)
plt.show()

4.4 Feature Importance

Decision trees automatically tell us which features are most important for making predictions!

Feature importance measures how much each feature contributes to reducing impurity across all splits in the tree.

Access in sklearn:

# Get feature importances
importances = clf.feature_importances_
print(importances)

Interpretation:

Example output:

[0.654 0.346 0.000 0.000]

This tells us that the first feature has 65.4% importance, second feature 34.6%, and the last two features aren't used at all!

Visualization:

import matplotlib.pyplot as plt

plt.bar(range(len(importances)), importances)
plt.xlabel('Feature')
plt.ylabel('Importance')
plt.show()

4.5 Complete Minimal Example

Here's a full working example on the Iris dataset:

from sklearn.datasets import load_iris
from sklearn.tree import DecisionTreeClassifier
from sklearn.model_selection import train_test_split

# Load data
iris = load_iris()
X, y = iris.data, iris.target

# Train/test split
X_train, X_test, y_train, y_test = train_test_split(
    X, y, test_size=0.3, random_state=42
)

# Train tree
clf = DecisionTreeClassifier(max_depth=3, random_state=42)
clf.fit(X_train, y_train)

# Evaluate
print(clf.score(X_train, y_train))
print(clf.score(X_test, y_test))

# Feature importances
print(clf.feature_importances_)

Expected output:

0.981
0.956
[0.000 0.000 0.551 0.449]

Interpretation: The tree achieves ~96% test accuracy using only petal measurements (features 2 and 3). Sepal features (0 and 1) aren't needed.

5. The Overfitting Problem

Decision trees are powerful, but they have a critical weakness: they are prone to overfitting.

5.1 The Perfect Training Accuracy Trap

Let's run an experiment. Train two trees on the same data:

Typical results:

Wait, what? 🤔

Tree 2 is perfect on training data but worse on test data! This is the hallmark of overfitting.

5.2 How Trees Memorize Data

An unrestricted decision tree will keep splitting until either:

  1. Every leaf is pure (all samples belong to one class), OR
  2. Every leaf has exactly one sample

The problem: The tree learns specific quirks of the training data rather than general patterns:

Analogy: It's like memorizing answers to practice exam questions instead of understanding the concepts. You'll ace the practice exam but fail the real exam with slightly different questions.

Why does this happen?

5.3 Visual Demonstration of Overfitting

Overfitting Comparison
Figure 6: Comprehensive demonstration of overfitting in decision trees. Top row shows decision boundaries for shallow (depth=2) vs deep (depth=15) trees. Bottom row shows how accuracy and impurity change with tree depth.

Key insights from this figure:

Top-left (Shallow tree):

Top-right (Deep tree):

Bottom-left (Accuracy vs Depth):

Bottom-right (Gini Impurity):

5.4 The Bias-Variance Tradeoff

This is a fundamental concept in machine learning:

Bias (underfitting):

Variance (overfitting):

For decision trees:

Tree Depth Bias Variance Typical Behavior
Very shallow (depth=1-2) High Low Underfits, misses patterns
Moderate (depth=4-6) Medium Medium Sweet spot!
Very deep (depth>10) Low High Overfits, memorizes noise

Goal: Find the depth that minimizes total error = Bias² + Variance

5.5 Hyperparameters for Controlling Overfitting

Fortunately, sklearn provides several "knobs" to control tree complexity:

5.5.1 max_depth

What it does: Limits maximum depth of the tree

Effect:

Typical values: 3-10 for most problems

Example:

clf = DecisionTreeClassifier(max_depth=5, random_state=42)

5.5.2 min_samples_split

What it does: Minimum number of samples required to split a node

Effect:

Typical values: 2-50

Example:

clf = DecisionTreeClassifier(min_samples_split=20, random_state=42)

5.5.3 min_samples_leaf

What it does: Minimum number of samples required in each leaf node

Effect:

Typical values: 1-20

Example:

clf = DecisionTreeClassifier(min_samples_leaf=5, random_state=42)

Relationship: min_samples_split must be at least 2 × min_samples_leaf

5.5.4 max_features

What it does: Number of features to consider when looking for the best split

Effect:

Typical values:

Example:

clf = DecisionTreeClassifier(max_features='sqrt', random_state=42)

Note: This is more commonly used with Random Forests (covered in optional section).

5.5.5 min_impurity_decrease

What it does: Minimum impurity decrease required to make a split

Effect:

Typical values: 0.0-0.01

Example:

clf = DecisionTreeClassifier(min_impurity_decrease=0.01, random_state=42)

5.6 Practical Guidelines

Start here:

clf = DecisionTreeClassifier(
    max_depth=5,
    min_samples_split=10,
    min_samples_leaf=5,
    random_state=42
)

Then tune based on results:

Always remember:

6. Hyperparameter Tuning & Best Practices

How do we find the best hyperparameters systematically?

6.1 Cross-Validation Review

Problem: A single train/test split might be lucky (or unlucky)

Solution: K-fold cross-validation

How it works:

  1. Split data into KK equal parts (folds)
  2. Train KK times, each time using a different fold as the test set
  3. Average the KK test scores

Visual:

Fold 1: [Test] [Train] [Train] [Train] [Train]
Fold 2: [Train] [Test] [Train] [Train] [Train]
Fold 3: [Train] [Train] [Test] [Train] [Train]
Fold 4: [Train] [Train] [Train] [Test] [Train]
Fold 5: [Train] [Train] [Train] [Train] [Test]

sklearn implementation:

from sklearn.model_selection import cross_val_score

clf = DecisionTreeClassifier(max_depth=5, random_state=42)
scores = cross_val_score(clf, X, y, cv=5)
print(scores)
print(scores.mean())

Example output:

[0.867 0.900 0.867 0.933 0.900]
0.893

Interpretation: The model achieves about 89.3% accuracy on average. This gives us much more confidence than a single 90% test accuracy!

6.2 Grid Search for Hyperparameter Tuning

Problem: Too many hyperparameters to try manually!

Solution: Grid Search - systematically try all combinations

How it works:

  1. Define a grid of hyperparameter values
  2. Try every combination
  3. Use cross-validation to evaluate each
  4. Return the best combination

sklearn implementation:

from sklearn.model_selection import GridSearchCV

param_grid = {
    'max_depth': [3, 5, 7, 10],
    'min_samples_split': [2, 10, 20],
    'min_samples_leaf': [1, 5, 10]
}

grid = GridSearchCV(
    DecisionTreeClassifier(random_state=42),
    param_grid,
    cv=5
)

grid.fit(X_train, y_train)
print(grid.best_params_)
print(grid.best_score_)

best_clf = grid.best_estimator_
print(best_clf.score(X_test, y_test))

Example output:

{'max_depth': 5, 'min_samples_leaf': 5, 'min_samples_split': 10}
0.892
0.907

How many models did we train?

Tips:

6.3 When to Use Decision Trees

Decision trees are not always the best choice. Here's when they shine and when they struggle:

Advantages ✓

  1. Highly interpretable

    • Can explain any prediction
    • Essential for regulated industries

  2. No feature scaling needed

    • Works with raw features
    • One less preprocessing step!

  3. Handles mixed data types

    • Numerical and categorical features

  4. Non-linear by nature

    • Captures complex interactions automatically

  5. Fast training and prediction

    • Training: O(nlog⁡n⋅d⋅depth)O(n \log n \cdot d \cdot \text{depth})
    • Prediction: O(depth)O(\text{depth})

  6. Automatic feature selection

    • Unimportant features naturally get ignored

Disadvantages ✗

  1. High variance (unstable)

    • Small changes in training data → completely different tree

  2. Prone to overfitting

    • Will memorize training data if not carefully regularized

  3. Axis-aligned boundaries only

    • Can't represent diagonal decision boundaries efficiently

  4. Biased with imbalanced classes

    • Tends to favor majority class

  5. Not globally optimal

    • Greedy algorithm might miss better overall tree

  6. Extrapolation is poor

    • Can't predict outside the range of training data

6.4 Comparison with Previous Methods

How do decision trees compare to methods we've learned?

Aspect Logistic Regression LDA/QDA Decision Trees
Decision boundary Linear Linear/Quadratic Axis-aligned, complex
Assumptions Linear in log-odds Gaussian None
Interpretability High Medium High
Feature scaling Required Not strictly Not required
Non-linearity Manual Quadratic only (QDA) Automatic
Overfitting tendency Low Low High

Rule of thumb:

6.5 Practical Tips

1. Start with a shallow tree

clf = DecisionTreeClassifier(max_depth=3, random_state=42)

2. Always visualize (if not too large)

from sklearn.tree import plot_tree
plot_tree(clf, filled=True)

3. Check feature importances

print(clf.feature_importances_)

4. Use cross-validation

from sklearn.model_selection import cross_val_score
scores = cross_val_score(clf, X, y, cv=5)

5. Monitor both training and test

print(clf.score(X_train, y_train))
print(clf.score(X_test, y_test))

6. Consider ensemble methods if single tree underperforms (covered in optional section for MPS439)

7. Real-World Example

Let's apply everything we've learned to a complete real-world problem!

7.1 Dataset: Wine Quality Classification

Source: UCI Machine Learning Repository / sklearn built-in datasets

Task: Predict wine quality category from chemical properties

Features: 13 chemical measurements

Target: 3 wine classes (cultivar types)

Samples: 178 wines

7.2 Complete Workflow

Step 1: Load and Explore Data 

from sklearn.datasets import load_wine
import numpy as np

wine = load_wine()
X, y = wine.data, wine.target

print(X.shape)
print(wine.feature_names)
print(wine.target_names)
print(np.bincount(y))

Output:

(178, 13)
['alcohol', 'malic_acid', 'ash', ...]
['class_0' 'class_1' 'class_2']
[59 71 48]

Observations:

Step 2: Train/Test Split 

from sklearn.model_selection import train_test_split

X_train, X_test, y_train, y_test = train_test_split(
    X, y, test_size=0.3, random_state=42
)

print(len(X_train), len(X_test))

Output:

124 54

Step 3: Train a Simple Tree 

from sklearn.tree import DecisionTreeClassifier

clf_simple = DecisionTreeClassifier(max_depth=3, random_state=42)
clf_simple.fit(X_train, y_train)

print(clf_simple.score(X_train, y_train))
print(clf_simple.score(X_test, y_test))

Output:

0.960
0.907

Analysis: Good baseline! 96% train, 91% test. Small gap suggests we're not overfitting badly.

Step 4: Hyperparameter Tuning 

from sklearn.model_selection import GridSearchCV

param_grid = {
    'max_depth': [2, 3, 4, 5, 7],
    'min_samples_split': [2, 5, 10],
    'min_samples_leaf': [1, 2, 4]
}

grid = GridSearchCV(
    DecisionTreeClassifier(random_state=42),
    param_grid,
    cv=5
)

grid.fit(X_train, y_train)
print(grid.best_params_)
print(grid.best_score_)

best_clf = grid.best_estimator_
print(best_clf.score(X_test, y_test))

Output:

{'max_depth': 4, 'min_samples_leaf': 2, 'min_samples_split': 2}
0.919
0.926

Analysis: Tuning improved test accuracy from 90.7% to 92.6%!

Step 5: Analyze Feature Importance 

importances = best_clf.feature_importances_
feature_names = wine.feature_names

for i in np.argsort(importances)[::-1]:
    if importances[i] > 0:
        print(feature_names[i], importances[i])

Typical output:

flavanoids 0.421
proline 0.267
color_intensity 0.154
od280/od315_of_diluted_wines 0.089
alcohol 0.069

Interpretation:

Step 6: Visualize Performance 

from sklearn.metrics import confusion_matrix

y_pred = best_clf.predict(X_test)
cm = confusion_matrix(y_test, y_pred)
print(cm)

Output:

[[17  1  0]
 [ 1 19  1]
 [ 0  1 14]]

Interpretation: Most errors are between class_1 and class_2

7.3 Interpretation of Results

What did the tree learn?

From feature importances:

"The decision tree primarily uses flavanoid content to distinguish wines. High flavanoids strongly suggest class_0. For wines with moderate flavanoids, proline content becomes the key discriminator. Finally, color intensity helps separate remaining cases."

This is the kind of interpretable insight that makes decision trees valuable!

Could we have done better?

Probably! Some options:

  1. Feature engineering
  2. Deeper tree (but watch for overfitting!)
  3. Ensemble methods (covered in optional section)
  4. More data

But 93% accuracy is already quite good!

7.4 Practical Lessons

From this example, we learned:

  1. Always start simple: The baseline tree (depth=3) gave 91% accuracy
  2. Tune systematically: Grid search improved us to 93%
  3. Interpret carefully: Understanding why the model works is important
  4. Context matters: 93% accuracy might be excellent or terrible depending on application

8. [OPTIONAL - MPS439] Beyond Single Trees: Ensemble Methods

Note: This section is optional and targeted at MPS439 students. If you're in MPS311, feel free to skip this section or read it for enrichment!

8.1 The Problem with Single Trees

We've seen that single decision trees have a major flaw: high variance.

What does high variance mean?

Example: Train the same tree 10 times with slightly different random subsamples:

The key insight: What if we could reduce this variance by combining multiple trees?

8.2 Ensemble Learning: The Big Idea

Ensemble learning means combining predictions from multiple models to get better overall performance.

Intuition: "Wisdom of crowds"

For decision trees:

Two main approaches:

  1. Bagging (Bootstrap Aggregating): Train trees on random subsets of data
  2. Boosting: Train trees sequentially, each correcting previous mistakes

8.3 Random Forests: Democracy of Trees

Random Forest is the most popular bagging method for decision trees.

8.3.1 How Random Forests Work

Algorithm (simplified):

1. Create N "bootstrap" datasets by sampling with replacement
2. For each dataset:
   a. Train a decision tree
   b. When splitting nodes, only consider random subset of features
3. To predict:
   - Classification: Vote from all trees (majority wins)
   - Regression: Average predictions from all trees

Key features:

Why does this work?

8.3.2 Implementation in sklearn

Random Forests are incredibly easy to use in sklearn:

from sklearn.ensemble import RandomForestClassifier

rf = RandomForestClassifier(n_estimators=100, random_state=42)
rf.fit(X_train, y_train)

print(rf.score(X_train, y_train))
print(rf.score(X_test, y_test))

Key parameters:

That's it! Random Forests are almost as easy as single trees.

8.3.3 Complete Example 

from sklearn.ensemble import RandomForestClassifier
from sklearn.datasets import load_wine
from sklearn.model_selection import train_test_split

wine = load_wine()
X, y = wine.data, wine.target

X_train, X_test, y_train, y_test = train_test_split(
    X, y, test_size=0.3, random_state=42
)

rf = RandomForestClassifier(n_estimators=100, random_state=42)
rf.fit(X_train, y_train)

print(rf.score(X_train, y_train))
print(rf.score(X_test, y_test))

print(rf.feature_importances_)

Typical output:

1.000
0.963
[0.112 0.029 0.012 0.032 0.025 0.051 0.144 0.011 0.031 0.152 0.096 0.131 0.174]

Observations:

8.3.4 Pros and Cons

Advantages ✓:

Disadvantages ✗:

8.4 Gradient Boosting: Sequential Improvement

Gradient Boosting is a different ensemble approach. Instead of training trees independently (bagging), we train them sequentially, each trying to correct the previous tree's mistakes.

8.4.1 The Core Idea

Intuition: "Learn from mistakes"

Algorithm (simplified):

1. Train a shallow tree on the data
2. Find samples where this tree makes errors
3. Train a new tree focusing on those errors
4. Add this tree to the ensemble (with small weight)
5. Repeat steps 2-4 for N iterations
6. Final prediction = weighted sum of all trees

Key differences from Random Forest:

8.4.2 Why "Gradient" Boosting?

The "gradient" comes from optimization theory:

You don't need to understand the math deeply - just know that it's a principled way to build sequential ensembles.

8.4.3 XGBoost: The State-of-the-Art

XGBoost (eXtreme Gradient Boosting) is the most popular and powerful gradient boosting implementation.

Why XGBoost dominates:

Installation:

pip install xgboost

Basic usage:

import xgboost as xgb

xgb_clf = xgb.XGBClassifier(n_estimators=100, max_depth=5, random_state=42)
xgb_clf.fit(X_train, y_train)

print(xgb_clf.score(X_train, y_train))
print(xgb_clf.score(X_test, y_test))

Key parameters:

8.4.4 Complete XGBoost Example 

import xgboost as xgb
from sklearn.datasets import load_wine
from sklearn.model_selection import train_test_split

wine = load_wine()
X, y = wine.data, wine.target

X_train, X_test, y_train, y_test = train_test_split(
    X, y, test_size=0.3, random_state=42
)

xgb_clf = xgb.XGBClassifier(
    n_estimators=100,
    max_depth=5,
    learning_rate=0.1,
    random_state=42
)

xgb_clf.fit(X_train, y_train)

print(xgb_clf.score(X_train, y_train))
print(xgb_clf.score(X_test, y_test))

Typical output:

1.000
0.981

Wow! 98.1% test accuracy vs 96.3% for Random Forest vs 93% for single tree!

8.4.5 Tuning XGBoost

XGBoost has many parameters. Here's a practical tuning strategy:

Step 1: Tune number of trees with early stopping

xgb_clf = xgb.XGBClassifier(
    n_estimators=1000,
    max_depth=5,
    learning_rate=0.1,
    random_state=42
)

xgb_clf.fit(
    X_train, y_train,
    eval_set=[(X_test, y_test)],
    verbose=False
)

print(xgb_clf.best_iteration)

This automatically finds the optimal number of trees.

Step 2: Tune tree depth and learning rate

from sklearn.model_selection import GridSearchCV

param_grid = {
    'max_depth': [3, 5, 7],
    'learning_rate': [0.01, 0.1, 0.3]
}

grid = GridSearchCV(
    xgb.XGBClassifier(n_estimators=100, random_state=42),
    param_grid,
    cv=5
)

grid.fit(X_train, y_train)
print(grid.best_params_)

Step 3: Fine-tune other parameters (if needed)

Usually the defaults work well!

8.5 Comparison: Single Tree vs Random Forest vs XGBoost

Let's compare all three methods on the wine dataset:

from sklearn.tree import DecisionTreeClassifier
from sklearn.ensemble import RandomForestClassifier
import xgboost as xgb
from sklearn.datasets import load_wine
from sklearn.model_selection import train_test_split

wine = load_wine()
X, y = wine.data, wine.target
X_train, X_test, y_train, y_test = train_test_split(
    X, y, test_size=0.3, random_state=42
)

# Single tree
dt = DecisionTreeClassifier(max_depth=5, random_state=42)
dt.fit(X_train, y_train)
print("Decision Tree:", dt.score(X_test, y_test))

# Random Forest
rf = RandomForestClassifier(n_estimators=100, random_state=42)
rf.fit(X_train, y_train)
print("Random Forest:", rf.score(X_test, y_test))

# XGBoost
xgb_clf = xgb.XGBClassifier(n_estimators=100, random_state=42)
xgb_clf.fit(X_train, y_train)
print("XGBoost:", xgb_clf.score(X_test, y_test))

Typical results:

Decision Tree: 0.926
Random Forest: 0.963
XGBoost: 0.981

Summary:

Method Test Accuracy Interpretability Training Time Prediction Speed
Decision Tree 92.6% ⭐⭐⭐⭐⭐ Fast Fastest
Random Forest 96.3% ⭐⭐⭐ Medium Slow
XGBoost 98.1% ⭐⭐⭐ Slow Medium

8.6 When to Use Each Method

Use Single Decision Tree when:

Use Random Forest when:

Use XGBoost when:

Example use cases:

8.7 Learning Resources for MPS439

To go deeper with ensemble methods:

XGBoost Documentation:

Kaggle:

Key Papers:

Books:

Practice Tips:

  1. Start with Random Forest (easy, robust)
  2. Move to XGBoost when you need extra accuracy
  3. Always compare to single tree baseline
  4. Tune systematically with grid search

9. Summary & Looking Ahead

9.1 Key Takeaways

Let's recap what we've learned about decision trees:

Core Concepts:

  1. ✅ Decision trees make predictions through hierarchical yes/no questions
  2. ✅ Trees are built greedily by choosing splits that maximize purity (minimize Gini/entropy)
  3. ✅ Trees are highly interpretable - you can visualize and explain any prediction
  4. ✅ Trees are prone to overfitting - they memorize training data if not constrained
  5. ✅ Hyperparameters like max_depth control model complexity
  6. ✅ Feature importance tells us which features drive predictions

Practical Skills Acquired (MPS311):

Advanced Skills Acquired (MPS439):

9.2 Limitations and Strengths

When Decision Trees Excel ✨:

When Trees Struggle 🚧:

The Solution (for MPS439): Ensemble methods!

9.3 The Bigger Picture

Where we've been (Supervised Learning - Weeks 2-6):

Linear Methods              Non-linear Methods
     |                            |
     |--- Linear Regression       |--- Decision Trees
     |--- Logistic Regression     |--- Random Forests (optional)
     |--- LDA/QDA                 |--- XGBoost (optional)
     |
     └→ Simple, interpretable, assume linearity
                                  └→ Complex, flexible, no assumptions

The supervised learning landscape:

9.4 Looking Ahead: Week 8 - PCA

Big transition: From supervised to unsupervised learning!

What changes:

Week 8: Principal Component Analysis (PCA)

The new challenge:

PCA's answer:

Connection to decision trees:

What to review before Week 8:

9.5 Before Next Week

Practice what you learned:

For everyone (MPS311):

  1. Try decision trees on a new dataset

  2. Experiment with hyperparameters

    • What happens when you vary max_depth?
    • How does min_samples_leaf affect overfitting?

  3. Visualize your trees

    • Use plot_tree() to understand what it learned
    • Interpret feature importances

For MPS439 students:

  1. Apply XGBoost to a Kaggle competition

    • Start with "tabular" competitions
    • Compare single tree vs Random Forest vs XGBoost

  2. Try hyperparameter tuning

    • Use grid search
    • Document what works and why

  3. Read the XGBoost paper (optional)

    • Chen & Guestrin (2016)

Prepare for PCA:

  1. Review eigenvalues/eigenvectors
  2. Refresh matrix operations
  3. Think about: "What makes a direction 'important' in data?"

Additional Resources

For All Students (MPS311)

sklearn Documentation:

Interactive Visualizations:

Books:

Videos:

For MPS439 Students

XGBoost Resources:

Papers:

Kaggle:

Advanced Topics (if interested):

Quick Reference Card

Key Formulas:

Gini Impurity:
Gini(N)=1−∑i=1Kpi2\text{Gini}(N) = 1 - \sum_{i=1}^{K} p_i^2

Entropy:
Entropy(N)=−∑i=1Kpilog⁡2(pi)\text{Entropy}(N) = -\sum_{i=1}^{K} p_i \log_2(p_i)

Weighted Impurity:
Ginisplit=nleftnGini(Nleft)+nrightnGini(Nright)\text{Gini}_{\text{split}} = \frac{n_{\text{left}}}{n} \text{Gini}(N_{\text{left}}) + \frac{n_{\text{right}}}{n} \text{Gini}(N_{\text{right}})

Key Code Snippets:

# Train tree
from sklearn.tree import DecisionTreeClassifier
clf = DecisionTreeClassifier(max_depth=5, random_state=42)
clf.fit(X_train, y_train)

# Visualize
from sklearn.tree import plot_tree
plot_tree(clf, filled=True)

# Feature importance
importances = clf.feature_importances_

# Grid search
from sklearn.model_selection import GridSearchCV
grid = GridSearchCV(clf, param_grid, cv=5)
grid.fit(X_train, y_train)

# Random Forest (MPS439)
from sklearn.ensemble import RandomForestClassifier
rf = RandomForestClassifier(n_estimators=100)

# XGBoost (MPS439)
import xgboost as xgb
xgb_clf = xgb.XGBClassifier(n_estimators=100)

End of Week 6 Lecture Notes

Next week: Principal Component Analysis (PCA) - Dimensionality Reduction

MPS311/439 - Machine Learning
Dr. Wei Xing
University of Sheffield
November 2025