Module 2: Classification — Algorithms,

Regularisation & Evaluation

Course: PCCST503 – Machine Learning | Semester: S5 CSE
Contact Hours: 9 | CIE: 40 marks | ESE: 60 marks (Part A: 3 marks × 2 Qs; Part B: 9 marks
× 1 Q)

Learning Objectives
By the end of this module, students should be able to:

● Apply Logistic Regression for binary classification problems

● Implement Naïve Bayes, K-Nearest Neighbours, and Decision Tree (ID3) classifiers
● Explain and handle overfitting using LASSO and RIDGE regularisation
● Distinguish between training, testing, and validation sets
● Calculate and interpret classification evaluation metrics (Precision, Recall, F-Measure,
ROC, AUC) and regression metrics (MAE, RMSE, R²)

1. Classification
Classification is a supervised learning task where the output y is a discrete class label.

Examples:
● Predicting whether an email is spam (1) or not spam (0) → Binary classification
● Predicting the digit in an image (0-9) → Multiclass classification
● Diagnosing a disease as Type A, B, or C → Multiclass classification

1.1 Logistic Regression

Despite its name, Logistic Regression is used for classification, not regression.
Why Not Use Linear Regression for Classification?
Linear regression can output values outside [0, 1] (e.g., −3.5 or 2.7), which cannot be
interpreted as probabilities. We need a model that outputs values between 0 and 1.

The Sigmoid (Logistic) Function

1
σ (z)= −z
1+e

Properties:
● σ(z) → 1 as z → +∞
● σ(z) → 0.5 when z = 0
● σ(z) → 0 as z → −∞
● Always outputs values in (0, 1)

📌 [Insert graph: S-shaped sigmoid curve σ(z) vs z, with horizontal dashed lines at 0, 0.5,
and 1]

Logistic Regression Hypothesis

1
hθ (x )=σ (θT x )= T

1+ e− θ x

Interpretation: h_θ(x) = estimated probability that y = 1 given x

P( y =1∣ x ; θ)=hθ ( x), P ( y=0 ∣ x ; θ)=1− hθ (x )

