k-NN

1. Purpose & Motivation

1.1 Why k-NN exists

  • Some problems are best solved by reasoning from similar past examples
  • No training phase is needed, making it ideal for small or evolving datasets
  • It provides a non-parametric baseline that makes no assumptions about data distribution

1.2 The core problem it solves

Classify or predict by finding the k most similar examples in the training set and aggregating their labels or values.

2. Definition & Core Idea

2.1 Formal definition

k-Nearest Neighbors is a non-parametric, instance-based algorithm that stores the entire training set and makes predictions by finding the k closest data points to a query point using a distance metric, then voting (classification) or averaging (regression).

2.2 Intuitive mental model

"To judge an unknown fruit, look at the k most similar fruits you have seen before and go with the majority label."

3. How It Works

3.1 Algorithm steps

  1. Store all training examples
  2. Given a new query point, compute distance to every training example
  3. Select the k nearest neighbors
  4. Classification: Return the majority class among the k neighbors
  5. Regression: Return the mean (or weighted mean) of the k neighbors' values

3.2 Distance metrics

Metric Formula concept Best for
Euclidean Straight-line distance Continuous, scaled features
Manhattan Sum of absolute differences Grid-like or sparse data
Cosine Angle between vectors Text and high-dimensional
Minkowski Generalized (p-norm) Tunable via parameter p

4. Choosing k

4.1 Effect of k

  • Small k (e.g., 1-3): Low bias, high variance; sensitive to noise
  • Large k: High bias, low variance; smoother decision boundaries
  • k = 1: Nearest neighbor; Voronoi tessellation of feature space

4.2 How to select k

  • Use cross-validation to find the k that minimizes validation error
  • Odd values of k avoid ties in binary classification
  • Typical range: 3 to 20, depending on dataset size

5. Practical Considerations

5.1 Feature scaling

  • k-NN is distance-based, so features must be normalized or standardized
  • Without scaling, features with larger ranges dominate the distance

5.2 Curse of dimensionality

  • In high dimensions, distances become nearly uniform
  • Performance degrades as feature count grows
  • Dimensionality reduction (PCA, feature selection) helps significantly

5.3 Computational cost

  • Prediction requires scanning all training points: O(n * d) per query
  • KD-trees and Ball trees accelerate neighbor search for moderate dimensions

6. Strengths & Limitations

6.1 Strengths

  • No training phase; adapts instantly to new data
  • Non-parametric: no assumptions about data distribution
  • Simple to understand and implement

6.2 Limitations

  • Slow prediction for large datasets
  • Sensitive to irrelevant features and feature scale
  • Memory-intensive (stores entire training set)

7. One-Sentence Summary

k-NN classifies new data points by finding the k most similar training examples and taking a majority vote, requiring no explicit training phase.

8. Related Knowledge Pages