MSc Machine Learning | Week 4: Classification Algorithms | Teaching Note

MSC MACHINE LEARNING

WEEK 4: CLASSIFICATION ALGORITHMS

Topics: Logistic Regression | k-Nearest Neighbors (kNN) | Decision Trees

1. Logistic Regression
What is it? Despite having the word 'regression' in its name, Logistic Regression is a
classification algorithm. This is a common point of confusion for beginners — so address it
directly. The algorithm predicts the probability that an input belongs to a particular class, such as
yes/no, 0/1, spam/not-spam. Because it outputs a probability (a number between 0 and 1), we apply
a threshold — typically 0.5 — to make the final class decision.

The Core Intuition

Think of Logistic Regression as a smart probability calculator. It takes a set of input features,
applies weights to them (learned from data), and produces a score. That score is then passed
through a mathematical function called the Sigmoid that converts any number into a probability
between 0 and 1.

REAL-LIFE ANALOGY: THE DOCTOR'S RISK SCORE

Imagine you are a doctor screening patients for a heart condition. You collect information
about each patient: their age, blood pressure, BMI, cholesterol level, and whether they
smoke. Instead of immediately saying 'this person has heart disease' or 'they don't', a good
doctor first calculates a risk score — a probability — before making a decision.
For example: 'This 55-year-old male with high cholesterol and hypertension has an 82%
chance of developing heart disease in the next 10 years, so I classify him as high-risk and
recommend treatment.' That probability — the 82% — is exactly what Logistic Regression
computes. The doctor's threshold (perhaps 70%) acts as the decision boundary.
The beauty of this output is that it is not just a yes/no — it carries confidence. A probability
of 51% means the model is barely sure. A probability of 97% means the model is very
confident. This is valuable in real-world decision-making.

How It Works: Step-by-Step

1. Compute a weighted sum (the linear part): The model takes each input feature and
multiplies it by a learned weight, then adds them all up. For example: Z = (0.04 x Age) + (0.3
x BMI) + (-0.5 x Exercise_Hours) + 0.8. This value Z can range from negative infinity to
positive infinity. It is essentially a raw 'risk score' before bounding.
2. Apply the Sigmoid function: To convert Z into a probability, we pass it through the
Sigmoid function: sigma(Z) = 1 / (1 + e^-Z). When Z is very large and positive, sigma(Z)

Week 4 | Classification Algorithms | Page 1 of 12

MSc Machine Learning | Week 4: Classification Algorithms | Teaching Note

approaches 1 (high probability). When Z is very large and negative, sigma(Z) approaches 0
(low probability). When Z = 0, sigma(Z) = 0.5 exactly. This S-shaped curve is what gives the
algorithm its name.
3. Apply a decision threshold: If the probability is >= 0.5, we classify the point as Class 1
(e.g., 'at risk'). If < 0.5, we classify it as Class 0 (e.g., 'healthy'). The threshold can be
adjusted — in medicine, we may lower it to 0.3 to catch more at-risk patients, accepting
more false positives to avoid missing true positives.
4. Learn the weights through training: The model learns the optimal weights using an
optimization technique called Gradient Descent. It minimises a loss function called Log-Loss
(also called Cross-Entropy), which penalises confident wrong predictions more heavily than
uncertain wrong ones. For example, predicting 99% probability when the true answer is 0 is
punished far more than predicting 55% when the answer is 0.

KEY MATHEMATICS
The Linear Combination: Z = w0 + w1*x1 + w2*x2 + ... + wn*xn
The Sigmoid Function: sigma(Z) = 1 / (1 + e^-Z)
Final prediction: if sigma(Z) >= 0.5 --> Class 1, else -->
Class 0
Log-Loss (training): L = -[y*log(y_hat) + (1-y)*log(1-y_hat)]

TEACHING TIP

Draw the sigmoid curve on the whiteboard. Mark the x-axis as Z (the raw score) and the y-
axis as Probability. Show how the curve flattens at both extremes: very negative Z gives
almost 0, very positive Z gives almost 1. Ask: 'Why can we not just use a straight line (linear
regression) to predict 0 or 1?' This leads to an excellent discussion. Key answers: a straight
line can predict values above 1 and below 0, which makes no sense for probabilities. The
sigmoid elegantly solves this.

Strengths and Limitations

