Classification Algorithms: Perceptron, KNN, Decision Trees

TAKEAWAYS

• Perceptron is a linear classifier that learns a decision boundary using gradient descent, but fails on non-linearly separable data unless combined with kernels (e.g., SVM).
• KNN classifies points by majority vote of their k nearest neighbors, where k controls bias-variance tradeoff: small k = high variance (overfitting), large k = high bias (underfitting).
• Decision Trees (ID3/C4.5) split data recursively using entropy/information gain, but suffer from overfitting unless pruned (e.g., max depth = 3 for Ncell churn prediction).
• Real-world tie: eSewa uses KNN to flag fraudulent transactions by comparing new payments to historical "normal" patterns (low k = 3 for sensitivity).
• Visual intuition: Perceptron’s weight updates trace a path in feature space; KNN’s decision boundary is a Voronoi diagram; Decision Trees are hierarchical "if-else" rules.
• Exam focus: Derive perceptron updates, compute KNN predictions, and build ID3 trees from scratch (given entropy tables).

---

1. Perceptron: The Linear Classifier

1.1 Definition and Intuition

The perceptron is the simplest supervised learning algorithm for binary classification. It models a linear decision boundary (hyperplane) in d-dimensional space: $$f(\mathbf{x})=\text{sign}({\mathbf{w}}^T\mathbf{x}+b)$$ where:

• $\mathbf{w}$ = weight vector (normal to the hyperplane),
• $b$ = bias term,
• $\text{sign}(z)=+1$ if $z\ge 0$, else $-1$.

1.2 How It Learns: Gradient Descent

The perceptron updates weights using the perceptron learning rule: $$\mathbf{w}\leftarrow \mathbf{w}+\eta (y_i-{\hat{y}}_i){\mathbf{x}}_i$$ $$b\leftarrow b+\eta (y_i-{\hat{y}}_i)$$ where:

• $\eta$ = learning rate (e.g., 0.1),
• $y_i$ = true label ($+1$ or $-1$),
• ${\hat{y}}_i$ = predicted label ($\text{sign}({\mathbf{w}}^T{\mathbf{x}}_i+b)$).

Worked Example: Spam Filter Train a perceptron on emails with features:

• $x_1$ = "contains 'free'" (1 if yes, 0 else),
• $x_2$ = "contains 'urgent'" (1 if yes, 0 else). Data:

  Email	$x_1$	$x_2$	Label (Spam=+1, Not=−1)
  A	1	0	+1
  B	0	1	+1
  C	0	0	−1

Steps:

1. Initialize $\mathbf{w}=[0,0]$, $b=0$, $\eta =0.1$.
2. For Email A: $\hat{y}=\text{sign}(0)=-1$ (error). Update: $$\mathbf{w}=[0,0]+0.1\times (1-(-1))\times [1,0]=[0.2,0]$$ $$b=0+0.1\times (1-(-1))=0.2$$
3. Repeat for B and C until convergence (e.g., after 3 epochs, $\mathbf{w}=[0.3,0.3]$, $b=0.4$).

Mermaid Diagram: Perceptron Learning Path

1.3 Limitations

• Linearly separable only: Fails on XOR or concentric circles (see IMAGE: "XOR problem non-linear" | Two classes forming an X shape).
• No probabilistic output: Only hard decisions ($+1$ or $-1$).
• Sensitive to feature scaling: Normalize inputs (e.g., min-max to $[0,1]$).

Real-World Use in Nepal:

• Ncell’s churn prediction: A perceptron classifies customers likely to switch providers based on call duration/features (linear boundary works if features like "average calls/day" and "data usage" separate churners clearly).

---

2. K-Nearest Neighbors (KNN): Lazy Learning

2.1 Definition

KNN is an instance-based algorithm:

1. Store the entire training dataset.
2. For a new point $\mathbf{x}$, find its k nearest neighbors in feature space (using Euclidean distance).
3. Assign the majority class label among those k neighbors.

Distance Metric: $$d({\mathbf{x}}_i,{\mathbf{x}}_j)=\sqrt{\sum _{l=1}^d(x_{i,l}-x_{j,l}{)}^2}$$

2.2 Choosing k: Bias-Variance Tradeoff

Worked Example: Daraz Customer Segmentation Data: 6 customers with features $[$age, monthly_spend$]$ and labels (Loyal=1, Churn=0):

New Customer: Age=27, Spend=4500. Find k=3 neighbors:

1. Compute distances:
   • $d(\text{E})=\sqrt{(27-22{)}^2+(4500-6000{)}^2}=1500$
   • $d(\text{C})=\sqrt{(27-28{)}^2+(4500-4000{)}^2}=500$
   • $d(\text{A})=\sqrt{(27-25{)}^2+(4500-5000{)}^2}=500$
   • $d(\text{B})=1000$, $d(\text{F})=1000$, $d(\text{D})=2000$.
