K-Nearest Neighbors

1. Introduction

K-Nearest Neighbors (KNN) is one of the most intuitive ML algorithms — it makes predictions based on a simple idea: "look at what similar, nearby data points did, and follow their lead." Unlike Linear and Logistic Regression, KNN doesn't learn an explicit mathematical equation; instead, it makes decisions by directly comparing new data to the data it has already seen.

2. What is K-Nearest Neighbors?

Simple definition: KNN is a supervised learning algorithm that classifies (or predicts a value for) a new data point by looking at the "k" closest points in the training data and going with the majority vote (for classification) or the average (for regression).

Technical explanation: KNN is a non-parametric, instance-based learning algorithm that, for a new data point, calculates its distance (commonly Euclidean distance) to every point in the training set, identifies the k nearest neighbors, and predicts the output based on those neighbors — majority class for classification, or average value for regression.

3. Why is it Important?

• It's one of the simplest algorithms to understand intuitively, making it an excellent teaching tool for the concept of similarity-based prediction.
• It requires no explicit "training" phase in the traditional sense — it simply stores the data and computes distances at prediction time.
• It performs surprisingly well on many real-world problems, especially with well-scaled features.

4. Prerequisites

Comfort with Linear Algebra Basics (Module 1, Topic 10, especially distance concepts) and Feature Scaling (Module 3, Topic 7) — KNN is highly sensitive to feature scale.

5. Core Concepts

1. Distance calculation (Euclidean distance)
2. Choosing the value of k
3. Majority voting (classification) vs averaging (regression)
4. Why feature scaling matters critically for KNN

6. Detailed Explanation

a) Distance Calculation

KNN measures how "close" two data points are, most commonly using Euclidean distance — essentially the straight-line distance between two points, calculated using the same idea as the Pythagorean theorem, extended across all feature dimensions.

b) Choosing `k`

k is a hyperparameter (Module 2, Topic 10) representing how many nearby neighbors to consider. A small k (like 1) makes predictions very sensitive to noise/outliers; a large k smooths predictions but risks ignoring genuinely local patterns. The right k is often found through experimentation (Module 7).

c) Majority Voting vs Averaging

For classification, KNN looks at the classes of the k nearest neighbors and predicts whichever class appears most often (majority vote). For regression, it instead averages the numeric values of the k nearest neighbors.

d) Why Feature Scaling Matters

Since KNN relies directly on distance calculations, a feature with a naturally larger numeric range (like salary, in the thousands) would completely dominate a feature with a smaller range (like age, in the tens) unless both are scaled to a comparable range first (Module 3, Topic 7).

7. How It Works