Strengths Limitations
• Outputs interpretable probabilities, not • Only draws a straight-line (linear)
just labels decision boundary
• Very fast to train, even on millions of • Cannot capture complex, curved, or non-
examples linear patterns
• Works well when classes are linearly • Sensitive to outliers in the data
separable • Requires feature scaling for best
• Coefficients reveal which features matter performance
most

Week 4 | Classification Algorithms | Page 2 of 12

MSc Machine Learning | Week 4: Classification Algorithms | Teaching Note

• Low overfitting risk with regularisation • Assumes features are independent of

(L1, L2) each other
• Works well as a strong baseline model • Not ideal for highly imbalanced class
distributions

Real-World Applications
• Email spam detection — classifying emails as spam or not spam
• Credit default prediction — will this borrower repay the loan?
• Medical diagnosis — does this patient have the disease?
• Customer churn prediction — will this customer leave next month?
• Ad click-through rate — will this user click the advertisement?
• Fraud detection — is this transaction fraudulent?

Week 4 | Classification Algorithms | Page 3 of 12

MSc Machine Learning | Week 4: Classification Algorithms | Teaching Note

2. k-Nearest Neighbors (kNN)

What is it? k-Nearest Neighbors is one of the most intuitive and visually understandable
algorithms in all of machine learning. The idea is beautifully simple: to classify a new data point,
look at the k most similar training examples and let them vote. Whichever class has the most
votes wins. There is no explicit 'training phase' — the algorithm simply memorises all the training
data and uses it at prediction time.

The Core Intuition

The key concept is similarity: data points that are close together in feature space tend to belong to
the same class. 'Close' is measured using a distance metric, most commonly Euclidean distance
(the straight-line distance between two points). The algorithm finds the k closest training points to
the new input and counts the votes.

REAL-LIFE ANALOGY: LAGOS RESTAURANT ADVICE

Imagine you just moved to a new part of Lagos and there is a restaurant you have never
visited. You do not have access to Google Reviews. What do you do? You ask your five
nearest neighbours — the people who live closest to you and know the neighbourhood best.
You ask five neighbours: 4 say 'Yes, excellent food! I go every week.' One says 'I went once
and was not impressed.' Based on majority vote (4 out of 5), you decide to try the
restaurant.
That is kNN in action. Your 'feature space' is the neighbourhood. 'Distance' is how close
your neighbours live to you. k=5 means you ask 5 people. The majority vote gives your
classification. Now imagine you only ask the single closest neighbour (k=1) — they might be
the one person who had a bad experience, and you would make a worse decision. This is
why choosing k carefully matters!

How It Works: Step-by-Step

1. Store all training data: Unlike most algorithms, kNN has no training phase. It simply stores
every training example in memory. This is why it is called a 'lazy learner' — it does all the
work at prediction time, not training time.
2. Receive a new data point: When a new unlabeled point arrives (e.g., a new patient, a new
email), we need to compute its distance to every single point in the training set.
3. Calculate distances: Using a distance metric (usually Euclidean), we compute how far the
new point is from each training point. IMPORTANT: features must be scaled before this
step, otherwise a feature with large values (like salary) will dominate over a feature with
small values (like age), distorting the distances.
4. Identify the k nearest neighbours: Sort all training points by their distance to the new point
and pick the k smallest distances. These are the 'nearest neighbours'.

Week 4 | Classification Algorithms | Page 4 of 12

MSc Machine Learning | Week 4: Classification Algorithms | Teaching Note

5. Majority vote: Count how many of the k neighbours belong to each class. The class with
the most votes is the prediction. In case of a tie, common strategies include picking the
class of the single nearest neighbour or choosing randomly.

KEY MATHEMATICS
Euclidean Distance (most common): d(A,B) = sqrt((x1-x2)^2 + (y1-
y2)^2 + ...)
Manhattan Distance (alternative): d(A,B) = |x1-x2| + |y1-y2| + ...
Final prediction: y_hat = mode(class of k nearest
neighbours)

THE BIAS-VARIANCE TRADEOFF WITH K

k = 1 (very small): The model uses only the single nearest neighbour. This creates a very
complex, jagged decision boundary that fits every training point exactly. Result: very low
bias (fits training data perfectly) but very high variance (sensitive to noise, poor on new
data). This is called OVERFITTING.
k = large (e.g., k = 100): The model considers many neighbours, creating a smooth
decision boundary. Result: lower variance but higher bias — it may oversimplify and miss
real patterns. This is called UNDERFITTING.
Optimal k: Found using cross-validation. Typically, odd values of k are preferred to avoid
ties. A common starting point is k = sqrt(n) where n is the number of training samples.

