k-Nearest Neighbors: Algorithm Deep Dive

Overview#

KNN is conceptually the simplest algorithm in this entire series — there is no training phase, no weights to learn, no loss function to minimize. It makes predictions purely by comparing a new point to the training data directly. This notebook goes deep into distance metrics and their geometric meaning, exactly how KNN makes decisions, the mathematics of why high dimensionality breaks it, efficient search structures that make it practical at scale, and a rigorous treatment of the bias-variance behavior as k varies.

1. The Algorithm, With No Simplification#

text
Ask AICopy
Training: store the entire training dataset (X, y). That's it — no
          computation happens at all.

Prediction, for a new point x_new:
1. Compute the distance from x_new to EVERY point in the training set
2. Sort all training points by distance, ascending
3. Take the k CLOSEST points
4. Classification: return the MAJORITY class among those k neighbors
   Regression: return the MEAN (or weighted mean) of their target values

Python
CopyAsk AI
import numpy as np

def knn_predict_manual(X_train, y_train, x_new, k=5):
    distances = np.sqrt(np.sum((X_train - x_new) ** 2, axis=1))   # Euclidean distance to every point
    nearest_indices = np.argsort(distances)[:k]                     # indices of the k closest points
    nearest_labels = y_train[nearest_indices]

    # Majority vote
    values, counts = np.unique(nearest_labels, return_counts=True)
    return values[np.argmax(counts)]

X_train = np.array([[1, 2], [2, 3], [3, 1], [6, 5], [7, 7], [8, 6]])
y_train = np.array([0, 0, 0, 1, 1, 1])

prediction = knn_predict_manual(X_train, y_train, np.array([2, 2]), k=3)
print(f"Prediction: {prediction}")   # 0, since the closest 3 points are all class 0

There is genuinely nothing more to the core algorithm than this — its entire complexity lies in choices around distance metric, k, and efficient implementation, not in the decision rule itself.

2. Distance Metrics, Mathematically#

Python
CopyAsk AI
def euclidean_distance(x1, x2):
    return np.sqrt(np.sum((x1 - x2) ** 2))

def manhattan_distance(x1, x2):
    return np.sum(np.abs(x1 - x2))

def minkowski_distance(x1, x2, p):
    return np.sum(np.abs(x1 - x2) ** p) ** (1 / p)

def chebyshev_distance(x1, x2):
    return np.max(np.abs(x1 - x2))

def cosine_distance(x1, x2):
    return 1 - np.dot(x1, x2) / (np.linalg.norm(x1) * np.linalg.norm(x2))

x1, x2 = np.array([1, 2, 3]), np.array([4, 1, 5])
print(f"Euclidean: {euclidean_distance(x1, x2):.3f}")
print(f"Manhattan: {manhattan_distance(x1, x2):.3f}")
print(f"Minkowski (p=3): {minkowski_distance(x1, x2, p=3):.3f}")
print(f"Chebyshev: {chebyshev_distance(x1, x2):.3f}")
print(f"Cosine: {cosine_distance(x1, x2):.3f}")

text
Ask AICopy
Minkowski distance is a GENERALIZATION: 
  p=1  → exactly Manhattan distance
  p=2  → exactly Euclidean distance
  p=∞  → exactly Chebyshev distance (the maximum single-dimension difference)

