Lesson 09 � Classification

KNN: K-NEAREST
NEIGHBORS

KNN sabse simple aur intuitive ML algorithm hai. Naya data point aaya✓ Sabse paas ke K neighbors dekho aur unka majority vote lo � jo sabse zyada dikha wahi class assign karo. Training ki zaroorat nahi, seedha data se directly predict karo.

? 20 min✓ Intermediate✓ Prerequisite: Naive Bayes

WHY: KNN kyun sabse easy hai?

KNN ka logic bilkul insaan jaisa hai � jab aap kisi nayi jagah jaate ho toh aap apne paas ke logon se poochte ho "yahan kya hota hai?" KNN bhi yahi karta hai: naye data point ke liye sabse paas ke K data points dhundhta hai, phir unki majority vote se class decide karta hai. Koi training nahi, koi formula nahi � sirf distance dekho aur vote lo.

K (NEIGHBORS)

Kitne nearest neighbors ko dekhna hai. K=3 ka matlab: sabse paas ke 3 data points dekho aur unka majority class assign karo. K chhota ho toh overfitting, K bada ho toh underfitting. Odd K lena better hai taaki tie na aaye.

DISTANCE

Do points ke beech ka distance kaise nikaalte hain. Sabse common hai Euclidean distance � straight-line distance. Manhattan distance (L1 norm) bhi use hota hai jab features bahut alag scales pe hon. Distance kam = point zyada similar hai.

MAJORITY VOTE

K neighbors ki class dekho � jo class sabse zyada baar aaye woh prediction. Agar K=5 aur 3 neighbors class A mein hain aur 2 class B mein, toh prediction = A. Tie ho jaaye toh distance-weighted voting use karo � paas wale ko zyada weight do.

LAZY LEARNER

KNN ko "lazy learner" bolte hai kyunki yeh training time pe kuch nahi seekhta. Seedha data store kar leta hai aur prediction time pe compute karta hai. Fast training, slow prediction. Memory-intensive hota hai kyunki poora data store karna padta hai.

WHAT: Distance metrics kya hain?

KNN ka sabse important part hai distance calculation � ki do data points kitne paas ya door hain. Jitna kam distance, utna zyada similar point. Distance metric choose karna model ki performance directly affect karta hai.

Distance Metrics:
?

1. EUCLIDEAN DISTANCE (L2 Norm):
 ✓ Sabse common � straight-line distance
 ✓ Formula: d = v((x2-x1)� + (y2-y1)�)
 ? 2D mein: Pythagoras theorem jaisa
 ✓ Jab sab features same scale pe hon

 Example:
 Point A: (1, 2)
 Point B: (4, 6)
 d = v((4-1)� + (6-2)�)
 d = v(9 + 16) = v25 = 5

2. MANHATTAN DISTANCE (L1 Norm):
 ✓ City block distance � seedha nahi, L-shape mein chalte ho
 ✓ Formula: d = |x2-x1| + |y2-y1|
 ✓ High-dimensional data mein better kaam karta hai
 ✓ Feature scales bahut alag hon toh use karo

 Example:
 Point A: (1, 2)
 Point B: (4, 6)
 d = |4-1| + |6-2| = 3 + 4 = 7

3. MINKOWSKI DISTANCE:
 ✓ Euclidean aur Manhattan ka general form
 ✓ Formula: d = (S|x? - y?|^p)^(1/p)
 ✓ p=2 ✓ Euclidean
 ✓ p=1 ✓ Manhattan

Comparison:
 Metric | Best For | Sensitivity
 --------------+-----------------------+-------------
 Euclidean | Same scale data | Outliers se affect
 Manhattan | High dimensions | Less sensitive
 Cosine | Text/word vectors | Angle-based
 Minkowski | Flexible | p parameter

WHAT: K value ka kya role hai?

K value sabse important hyperparameter hai KNN mein. Yeh decide karta hai kitne neighbors ko dekhna hai. K ki value change karo toh decision boundary badal jaati hai � bahut chhota K toh model noise capture karta hai, bahut bada K toh oversimplify ho jaata hai.

K Value Impact:
?

K = 1:
 ✓ Sirf sabse paas ka ek point dekhta hai
 ✓ Training accuracy: 100% (perfect memorize)
 ✓ Test accuracy: bahut kam (overfitting)
 ✓ Har noise ko capture karta hai
 ✓ Decision boundary: bahut jagged/complex

K = 3:
 ✓ Top 3 neighbors ka vote leta hai
 ✓ Thoda smooth decision boundary
 ✓ Better generalization
 ✓ Odd number � tie ka risk kam