TEACHING TIP — BOARD ACTIVITY

Draw 10 points on the board: 5 circles (Class A) clustered on the left, 5 squares (Class B)
clustered on the right. Plot a new point somewhere in the middle. Ask students: 'If k=1,
which class do we predict? What about k=3? k=5? k=10?' This immediately and visually
demonstrates how k controls the sensitivity of the model. Then ask: 'What if one feature is
age (0-80) and another is annual salary (0-10,000,000)? Which feature will dominate the
distance calculation and why?' This motivates the critical need for feature scaling.

Strengths and Limitations

Strengths Limitations
• Extremely simple and highly intuitive • Slow at prediction time: checks all
• No training time needed — instant to set training points
up • Very sensitive to feature scaling —

Week 4 | Classification Algorithms | Page 5 of 12

MSc Machine Learning | Week 4: Classification Algorithms | Teaching Note

• Naturally handles multi-class problems MUST normalise

• Non-parametric: no assumptions about • High memory usage: stores all training
data shape data
• Adapts to complex, non-linear decision • Suffers from 'curse of dimensionality' in
boundaries high dimensions
• Easy to update with new training data • Choosing k requires careful tuning via
cross-validation
• Sensitive to irrelevant or noisy features

Real-World Applications
• Recommendation systems — suggesting movies, music, or products
• Handwriting recognition — identifying handwritten digits
• Medical classification — grouping patients by symptom similarity
• Anomaly detection — finding unusual patterns in data
• Face recognition — matching a new face to known faces

Week 4 | Classification Algorithms | Page 6 of 12

MSc Machine Learning | Week 4: Classification Algorithms | Teaching Note

3. Decision Trees
What is it? A Decision Tree is an algorithm that classifies data by learning a series of yes/no
questions about the input features. Starting from a single root node, the tree recursively splits the
data based on the most informative feature at each step. Each internal node is a question, each
branch is an answer, and each leaf node is a final class prediction.

The Core Intuition

Decision Trees mimic how humans naturally make decisions — through a series of logical,
sequential choices. What makes them powerful is that the computer learns which questions to ask
and in what order, purely from the training data. The goal at each step is to ask the question that
creates the cleanest separation between classes.

REAL-LIFE ANALOGY: MEDICAL TRIAGE

Imagine a doctor doing rapid triage in an emergency room. They don't examine everything
at once. They ask structured questions in a specific order:
First question: 'Is the patient's temperature above 38°C?'
If YES, ask: 'Does the patient have a rash on the skin?'
If YES to rash: 'Is it a specific type of rash?' --> Likely Measles. Quarantine immediately.
If NO rash: 'Is there a severe sore throat?' --> If YES: Likely Strep Throat. Prescribe
antibiotics.
If NO to fever: 'Is there chest pain?' --> If YES: Possible cardiac event. Run ECG
immediately.
Notice how each question splits the patients into smaller and smaller groups until a clear
diagnosis emerges. A Decision Tree does exactly this — but it learns the best questions
and order automatically from historical patient data, rather than relying on a human expert
to specify them.

CONCRETE EXAMPLE: SHOULD WE APPROVE THIS LOAN?

Consider a bank that wants to automate loan decisions. The training data contains
thousands of past applications with features like Credit Score, Employment Status, Annual
Income, and Existing Debt, with labels 'Approved' or 'Denied'.
The Decision Tree might learn this structure:
Root Question: Is Credit Score > 700?
--> NO: Ask: Is the applicant currently employed?
--> NO: DENY (high risk, poor credit, no income)
--> YES: APPROVE (employed, manageable risk)

Week 4 | Classification Algorithms | Page 7 of 12

MSc Machine Learning | Week 4: Classification Algorithms | Teaching Note

--> YES: Ask: Is Annual Income > 5,000,000 Naira?

--> NO: DENY (good credit but income is borderline)
--> YES: APPROVE (strong profile, low risk)

How It Works: Step-by-Step

