K-Nearest Neighbors (KNN)

Intuition

K-Nearest Neighbors (KNN) is one of the simplest yet most effective machine learning algorithms. It is based on a powerful idea: similar inputs tend to have similar outputs. To make a prediction for a new point, KNN looks at the K most similar examples in the training data (its "neighbors") and lets them vote (for classification) or averages their values (for regression).

Unlike most algorithms, KNN does not actually learn a function during training. It simply stores the training set. All the real work happens at prediction time — which is why it's called a lazy learner or an instance-based / non-parametric method.

How It Works — Step by Step

• Store the entire labeled training dataset (no model fitting).
• Given a query point x, compute the distance from x to every training point.
• Sort the training points by distance and pick the K closest ones.
• For classification: return the majority class among the K neighbors (optionally weighted by 1/distance).
• For regression: return the mean (or weighted mean) of the K neighbors' target values.

Distance Metrics

The notion of "nearest" depends entirely on the distance metric you choose. The right metric depends on the data type and geometry of your feature space.

• Euclidean — default, works well for continuous features on similar scales.
• Manhattan — more robust to outliers, common in high-dimensional grid-like data.
• Minkowski — generalization; p=1 is Manhattan, p=2 is Euclidean.
• Cosine — best for text or high-dimensional sparse vectors where direction matters more than magnitude.
• Hamming — for categorical or binary features.

Choosing K

K controls the bias-variance trade-off. Small K makes the decision boundary jagged and sensitive to noise (low bias, high variance). Large K smooths the boundary but may blur important class differences (high bias, low variance).

• Small K (e.g., K=1) → flexible, noisy, prone to overfitting.
• Large K → smoother, more stable, may underfit.
• Use cross-validation (typically over a grid like K = 1, 3, 5, …, 31) to pick K.
• Prefer odd K in binary classification to avoid tie votes.
• A common rule of thumb: K ≈ √n, where n is the training set size.

Weighted KNN

By default, all K neighbors vote equally. In weighted KNN, closer neighbors get a larger say — usually weighted by the inverse of their distance:

This often improves accuracy, especially when K is large or when neighbors are at very different distances from the query.

Feature Scaling Matters

Curse of Dimensionality

As the number of features grows, all points start to look roughly equidistant from each other — the very notion of "nearest" loses meaning. KNN performance degrades sharply in high-dimensional spaces. Mitigations:

• Apply dimensionality reduction (PCA, autoencoders, feature selection).
• Remove irrelevant or redundant features.
• Use distance metric learning to weight features appropriately.

Efficient Neighbor Search

Naive KNN is O(n · d) per query, which is too slow for large datasets. Spatial data structures speed this up dramatically:

• KD-Tree — efficient for low-to-moderate dimensions (d < 20).
• Ball Tree — handles higher dimensions and non-Euclidean metrics better.
• Approximate NN (FAISS, Annoy, HNSW) — for very large or high-dimensional datasets, trade a tiny bit of accuracy for huge speedups.

In scikit-learn, set algorithm="kd_tree", "ball_tree", or "auto".

KNN for Regression

KNN isn't only for classification — KNeighborsRegressor predicts a continuous target by averaging the targets of the K nearest neighbors (optionally weighted by distance). It's a non-parametric alternative to linear regression for capturing local, non-linear patterns.

Python Implementation

Classification with scaling and cross-validation

from sklearn.neighbors import KNeighborsClassifier
from sklearn.datasets import load_iris
from sklearn.model_selection import train_test_split, GridSearchCV
from sklearn.preprocessing import StandardScaler
from sklearn.pipeline import Pipeline

X, y = load_iris(return_X_y=True)
X_tr, X_te, y_tr, y_te = train_test_split(X, y, test_size=0.2, random_state=42)

pipe = Pipeline([
    ("scaler", StandardScaler()),
    ("knn", KNeighborsClassifier()),
])

grid = GridSearchCV(
    pipe,
    {
        "knn__n_neighbors": [1, 3, 5, 7, 9, 11, 15, 21],
        "knn__weights": ["uniform", "distance"],
        "knn__metric": ["euclidean", "manhattan"],
    },
    cv=5,
    n_jobs=-1,
)
grid.fit(X_tr, y_tr)
print("Best params:", grid.best_params_)
print("Test accuracy:", grid.score(X_te, y_te))

Regression example

from sklearn.neighbors import KNeighborsRegressor
from sklearn.datasets import fetch_california_housing
from sklearn.preprocessing import StandardScaler
from sklearn.pipeline import make_pipeline
from sklearn.model_selection import cross_val_score

X, y = fetch_california_housing(return_X_y=True)
model = make_pipeline(StandardScaler(),
                     KNeighborsRegressor(n_neighbors=10, weights="distance"))
scores = cross_val_score(model, X, y, cv=5, scoring="r2")
print("R^2:", scores.mean())

Pros and Cons

Pros: Extremely simple to understand and implement; no training phase; naturally handles multi-class problems; captures non-linear decision boundaries; works for both classification and regression; only one main hyperparameter (K).

Cons: Slow at prediction time on large datasets (must compare to all training points); high memory cost (stores entire training set); sensitive to feature scaling, irrelevant features, and the curse of dimensionality; struggles with imbalanced classes unless distance-weighting is used.

When to Use KNN

• Small-to-medium datasets where prediction latency isn't critical.
• Low-dimensional feature spaces with meaningful distance metrics.
• As a strong, interpretable baseline to compare more complex models against.
• Recommendation systems and similarity search (often via approximate NN).