K = 5 ya 7:
 ✓ Zyada neighbors � smoother boundary
 ✓ Less overfitting
 ✓ Lekin important patterns bhi miss ho sakte hain
 ✓ Generalization better

K = N (poora dataset):
 ✓ Har bar majority class predict karega
 ✓ Underfitting � kuch nahi seekha
 ✓ Accuracy = minority class percentage

Best K kaise choose karo:
 ✓ Odd K choose karo (taaki tie na aaye)
 ✓ Cross-validation use karo
 ✓ K = vN formula (N = total data points)
 ✓ Elbow method � K badhate jao, error plot karo
 jahan error elbow dikhaye wahan best K hai

Visual Effect:
 K=1: *.*.*.* (noisy, jagged)
 K=3: *.*.* (slightly smooth)
 K=7: *.* (very smooth)
 K=N: * (flat line � useless)

WHAT: Lazy Learning vs Eager Learning

KNN "lazy learner" hai � jabki most other algorithms "eager learner" hain. Lazy learner kuch nahi seekhta training time pe, seedha data store kar leta hai. Prediction time pe kaam karta hai. Eager learner training pe time lagake ek model banata hai, phir prediction fast hoti hai.

Lazy Learning (KNN) vs Eager Learning (others):
?

 | Lazy (KNN) | Eager (Decision Tree, SVM)
--------------------+---------------------+-----------------------------
Training Time | Almost zero | High � model build karta hai
Prediction Time | High � har bar | Low � model ready hai
Memory Usage | High � poora data | Low � sirf model store
Model Complexity | No explicit model | Explicit model banata hai
Interpretability | Distance-based | Algorithm pe depend karta hai
Overfitting Risk | High K=1 pe | Regularization se control
New Data Add | Turant add kar sakte| Retrain karna padta hai

Real-world Analogy:
 LAZY: Apne (notes) ghhar pe rakh lo,
 exam mein directly dekh lo
 EAGER: Pehle notes se summary banao,
 summary se padho � exam mein summary dekho

Kab Lazy better hai:
 ✓ Data thoda hai (memory issue nahi)
 ✓ Data fast badhta hai (frequent updates)
 ✓ Quick prototype banana hai

Kab Eager better hai:
 ✓ Data bahut hai (memory issue)
 ✓ Fast prediction chahiye (production)
 ✓ Model interpretability important hai

TRY IT: Python mein KNN

Neeche ka editor Python jaisa hai. Yahan code likho aur "Run Python" dabao. Real scikit-learn KNeighborsClassifier use ho raha hai � K ki value change karke dekho accuracy kaise badalti hai.

Python playgroundKNN Classifier � K value experiment

main.py

from sklearn.neighbors import KNeighborsClassifier
from sklearn.model_selection import train_test_split
from sklearn.metrics import accuracy_score
import numpy as np

# Simple 2D dataset � 2 classes
X = np.array([[1,2],[2,3],[3,3],[6,1],[7,2],[8,3],[4,4],[5,2]])
y = np.array([0,0,0,1,1,1,0,1])

print("=== Training Data ===")
for features, label in zip(X, y):
 cls = "Class 1" if label == 1 else "Class 0"
 print(f" Point {features} ? {cls}")

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

# KNN with K=3
model = KNeighborsClassifier(n_neighbors=3)
model.fit(X_train, y_train)
print(f"\n=== KNN Results (K=3) ===")
print(f"Accuracy: {model.score(X_test, y_test):.2%}")

# Predict new point
new_point = [[5,2]]
prediction = model.predict(new_point)
print(f"\nPredict {new_point}: Class {prediction[0]}")

# Find actual neighbors
distances, indices = model.kneighbors(new_point)
print(f"\nNearest neighbors for {new_point}:")
for i, (idx, dist) in enumerate(zip(indices[0], distances[0])):
 print(f" Neighbor {i+1}: {X_train[idx]} (Class {y_train[idx]}) � Distance: {dist:.2f}")

# Experiment with different K values
print(f"\n=== K Value Experiment ===")
for k in [1, 3, 5, 7]:
 m = KNeighborsClassifier(n_neighbors=k)
 m.fit(X_train, y_train)
 acc = m.score(X_test, y_test)
 print(f" K={k}: Accuracy = {acc:.2%}")

Optional input

Code ko apni info se update karke run karein

HOW: Feature Scaling kyun zaroori hai?

KNN distance-based algorithm hai. Agar features alag scales pe hain toh bade wale feature dominate karega. Jaise "Salary" (0-100000) aur "Age" (0-100) � salary ka distance hamesha zyada dikhega, Age ka effect gayab. Isliye feature scaling karna zaroori hai.

Feature Scaling:


