Supervised Learning · Classification

K-Nearest Neighbors & Decision Boundaries

Witness the Bias-Variance tradeoff live: how neighborhood size $K$ shifts the classifier from overfitting to underfitting

Non-Parametric Estimation & Majority Voting

Unlike parametric models (e.g. Logistic Regression) that assume a specific functional form, the K-Nearest Neighbors (KNN) algorithm makes no prior structural assumptions about the data distribution. Given a query point $\mathbf{x} \in \mathbb{R}^d$, KNN locates the set $\mathcal{N}_K(\mathbf{x})$ of the $K$ closest training samples and estimates class probabilities via local empirical frequencies:

$$P(Y = c \mid \mathbf{x}) = \frac{1}{K} \sum_{i \in \mathcal{N}_K(\mathbf{x})} \mathbb{I}(y_i = c)$$

The predicted label is the plurality winner: $\hat{y} = \arg\max_c P(Y = c \mid \mathbf{x})$.

Why choose odd values for $K$? In binary classification, restricting $K \in \{1, 3, 5, \dots\}$ guarantees that majority voting can never result in an ambiguous $50/50$ tie.

Interactive Classification Workbench

Optimal Generalization

Model Hyperparameters

Parameter K (Neighbors) 3

K=1 (Overfit) K=9 (Balanced) K=21 (Underfit)

Click Canvas to Add Point

Class A (Red) Class B (Blue)

Distance Metric

Benchmark Geometry

Diagnostics & Complexity 50×50 Grid

Neighborhood (K) 3

Class A Points (Red) 45

Class B Points (Blue) 45

Total Observations (N) 90

Training Accuracy 98.9%

Bias-Variance State

Balanced trade-off between variance and bias; boundary reflects underlying manifold.

Click anywhere on the graph to add a training point

Overfitting at Low K (K = 1)
When $K=1$, the decision boundary tightly wraps around every single training observation. Training error is zero, but variance is extreme: any slight label noise creates an isolated "island" in feature space that devastates test-set generalization.

Underfitting at High K (K ≥ 15)
As $K$ approaches sample size $N$, local neighborhood context is lost. The model votes become dominated by the global class balance, causing high bias. Complex geometric boundaries (like interlocking spirals or moons) are smoothed out into flat planes.

Theoretical Foundations & Nuances

1. The Curse of Dimensionality

In high-dimensional spaces ($d \gg 10$), the volume of space grows exponentially. All data points become approximately equidistant from one another ($\lim_{d \to \infty} \frac{\text{dist}_{\max} - \text{dist}_{\min}}{\text{dist}_{\min}} \to 0$), severely degrading distance-based metrics.

2. Computational Complexity

KNN is a lazy learner: training cost is $O(1)$, but inference cost is $O(n \cdot d)$ per query because all pairwise distances must be calculated. In production systems, $k$-d trees or Approximate Nearest Neighbor (ANN) indexes like HNSW are used.

3. Metric Sensitivity

Switching between Euclidean ($L_2$) and Manhattan ($L_1$) changes the shape of equidistant contours from circles to diamonds. In grid-like feature spaces (such as city blocks or taxicab routing), $L_1$ often outperforms $L_2$.