K-Nearest Neighbors (KNN)

 

K-Nearest Neighbors (KNN)

K-Nearest Neighbors (KNN) is a simple, intuitive supervised learning algorithm used for:

• Classification (e.g., spam vs not spam)
• Regression (predicting continuous values)

It is a lazy learning algorithm, meaning:

It does not build an explicit model during training—it stores the data and makes decisions at prediction time.

---

🧠 Core Idea

“A data point is likely to have the same label as its nearest neighbors.”

When a new data point comes in:

1. Find the K closest points in the training data
2. Look at their labels
3. Assign the majority label (for classification)

---

⚙️ How KNN Works (Step-by-Step)

Step 1: Choose K

• Number of neighbors to consider
• Example: K = 3, 5, 7

---

Step 2: Compute Distance

The most common distance metric is Euclidean distance:

$d(x,y)=\sqrt{\sum_{i=1}^{n}(x_i - y_i)^2}$

Other distance measures:

• Manhattan distance
• Minkowski distance
• Cosine similarity (for text data)

---

Step 3: Find Nearest Neighbors

• Compute distance from new point to all training points
• Sort and select K smallest distances

---

Step 4: Make Prediction

For Classification:

• Use majority voting

For Regression:

• Take average of neighbors

---

📊 Example (Simple Classification)

Dataset

Student	Study Hours	Result
A	2	Fail
B	4	Fail
C	6	Pass
D	8	Pass

---

Predict for New Student:

• Study Hours = 5
• Choose K = 3

Step 1: Compute Distance

Point	Distance from 5
2	3
4	1
6	1
8	3

---

Step 2: Pick 3 Nearest

→ (4, 6, 2)

Labels:

• Fail, Pass, Fail

---

Step 3: Majority Vote

👉 Fail = 2
👉 Pass = 1

✅ Prediction: FAIL

---

🎯 Choosing the Value of K

K Value	Behavior
Small K (e.g., 1)	Sensitive to noise (overfitting)
Large K	Smooth decision boundary (underfitting)

👉 Common practice:

• Use odd K for binary classification
• Choose K using cross-validation

---

📐 Important Concept: Feature Scaling

KNN depends on distance → scale matters!

Example:

• Salary (₹) vs Age (years)

👉 Use:

• Min-Max Scaling
• Standardization

🧮 KNN Regression

For ordinary KNN regression, take the average:

Prediction=355+65+45​=55

💰 Predicted price = ₹55 lakh

---

⚖️ Weighted KNN

In ordinary KNN, every neighbor gets equal importance.

In Weighted KNN, closer neighbors get more importance.

📌 A common weight is:

wi​=1/di​

where di​ is the distance from the new observation.

Example

Suppose the three neighbors are:

Neighbor	Distance	Price	Weight
A	0.5	₹50 lakh	2.0
B	1.0	₹45 lakh	1.0
C	2.0	₹30 lakh	0.5

Notice:

🔵 Closer → higher weight
🟠 Farther → lower weight

The weighted prediction is:

y^​=∑wi​yi​​/∑wi​=(2)(50)+(1)(45)+(0.5)(30)​/2+1+0.5 =160​/3.5=45.71

💰 Weighted KNN prediction = ₹45.71 lakh

---

🔑 KNN vs Weighted KNN

	KNN	Weighted KNN
👥 Neighbors	K closest	K closest
⚖️ Importance	Equal	Based on distance
📊 Regression	Simple average	Weighted average
🏷️ Classification	Majority vote	Weighted vote
📍 Closest point	Same importance	More important

⭐ Easy way to remember

KNN:

👥 All neighbors have an equal vote.

Weighted KNN:

📍 Closer neighbors have a stronger vote.

---

Ordinary KNN vs Weighted KNN

Feature	KNN	Weighted KNN
Neighbor importance	Equal	Depends on distance
Close neighbor	Same importance	Higher importance
Distant neighbor	Same importance	Lower importance
Regression	Average of neighbors	Weighted average
Classification	Majority vote	Weighted vote

---

⚡ Advantages

• ✅ Simple to understand and implement
• ✅ No training phase
• ✅ Works well with small datasets
• ✅ Non-parametric (no assumptions about data distribution)

---

⚠️ Disadvantages

• ❌ Slow for large datasets (computationally expensive)
• ❌ Sensitive to irrelevant features
• ❌ Requires proper scaling
• ❌ Memory intensive (stores all data)

---

📌 Real-World Applications

• 📧 Spam detection
• 🏥 Medical diagnosis
• 🎯 Recommendation systems
• 🖼️ Image classification
• 🧍 Pattern recognition

---

🧩 KNN vs Naïve Bayes (Quick Contrast)

Aspect	KNN	Naïve Bayes
Type	Instance-based	Probabilistic
Training	None	Required
Speed	Slow at prediction	Fast
Assumption	None	Feature independence

---

📌 Final Summary

• KNN is a distance-based algorithm
• It predicts using similarity
• Works by majority voting of neighbors