1. Start at the root with all training data: All training samples begin at the root node. The
algorithm now needs to find the single best feature and the best split point (threshold) that
divides the data as cleanly as possible into classes.
2. Evaluate all possible splits: For every feature (e.g., Age, Income, Credit Score) and every
possible threshold value, the algorithm calculates how 'pure' the resulting child nodes would
be. Purity means how dominated they are by a single class. For example, a node containing
100 'Approve' and 0 'Deny' decisions is perfectly pure.
3. Select the best split using Gini Impurity or Entropy: The algorithm picks the split that
maximises the reduction in impurity (called Information Gain). Gini = 0 means perfectly pure
(only one class). Gini = 0.5 means maximally mixed (equal classes). The algorithm always
chooses the split that produces the lowest Gini in the children.
4. Recursively repeat on each child node: Each child node becomes a new parent node,
and the process repeats: find the best split among the remaining samples. This continues
until a stopping condition is met: maximum tree depth reached, minimum number of
samples in a node, or no further improvement possible.
5. Predict on new data: To classify a new data point, start at the root and follow the branches
by answering each question (Is Age > 40? Is Income > 5M?) until you reach a leaf node.
The leaf's majority class is the prediction.

KEY MATHEMATICS: GINI IMPURITY — WORKED EXAMPLE

Gini Impurity Formula: Gini(t) = 1 - sum( p(ci)^2 )
Example: A node has 10 loan applications: 7 Approved, 3 Denied.
p(Approved) = 7/10 = 0.7, p(Denied) = 3/10 = 0.3
Gini = 1 - (0.7^2 + 0.3^2) = 1 - (0.49 + 0.09) = 1 - 0.58 = 0.42
Now suppose we split on Credit Score > 700:
Left child (Credit <= 700): 1 Approved, 3 Denied --> Gini = 1 -
(0.25^2 + 0.75^2) = 0.375
Right child (Credit > 700): 6 Approved, 0 Denied --> Gini = 1 -
(1.0^2 + 0.0^2) = 0.0 (PERFECT!)
Weighted Gini after split = (4/10)*0.375 + (6/10)*0.0 = 0.15. Information Gain = 0.42 - 0.15 =
0.27. This is a very good split! Walk through this on the board to make the math tangible.

Week 4 | Classification Algorithms | Page 8 of 12

MSc Machine Learning | Week 4: Classification Algorithms | Teaching Note

TEACHING TIP — OVERFITTING DEMONSTRATION

Train a Decision Tree to 100% accuracy on training data by setting no depth limit. Then
show its performance on test data drops to perhaps 60-70%. Ask: 'What is happening?'
Answer: the tree has memorised noise in the training data — it has become so specific to
the training set that it cannot generalise. Then apply max_depth=3 and show how test
accuracy improves dramatically. This is one of the clearest demonstrations of overfitting in
all of machine learning.

Strengths and Limitations

Strengths Limitations
• Highly interpretable: humans can follow • Prone to overfitting if tree grows too
the logic visually deep (must prune)
• No feature scaling required • High variance: small data changes alter
• Handles both numeric and categorical the tree structure
features naturally • Can be biased towards features with
• Automatically selects the most important more possible split values
features • Does not capture smooth probability
• Fast at prediction time: just traverse the transitions well
tree • A single tree rarely outperforms
• Foundation for powerful ensemble ensemble methods
methods (Random Forest, XGBoost) • Requires careful tuning of max_depth
and min_samples

Real-World Applications
• Loan and credit approval systems at banks and fintechs
• Medical triage and diagnostic decision support systems
• Customer segmentation and targeted marketing
• Fault diagnosis in engineering and manufacturing
• Insurance risk assessment and pricing
• HR screening: should this candidate proceed to interview?

Week 4 | Classification Algorithms | Page 9 of 12

MSc Machine Learning | Week 4: Classification Algorithms | Teaching Note

4. Side-by-Side Comparison
Use this table to help students understand when to use each algorithm and what trade-offs they are
making. There is no universally best algorithm — the right choice depends on the data, the
problem, and the constraints (speed, interpretability, accuracy requirements).

Property Logistic Regression k-Nearest Neighbors Decision Tree

Core Idea Probability via sigmoid Majority vote of k nearest Series of yes/no questions
function neighbours

Training Speed Fast (gradient descent) Instant (just stores all data) Medium (builds the tree
recursively)

Prediction Speed Very fast Slow (searches all training Very fast (traverse the tree)
points)

Interpretability Medium (check Low (just a vote count) High (visual flowchart,
coefficients) human-readable)

Feature Scaling Yes (important) Yes (critical — must scale!) No (trees are scale-
Needed? invariant)

