k-Nearest Neighbours

What is k-Nearest Neighbors (k-NN)?

k-Nearest Neighbors (k-NN) is one of the simplest supervised machine learning algorithms.

It relies on a intuitive principle: "Birds of a feather flock together."

Given a new unlabelled test sample $x_{\text{test}}$:

1. Measure geometric distance between $x_{\text{test}}$ and every single training point.
2. Identify the $k$ closest training points (Neighbors).
3. Classify: Take a majority vote among the $k$ neighbors.
4. Regress: Calculate the average target value of the $k$ neighbors.

  Class A (Red Circles)                     Class B (Blue Squares)
        (O)   (O)                                  (X)   (X)
           \   │   /                            /   │   /
            ▼  ▼  ▼                            ▼  ▼  ▼
         [ NEW TEST SAMPLE (?) ] ──► Find 3 Closest Neighbors: (2 Red, 1 Blue)
                                 ──► Predict: Class A (Red)!

Why k-NN is a "Lazy Learner"

Most ML algorithms (Linear Regression, Neural Nets) are Eager Learners: they process training data upfront to learn parameter weights ($w, b$), and throw away the raw training data.

k-NN is a Lazy Learner (Instance-Based Learning):

• Training Phase: Zero math! Simply stores the raw training dataset in memory.
• Inference Phase: Computes distances to all $N$ training samples when a query arrives.

Distance Metrics

1. Euclidean Distance (L2 Distance): Straight line distance in 2D/3D space.

$$d(x, z) = \sqrt{\sum_{i=1}^d (x_i - z_i)^2}$$

2. Manhattan Distance (L1 Distance): City block grid distance.

$$d(x, z) = \sum_{i=1}^d |x_i - z_i|$$

3. Cosine Distance: Measures vector direction angle rather than magnitude, ideal for text embeddings.

The Impact of Hyperparameter k

┌──────────────────────────┬──────────────────────────┐
│ SMALL k (e.g. k = 1)     │ LARGE k (e.g. k = 50)    │
├──────────────────────────┼──────────────────────────┤
│ High Variance / Overfitting│ High Bias / Underfitting│
│ Boundary noise sensitive.│ Decision boundary becomes│
│ Fits individual outliers.│ smooth and over-averaged.│
└──────────────────────────┴──────────────────────────┘

Always choose an odd value for $k$ in binary classification (e.g. $k = 3, 5, 7$) to prevent tie votes!

Severe Limitations of k-NN

1. Curse of Dimensionality: As feature count $d$ grows large, distance between points becomes uniform, ruining neighbor search quality.
2. Inference Latency $O(N \cdot d)$: Must measure distance to every single sample $N$ at prediction time. Slow for millions of samples unless indexed via KD-Trees or Ball-Trees.
3. Feature Scaling Mandatory: Un-scaled features dominate distance formulas. Always apply StandardScaler first.

Say this out loud

k-Nearest Neighbors is a non parametric instance based lazy learner that makes predictions by finding the k closest training points using distance metrics. Small k produces high variance decision boundaries sensitive to noise, while large k produces high bias. Feature scaling is mandatory because distance metrics are sensitive to feature numerical ranges.

Followups to expect

1. How do KD-Trees speed up k-NN inference? Partitioning feature space into a binary tree structure, reducing neighbor search time from $O(N)$ brute force down to $O(\log N)$ for low dimensional data ($d < 20$).
2. What is Weighted k-NN? Weighting neighbor votes inversely by distance ($w = 1 / d^2$) so closer neighbors have a stronger influence on predictions than distant neighbors.