Unit 3: Classification & Instance-Based Learning

Course - Machine Learning Algorithms (21CSC555J)
Assessment - Continuous Test 2 (CT-2)
Unit - Unit 3: Naïve Bayes & K-Nearest Neighbors
Total Weightage - 40 Marks (Question 1.a: 15 Marks; Question 1.b: 5 Marks; Question 2: 20 Marks)

---

Question 1.a: Naïve Bayes Spam Filtering (15 Marks)

info

Question Statement

An email filtering system uses Naïve Bayes to classify messages as Spam or Not Spam. Given the training dataset:

Training Dataset for Spam Classification

Email	Contains 'Offer'	Contains 'Win'	Spam
E1	Yes	Yes	Yes
E2	No	Yes	Yes
E3	Yes	No	No
E4	No	No	No

• i) Calculate the conditional probabilities (5 marks)
  $P(\text{Offer} \mid \text{Spam})$, $P(\text{Win} \mid \text{Spam})$, $P(\text{Offer} \mid \text{NotSpam})$, $P(\text{Win} \mid \text{NotSpam})$.
• ii) For a new email with "Offer = Yes, Win = Yes", compute (5 marks)
  $P(\text{Spam} \mid \text{Email})$ and $P(\text{NotSpam} \mid \text{Email})$
• iii) Predict the class and briefly explain the independence assumption. (5 marks)

---

Solution 1.a

📝 Exam-Ready Answer (Structured for 15 Marks)

(i) Calculate Conditional Probabilities (5 Marks)

1. Step 1: Dataset Partitioning & Class Totals (1 Mark)

   • Total number of training samples: $N = 4$
   • Total Spam emails ($C = \text{Spam}$): $N_{\text{Spam}} = 2$ (Emails: E1, E2)
   • Total Not Spam emails ($C = \text{NotSpam}$): $N_{\text{NotSpam}} = 2$ (Emails: E3, E4)

2. Step 2: General Formula for Maximum Likelihood Conditional Probability (1 Mark) $P(X_i = x \mid C = c) = \frac{\text{Count}(X_i = x \text{ and } C = c)}{\text{Count}(C = c)}$

3. Step 3: Evaluate Conditional Probabilities for Spam Class (1.5 Marks)

   • For feature 'Offer' = Yes: $P(\text{Offer} = \text{Yes} \mid \text{Spam}) = \frac{\text{Count}(\text{Offer}=\text{Yes} \text{ and } \text{Spam})}{\text{Count}(\text{Spam})} = \frac{1}{2} = \mathbf{0.5}$ (Email E1 has Offer=Yes; E2 has Offer=No)
   • For feature 'Win' = Yes: $P(\text{Win} = \text{Yes} \mid \text{Spam}) = \frac{\text{Count}(\text{Win}=\text{Yes} \text{ and } \text{Spam})}{\text{Count}(\text{Spam})} = \frac{2}{2} = \mathbf{1.0}$ (Both emails E1 and E2 have Win=Yes)

4. Step 4: Evaluate Conditional Probabilities for Not Spam Class (1.5 Marks)

   • For feature 'Offer' = Yes: $P(\text{Offer} = \text{Yes} \mid \text{NotSpam}) = \frac{\text{Count}(\text{Offer}=\text{Yes} \text{ and } \text{NotSpam})}{\text{Count}(\text{NotSpam})} = \frac{1}{2} = \mathbf{0.5}$ (Email E3 has Offer=Yes; E4 has Offer=No)
   • For feature 'Win' = Yes: $P(\text{Win} = \text{Yes} \mid \text{NotSpam}) = \frac{\text{Count}(\text{Win}=\text{Yes} \text{ and } \text{NotSpam})}{\text{Count}(\text{NotSpam})} = \frac{0}{2} = \mathbf{0.0}$ (Neither E3 nor E4 has Win=Yes)

Conditional Probability Summary Table