Decision Boundary Linear only (straight line) Non-linear, complex, Rectangular/stepped (axis-
Shape flexible parallel)

Handles Noise Yes — robust to outliers No — sensitive to noisy Medium — overfits without
Well? neighbours pruning

Risk of Overfitting Low (with regularisation) High (with k=1) High (without depth control)

Best For Baseline model, probability Small datasets, Explainability, tabular data
outputs recommendation

Key Regularisation strength (C) Number of neighbours (k) max_depth,

Hyperparameter min_samples_leaf

Memory Usage Low High (stores all data) Low (just the tree structure)

5. Discussion Questions for Students

Use these questions to test deeper understanding, provoke critical thinking, and generate
classroom debate. There is often no single correct answer — the quality of the student's reasoning
and justification matters most.

1. Fraud Detection at a Bank: You are building a model to detect fraudulent bank
transactions. The dataset is highly imbalanced: 99% of transactions are legitimate and only
1% are fraud. Which of the three algorithms would you start with and why? What accuracy

Week 4 | Classification Algorithms | Page 10 of 12

MSc Machine Learning | Week 4: Classification Algorithms | Teaching Note

metric would you use — and would raw accuracy (% correct) be a good metric here? What
trade-offs are you accepting with your chosen algorithm?

2. Hospital Explainability Requirement: A hospital wants a model to recommend whether a

patient should be admitted for further testing. The hospital's board insists the model must be
explainable to non-technical doctors who will use it daily. Which algorithm is most
appropriate? Which would you avoid and why? How would you explain the model's decision
to a doctor for a specific patient?

3. kNN Overfitting Diagnosis: Your kNN model achieves 97% accuracy on the training set
but only 64% on the test set. What is happening? How does your choice of k contribute to
this problem? Name two changes you could make to the model or data to improve test
accuracy.

4. Decision Tree Overfitting: A Decision Tree was trained on a student grade dataset with no
depth restriction. Its training accuracy is 100%, but its test accuracy is 58%. Explain
precisely what has happened in terms of what the tree has learned. What is the name for
this phenomenon? Describe two specific techniques to fix it.

5. Algorithm Selection Challenge: You have a dataset with 200 features (inputs). A domain
expert tells you that probably only 15 of those features are actually relevant to the
prediction. Which of the three algorithms would handle this scenario best, and which would
handle it worst? Explain your reasoning for each.

6. Key Takeaways
These are the core messages every student should be able to recall and explain after today's
session:

WHAT EVERY STUDENT MUST KNOW

1. Classification is about boundaries: Every algorithm draws a line — or curve, or set of

questions — that separates classes. Logistic Regression draws a straight line (linear
boundary). kNN draws a complex, flexible boundary shaped by the data. Decision Trees
draw a rectangular, stepped boundary. Understanding the shape of each boundary explains
when each algorithm will succeed and when it will fail.
2. No algorithm is universally the best: Logistic Regression is your reliable, interpretable
baseline. kNN is intuitive but computationally expensive. Decision Trees are explainable but
prone to overfitting. The right choice always depends on the data size, feature types, need
for interpretability, and computational constraints.
3. The bias-variance tradeoff is fundamental: kNN with k=1 is low bias, high variance
(overfits). Logistic Regression is medium bias, low variance. A deep Decision Tree is low

Week 4 | Classification Algorithms | Page 11 of 12

MSc Machine Learning | Week 4: Classification Algorithms | Teaching Note

bias, high variance (overfits). A shallow Decision Tree is high bias, low variance (underfits).
Every modelling decision moves you along this tradeoff — understanding this is the key to
building good models.
4. Decision Trees are the foundation of modern ML: Random Forest (many trees
averaged together) and XGBoost/Gradient Boosting (trees built sequentially to correct
errors) are among the most powerful and widely-used algorithms in industry. Both are built
on Decision Trees. If students truly understand Gini impurity, splits, and tree depth today,
they will find these advanced methods far more approachable next week.

BRIDGE TO NEXT WEEK

Next week we move to Ensemble Methods — Random Forest and Gradient Boosting —
which combine many Decision Trees to dramatically reduce overfitting while maintaining
interpretability. If students leave today with a solid understanding of how a single Decision
Tree works, how Gini impurity drives splits, and why deep trees overfit, they will be well
prepared. Consider setting a short reading exercise: ask students to look up what 'bagging'
and 'boosting' mean before the next lecture.

Week 4 | Classification Algorithms | Page 12 of 12