K-Nearest Neighbors (KNN) from Scratch

An explanation of the K-Nearest Neighbors (KNN) algorithm — how it works and when to use it.

K-Nearest Neighbors (KNN) is a simple classification and regression algorithm.

It predicts by looking at the "k" most similar training examples and aggregating their labels or values — majority vote for classification, average for regression.

It assumes that points close together in the feature space share the same labels or values.

There is no explicit training step — the model is the dataset itself.

• Pros: simple, interpretable via neighbors, no training time, a strong baseline.
• Cons: slow at inference, memory-heavy, sensitive to feature scaling and irrelevant features, struggles with high-dimensional raw features (curse of dimensionality).

1. Choose "k" (an integer)
   • Small k: low bias, high variance (noisy — overfit)
   • Large k: higher bias, lower variance (smoother — underfit)
2. Choose a distance metric (Euclidean, Manhattan, Cosine Similarity, Hamming) — weighting can be applied to distance values to improve accuracy

$$ | \mathbf{A} - \mathbf{B} | = \sqrt{(A_x - B_x)^2 + (A_y - B_y)^2 + (A_z - B_z)^2} $$

3. Normalize features (0–1) to prevent any single feature from dominating.
   • One-hot encode categorical features (all categories equidistant)
4. For a new point:
   • Compute the distance to all training points
   • Select the "k" closest neighbors
   • Predict:
     • Classification: majority vote
     • Regression: mean or median

• When interpretability via similar cases is valuable.
• When features are reasonably clean, scaled, and informative — not sparse, high-dimensional data like raw bag-of-words with 50k tokens.
• When the data fits in memory, or can be indexed for speed.

Example use cases:

• Image retrieval: surface similar X-rays/MRIs
• Patient similarity search: cohort discovery for outcomes like readmission or adverse events
• Presidential election predictions
• Email spam filtering
• Recommender systems: predict music or movie preferences to suggest to users
  • Movie recommendations: find the 10 closest movies in embedding space
• Clinical decision support (baseline): predict the likelihood of an outcome from tabular vitals/lab results
• Identify patients with similar longitudinal patterns (changes over time)
  • Biological and social changes

• https://en.wikipedia.org/wiki/K-nearest_neighbors_algorithm