Feature ($X_i$)	Value	$P(X_i \mid \text{Spam})$	$P(X_i \mid \text{NotSpam})$
Contains 'Offer'	Yes	$1/2 = \mathbf{0.5}$	$1/2 = \mathbf{0.5}$
Contains 'Win'	Yes	$2/2 = \mathbf{1.0}$	$0/2 = \mathbf{0.0}$

---

(ii) Compute Probabilities for New Email: $\mathbf{X}_{\text{new}} = (\text{Offer} = \text{Yes}, \text{Win} = \text{Yes})$ (5 Marks)

1. Step 1: Compute Prior Class Probabilities (1 Mark) $P(\text{Spam}) = \frac{N_{\text{Spam}}}{N} = \frac{2}{4} = \mathbf{0.5}$ $P(\text{NotSpam}) = \frac{N_{\text{NotSpam}}}{N} = \frac{2}{4} = \mathbf{0.5}$

2. Step 2: State Bayes' Posterior Formula with Conditional Independence (1 Mark) $P(C \mid \mathbf{X}) = \frac{P(\mathbf{X} \mid C) \cdot P(C)}{P(\mathbf{X})} = \frac{P(\text{Offer}=\text{Yes} \mid C) \cdot P(\text{Win}=\text{Yes} \mid C) \cdot P(C)}{P(\mathbf{X})}$

3. Step 3: Calculate Unnormalized Joint Likelihoods (1.5 Marks)

   • For class Spam: $\mathcal{L}(\text{Spam}) = P(\text{Offer}=\text{Yes} \mid \text{Spam}) \times P(\text{Win}=\text{Yes} \mid \text{Spam}) \times P(\text{Spam})$ $\mathcal{L}(\text{Spam}) = 0.5 \times 1.0 \times 0.5 = \mathbf{0.25}$

   • For class Not Spam: $\mathcal{L}(\text{NotSpam}) = P(\text{Offer}=\text{Yes} \mid \text{NotSpam}) \times P(\text{Win}=\text{Yes} \mid \text{NotSpam}) \times P(\text{NotSpam})$ $\mathcal{L}(\text{NotSpam}) = 0.5 \times 0.0 \times 0.5 = \mathbf{0.0}$

4. Step 4: Compute Evidence (Marginal Probability $P(\mathbf{X})$) (0.5 Marks) $P(\mathbf{X}) = \mathcal{L}(\text{Spam}) + \mathcal{L}(\text{NotSpam}) = 0.25 + 0.0 = \mathbf{0.25}$

5. Step 5: Normalize to Obtain Final Posterior Probabilities (1 Mark) $P(\text{Spam} \mid \text{Email}) = \frac{\mathcal{L}(\text{Spam})}{P(\mathbf{X})} = \frac{0.25}{0.25} = \mathbf{1.0} \quad (100\%)$ $P(\text{NotSpam} \mid \text{Email}) = \frac{\mathcal{L}(\text{NotSpam})}{P(\mathbf{X})} = \frac{0.0}{0.25} = \mathbf{0.0} \quad (0\%)$

---

(iii) Class Prediction & Independence Assumption (5 Marks)

• Class Prediction (2 Marks):

  • MAP Decision Rule: $\hat{y} = \arg\max_{c} P(C = c \mid \mathbf{X})$
  • Since $P(\text{Spam} \mid \text{Email}) = 1.0 > P(\text{NotSpam} \mid \text{Email}) = 0.0$, the email is classified as Spam.

• Class-Conditional Independence Assumption (1.5 Marks):

  • Formal Definition: All features are assumed conditionally independent given the class label: $P(X_1, X_2, \dots, X_d \mid C) = \prod_{j=1}^d P(X_j \mid C)$
  • In this context, knowing the email contains 'Offer' provides zero information about 'Win', once the class is fixed.

• Practical Validity & Trade-offs (1.5 Marks):

  • Why "Naïve": Real-world text features are strongly correlated (e.g., "Offer" and "Win" co-occur in spam).
  • Why It Works: Classification only requires the correct probability ranking ($\arg\max$), not calibrated values. It reduces parameter complexity from $O(2^d)$ to $O(d)$, preventing overfitting.

---

Question 1.b: Comparative Analysis of Classifiers on Medical Data (5 Marks)

