K-Nearest Neighbors (KNN) & Distance Metrics

K-Nearest Neighbors (KNN) is one of the simplest yet remarkably powerful machine learning algorithms. Unlike parametric algorithms (like Linear or Logistic Regression) that learn mathematical weights w during an explicit training step, KNN is a Non-Parametric, Lazy Learning algorithm that memorizes the entire training dataset and defers all computation until prediction time.

How KNN Works: The 3-Step Inference Rule

Calculate Distance: When a new query point x_new arrives, compute its distance to every single point in the historical training set.
Find K Neighbors: Identify the k closest training data points.
Vote or Average: For classification, assign the majority class label among the k neighbors. For regression, predict the mean average target value of the k neighbors.

Core Distance Metrics in KNN

The performance of KNN depends heavily on the geometric distance function selected for the feature space:

Distance Metric	Mathematical Formula	Geometric Properties
Euclidean Distance (L2)	`d(p, q) = √∑(pᵢ - qᵢ)²`	Straight-line "as the crow flies" shortest distance. Most common default.
Manhattan Distance (L1)	`d(p, q) = ∑\|pᵢ - qᵢ\|`	Grid-like city block navigation. Better than L2 for higher-dimensional spaces.
Minkowski Distance (L_p)	`d(p, q) = (∑\|pᵢ - qᵢ\|^p)^(1/p)`	Generalization: p=1 yields Manhattan; p=2 yields Euclidean.
Cosine Distance	`1 - (p · q) / (\|\|p\|\| \|\|q\|\|)`	Measures angular orientation rather than magnitude; ideal for text NLP.

Choosing the Optimal Hyperparameter K

Selecting the number of neighbors K controls the Bias-Variance tradeoff of the classifier:

Small K (e.g., K = 1): High Variance, Low Bias. The decision boundary wraps tightly around every individual data point, memorizing noise and causing severe overfitting.
Large K (e.g., K = 100): High Bias, Low Variance. The boundary becomes overly smooth and flat, eventually predicting whatever class has the largest population in the dataset.
Rule of Thumb: Start with K = √N (where N is the sample size). Always choose an odd number for binary classification to prevent tied votes!

Two Fatal Weaknesses of KNN in Production

1. O(N · d) Prediction Latency: Because KNN must compute distances to every sample for each query, inference is extremely slow on large databases. Use KD-Trees or Ball-Trees to accelerate search.
2. Curse of Dimensionality: In spaces with hundreds of features, all points become almost equidistant from each other, rendering distance metrics meaningless.

Frequently Asked Questions (FAQ) - Student & Interview Review

Q1. Why is Feature Scaling mandatory for KNN?

KNN calculates distances. If one feature (Income: 50,000) has a much wider scale than another (Age: 30), the distance calculation will be completely dominated by the income feature.

Q2. Is training time fast or slow in KNN?

Training time is instantaneous O(1) because KNN simply stores the data without learning parameters. However, prediction inference time is slow O(N*d).

Q3. How does Weighted KNN work?

Weighted KNN assigns weights inversely proportional to distance (weight = 1 / distance), giving closer neighbors a significantly greater say in the majority vote than distant neighbors.