KNN — Module 5.2 | Codextroop

How This Lesson Fits the Module

Most algorithms in this module learn an explicit function during training. K-nearest neighbors (KNN) is lazy: it stores training data and decides at prediction time by majority vote (or average) among the k closest points. It is the clearest introduction to distance metrics and why feature scaling matters.

KNN is a sanity-check baseline and a stepping stone to kernel methods like SVM.

Learning Objectives

By the end of this lesson, students should be able to:

Describe KNN classification (majority vote) and regression (mean/median).
Configure KNeighborsClassifier with n_neighbors, weights, and metric.
Scale features before distance computation using StandardScaler in a pipeline.
Select k with cross-validation and interpret bias–variance tradeoffs.
Recognize computational limits of brute-force KNN at scale.

Prediction by Proximity

Given a query point, KNN finds the n_neighbors training samples with smallest distance (usually Euclidean). Classification returns the most common label; regression returns the mean target. weights="distance" gives closer neighbors more influence—helpful when boundaries are irregular.

Choice of k	Behavior	Risk
Small k (e.g., 1–3)	Flexible, follows local structure	High variance, sensitive to noise
Large k	Smoother decision regions	High bias, blurs fine structure
Odd k (binary)	Avoids tie votes	—
`weights="distance"`	Closer points dominate	Outliers with tiny distance can dominate

sklearn Pipeline with Scaling

On the wine dataset, unscaled alcohol and color intensity features live on different scales—without scaling, the largest-magnitude feature dominates distance.

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

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, stratify=y, random_state=42
)

knn_pipe = Pipeline([
    ("scale", StandardScaler()),
    ("knn", KNeighborsClassifier()),
])

search = GridSearchCV(
    knn_pipe,
    param_grid={"knn__n_neighbors": [3, 5, 7, 11, 15]},
    cv=5,
    scoring="accuracy",
)
search.fit(X_train, y_train)
print("Best k:", search.best_params_["knn__n_neighbors"])
print("Test accuracy:", round(search.score(X_test, y_test), 3))

Distance Metrics and Curse of Dimensionality

Euclidean distance is the default; Manhattan (metric="manhattan") can help with sparse or high-dimensional data. As dimensions grow, all points become roughly equidistant—KNN degrades unless you reduce dimensionality or engineer better features.

Engineering Habit — Neighbor Inspection

For a mispredicted test point, retrieve neighbor indices with kneighbors() and inspect their features. This “why did the model say that?” workflow builds trust and catches labeling errors.

Critical Mistake — Skipping the Scaler

Raw income in thousands and age in years are not comparable units. Fitting KNN on unscaled tabular data silently weights income ~1000× more than age. Always pipeline StandardScaler before KNeighborsClassifier.

Knowledge Check

Short Answer: Why is KNN called a lazy learner? Answer: It defers computation until prediction time; no explicit training phase beyond storing data.
True/False: KNN with k=1 always generalizes best. Answer: False—it memorizes noise and often overfits.
Multiple Choice: Must-do preprocessing for KNN on mixed-scale features: (a) one-hot only, (b) scaling, (c) log target. Answer: (b).
Short Answer: What does algorithm="ball_tree" improve? Answer: Faster neighbor search for moderate dimensions via spatial indexing.
Short Answer: When is KNN a poor production choice? Answer: Millions of training rows or high query volume where O(n) search per prediction is too slow.
True/False: Euclidean distance assumes comparable feature scales. Answer: True.
Multiple Choice: Larger k generally: (a) more variance, (b) smoother / higher bias, (c) no effect. Answer: (b).
Short Answer: How does KNN classify a new point? Answer: Majority (or distance-weighted) vote among the k nearest training neighbors.
True/False: KNN stores a parametric weight vector like logistic regression. Answer: False—it stores the training set.
Multiple Choice: weights="distance" means: (a) ignore k, (b) closer neighbors vote more, (c) random vote. Answer: (b).

Key Takeaways

KNN classifies by majority vote among the k nearest training points.
Feature scaling is mandatory for meaningful distance calculations.
Tune k with cross-validation to balance bias and variance.
Distance weighting and metric choice matter on irregular boundaries.
Next: SVM for maximum-margin boundaries with kernels.

Trainer’s Guide

Hands-on idea: Plot validation accuracy vs. k for wine data. Students mark the elbow where gains flatten and explain overfitting at k=1.

Discussion prompt: How would categorical features break vanilla Euclidean KNN? What encodings fix it?

Recap: KNN classifies by nearby training examples; scale features and tune k. Continue with SVM.