Decision Boundary: Predict y=1 if hθ (x )≥ 0.5 (i.e.,θ T x ≥ 0 ¿

📌 [Insert 2D plot: Two classes (red/blue points) separated by a decision boundary line
(θ₀ + θ₁x₁ + θ₂x₂ = 0)]
Cost Function for Logistic Regression
We cannot use MSE because it is non-convex with the sigmoid — it has many local minima.
Instead, we use Cross-Entropy Loss:

Why this formula?

● When y = 1: Loss = −log(h_θ(x)) → 0 if h_θ(x) → 1 (correct); → ∞ if h_θ(x) → 0
(wrong)
● When y = 0: Loss = −log(1 − h_θ(x)) → 0 if h_θ(x) → 0 (correct); → ∞ if h_θ(x) → 1
(wrong)

This function is convex — guaranteed single global minimum.

Gradient Descent for Logistic Regression

m
1
θ j :=θ j − α ∑ (¿ hθ (x(i) )− y(i) )x (i)j ¿
m i=1

Interestingly, this looks identical to linear regression's update rule — but h_θ(x) is now the
sigmoid function.

Pseudocode:

def sigmoid(z):
return 1 / (1 + [Link](-z))

theta = [Link](n+1)
for iteration in range(max_iterations):
z = X_b @ theta # linear combination
h = sigmoid(z) # predicted probabilities

errors = h - y # prediction errors

gradient = (1/m) * X_b.T @ errors # gradient
theta = theta - alpha * gradient # update
1.2 Naïve Bayes Classifier
Naïve Bayes is a probabilistic classifier based on Bayes' Theorem with a strong (naïve)
independence assumption.

Bayes' Theorem for Classification

P(x ∣C k )⋅ P(C k )
P(C k ∣ x)=
P( x )

We predict the class with highest posterior:

^y =arg ⁡max ⁡ P(Ck ∣ x )=arg ⁡max ⁡ P( x ∣C k )⋅ P (Ck )
Ck Ck

The Naïve Independence Assumption

Assume all features x₁, x₂, ..., xₙ are conditionally independent given the class:
n
P(x ∣C k )=∏ ❑ x j ∣C k ¿
j=1

This is "naïve" because real features are rarely independent, but the classifier works
surprisingly well in practice.

Naïve Bayes Rule

n
^y =arg ⁡max ⁡ P(Ck ) ∏ ❑ x j ∣C k ¿
Ck j =1

Types of Naïve Bayes

Type Feature Distribution Use Case

Gaussian NB Continuous; normal General numeric features
distribution
Multinomial NB Count data Text classification (word
counts)
 Type Feature Distribution Use Case
Bernoulli NB Binary features (0/1) Document classification

Worked Example (Spam Detection)

Training data summary:
● P(Spam) = 0.4, P(Not Spam) = 0.6
● P("free" | Spam) = 0.8, P("free" | Not Spam) = 0.1
● P("offer" | Spam) = 0.7, P("offer" | Not Spam) = 0.05

For email with words "free" and "offer":

● P(Spam | email) ∝ 0.4 × 0.8 × 0.7 = 0.224
● P(Not Spam | email) ∝ 0.6 × 0.1 × 0.05 = 0.003

→ Classify as Spam

Laplace Smoothing
If a word never appears in training data for a class, P(word|class) = 0, making the entire
product 0. Fix with Laplace smoothing:

count( x j , C k )+1
P(x j ∣C k )=
count(C k )+∣V ∣

Where |V| = number of unique features (vocabulary size).

Advantages of Naïve Bayes:

● Very fast, simple, works well with small data
● Excellent for text classification
● Handles high-dimensional data well

Disadvantages:
● Independence assumption is rarely true
● Poor probability estimates (but good classification)
1.3 K-Nearest Neighbours (KNN)
KNN is a non-parametric, instance-based (lazy) learning algorithm — it doesn't build an
explicit model during training.

Idea: To classify a new point, find the K training examples closest to it and let them vote
for the class.

KNN Algorithm

Training Phase:
Store all training examples (X_train, y_train) — no actual
"training"

Prediction for a new point x_new:

1. Compute distance from x_new to all training points
2. Sort distances and pick K nearest neighbours
3. For Classification: take majority vote among K neighbours
For Regression: take average of K neighbours' values
4. Return predicted class (or value)

Distance Metrics:

Metric Formula Use Case

Euclidean √Σ(xᵢ - yᵢ)² Continuous features
Manhattan Σ|xᵢ - yᵢ| Grid/city-block distances
Minkowski (Σ|xᵢ - yᵢ|ᵖ)^(1/p) General (p=2: Euclidean, p=1:
Manhattan)
Hamming Fraction of differing bits Categorical / binary features

Choosing the Right K

K value Effect Problem

Small K (e.g., K=1) Very complex boundary Overfitting (noise-sensitive)
 K value Effect Problem
Large K (e.g., K=m) Very smooth boundary Underfitting (too simple)
Optimal K Balance between them Use cross-validation

📌 [Insert figure: Three KNN decision boundaries — K=1 (complex jagged), K=5
(smooth), K=15 (very smooth), each with coloured decision regions]

Rule of thumb: Start with K = √m (where m = training set size)

KNN Example
Given: Training points (1,1)→Class A, (2,2)→Class A, (3,1)→Class B, (3,3)→Class B
Query point: (2.5, 2)

With K=3:
● Distance to (1,1): √(2.25+1) = 1.80
● Distance to (2,2): √(0.25+0) = 0.50 ← nearest
● Distance to (3,1): √(0.25+1) = 1.12 ← 2nd nearest
● Distance to (3,3): √(0.25+1) = 1.12 ← 3rd nearest

K=3 neighbours: Class A (1), Class B (2) → Predict Class B (majority)

Advantages of KNN:
● Simple to understand and implement
● No training time
● Naturally handles multiclass

Disadvantages:
● Slow prediction (must compute all distances)
● Sensitive to irrelevant features
● Requires feature scaling
● High memory usage (stores all training data)
1.4 Decision Trees — ID3 Algorithm
A Decision Tree is a tree-structured model where:
● Internal nodes = tests on features
● Branches = possible outcomes of the test
● Leaf nodes = class labels (predictions)

📌 [Insert diagram: A sample decision tree for predicting loan approval — root node:
"Income > 50K?", branches to sub-trees based on Age, Credit Score, etc., leaf nodes:
Approve/Reject]

Building a Decision Tree: Information Gain

The ID3 (Iterative Dichotomiser 3) algorithm by Ross Quinlan builds trees using
Information Gain based on Entropy.

Entropy measures the impurity or disorder of a dataset: H (S)=− ∑ ❑ p c log ⁡2 pc

c∈C

Where pₓ = fraction of examples belonging to class c.

Interpretation:
● H = 0: Pure (all examples same class) — best
● H = 1: Maximum disorder (equal distribution) — worst for binary classification

Example:
● S = {9 Yes, 5 No} → P(Yes) = 9/14, P(No) = 5/14
● H(S) = −(9/14)log₂(9/14) − (5/14)log₂(5/14) = 0.940 bits

∣ Sv ∣
Information Gain of splitting on attribute A: IG(S , A)=H (S)− ∑ ❑
∣S∣
H (S v )
v ∈ Values ( A)

Where S_v = subset of S where attribute A has value v.

ID3 selects the attribute with the highest Information Gain as the split criterion.
ID3 Algorithm (Pseudocode)

ID3(S, Features):
If all examples in S have same class:
Return leaf node with that class
If Features is empty:
Return leaf node with majority class in S

A = feature with highest Information Gain in S

Create a node with test A

For each value v of A:

S_v = subset of S where A = v
If S_v is empty:
Add leaf node with majority class of S
Else:
Add subtree: ID3(S_v, Features - {A})

Return the tree

ID3 Worked Example (Play Tennis Dataset)

Day Outlook Temperature Humidity Wind Play?

D1 Sunny Hot High Weak No
D2 Sunny Hot High Strong No
D3 Overcast Hot High Weak Yes
D4 Rain Mild High Weak Yes
D5 Rain Cool Normal Weak Yes
D6 Rain Cool Normal Strong No
D7 Overcast Cool Normal Strong Yes
D8 Sunny Mild High Weak No
D9 Sunny Cool Normal Weak Yes
D10 Rain Mild Normal Weak Yes
D11 Sunny Mild Normal Strong Yes
D12 Overcast Mild High Strong Yes
D13 Overcast Hot Normal Weak Yes
D14 Rain Mild High Strong No
S = {9 Yes, 5 No} → H(S) = 0.940 bits

Information Gain for Outlook:

● Sunny: {2 Yes, 3 No} → H = 0.971; weight = 5/14
● Overcast: {4 Yes, 0 No} → H = 0; weight = 4/14
● Rain: {3 Yes, 2 No} → H = 0.971; weight = 5/14

IG(S, Outlook) = 0.940 − [5/14×0.971 + 4/14×0 + 5/14×0.971]

= 0.940 − 0.693 = 0.247 bits

Similarly compute for Temperature (0.029), Humidity (0.151), Wind (0.048)

Outlook has highest IG → split on Outlook first!

Overcast always leads to "Yes" → Leaf node.

Continue recursively on Sunny and Rain subsets.

📌 [Insert completed decision tree for Play Tennis: Root = Outlook, Overcast → Yes
(leaf), Sunny subtree splits on Humidity, Rain subtree splits on Wind]

Advantages of Decision Trees:

● Easy to visualise and interpret
● No feature scaling needed
● Handles both categorical and numerical features
● Non-linear decision boundaries

Disadvantages:
● Prone to overfitting (deep trees)
● Unstable (small data change → different tree)
● Biased toward features with more values (ID3)
2. Generalisation and Overfitting
2.1 The Problem of Overfitting
Overfitting: The model learns the training data too well, including noise, but fails to
generalise to new unseen data.

Underfitting: The model is too simple and doesn't even fit the training data well.

📌 [Insert three graphs for regression: Underfitting (straight line on curved data), Good
fit (correct polynomial), Overfitting (wiggly polynomial that passes through all training
points but curves wildly)]

Training Error Generalisation Error (Test Error)

Underfitting High High
Good Fit Low Low
Overfitting Very Low High

Causes of overfitting:
● Model is too complex (too many parameters)
● Training data is too small
● Training for too many iterations

2.2 Regularisation — LASSO and RIDGE

Regularisation is a technique to prevent overfitting by adding a penalty term to the cost
function that discourages large parameter values.

m
1
Regularised Cost Function: J (θ)= ∑ ¿¿¿
2 m i=1

Where λ (lambda) = regularisation parameter controlling the strength of the penalty.

RIDGE Regularisation (L2 Regularisation)
n
Penalty: Sum of squares of parameters R(θ)=∑ ❑ θ j =∥ θ ∥2
2 2

j =1

m
1
Cost Function: J (θ)= ∑ ¿¿
2 m i=1

(Note: θ₀ is usually not penalised)

Effect:
● Shrinks all coefficients toward zero but never exactly to zero
● Spreads the penalty across all features
● Better when all features are somewhat relevant

Normal Equation with Ridge: θ=¿

Where I is the identity matrix (with 0 in top-left for θ₀)

LASSO Regularisation (L1 Regularisation)

n
Penalty: Sum of absolute values of parameters R(θ)=∑ ∣θ j ∣=∥ θ ∥1
j =1

m
1
Cost Function: J (θ)= ∑ ¿¿
2 m i=1

Effect:
● Can shrink coefficients exactly to zero → performs automatic feature selection
● Creates sparse models (many zero coefficients)
● Better when only a few features are truly relevant

Comparison: LASSO vs. RIDGE

Feature LASSO (L1) RIDGE (L2)

Penalty Σ|θⱼ| Σθⱼ²
Effect on coefficients Sets some to exactly 0 Shrinks all toward 0
Feature selection Yes (automatic) No
Solution May not be unique Always unique
Best when Few relevant features All features relevant
Sparsity Sparse solution Dense solution

📌 [Insert diagram: Regularisation paths showing how LASSO (L1) coefficients reach zero
sharply while RIDGE (L2) coefficients shrink but don't reach zero as λ increases]

Choosing λ:
● λ = 0: No regularisation (standard regression)
● λ → ∞: All coefficients → 0 (extreme underfitting)
● Optimal λ: chosen via cross-validation

2.3 Training, Testing, and Validation Sets

To properly evaluate a model, we split data into three parts:

Split Purpose Typical Size

Training Set Fit the model parameters 60–80%
Validation Set Tune hyperparameters (λ, K, etc.) 10–20%
Test Set Final unbiased evaluation 10–20%
Workflow:

Full Dataset
├── Training Set → Train model with different λ values
├── Validation Set → Pick best λ (best validation error)
└── Test Set → Report final performance

⚠️Never use test set for hyperparameter tuning — this would give an optimistic
(overfitted) estimate of performance.

Why do we need a validation set?

If we tune λ on the test set, we've effectively trained on the test set → biased estimate.

📌 [Insert diagram: Dataset → split into Training/Validation/Test, showing the workflow

of training → validation selection → test evaluation]

3. Evaluation Measures
3.1 Classification Evaluation Metrics
Confusion Matrix is the foundation of all classification metrics:

Predicted
Positive Negative
Actual Positive | TP | FN |
Negative | FP | TN |

Term Meaning Example

True Positive (TP) Correctly predicted Actual spam predicted as spam
Positive
False Positive (FP) Incorrectly predicted Not-spam predicted as spam
Positive (Type I error)
True Negative (TN) Correctly predicted Not-spam predicted as not-spam
Negative
 Term Meaning Example
False Negative (FN) Incorrectly predicted Spam predicted as not-spam
Negative (Type II error)

📌 [Insert 2×2 confusion matrix diagram with colour coding and labels TP, FP, FN, TN]

Accuracy
TP+TN
Accuracy=
TP+ TN + FP+ FN

Limitation: Misleading for imbalanced datasets.

● Example: 95% class A, 5% class B → Always predicting A gives 95% accuracy but
misses all B!

Precision
TP
Precision=
TP+ FP

"Of all the items I predicted as positive, how many are actually positive?"

● High precision → Few false alarms

● Important when FP is costly (e.g., wrongly diagnosing cancer in healthy people)

Recall (Sensitivity / True Positive Rate)

TP
Recall=
TP+ FN
"Of all actually positive items, how many did I correctly identify?"

● High recall → Few misses

● Important when FN is costly (e.g., missing actual cancer patients)

Precision-Recall Tradeoff:
Increasing the decision threshold → Higher precision, Lower recall
Decreasing the threshold → Lower precision, Higher recall

F-Measure (F1 Score)

2 × Precision× Recall 2TP
Harmonic mean of Precision and Recall: F 1= =
Precision+Recall 2 TP+ FP+ FN

2 Precision × Recall
The F-β score generalises this: F β =(1+ β ) 2
β × Precision+Recall

● β = 1: Equal weight to Precision and Recall (F1)

● β > 1: Recall weighted more (β = 2: medical diagnosis)
● β < 1: Precision weighted more

Example Calculation:
TP = 90, FP = 10, FN = 5, TN = 895
● Precision = 90/(90+10) = 0.90
● Recall = 90/(90+5) = 0.947
● F1 = 2×0.90×0.947/(0.90+0.947) = 0.923

ROC Curve (Receiver Operating Characteristic)

The ROC curve plots:
● X-axis: False Positive Rate (FPR) = FP/(FP+TN)
● Y-axis: True Positive Rate (TPR) = TP/(TP+FN) = Recall

At different decision thresholds (0 to 1), you get different (FPR, TPR) points — plotting them
gives the ROC curve.

📌 [Insert ROC curve diagram: axes FPR (x) vs TPR (y), showing random classifier
(diagonal line), good classifier (curve toward top-left), perfect classifier (goes to (0,1))]

Area Under Curve (AUC):

● AUC = 1.0: Perfect classifier
● AUC = 0.5: Random classifier (useless)
● AUC > 0.9: Excellent; AUC > 0.8: Good; AUC > 0.7: Acceptable

Advantage of ROC-AUC: Not affected by class imbalance; compares classifiers across all
thresholds.

3.2 Regression Evaluation Metrics

Mean Absolute Error (MAE)
m
1
MAE= ∑ ∣ y i − ^y i ∣
m i=1

● Average of absolute differences between actual and predicted values

● Robust to outliers (doesn't square the error)
● Same units as target variable

Root Mean Squared Error (RMSE)

√
m
1
RMSE= ∑ ¿¿¿
m i=1

● Square root of average squared differences

● Penalises large errors more (due to squaring)
● Same units as target variable
● More sensitive to outliers than MAE

R² Score (Coefficient of Determination)

2 S S res
R =1 − =1 −∑ ¿ ¿
S Stot

Where ȳ = mean of actual values, SS_res = residual sum of squares, SS_tot = total sum of
squares

Interpretation:
● R² = 1.0: Perfect predictions (0% unexplained variance)
● R² = 0.0: Model predicts the mean (no better than baseline)
● R² < 0: Model is worse than predicting the mean (bad model)
● R² = 0.85 means the model explains 85% of the variance in y

Comparison of Regression Metrics:

Metric Formula Unit Outlier Sensitivity Best Use

MAE Σ|y-ŷ|/m Same as y Low Robust evaluation
RMSE √(Σ(y-ŷ)²/m) Same as y High Penalize big errors
R² 1 - SS_res/SS_tot Unitless Medium Explained variance

Module 2 Summary
Key Concepts Checklist
● ✅ Logistic Regression uses sigmoid function for binary classification; decision boundary
at 0.5
● ✅ Cross-entropy loss is convex and used for logistic regression training
● ✅ Naïve Bayes applies Bayes' theorem with feature independence assumption; uses
Laplace smoothing
● ✅ KNN is a lazy learner; classifies by majority vote of K nearest neighbours
● ✅ ID3 builds decision trees by maximising Information Gain (based on Entropy)
● ✅ Overfitting: model too complex, memorises training noise; poor generalisation
● ✅ LASSO (L1): forces some coefficients to exactly zero — feature selection
● ✅ RIDGE (L2): shrinks all coefficients toward zero — never exactly zero
● ✅ Training/Validation/Test split for unbiased model evaluation
● ✅ Confusion matrix: TP, FP, TN, FN are the building blocks of all classification metrics
● ✅ Precision = TP/(TP+FP); Recall = TP/(TP+FN); F1 = harmonic mean of P and R
● ✅ ROC-AUC measures classifier quality across all thresholds; perfect = 1.0, random = 0.5
● ✅ MAE is outlier-robust; RMSE penalises large errors; R² measures explained variance

Expected Exam Questions

Part A — Short Answer Questions (3 marks each)
1. (Easy) What is the role of the sigmoid function in Logistic Regression? Draw its graph and
state its mathematical formula. (3 marks)
2. (Easy) State Bayes' theorem and explain the naïve independence assumption used in Naïve
Bayes classifier. (3 marks)
3. (Medium) Explain the K-Nearest Neighbours algorithm. What is the effect of increasing K
on the decision boundary? (3 marks)
4. (Medium) Define Entropy and Information Gain. How are they used in the ID3 algorithm?
(3 marks)
5. (Easy) What is overfitting? How do LASSO and RIDGE regularisation help prevent it? (3
marks)
6. (Medium) Define Precision and Recall. In which applications is each more important? (3
marks)
7. (Easy) What is a ROC curve? What does the Area Under Curve (AUC) measure? (3
marks)
8. (Medium) Differentiate between MAE, RMSE, and R² as regression evaluation metrics.
(3 marks)
9. (Medium) Why is it important to have separate training, validation, and test sets? (3
marks)
10. (Hard) Explain the precision-recall tradeoff and how it relates to the choice of decision
threshold in logistic regression. (3 marks)
Part B — Long Answer / Essay Questions (9 marks each)
1. (Medium) (a) Derive the logistic regression hypothesis and cost function. (b) Write the
gradient descent update rule for logistic regression. (c) How does logistic regression differ
from linear regression for classification? (9 marks)
2. (Hard) (a) Explain the Naïve Bayes classifier with Bayes' theorem. (b) Apply Naïve
Bayes to classify a new email given the following training statistics: [Provide a sample table
of P(word|class) values and class priors]. Include Laplace smoothing in your solution. (9
marks)
3. (Medium) (a) Explain the ID3 algorithm with the Play Tennis dataset. (b) Compute the
entropy of the full dataset and the information gain for the "Outlook" and "Wind" attributes.
(c) Draw the partial decision tree resulting from the first split. (9 marks)
4. (Hard) (a) Differentiate between LASSO and RIDGE regularisation using mathematical
formulations. (b) Write the regularised cost function for linear regression with Ridge. (c)
Derive the Normal Equation with Ridge regularisation. (d) How is the regularisation
parameter λ chosen? (9 marks)
5. (Medium) (a) Define the confusion matrix and derive Precision, Recall, F1-Score, and
Accuracy from it. (b) Compute all four metrics for: TP=50, FP=10, FN=5, TN=100. (c)
Explain the ROC curve and AUC with a diagram. (9 marks)
6. (Medium) (a) Explain the KNN algorithm for classification and regression. (b) What are
the effects of choosing different values of K? (c) What distance metrics can be used, and
when is each appropriate? (d) What are the main limitations of KNN? (9 marks)

End of Module 2