1. Store the entire training dataset (KNN doesn't build an explicit model during "training" — it just remembers the data).
2. When a new data point needs a prediction, calculate its distance to every point in the training set.
3. Identify the k closest points (the "nearest neighbors").
4. For classification: predict the majority class among these neighbors. For regression: predict the average value among these neighbors.

8. Real-World Example

Imagine trying to guess a new house's price by looking at the 5 most similar houses (in terms of size, location, and age) that have already sold. If most of those 5 similar houses sold for around $300,000, you'd reasonably guess the new house is worth around that much too — this is exactly the intuition behind KNN.

9. Mathematical Explanation

Euclidean Distance Formula (Two Points):

distance = √((x₂ − x₁)² + (y₂ − y₁)²)

For higher dimensions (multiple features), this extends to:

distance = √(Σ(featureᵢA − featureᵢB)²)

Where:

• featureᵢA, featureᵢB = the value of feature i for points A and B respectively
• The sum is taken across all features

Numerical Example:

Point A (new house): [size=20, age=5] Point B (existing house): [size=22, age=8]

distance = √((22−20)² + (8−5)²) = √(4 + 9) = √13 ≈ 3.61

Interpreting the Result: A smaller distance value means the two points are more similar across their features; KNN would rank this house as "closer" compared to houses with larger calculated distances, and closer houses have more influence on the final prediction.

10. Python Example

python
from sklearn.neighbors import KNeighborsClassifier
from sklearn.preprocessing import StandardScaler
import numpy as np

# Features: [hours_studied, attendance_percent]
X = np.array([
    [1, 60], [2, 65], [3, 70], [8, 95], [9, 98], [7, 90]
])
y = np.array([0, 0, 0, 1, 1, 1])   # 0 = Fail, 1 = Pass

# Scaling is important for KNN since features have very different ranges
scaler = StandardScaler()
X_scaled = scaler.fit_transform(X)

model = KNeighborsClassifier(n_neighbors=3)
model.fit(X_scaled, y)

# Predicting for a new student (must be scaled the same way)
new_student = scaler.transform([[6, 85]])
prediction = model.predict(new_student)
print("Prediction (0=Fail, 1=Pass):", prediction[0])

Expected Output (approximate):

text
Prediction (0=Fail, 1=Pass): 1

11. Code Explanation

• StandardScaler().fit_transform(X) scales both features to a comparable range, which is essential since "attendancepercent" (60-98) has a much larger numeric range than "hoursstudied" (1-9).
• KNeighborsClassifier(n_neighbors=3) sets k=3, meaning the algorithm will look at the 3 closest training points for each prediction.
• scaler.transform([[6, 85]]) applies the SAME scaling (fit only on training data) to the new student's data before predicting — critical for consistent distance calculations.
• model.predict(new_student) finds the 3 nearest neighbors to this new student in the scaled feature space and predicts based on their majority class.

12. Advantages

• Simple, intuitive, and easy to explain to non-technical audiences.
• No explicit training phase — new data can be incorporated simply by adding it to the stored dataset.
• Naturally handles multi-class classification problems without modification.

13. Limitations

• Can be slow at prediction time for large datasets, since it must calculate distances to every training point for each new prediction.
• Highly sensitive to feature scale — unscaled data can produce very misleading results.
• Sensitive to irrelevant features, since they still contribute to the distance calculation even if they don't actually help distinguish classes.
• Choosing the right k requires experimentation.

14. Common Mistakes

• Forgetting to scale features before applying KNN, leading to features with larger ranges dominating the distance calculation.
• Choosing k=1, which makes the model extremely sensitive to noise and outliers in the training data.
• Not considering the computational cost of KNN on very large datasets.
• Fitting the scaler on the full dataset instead of the training set only (a data leakage mistake, see Module 3, Topic 7).

15. Best Practices

• Always scale features before applying KNN.
• Experiment with different values of k (often using Grid Search, Module 7) to find the best-performing choice.
• Consider removing irrelevant features before applying KNN, since they can distort distance calculations.
• Be mindful of computational cost with very large datasets.

16. Real-World Applications

• Recommendation systems (finding users or items similar to a given one).
• Handwriting and image recognition (comparing new images to labeled examples).
• Simple anomaly detection (points far from all their neighbors may be outliers).

17. Interview-Oriented Points

• Be ready to explain how KNN makes predictions using distance and majority voting/averaging.
• Understand why feature scaling is critical for KNN specifically.
• Be able to explain the tradeoff between small and large values of k.

18. Exam-Oriented Points

• KNN predicts based on the k nearest neighbors' majority class (classification) or average (regression).
• Euclidean distance is the most common distance metric used.
• Feature scaling is essential, since KNN relies directly on distance calculations.
• k is a hyperparameter chosen before training, not learned from the data.

19. Comparison Table — KNN vs Logistic Regression

20. Quick Revision

• KNN predicts based on the majority class (or average value) among the k nearest neighbors to a new data point.
• Distance is typically measured using Euclidean distance.
• Feature scaling is critical for KNN, since it directly relies on distance calculations.
• k is a hyperparameter that must be chosen carefully — too small risks noise sensitivity, too large risks over-smoothing.