K-Nearest Neighbors:
Predictions by Association

You move to a new neighborhood. You want to know: what kind of area is this?
You don't read the city report. You don't analyze census data.
You look at the five houses nearest to you.
Three are families with children. One is a young couple. One is a retired person.
You conclude: this is a family neighborhood. Probably safe. Probably quiet.

You just ran K-Nearest Neighbors with K = 5.

01 — The Laziest Model in Machine Learning

KNN has a radical design philosophy: do absolutely nothing during training. No weights to learn, no equations to fit, no optimization loop. Just take the entire training dataset and store it in memory. Every other algorithm we've seen — linear regression, logistic regression — spends training time compressing the data into a small set of learned parameters. KNN refuses to compress anything. It keeps everything.

All the real work happens at prediction time. When a new data point arrives asking for a prediction, KNN searches through every stored training point, finds the K closest ones, and asks them to vote:

This is why KNN is called a lazy learner or instance-based learner — it defers all computation to prediction time, and the training data itself is the model. There are no parameters. There is no "learned function." Just data, and the assumption that similar inputs produce similar outputs.

02 — Distance: The Heart of KNN

Everything in KNN depends on one question: how do you define "closeness" between two data points? The answer is a distance metric — a mathematical formula that takes two points and returns a number. Smaller number = more similar.

Let's make this concrete. Suppose you have two people described by two features: Age and Income (in thousands).

Person A: (30, 50)  ·  Person B: (34, 53)

03 — Choosing K: The Bias-Variance Dial

K is the only hyperparameter KNN has, and it controls the fundamental tradeoff between overfitting and underfitting. Think of K as a dial that adjusts how much you trust individual neighbors vs the crowd.

04 — From Scratch: KNN in Pure Python

KNN is one of the easiest algorithms to implement from scratch — no calculus, no matrices, just loops and distance formulas. Reading this makes the sklearn version completely transparent.

import numpy as np
from collections import Counter

def euclidean(a, b):
    """Straight-line distance between two points."""
    return np.sqrt(np.sum((a - b) ** 2))

def knn_predict(X_train, y_train, x_new, k=3):
    """Classify x_new using the k nearest neighbors in X_train."""
    # Step 1: compute distance from x_new to every training point
    distances = [euclidean(x_new, x_train) for x_train in X_train]

    # Step 2: get the indices of the k smallest distances
    k_indices = np.argsort(distances)[:k]

    # Step 3: look up the labels of those k neighbors
    k_labels = [y_train[i] for i in k_indices]

    # Step 4: majority vote — return the most common label
    most_common = Counter(k_labels).most_common(1)
    return most_common[0][0]

# Simple 2D dataset: two clusters
#   Class 0 = bottom-left region
#   Class 1 = top-right region
X_train = np.array([[1,2],[2,3],[3,1],[6,5],[7,8],[8,6]])
y_train = np.array([0, 0, 0, 1, 1, 1])

x_new = np.array([5, 4])   # unknown point — which cluster?
prediction = knn_predict(X_train, y_train, x_new, k=3)
print(f"Nearest 3 neighbors vote: class {prediction}")

# Show the distances explicitly
distances = [(i, euclidean(x_new, X_train[i]), y_train[i])
             for i in range(len(X_train))]
distances.sort(key=lambda d: d[1])
print("\nAll training points sorted by distance from (5,4):")
for idx, dist, label in distances:
    print(f"  Point {X_train[idx]} | dist={dist:.2f} | class={label}")

05 — KNN in sklearn (Real Dataset)

The sklearn version handles scaling, cross-validation, and K selection cleanly. This is the production pattern.

from sklearn.neighbors import KNeighborsClassifier
from sklearn.datasets import load_iris
from sklearn.model_selection import train_test_split, cross_val_score
from sklearn.preprocessing import StandardScaler
import numpy as np

# Iris dataset: 150 flowers, 4 features, 3 species
X, y = load_iris(return_X_y=True)
X_train, X_test, y_train, y_test = train_test_split(
    X, y, test_size=0.2, random_state=42)

# ── Scale first — mandatory for KNN ─────────────────────────────────
# fit_transform on train: learn mean/std from training data only
# transform on test: apply the SAME scaling (never refit on test!)
scaler  = StandardScaler()
X_train = scaler.fit_transform(X_train)
X_test  = scaler.transform(X_test)

# ── Find best K via 5-fold cross-validation ──────────────────────────
cv_scores = [cross_val_score(KNeighborsClassifier(k), X_train, y_train, cv=5).mean()
             for k in range(1, 21)]
best_k = np.argmax(cv_scores) + 1
print(f"Best K = {best_k}")
print(f"CV accuracy at best K = {cv_scores[best_k-1]:.2%}")

# ── Final evaluation on held-out test set ───────────────────────────
model = KNeighborsClassifier(best_k).fit(X_train, y_train)
print(f"Test accuracy = {model.score(X_test, y_test):.2%}")

06 — The Curse of Dimensionality

KNN's single biggest weakness is high-dimensional data. As the number of features grows, something counterintuitive and devastating happens to the concept of distance.

Practically: KNN works well with 2–50 features. Above 100 features, performance degrades noticeably. Above 500, it often becomes useless without intervention.

07 — When KNN Wins (and When It Loses)

08 — A Thought to Sit With

09 — Coming Up Next

Tomorrow — Day 7: Naive Bayes. A probabilistic model that classifies spam before you even open it. It makes an absurd mathematical assumption — that all features are completely independent of each other — and somehow works brilliantly anyway. Understanding why it works despite being "wrong" teaches something deep about the relationship between model assumptions and real-world performance.

10 — Go Deeper

▶ StatQuest: K-Nearest Neighbors, Clearly Explained
YouTube · 9 min · The clearest short introduction to KNN — great for cementing the intuition after reading this post.

▶ Kaggle: Intro to Machine Learning
Free interactive course · Apply KNN and other classifiers to real datasets in your browser. The fastest way to build hands-on intuition.

▶ Coursera: Deep Learning Specialization — Andrew Ng
5-course specialization · Covers embeddings and vector representations that make KNN powerful at scale — the bridge from this post to modern AI retrieval systems.