info

Question Statement

A data scientist is working on three models for classifying medical test results:

• KNN ($k=5$)
• Gaussian Naïve Bayes
• SVM with RBF kernel

Assume given is a small dataset with numeric features:

• a. Which algorithm handles non-linear boundaries best and why? (2 Marks)
• b. Which algorithm is most sensitive to irrelevant features? (1.5 Marks)
• c. Which algorithm performs better when data is small and has missing values? (1.5 Marks)

---

Solution 1.b

📝 Exam-Ready Answer (Crisp 5-Mark Structure)

(a) Best for Non-Linear Boundaries: SVM with RBF Kernel (2 Marks)

• Algorithm: SVM with RBF Kernel
• Why (Key Points):
  • Infinite-Dimensional Mapping: The RBF kernel $K(\mathbf{x}, \mathbf{x}') = \exp(-\gamma \|\mathbf{x} - \mathbf{x}'\|^2)$ projects inputs into an infinite-dimensional Hilbert space.
  • Smooth Decision Surfaces: A linear hyperplane in this transformed space maps back to smooth, continuous non-linear contours in the original feature space.

(b) Most Sensitive to Irrelevant Features: KNN ($k=5$) (1.5 Marks)

• Algorithm: K-Nearest Neighbors (KNN)
• Why (Key Points):
  • Uniform Distance Metric: Calculates Euclidean distance equally across all $D$ features: $d = \sqrt{\sum_{j=1}^D (x_j - y_j)^2}$.
  • Curse of Dimensionality: Irrelevant dimensions inject random noise, collapsing distance contrast ($d_{\max} \approx d_{\min}$) and destroying neighborhood ranking.

(c) Best for Small Data and Missing Values: Gaussian Naïve Bayes (1.5 Marks)

• Algorithm: Gaussian Naïve Bayes
• Why (Key Points):
  • Parameter Efficiency: Estimates only $2$ parameters per feature ($\mu, \sigma^2$), resisting overfitting on small samples via high bias/low variance.
  • Native Missing Value Handling: Computes likelihoods by simply omitting missing attributes from the conditional product: $P(\mathbf{x}_{\text{obs}} \mid C) = \prod_{j \in \text{obs}} P(x_j \mid C)$.

Quick Comparison Summary

Criterion	Winner	Core Reason
Non-Linear Boundary (2M)	SVM (RBF)	Kernel trick creates smooth boundaries in infinite-dimensional space.
Sensitive to Irrelevant Features (1.5M)	KNN ($k=5$)	Euclidean distance equally sums noise from all dimensions.
Small Data + Missing Values (1.5M)	Gaussian NB	Few parameters ($\mu, \sigma^2$) + naturally omits missing features in product.

---

Question 2: K-Nearest Neighbors Customer Spending Classification (20 Marks)

info

Question Statement

A company wants to classify new customers as "High Spender" or "Low Spender" based on their income and average monthly spending.

Training data:

Customer	Income (₹1000s)	Spending (₹1000s)	Class
C1	20	5	Low
C2	25	7	Low
C3	50	20	High
C4	55	22	High
C5	30	10	Low

• (a) For a new customer with $\text{Income} = 40$ and $\text{Spending} = 15$, calculate the Euclidean distance from each training point. (5 Marks)
• (b) Predict the class when $K=3$. Show all steps clearly. (5 Marks)
• (c) Recalculate distances using the Manhattan distance metric and compare the result. (5 Marks)
• (d) Explain: How feature scaling/normalization affects KNN results, and what happens when $K$ is too small or too large. (3 Marks)
• (e) Mention one real-world application where KNN is used and why it is preferred there. (2 Marks)

---

Solution 2

📝 Exam-Ready Answer (Structured for 20 Marks)

Let the query point for the new customer be: $\mathbf{X}_{\text{new}} = (x_1, x_2) = (40, 15)$ where $x_1$ represents Income (in ₹1000s) and $x_2$ represents Spending (in ₹1000s).

---

(a) Euclidean Distance Calculation (5 Marks)

