K-Nearest Neighbors

K-nearest neighbors (KNN) is the most intuitive classifier in machine learning: to classify a new point, find the k training points closest to it and take a majority vote (for regression, average their values). There is no training phase at all - the "model" is the dataset, and prediction is a distance lookup. That makes KNN a powerful baseline, a good local-structure explorer, and a cautionary tale about distance, scaling, and the cost of prediction at scale.

How It Works

from sklearn.datasets import make_moons
from sklearn.neighbors import KNeighborsClassifier
from sklearn.model_selection import train_test_split
from sklearn.metrics import accuracy_score
from sklearn.preprocessing import StandardScaler

X, y = make_moons(n_samples=400, noise=0.25, random_state=0)
Xtr, Xte, ytr, yte = train_test_split(X, y, test_size=0.3, random_state=0)

scaler = StandardScaler().fit(Xtr)
knn = KNeighborsClassifier(n_neighbors=5)
knn.fit(scaler.transform(Xtr), ytr)
print("accuracy:", round(accuracy_score(yte, knn.predict(scaler.transform(Xte))), 3))

Two details carry the whole method. First, fit only stores the training set - prediction computes distances to all of it, which is why KNN gets slow on large data and why the data must fit in memory. Second, the scaler is fitted on the training set and applied to both - KNN is a distance model, and without scaling, the feature with the largest raw range dominates every distance computation.

Choosing k

import numpy as np
from sklearn.model_selection import cross_val_score

results = {}
for k in range(1, 31, 2):
    knn = KNeighborsClassifier(n_neighbors=k)
    s = cross_val_score(knn, scaler.transform(Xtr), ytr, cv=5)
    results[k] = s.mean()
    print(f"k={k:2d}  CV accuracy={s.mean():.3f}")

best_k = max(results, key=results.get)
print("best k:", best_k)

The bias-variance curve is visible in the scan: k=1 is the most flexible (it memorizes the training points, so noise wins), and large k is the most rigid (the vote averages toward the base rate, blurring the boundary). The sweet spot is in between - usually an odd number between 3 and 21 - and cross-validation finds it. A useful habit: plot the curve, because the shape tells you how noisy the boundary is.

Distance and Metrics

• Euclidean (the default) - the geometric distance; fine for standardized numeric data.
• Manhattan (metric="manhattan") - sum of absolute differences; more robust to a few noisy dimensions.
• Minkowski - the general form with exponent p; p=2 is Euclidean, p=1 is Manhattan.
• Weighted voting (weights="distance") - close neighbors count more than far ones; often a small improvement over uniform voting.

For categorical data the metric question gets harder (Hamming distance, or one-hot plus Euclidean), and KNN's advantage over tree-based models mostly disappears - trees handle mixed types without a distance definition.

Strengths and Weaknesses

Summary

Use KNN as the no-assumptions baseline: scale the features first (always, for KNN), sweep k with cross-validation, and prefer an odd k in the 3-21 range with distance-weighted voting when the boundary is noisy. It is slow on large data and weak in high dimensions, but its transparency - the prediction is literally the average of visible neighbors - makes it an excellent teaching model and a quick sanity check on any dataset.