Machine Learning

Supervised Learning Classification

K-Nearest Neighbors

Chapter 1's logistic regression learns a fixed set of coefficients during training, then discards the raw training data. K-Nearest Neighbors (KNN) does the oppo

JrCodex·8 min read

Jr Codex ML Notes

Level: Intermediate Prerequisites: Chapter 1 Time to complete: ~25 minutes

Table of Contents

  1. A Fundamentally Different Kind of Algorithm
  2. How KNN Classification Works
  3. Distance Metrics
  4. Choosing K
  5. Why Scaling Is Mandatory for KNN
  6. KNN for Regression
  7. The Curse of Dimensionality Strikes KNN Hardest
  8. Computational Cost
  9. Summary & Next Steps

1. A Fundamentally Different Kind of Algorithm

Chapter 1's logistic regression learns a fixed set of coefficients during training, then discards the raw training data. K-Nearest Neighbors (KNN) does the opposite: it keeps the entire training dataset, and makes predictions by directly comparing a new point to its stored examples — no traditional "training" phase at all.

Eager Learning (Logistic Regression)     Lazy Learning (KNN)
─────────────────────────────────────    ─────────────────────────────
  TRAIN: fit coefficients from data          TRAIN: literally just STORE
                                                the training data
  PREDICT: apply the LEARNED formula          PREDICT: find the CLOSEST
  to new data (fast, data discarded)             stored examples, vote
                                                   among them (slower per
                                                    prediction, Section 8)
─────────────────────────────────────────────────────────────────────

2. How KNN Classification Works

The KNN Algorithm
─────────────────────────────────────────
  1. Given a NEW point to classify
  2. Find the K CLOSEST points in the training data
     (by some distance metric, Section 3)
  3. Let those K neighbors VOTE — the MAJORITY class among
     them becomes the prediction
─────────────────────────────────────────

from sklearn.neighbors import KNeighborsClassifier
import numpy as np
 
X_train = np.array([[1, 2], [2, 3], [3, 3], [6, 7], [7, 8], [8, 8]])
y_train = np.array([0, 0, 0, 1, 1, 1])      # two clear clusters
 
model = KNeighborsClassifier(n_neighbors=3)
model.fit(X_train, y_train)      # "training" is literally just storing the data
 
new_point = [[4, 4]]
prediction = model.predict(new_point)
print(prediction)      # depends on which class dominates among the 3 CLOSEST training points
 
probabilities = model.predict_proba(new_point)
print(probabilities)      # e.g. [[0.67, 0.33]] — 2 of 3 neighbors were class 0
KNN, Visualized
─────────────────────────────────────────
        ● (class 0)      ○ = new point to classify
      ●   ●
              ○
                    ● (class 1)
                  ●   ●

  With k=3, look at the 3 CLOSEST training points to ○,
  and predict whichever class is the MAJORITY among them.
─────────────────────────────────────────

3. Distance Metrics

"Closest" requires a precise definition of distance — directly connects to the concept first introduced in the AI Notes' search algorithms (heuristic distance estimates).

import numpy as np
 
def euclidean_distance(a, b):
    """The DEFAULT — straight-line distance, like a ruler."""
    return np.sqrt(np.sum((a - b) ** 2))
 
def manhattan_distance(a, b):
    """Sum of ABSOLUTE differences per dimension — like navigating city BLOCKS."""
    return np.sum(np.abs(a - b))
 
point_a = np.array([1, 2])
point_b = np.array([4, 6])
 
print(f"Euclidean: {euclidean_distance(point_a, point_b):.2f}")      # 5.0
print(f"Manhattan: {manhattan_distance(point_a, point_b):.2f}")        # 7
from sklearn.neighbors import KNeighborsClassifier
 
# scikit-learn supports many distance metrics via the `metric` parameter
model_euclidean = KNeighborsClassifier(n_neighbors=3, metric="euclidean")
model_manhattan = KNeighborsClassifier(n_neighbors=3, metric="manhattan")
When Manhattan Distance Might Be Preferred
─────────────────────────────────────────
  Euclidean distance is the natural default for most continuous
  features. Manhattan distance can be more appropriate for
  HIGH-DIMENSIONAL data, or when movements along each dimension
  are genuinely INDEPENDENT and shouldn't be combined
  diagonally (e.g. grid-based navigation, directly echoing the
  AI Notes' search chapter's own grid-world examples).
─────────────────────────────────────────

4. Choosing K

K is KNN's central hyperparameter, and directly maps onto Module 1, Chapter 4's bias-variance tradeoff in an unusually clean, visual way.

from sklearn.model_selection import train_test_split
from sklearn.neighbors import KNeighborsClassifier
from sklearn.metrics import accuracy_score
import numpy as np
 
np.random.seed(0)
X = np.random.randn(200, 2)
y = (X[:, 0] + X[:, 1] > 0).astype(int)
 
X_train, X_test, y_train, y_test = train_test_split(X, y, test_size=0.3, random_state=42)
 
for k in [1, 3, 5, 15, 50]:
    model = KNeighborsClassifier(n_neighbors=k)
    model.fit(X_train, y_train)
    train_acc = accuracy_score(y_train, model.predict(X_train))
    test_acc = accuracy_score(y_test, model.predict(X_test))
    print(f"k={k:2d}: train accuracy={train_acc:.3f}, test accuracy={test_acc:.3f}")
The Bias-Variance Tradeoff, Direct and Visual for KNN
─────────────────────────────────────────
  k=1:        EXTREMELY flexible decision boundary — follows
                every single training point exactly, including
                noise (HIGH VARIANCE, classic overfitting —
                perfect training accuracy, worse test accuracy)

  k=LARGE:      EXTREMELY smooth decision boundary — averages
                  over so many neighbors that fine detail is lost
                  (HIGH BIAS, classic underfitting)

  k="just right":  the SWEET SPOT (Module 1, Ch.4) — found via
                     cross-validation (Module 1, Ch.5; Module 7)