Problem:
 Feature 1: Age (0-100)
 Feature 2: Salary (30000-150000)

 Point A: (25, 50000)
 Point B: (30, 52000)

 Euclidean Distance:
 = v((30-25)� + (52000-50000)�)
 = v(25 + 4000000)
 = v4000025 � 2000

 ✓ Salary ne distance ko dominate kiya!
 ✓ Age ka koi effect nahi dikha

Solutions:

1. MIN-MAX SCALING (0-1 range):
 ✓ X_scaled = (X - X_min) / (X_max - X_min)
 ✓ Sab features 0 aur 1 ke beech aa jaate hain
 ✓ Sensitive hai outliers ke liye

2. STANDARD SCALING (Z-score):
 ✓ X_scaled = (X - mean) / std_dev
 ✓ Mean = 0, Std = 1
 ✓ Outliers se less affected
 ✓ Sabse common use hota hai

Scikit-learn mein:
 from sklearn.preprocessing import StandardScaler
 scaler = StandardScaler()
 X_train_scaled = scaler.fit_transform(X_train)
 X_test_scaled = scaler.transform(X_test) # sirf transform, fit nahi!

Rule:
 ✓ KNN mein hamesha scaling karo
 ✓ fit_transform sirf training data pe
 ✓ sirf transform test data pe (data leak se bachna)

Quick check

Exercise

KNN mein K ka role kya hai?

Sochho � jab naya point aata hai toh KNN kitne paas ke points dekhta hai✓ K value decide karti hai ki "nearest" ka matlab kitne neighbors hain. K=3 ka matlab sabse paas ke 3 points ka vote lo.

HOW: Distance calculation example

KNN Step-by-Step Example:
?

Training Data:
 Point A: (2, 3) ✓ Class 0
 Point B: (1, 1) ✓ Class 0
 Point C: (5, 4) ✓ Class 1
 Point D: (6, 2) ✓ Class 1
 Point E: (4, 6) ✓ Class 1

New Point: P = (3, 4), K = 3

Step 1: Distances calculate karo
 d(P,A) = v((3-2)� + (4-3)�) = v(1+1) = 1.41
 d(P,B) = v((3-1)� + (4-1)�) = v(4+9) = 3.61
 d(P,C) = v((3-5)� + (4-4)�) = v(4+0) = 2.00
 d(P,D) = v((3-6)� + (4-2)�) = v(9+4) = 3.61
 d(P,E) = v((3-4)� + (4-6)�) = v(1+4) = 2.24

Step 2: Sort by distance
 1. A: 1.41 ✓ Class 0
 2. C: 2.00 ✓ Class 1
 3. E: 2.24 ✓ Class 1

Step 3: K=3 nearest neighbors
 ✓ A (Class 0), C (Class 1), E (Class 1)

Step 4: Majority vote
 ✓ Class 0: 1 vote
 ✓ Class 1: 2 votes
 ✓ Prediction: Class 1 ?

Distance Weighted Voting:
 Agar tie ho toh � paas wale ko zyada weight do
 Weight = 1/distance

 A: 1/1.41 = 0.71 (Class 0)
 C: 1/2.00 = 0.50 (Class 1)
 E: 1/2.24 = 0.45 (Class 1)

 Weighted Class 0 = 0.71
 Weighted Class 1 = 0.50 + 0.45 = 0.95
 ✓ Prediction: Class 1 ?

Common beginner mistakes

Feature scaling skip karna: KNN distance-based hai. Bade scale wale features dominate kar denge. Hamesha StandardScaler ya MinMaxScaler use karo. Fit sirf training data pe, transform dono pe.
K=1 rakhna: K=1 pe overfitting hota hai � har noise point ko capture karta hai. Testing pe accuracy bahut kam aati hai. Odd K=3 ya K=5 se start karo.
Odd K na lena: Agar K even hai toh tie ho sakta hai (2 votes Class 0, 2 votes Class 1). Hamesha odd K choose karo taaki clear majority aaye.
Sab features same samajhna: Har feature ka importance alag hota hai. Feature selection karo � irrelevant features hatao. Feature scaling karo � sab features ko same scale pe lao.
Large dataset pe KNN use karna: Prediction time O(N) hai � har prediction pe poora data scan karo. 10 lakh rows pe KNN bahut slow hoga. Ball tree ya KD-tree use karo ya doosra algorithm choose karo.
Categorical features ka distance nahi samajhna: Euclidean distance numerical features ke liye hai. Categorical features ke liye one-hot encoding karo ya Hamming distance use karo.

KNN clear?

Ab Clustering par chalo � data ko groups mein todna bina labels ke. K-Means, Hierarchical, DBSCAN � sab cover honge.

KNN: K-NEARESTNEIGHBORS