1. Step 1: Formula Definition (1 Mark)

   • Euclidean Distance Formula between two points $(x_1, y_1)$ and $(x_2, y_2)$: $d = \sqrt{(x_2 - x_1)^2 + (y_2 - y_1)^2}$
   • Applied to Query Point $(40, 15)$ and Training Point $(x_{i1}, x_{i2})$: $d_E = \sqrt{(40 - x_{i1})^2 + (15 - x_{i2})^2}$

2. Step 2: Individual Distance Computations (3 Marks)

   • For Customer C1 $(20, 5)$: $d_E(\mathbf{X}, C_1) = \sqrt{(40 - 20)^2 + (15 - 5)^2} = \sqrt{20^2 + 10^2} = \sqrt{400 + 100} = \sqrt{500} \approx \mathbf{22.36}$

   • For Customer C2 $(25, 7)$: $d_E(\mathbf{X}, C_2) = \sqrt{(40 - 25)^2 + (15 - 7)^2} = \sqrt{15^2 + 8^2} = \sqrt{225 + 64} = \sqrt{289} = \mathbf{17.00}$

   • For Customer C3 $(50, 20)$: $d_E(\mathbf{X}, C_3) = \sqrt{(40 - 50)^2 + (15 - 20)^2} = \sqrt{(-10)^2 + (-5)^2} = \sqrt{100 + 25} = \sqrt{125} \approx \mathbf{11.18}$

   • For Customer C4 $(55, 22)$: $d_E(\mathbf{X}, C_4) = \sqrt{(40 - 55)^2 + (15 - 22)^2} = \sqrt{(-15)^2 + (-7)^2} = \sqrt{225 + 49} = \sqrt{274} \approx \mathbf{16.55}$

   • For Customer C5 $(30, 10)$: $d_E(\mathbf{X}, C_5) = \sqrt{(40 - 30)^2 + (15 - 10)^2} = \sqrt{10^2 + 5^2} = \sqrt{100 + 25} = \sqrt{125} \approx \mathbf{11.18}$

3. Step 3: Distance Summary Table (1 Mark)

Customer	Income ($x_{i1}$)	Spending ($x_{i2}$)	Class	Euclidean Distance ($d_E$)
C1	20	5	Low	$\sqrt{500} \approx \mathbf{22.36}$
C2	25	7	Low	$\sqrt{289} = \mathbf{17.00}$
C3	50	20	High	$\sqrt{125} \approx \mathbf{11.18}$
C4	55	22	High	$\sqrt{274} \approx \mathbf{16.55}$
C5	30	10	Low	$\sqrt{125} \approx \mathbf{11.18}$

---

(b) Predict Class When $K=3$ (5 Marks)

1. Step 1: Rank Distances in Ascending Order (1.5 Marks)

Rank	Customer	Euclidean Distance ($d_E$)	Class Label	Included in $K=3$?
1	C3	$11.18$	High	Yes
2	C5	$11.18$	Low	Yes
3	C4	$16.55$	High	Yes
4	C2	$17.00$	Low	No
5	C1	$22.36$	Low	No

2. Step 2: Identify the $K=3$ Nearest Neighbors (1.5 Marks)

   • Nearest Neighbor 1: C3 with $d_E = 11.18$ $\implies$ Class = High
   • Nearest Neighbor 2: C5 with $d_E = 11.18$ $\implies$ Class = Low
   • Nearest Neighbor 3: C4 with $d_E = 16.55$ $\implies$ Class = High

3. Step 3: Majority Voting & Posterior Probability (1 Mark)

   • Vote count for Class High: $2$ (from C3, C4)
   • Vote count for Class Low: $1$ (from C5)
   • Empirical class probability: $P(\text{High} \mid \mathbf{X}) = \frac{2}{3} \approx 66.67\%$ $P(\text{Low} \mid \mathbf{X}) = \frac{1}{3} \approx 33.33\%$

4. Step 4: Final Prediction Statement (1 Mark)

   • By majority voting rule ($2 > 1$), the new customer with $\text{Income} = 40$ and $\text{Spending} = 15$ is predicted as: $\hat{y} = \text{\textbf{High Spender}}$