─────────────────────────────────────────

Practical Guidance
─────────────────────────────────────────
  - k=1 is ALWAYS the most overfitting-prone choice — a single
    noisy or mislabeled training point can flip a prediction
  - ODD values of k avoid TIES in binary classification voting
  - A common starting point: k = √n (square root of the number
    of training samples), then TUNE via cross-validation
    (Module 7)
─────────────────────────────────────────

5. Why Scaling Is Mandatory for KNN

Directly reprising Module 2, Chapter 3's warning, now demonstrated concretely — KNN is a distance-based algorithm, making it maximally sensitive to feature scale.

import numpy as np
from sklearn.neighbors import KNeighborsClassifier
from sklearn.preprocessing import StandardScaler
 
# Two features on WILDLY different scales
X_unscaled = np.array([[25, 50000], [30, 55000], [45, 200000], [50, 210000]])
y = np.array([0, 0, 1, 1])
 
# WITHOUT scaling — income (in the tens of thousands) will TOTALLY
# dominate the distance calculation, making age nearly irrelevant
model_unscaled = KNeighborsClassifier(n_neighbors=1).fit(X_unscaled, y)
 
# WITH scaling — both features contribute FAIRLY to distance
scaler = StandardScaler()
X_scaled = scaler.fit_transform(X_unscaled)
model_scaled = KNeighborsClassifier(n_neighbors=1).fit(X_scaled, y)

This is not optional for KNN, the way it's optional for tree-based models (Chapter 3) — skipping scaling here can silently and severely distort every distance calculation the algorithm relies on entirely.

6. KNN for Regression

The same core idea applies directly to predicting continuous values (Module 3) — instead of a majority vote, average the neighbors' target values.

from sklearn.neighbors import KNeighborsRegressor
import numpy as np
 
X_train = np.array([[1200], [1800], [2400], [1500]])      # house sqft
y_train = np.array([250000, 340000, 410000, 275000])         # house price
 
model = KNeighborsRegressor(n_neighbors=2)
model.fit(X_train, y_train)
 
prediction = model.predict([[1600]])
print(prediction)      # the AVERAGE price of the 2 closest houses by sqft
KNN Regression vs Classification
─────────────────────────────────────────
  Classification (Section 2):    neighbors VOTE — majority class wins
  Regression (this section):        neighbors' values are AVERAGED
                                      (or weighted by distance —
                                      closer neighbors count more)
─────────────────────────────────────────

7. The Curse of Dimensionality Strikes KNN Hardest

Directly connecting to Module 2, Chapter 4's dimensionality preview — KNN suffers from high-dimensional data more severely than most other algorithms.

Why KNN Is Especially Vulnerable
─────────────────────────────────────────
  In HIGH dimensions, the concept of "nearest" neighbor breaks
  down — as dimensions increase, the DISTANCE between the
  closest and farthest points in a dataset tends to become
  nearly IDENTICAL (a genuine, counter-intuitive mathematical
  fact). "Nearest neighbor" becomes a nearly MEANINGLESS
  concept once dimensionality gets high enough.

  This is EXACTLY why Module 6's dimensionality reduction
  techniques (PCA and friends) are often applied BEFORE KNN
  on high-dimensional data — reducing dimensions FIRST restores
  KNN's core distance-based logic to a meaningful state.
─────────────────────────────────────────

8. Computational Cost

KNN's "lazy learning" (Section 1) has a real cost: since no summarizing happens during training, every single prediction requires comparing against the entire stored training set.

Training Time vs Prediction Time — KNN's Unusual Trade-off
─────────────────────────────────────────
  Logistic Regression (Ch.1):    SLOW-ish training (gradient
                                    descent iterations), FAST
                                    prediction (just apply the
                                    learned formula)

  KNN:                              INSTANT "training" (just
                                       store data), SLOW
                                       prediction (compare against
                                       EVERY stored point, for
                                       EVERY new prediction)
─────────────────────────────────────────

This trade-off matters enormously for production deployment (Module 9) — an algorithm needing to serve millions of real-time predictions per day may find KNN's per-prediction cost prohibitive, even if its accuracy is excellent, favoring an "eager" algorithm (Chapter 1, or Module 4-5's tree-based methods) instead.

9. Summary & Next Steps

Key Takeaways

  • KNN is a "lazy learning" algorithm — it stores the entire training set and makes predictions by finding the K closest stored points and having them vote (classification) or average (regression).
  • K is KNN's central hyperparameter, directly and visually demonstrating the bias-variance tradeoff: small k overfits (high variance), large k underfits (high bias).
  • Feature scaling is mandatory for KNN, since it's a purely distance-based algorithm — unscaled features with larger raw ranges will dominate distance calculations.
  • KNN suffers especially badly from the curse of dimensionality, since "nearest neighbor" becomes a nearly meaningless concept in very high-dimensional spaces.
  • KNN's computational cost is backwards from most algorithms: instant training, but potentially slow predictions, since every prediction compares against the entire stored dataset.

Concept Check

  1. Why is KNN called a "lazy learning" algorithm, in contrast to logistic regression?
  2. What happens to a KNN model's decision boundary as k grows very large, and what does that correspond to in the bias-variance tradeoff?
  3. Why does feature scaling matter more for KNN than it does for decision trees (Chapter 3)?

Next Chapter

→ Chapter 3: Decision Trees

Jr Codex — 1-on-1 Personalized Coaching | Back to Module Index