K-Nearest Neighbors (KNN) in Python: Math, Distance Metrics, and Code

K-Nearest Neighbors (KNN) is a non-parametric, distance-based supervised learning algorithm. Rather than estimating mathematical parameter weights during a training phase, KNN stores the complete training dataset as a spatial coordinate index and predicts new observations at query time by tallying votes (for classification) or averaging values (for regression) among the $K$ closest neighboring data points.

Imagine moving to a new residential street and wanting to estimate your property's value. Rather than building a complex macroeconomic housing model, you look at the 3 or 5 houses physically closest to yours and take their average price. KNN operates on this exact spatial assumption: data points residing close together in multidimensional feature space share similar target labels.

1. Why KNN Is Called a 'Lazy Learner'

• Zero Training Computation: The fit() step merely caches the training matrix ($O(1)$ time complexity).
• Inference-Heavy: The computational workload is deferred entirely to predict(), which computes distances to all $N$ training points across $d$ dimensions ($O(N \cdot d)$ per query).
• Non-Parametric Flexibility: Makes zero assumptions regarding linear boundaries or underlying Gaussian distributions, conforming naturally to complex, winding decision boundaries.

2. Distance Metric Taxonomy

3. The Bias-Variance Tradeoff in Choosing K

4. Worked Numerical Example (By Hand)

Consider $5$ training points in 2D space. We classify query point $x_{\text{new}} = (3, 3)$ with $K = 3$:

• Distance Ranking: P2 ($1.00$) < P4 ($2.00$) < P1 ($2.24$) < P3 ($4.24$) < P5 ($4.47$).
• Top $K = 3$ Neighbors: P2 (Red), P4 (Red), P1 (Red).
• Majority Vote: $3$ Red vs $0$ Blue $\implies$ Predicted Class: Red.

5. Code: Python Implementation From Scratch & Scikit-Learn

1. NumPy KNN Classifier Engine From Scratch

import numpy as np
from collections import Counter

X_train = np.array([[1, 2], [2, 3], [6, 6], [3, 1], [7, 5]], dtype=float)
y_train = np.array(["Red", "Red", "Blue", "Red", "Blue"])

def euclidean_distance(a, b):
    return np.sqrt(np.sum((a - b) ** 2))

class SimpleKNN:
    def __init__(self, k=3, distance_weighted=False):
        self.k = k
        self.distance_weighted = distance_weighted
        self.X_train = None
        self.y_train = None

    def fit(self, X, y):
        # Lazy training step: store references
        self.X_train = np.array(X)
        self.y_train = np.array(y)

    def predict(self, x_new):
        distances = []
        for idx, x_point in enumerate(self.X_train):
            d = euclidean_distance(x_point, x_new)
            distances.append((d, self.y_train[idx]))

        # Sort by distance
        distances.sort(key=lambda item: item[0])
        neighbors = distances[:self.k]

        if not self.distance_weighted:
            labels = [label for _, label in neighbors]
            return Counter(labels).most_common(1)[0][0]
        else:
            # Inverse distance weighting: closer points carry higher voting weight
            weights = {}
            for d, label in neighbors:
                w = 1.0 / (d + 1e-6)
                weights[label] = weights.get(label, 0.0) + w
            return max(weights, key=weights.get)

knn = SimpleKNN(k=3)
knn.fit(X_train, y_train)

query = np.array([3, 3])
print(f"Predicted class for {query.tolist()}: {knn.predict(query)}")

2. Production Scikit-Learn Pipeline with Preprocessing

from sklearn.neighbors import KNeighborsClassifier
from sklearn.preprocessing import StandardScaler
from sklearn.pipeline import make_pipeline

# Distance-based models REQUIRE feature standardization
knn_pipe = make_pipeline(
    StandardScaler(),
    KNeighborsClassifier(n_neighbors=3, metric="euclidean", weights="uniform")
)
knn_pipe.fit(X_train, y_train)

print(f"Scikit-Learn Prediction: {knn_pipe.predict([[3, 3]])[0]}")
print(f"Class Probabilities: {knn_pipe.predict_proba([[3, 3]])[0]}")

6. Critical Pitfalls: The Curse of Dimensionality & Scaling

• Mandatory Feature Standardization: If feature 1 ranges $0–1$ and feature 2 ranges $0–50,000$, feature 2 completely dominates the distance metric. Always scale with StandardScaler.
• The Curse of Dimensionality: As feature dimension $d$ grows, points become equidistant from one another in high-dimensional hypercubes, eroding relative distance metrics. Apply PCA or feature selection first.
• Ties in Binary Classification: Always select odd values of $K$ (e.g. $K=3, 5, 7$) for binary tasks to prevent $50/50$ vote deadlocks.

Summary

• KNN is an instance-based lazy learner that makes predictions based on the majority vote of the $K$ nearest neighbors.
• Distance Metrics: Euclidean ($L_2$) and Manhattan ($L_1$) measure spatial proximity across normalized continuous features.
• Choosing $K$ balances the bias-variance tradeoff: small $K$ overfits to local noise; large $K$ underfits toward the global majority.
• Feature scaling is strictly mandatory to prevent high-magnitude features from skewing distance measurements.