k-Nearest Neighbors Classification

You've trained models that learn from data, but sometimes the smartest move is to let the data speak for itself. Enter k-nearest neighbors (k-NN), a classification algorithm so intuitive that it's often the first stop for any ML practitioner. This lesson walks you through implementing k-nearest neighbors classification in Python — from the mental model to production-ready code — so you can classify new data with confidence, even when the boundary between classes is messy.

The Problem This Lesson Solves

Imagine you're building a system to detect whether a mushroom is edible or poisonous based on features like cap diameter and gill color. You have hundreds of labeled examples, but you can't write explicit if-else rules for every combination. Rules fail when data overlaps or when you encounter a new example that doesn't fit your predefined categories.

k-NN solves this by using the data itself as the decision rule. Instead of learning a function that maps features to labels, it classifies a new point by looking at the closest labeled points in your dataset. It's a lazy learner — it doesn't build a model during training; it just stores the training data. That simplicity is its superpower: no assumptions about data distribution, no complex training loop, and it works surprisingly well for many real-world problems.

By the end of this lesson, you'll understand the core idea behind k-NN, implement it from scratch with Python, and then use scikit-learn's production-ready KNeighborsClassifier to classify real data.

Core Concept / Mental Model

Think of voting by your neighbors. If you move to a new city and want to know if a neighborhood is safe, you ask the five people living closest to you. If four out of five say it's safe, you'd likely feel comfortable. That's k-NN in a nutshell.

Formally, k-NN works in feature space — a multi-dimensional space where each axis is a feature (e.g., height, weight, color intensity). Each labeled data point is a dot in this space. To classify a new, unlabeled point:

1. Calculate the distance (often Euclidean) between the new point and every training point.
2. Select the k training points with the smallest distances — these are your neighbors.
3. Take a majority vote among the labels of those k neighbors. The new point gets the label that appears most often.

If k is too small (like 1), you risk overfitting to noise. If k is too large, you wash out local patterns. The sweet spot is found empirically, usually with odd values to avoid ties in binary classification.

Key Definitions

• Feature vector: An array of numbers representing a data point.
• Distance metric: A function that quantifies similarity; Euclidean distance is the default.
• Training set: Labeled examples used for classification.
• Query point: The unlabeled example you want to classify.

How It Works Step by Step

Here's the algorithmic flow — the core logic you'll implement:

1. Store the training data: Keep all feature vectors and their labels.
2. Compute distances: For a new query point, calculate the distance to every training point.
3. Sort distances: Rank the training points by increasing distance.
4. Select k neighbors: Take the first k entries from the sorted list.
5. Vote: Count the labels among those k neighbors.
6. Predict: Return the label with the highest count.

The Mathematics: Euclidean Distance

For two points p and q in n-dimensional space, the Euclidean distance is:

d(p, q) = sqrt( (p₁ - q₁)² + (p₂ - q₂)² + ... + (pₙ - qₙ)² )

In NumPy, this becomes: np.sqrt(np.sum((p - q)**2)).

Choosing k

• k = 1: Perfectly memorizes the training set — high variance, poor generalization.
• k too large: Decisions become global, ignoring local structure — high bias.
• Odd k avoids tie in binary classification.

You'll typically try k = 3, 5, 7 and evaluate with cross-validation.

Hands-On Walkthrough

Let's implement k-NN from scratch first to build intuition, then we'll use scikit-learn for the production version. We'll use the classic Iris dataset — 150 flowers with 3 species, 4 features, perfect for classification.

Step 1: Implement from Scratch

import numpy as np
from sklearn.datasets import load_iris
from sklearn.model_selection import train_test_split
from collections import Counter

def euclidean_distance(p, q):
    return np.sqrt(np.sum((p - q) ** 2))

def k_nearest_neighbors(X_train, y_train, query, k=5):
    distances = [(i, euclidean_distance(query, x)) for i, x in enumerate(X_train)]
    distances.sort(key=lambda t: t[1])
    neighbors = [y_train[i] for i, _ in distances[:k]]
    vote = Counter(neighbors)
    return vote.most_common(1)[0][0]