Euclidean is the default, most intuitive choice for continuous, similarly-
scaled features. Manhattan can be more appropriate in high-dimensional
spaces or grid-like structures (e.g., city block navigation, or when
features shouldn't compound multiplicatively). Cosine distance ignores
MAGNITUDE entirely, comparing only the ANGLE between vectors — extremely
common for text/document similarity, where document LENGTH shouldn't
affect similarity, only the relative proportions of terms used.

Why the choice of metric actually changes results#

Python
CopyAsk AI
from sklearn.neighbors import KNeighborsClassifier
from sklearn.datasets import load_wine
from sklearn.model_selection import train_test_split, cross_val_score
from sklearn.preprocessing import StandardScaler

X, y = load_wine(return_X_y=True)
X_train, X_test, y_train, y_test = train_test_split(X, y, test_size=0.2, random_state=42)
scaler = StandardScaler()
X_train_scaled = scaler.fit_transform(X_train)

for metric in ["euclidean", "manhattan", "chebyshev"]:
    knn = KNeighborsClassifier(n_neighbors=5, metric=metric)
    scores = cross_val_score(knn, X_train_scaled, y_train, cv=5)
    print(f"{metric}: CV accuracy = {scores.mean():.3f}")

The "shape" implied by each distance metric genuinely changes which points count as "close" — Euclidean distance treats all directions equally (circular neighborhoods), Manhattan distance favors axis-aligned proximity (diamond-shaped neighborhoods), and the best choice is genuinely data-dependent, worth treating as a tunable hyperparameter via cross-validation rather than assuming Euclidean by default.

3. The Curse of Dimensionality, Proven Mathematically#

Python
CopyAsk AI
import numpy as np

def demonstrate_curse(n_dims, n_points=10000):
    """Shows how the ratio of nearest to farthest distance behaves as
    dimensionality grows, using randomly distributed points in a unit
    hypercube."""
    points = np.random.rand(n_points, n_dims)
    origin = np.zeros(n_dims)
    distances = np.sqrt(np.sum((points - origin) ** 2, axis=1))
    return distances.min(), distances.max(), distances.max() / distances.min()

for dims in [2, 10, 50, 100, 500]:
    d_min, d_max, ratio = demonstrate_curse(dims)
    print(f"{dims} dims: min={d_min:.3f}, max={d_max:.3f}, ratio={ratio:.3f}")

text
Ask AICopy
2 dims:   min=0.006, max=1.396, ratio=232.667
10 dims:  min=0.687, max=2.030, ratio=2.954
50 dims:  min=2.443, max=3.667, ratio=1.501
100 dims: min=3.658, max=4.796, ratio=1.311
500 dims: min=8.512, max=9.708, ratio=1.140

text
Ask AICopy
As dimensionality grows, the ratio between the farthest and nearest point
converges toward 1 — meaning EVERY point becomes approximately equidistant
from every other point. This isn't a quirk of a specific dataset; it's a
mathematical property of how volume and distance behave in high-dimensional
space (related to the fact that the volume of a hypersphere becomes
vanishingly small relative to its bounding hypercube as dimensions grow).

The direct consequence for KNN: the entire concept of a "nearest neighbor"
becomes statistically meaningless once dimensionality is high enough — the
signal that makes KNN work (that CLOSE points tend to share labels)
degrades toward pure noise.

The practical implication#

Python
CopyAsk AI
from sklearn.decomposition import PCA
from sklearn.pipeline import Pipeline

# When KNN performs poorly on high-dimensional data, dimensionality
# reduction BEFORE applying KNN is a standard, mathematically justified
# remedy — not just an arbitrary preprocessing trick
knn_pipeline = Pipeline([
    ("scaler", StandardScaler()),
    ("pca", PCA(n_components=0.95)),
    ("knn", KNeighborsClassifier(n_neighbors=5)),
])

4. The Bias-Variance Behavior of k, Precisely#

Python
CopyAsk AI
from sklearn.model_selection import cross_val_score
import numpy as np

k_values = range(1, 41, 2)
cv_means = []
cv_stds = []

for k in k_values:
    knn = KNeighborsClassifier(n_neighbors=k)
    scores = cross_val_score(knn, X_train_scaled, y_train, cv=5)
    cv_means.append(scores.mean())
    cv_stds.append(scores.std())

best_k = list(k_values)[np.argmax(cv_means)]
print(f"Best k: {best_k}")

text
Ask AICopy
Mathematically, KNN's prediction for a point x can be written as:
  f_hat(x) = (1/k) * sum of y_i for the k nearest neighbors of x

This is literally a LOCAL AVERAGE. As k increases:
- The average is taken over MORE points → smoother, less noisy estimate
  → LOWER VARIANCE
- But those points are, on average, FARTHER from x → the average is less
  representative of the TRUE value specifically AT x → HIGHER BIAS

As k → n (the entire dataset), the prediction converges to simply the
GLOBAL average/majority class for every single point, regardless of
location — maximum bias, minimum variance (a completely flat, uninformative
model).

As k → 1, the prediction is based on a single, possibly noisy point
— minimum bias, maximum variance.

This is a genuinely rigorous, not just intuitive, characterization of the same bias-variance tradeoff covered throughout this course — KNN happens to make the mechanism unusually transparent, since the model literally IS a local averaging operation.

5. Efficient Nearest-Neighbor Search: Why KNN Can Scale (With Care)#

text
Ask AICopy
The NAIVE approach — computing distance to every single training point
for every prediction — is O(n * d) per query (n = training samples,
d = dimensions), which becomes impractically slow for large n.

Two data structures make this far more efficient for LOWER-dimensional
data:

Python
CopyAsk AI
from sklearn.neighbors import KNeighborsClassifier

# KD-Tree: partitions space using axis-aligned splits (similar in spirit
# to a decision tree), enabling FAST nearest-neighbor search by pruning
# large portions of the search space — but its advantage DEGRADES as
# dimensionality increases (another manifestation of the curse of
# dimensionality), typically becoming ineffective beyond ~20 dimensions
knn_kdtree = KNeighborsClassifier(n_neighbors=5, algorithm="kd_tree")

# Ball-Tree: partitions space using nested hyperspheres instead of
# axis-aligned boxes — generally more robust than KD-Tree in moderately
# higher dimensions, though still eventually degrades
knn_balltree = KNeighborsClassifier(n_neighbors=5, algorithm="ball_tree")

# Brute force: the naive O(n*d) approach — actually FASTEST for very
# high-dimensional data, where tree-based structures provide no real
# advantage anyway
knn_brute = KNeighborsClassifier(n_neighbors=5, algorithm="brute")

# "auto" (the default): scikit-learn picks the best strategy automatically
# based on the data's shape and dimensionality
knn_auto = KNeighborsClassifier(n_neighbors=5, algorithm="auto")

text
Ask AICopy
Both KD-Tree and Ball-Tree work by recursively partitioning the training
data into a tree structure, allowing large portions of the space to be
PRUNED (skipped entirely) during search once it's mathematically
guaranteed they cannot contain a closer point than what's already been
found — dramatically reducing the number of actual distance computations
needed, in LOW-to-MODERATE dimensional data specifically.

6. Weighted KNN#

Python
CopyAsk AI
from sklearn.neighbors import KNeighborsClassifier

# Uniform weighting: every one of the k neighbors votes equally,
# regardless of how close or far within the k-neighborhood they are
knn_uniform = KNeighborsClassifier(n_neighbors=10, weights="uniform")

# Distance weighting: closer neighbors get MORE influence on the
# prediction than farther ones (typically weighted by 1/distance)
knn_distance = KNeighborsClassifier(n_neighbors=10, weights="distance")

text
Ask AICopy
Distance weighting formula (typical implementation):
  weight_i = 1 / distance(x_new, x_i)

  prediction = sum(weight_i * y_i) / sum(weight_i)    [for regression]

This makes intuitive sense: among the k nearest neighbors, the CLOSEST
one is likely more informative about x_new than the k-th closest — treating
them identically (uniform weighting) throws away that ordering information.
Distance weighting also makes KNN somewhat LESS sensitive to the exact
choice of k, since distant neighbors within the k-window contribute only
weakly anyway.

7. KNN as a Non-Parametric Method#

text
Ask AICopy
KNN is called "NON-PARAMETRIC" — not because it has no parameters at all,
but because the number of "effective parameters" GROWS with the size of
the training data, rather than being fixed in advance.

Contrast with linear regression: no matter how much training data you
have, a linear regression model with 5 features always has exactly 6
parameters (5 weights + 1 bias) — a fixed, PARAMETRIC model.

KNN, by storing the entire training set and using it directly at
prediction time, has "complexity" that scales directly with n — this is
precisely why KNN can, in principle, represent arbitrarily complex
decision boundaries GIVEN ENOUGH DATA (very low bias asymptotically), but
also why it needs substantially more data to reach that potential than a
parametric model would.

Notes#

• KNN has no training phase in the traditional sense — the entire "model" is just the stored training data, plus the choice of k and distance metric.
• The choice of distance metric genuinely changes which points are considered "neighbors" and should be tuned via cross-validation, not assumed to be Euclidean by default.
• The curse of dimensionality is a provable mathematical property, not an empirical rule of thumb — distances between points converge toward equal as dimensionality grows, degrading the core assumption KNN relies on.
• KNN's bias-variance behavior with respect to k is unusually transparent mathematically, since the prediction literally is a local average over k points.
• KD-Tree and Ball-Tree search structures accelerate KNN substantially in low-to-moderate dimensions, but their advantage disappears in high dimensions, where brute-force search becomes competitive again.

Best Practices Checklist#

• Always scale features before using KNN, regardless of which distance metric is chosen
• Treat the distance metric as a tunable hyperparameter, not a fixed default choice
• Apply dimensionality reduction before KNN when the feature count is large, as a mathematically justified remedy for the curse of dimensionality
• Use cross-validation to select k, understanding it directly trades off bias against variance via the local-averaging mechanism
• Prefer weights="distance" over weights="uniform" when the ordering within the k-nearest neighborhood carries real information
• Let scikit-learn's algorithm="auto" choose the search structure unless there's a specific reason to force kd_tree, ball_tree, or brute
• Remember KNN needs substantially more data than a parametric model to reach comparable performance, since its effective complexity grows with the training set size