---

(c) Recalculate Distances Using Manhattan Metric & Compare (5 Marks)

1. Step 1: Formula Definition (1 Mark)

   • Manhattan Distance Formula between two points $(x_1, y_1)$ and $(x_2, y_2)$: $d_M = \lvert x_2 - x_1 \rvert + \lvert y_2 - y_1 \rvert$
   • Applied to Query Point $(40, 15)$ and Training Point $(x_{i1}, x_{i2})$: $d_M = \lvert 40 - x_{i1} \rvert + \lvert 15 - x_{i2} \rvert$

2. Step 2: Individual Computations (2 Marks)

   • For C1 $(20, 5)$: $d_M = \lvert 40 - 20 \rvert + \lvert 15 - 5 \rvert = 20 + 10 = \mathbf{30}$
   • For C2 $(25, 7)$: $d_M = \lvert 40 - 25 \rvert + \lvert 15 - 7 \rvert = 15 + 8 = \mathbf{23}$
   • For C3 $(50, 20)$: $d_M = \lvert 40 - 50 \rvert + \lvert 15 - 20 \rvert = 10 + 5 = \mathbf{15}$
   • For C4 $(55, 22)$: $d_M = \lvert 40 - 55 \rvert + \lvert 15 - 22 \rvert = 15 + 7 = \mathbf{22}$
   • For C5 $(30, 10)$: $d_M = \lvert 40 - 30 \rvert + \lvert 15 - 10 \rvert = 10 + 5 = \mathbf{15}$

3. Step 3: Metric Comparison Table (1 Mark)

Customer	Class	Euclidean Distance ($d_E$)	Euclidean Rank	Manhattan Distance ($d_M$)	Manhattan Rank
C3	High	$11.18$	1 (Tie)	$15$	1 (Tie)
C5	Low	$11.18$	1 (Tie)	$15$	1 (Tie)
C4	High	$16.55$	3	$22$	3
C2	Low	$17.00$	4	$23$	4
C1	Low	$22.36$	5	$30$	5

4. Step 4: Analytical Comparison & Conclusion (1 Mark)
   • Set Invariance: The set of $K=3$ nearest neighbors under Manhattan distance is identical: $\{C_3, C_5, C_4\}$.
   • Tally & Outcome: The majority vote remains $2 \text{ High}$ vs $1 \text{ Low}$.
   • Conclusion: The prediction remains unchanged as High Spender. This demonstrates that the local neighborhood around query point $(40, 15)$ is topologically stable across both $L_1$ and $L_2$ geometric norms.

---

(d) Feature Scaling & Choice of K (3 Marks)

• Impact of Feature Scaling (1.5 Marks):

  • Scale Dominance: KNN distance calculations are sensitive to magnitude. Features with larger ranges (e.g., Income in thousands) dominate features with smaller ranges (e.g., Spending in tens), distorting distance measurements.
  • Remedy: Apply Min-Max Normalization ($[0, 1]$) or Z-Score Standardization so all dimensions contribute proportionally.

• Effect of Parameter $K$ (1.5 Marks):

  • $K$ Too Small ($K = 1$): Low Bias, High Variance $\implies$ sensitive to noise and outliers, causing Overfitting (jagged boundaries).
  • $K$ Too Large ($K \to N$): High Bias, Low Variance $\implies$ overly smooth boundaries, degenerating into global majority voting (Underfitting).
  • Tip: Choose an odd $K$ to break ties (rule of thumb: $K \approx \sqrt{N}$).

---

(e) Real-World Application of KNN (2 Marks)

• Application (1 Mark):
  • Recommender Systems / Collaborative Filtering (e.g., Amazon product recommendations or Spotify music matching).
• Why Preferred (1 Mark):
  • Lazy Learning (Zero Training Cost): Stores training data directly; new users or products are ingested in real time without expensive model retraining.
  • Intuitive & Non-Parametric: Recommends items by finding users with similar consumption profiles without assuming any underlying mathematical distribution.