# Load data and split
iris = load_iris()
X_train, X_test, y_train, y_test = train_test_split(
    iris.data, iris.target, test_size=0.2, random_state=42
)

# Test on the first test sample
pred = k_nearest_neighbors(X_train, y_train, X_test[0], k=5)
print(f"Predicted: {iris.target_names[pred]}, Actual: {iris.target_names[y_test[0]]}")
# Expected output: Predicted: setosa, Actual: setosa

This simple code works because the Iris data has clear boundaries. Notice we used most_common(1) to get the majority vote.

Step 2: Evaluate Accuracy on the Test Set

def predict_all(X_train, y_train, X_test, k=5):
    return [k_nearest_neighbors(X_train, y_train, x, k) for x in X_test]

predictions = predict_all(X_train, y_train, X_test, k=5)
accuracy = np.mean(predictions == y_test)
print(f"Accuracy: {accuracy * 100:.2f}%")
# Expected output: Accuracy: 100.00% (or 96.67% depending on split)

Step 3: Use scikit-learn's Optimized Implementation

from sklearn.neighbors import KNeighborsClassifier

model = KNeighborsClassifier(n_neighbors=5)
model.fit(X_train, y_train)
accuracy = model.score(X_test, y_test)
print(f"Scikit-learn accuracy: {accuracy * 100:.2f}%")  # ▶ 100.0%

The scikit-learn version uses efficient data structures (KD-trees or ball trees) under the hood, making it much faster on large datasets.

Pro tip: Always use scikit-learn for real projects. The from-scratch code is for learning only — it's slow for large datasets because it computes all distances each time.

Compare Options / When to Choose What

Variations to explore: - Distance metrics: Manhattan (L1) vs Euclidean (L2) changes the decision boundary. - Weighted voting: Give closer neighbors more influence (useful for noisy data). - Radius-based neighbor search: Fixed radius instead of fixed k — good for uneven density.

Troubleshooting & Edge Cases

1. Feature Scaling is Critical

If one feature has a much larger range (e.g., salary in dollars vs. age), it dominates the distance calculation, making other features useless. Always standardize features to mean 0 and variance 1.

from sklearn.preprocessing import StandardScaler
scaler = StandardScaler()
X_train_scaled = scaler.fit_transform(X_train)
X_test_scaled = scaler.transform(X_test)  # fit only on training!

2. Ties in Voting

With even k, you can get a tie. Use odd k. Alternatively, use weighted voting to break ties by distance.

3. The Curse of Dimensionality

As the number of features increases, all points become equidistant, and k-NN loses meaning. If you have hundreds of features, reduce dimensionality (e.g., PCA) or switch to another algorithm.

4. Imbalanced Classes

If one class has 99% of the data, k-NN will always predict that class. Use stratified sampling or resampling techniques like SMOTE.

5. Wrong Accuracy from Data Leakage

Never fit the scaler on the entire dataset before splitting — you leak information from the test set. Always fit on training data only, as shown above.

What You Learned & What's Next

You now understand the core idea behind k-NN: classification by neighbor voting. You implemented it from scratch, used scikit-learn's optimized version, and learned how to choose k and handle edge cases. You can now confidently implement k-nearest neighbors classification for your own projects.

As next steps in your Python for machine learning path: - Explore hyperparameter tuning with GridSearchCV to find the best k automatically. - Learn about other lazy learners like RadiusNeighborsClassifier. - Move on to model evaluation with cross-validation to get robust accuracy estimates.

The key takeaway? k-NN is a powerful baseline — simple to implement, hard to beat on small datasets, and a great first model to try before reaching for complex algorithms.

Now go ahead and practice by applying k-NN to a dataset from sklearn.datasets like the breast cancer dataset. Try different k values and distance metrics, and see how feature scaling affects your accuracy.