2. Nearest 3: C, A, B → Labels: 1, 1, 0 → Majority = 1 (Loyal).

Mermaid Diagram: KNN Voronoi Boundaries

2.3 Advantages/Disadvantages

Real-World Use in Nepal:

• eSewa Fraud Detection: Uses KNN (k=3) to flag transactions. If a new payment’s features (amount, time, location) match 3/3 known fraudulent transactions, it’s blocked.
• Pathao Driver Matching: Finds k=5 nearest drivers (by location/speed) to assign a ride.

---

3. Decision Trees: Hierarchical Rules

3.1 ID3 Algorithm (Entropy-Based Splitting)

Decision trees split data recursively using information gain (reduction in entropy).

Entropy measures impurity: $$H(S)=-\sum _{i=1}^c{p}_i{\log }_2{p}_i$$ where $p_i$ = proportion of class i in set S.

Information Gain of feature A: $$IG(S,A)=H(S)-\sum _{v\in \text{Values}(A)}\frac{|S_v|}{|S|}H(S_v)$$

Worked Example: NTC Customer Complaint Routing Data:

Steps:

1. Calculate entropy of root: $$H(S)=-\left(\frac{3}{4}{\log }_2\frac{3}{4}+\frac{1}{4}{\log }_2\frac{1}{4}\right)=0.811$$
2. Compute IG for each feature:
   • Outlook:
     • Sunny: $H=0$ (2 Yes, 1 No),
     • Overcast: $H=0$ (1 Yes),
     • Rain: $H=0$ (1 No). $$IG=0.811-\left(\frac{3}{4}\times 0+\frac{1}{4}\times 0\right)=0.811$$
   • Temperature: IG = 0.152 (lower than Outlook).
3. Split on Outlook=Sunny:
   • Left subtree: Check Wind (IG = 0.918).
   • Right subtree: Overcast → Yes; Rain → No.

Mermaid Diagram: ID3 Tree for NTC Complaints

3.2 Advantages/Disadvantages

Real-World Use in Nepal:

• Nepal Rastra Bank Loan Approval: Decision trees evaluate loan applications by splitting on criteria like "income > 50k", "credit score > 700", etc.
• Khalti Transaction Risk: Splits transactions by amount, user history, and time to flag high-risk ones.

---

## In the Real World

1. eSewa Fraud Detection

   • Algorithm: KNN (k=3) with features = [transaction amount, time of day, user location].
   • How it works: If a new payment’s features match 3/3 known fraudulent transactions (e.g., high amount + unusual time), it’s flagged for review.
   • Why KNN? Simple to implement and effective for anomaly detection in small datasets.

2. Daraz Recommendation System

   • Algorithm: Decision Trees (or Random Forest) to predict "buy again" probability.
   • Features: [user browsing history, item category, price, discounts].
   • Example: A user who buys electronics frequently gets recommended a new smartphone if the tree splits on "category=electronics" → "price < 30k" → "buy probability = 0.85".

3. Ncell Customer Churn Prediction

   • Algorithm: Perceptron (for linear separability) or Decision Tree (for rules).
   • Features: [average calls/day, data usage, customer tenure].
   • Real Example: If a customer’s calls drop below 5/day and data usage < 1GB/month, the tree predicts churn with 80% accuracy.

---

## Exam Tip

1. Perceptron:

   • Must-know: Update rule $\mathbf{w}\leftarrow \mathbf{w}+\eta (y_i-{\hat{y}}_i){\mathbf{x}}_i$.
   • Common pitfall: Forgetting to normalize features (e.g., age vs. income scales differ).
   • Exam question: Given a small dataset, derive the final weights after 1–2 epochs.

2. KNN:

   • Must-know: How k affects bias/variance; Euclidean distance formula.
   • Common pitfall: Not scaling features (e.g., age in years vs. income in lakhs).
   • Exam question: Given 2D points, find the class of a new point using k=3.

3. Decision Trees (ID3):

   • Must-know: Entropy formula, information gain calculation, and how to build the tree step-by-step.
   • Common pitfall: Stopping splits too early (overfitting) or too late (complexity).
   • Exam question: Given a table, compute IG for each feature and choose the best split.

4. Visuals in Exams:

   • Always draw the decision boundary for perceptron/KNN.
   • For decision trees, show the tree structure with splits and leaf nodes labeled by class.

5. Real-World Connection:

   • Link KNN to fraud detection (eSewa) or medical diagnosis.
   • Link decision trees to loan approval (NRB) or customer segmentation (Daraz).

---