how to implement k nearest neighbors from scratch

Imagine you're in a new city and want to know if a neighborhood is safe. You'd probably ask your closest neighbors for their experiences, right?

KNN works exactly like that. It's an algorithm that classifies or predicts a new data point by looking at the k most similar (nearest) examples from its training data. No complex rules—just similarity-based reasoning.

You use the same core logic for both—just change the final aggregation step. It's simple, intuitive, and requires no assumptions about your data's underlying distribution.

How the KNN algorithm makes predictions step by step

That's the entire algorithm. All the "learning" happens at prediction time by measuring similarity. No parameters to tweak during training—just your data, a distance metric, and a choice of k.

Before writing any KNN logic, you need a clean workspace where you can focus on the algorithm itself—not on fighting your tools. Think of this like sharpening your pencil before drawing: it makes everything else smoother.

You only need two core libraries for a from-scratch implementation:

• NumPy: For efficient numerical operations, especially distance calculations between vectors.
• scikit-learn (optional but helpful): We won't use its KNN class, but it provides nice datasets and utilities like train_test_split to quickly generate and partition data for testing.

Note: You don't need pandas or matplotlib for the core KNN code—keep dependencies minimal.

import numpy as np

# Example with two features (e.g., height and weight)
X_train = np.array([
    [5.1, 3.5],
    [4.9, 3.0],
    [7.0, 3.2]
])
y_train = np.array([0, 0, 1])  # class labels

from sklearn.preprocessing import StandardScaler

scaler = StandardScaler()
X_train_scaled = scaler.fit_transform(X_train)
# For a new point:
X_new_scaled = scaler.transform(X_new.reshape(1, -1))

def euclidean_distance(a, b):
    return np.sqrt(np.sum((a - b) ** 2))

# Test
point1 = np.array([1, 2])
point2 = np.array([4, 6])

print(euclidean_distance(point1, point2))
# Output should be 5.0

import numpy as np

# 1. Compute distances efficiently using NumPy broadcasting
# X_train shape: (n_samples, n_features)
distances = np.linalg.norm(X_train - x_new, axis=1)

# 2. Sort and select top k indices
k_nearest_indices = np.argsort(distances)[:k]

# 3. Get their labels
k_nearest_labels = y_train[k_nearest_indices]

# 4. Majority Vote (for classification)
from scipy.stats import mode
prediction = mode(k_nearest_labels).mode

This formal process is exactly what you envisioned in the introduction—it's just the precise, vectorized implementation of those mental steps. The key insight: all learning is reduced to a distance calculation and a simple vote/average. There are no parameters to learn, only the choice of k and the distance metric to define what "nearest" means.

Now we turn the mental model into real code. You already know the steps: store training data, compute distances, find k nearest, then aggregate. The implementation mirrors that exactly—no hidden magic.

import numpy as np

class KNN:
    def __init__(self, k=3, task='classification'):
        self.k = k
        self.task = task  # 'classification' or 'regression'
    
    def fit(self, X_train, y_train):
        # Simply store the data—no training happens here.
        self.X_train = X_train
        self.y_train = y_train
    
    def predict(self, X_test):
        predictions = []
        for x in X_test:
            # 1. Compute Euclidean distance to every training point
            distances = np.linalg.norm(self.X_train - x, axis=1)
            
            # 2. Find indices of the k smallest distances
            k_nearest_indices = np.argsort(distances)[:self.k]
            
            # 3. Get the labels of those neighbors
            k_nearest_labels = self.y_train[k_nearest_indices]
            
            # 4. Aggregate based on task
            if self.task == 'classification':
                # Majority vote
                labels, counts = np.unique(k_nearest_labels, return_counts=True)
                pred = labels[np.argmax(counts)]
            else:  # regression
                pred = np.mean(k_nearest_labels)
            
            predictions.append(pred)
        
        return np.array(predictions)

Why this works:

• np.linalg.norm(..., axis=1) computes Euclidean distance from x to every row in X_train in one vectorized step.
• np.argsort(distances) returns indices that would sort the distances from smallest to largest. Slicing [:self.k] gives exactly k indices of the nearest neighbors.
• For classification, np.unique with return_counts=True counts occurrences of each class among the k neighbors. np.argmax(counts) picks the class with the highest count.
• For regression, np.mean averages the neighbor values.

You've built a working KNN. But what happens when your training set grows from 100 points to 100,000?

The brute-force approach—calculating the distance from your new point to every single training sample—becomes painfully slow. It's an O(n_train) operation per query. If you have millions of points, a single prediction could take seconds or even minutes.

To fix this, we need to stop looking at everything. Let's explore two optimization philosophies: Exact Speedups (finding the true nearest neighbors faster) and Approximate Methods (trading a tiny bit of accuracy for massive speed gains).

import numpy as np

class ApproximateKNN:
    def __init__(self, k=3, sample_size=1000):
        self.k = k
        self.sample_size = sample_size
    
    def fit(self, X_train, y_train):
        self.X_train = X_train
        self.y_train = y_train
        n = len(X_train)
        
        # 1. Pick a fixed random subset during fit
        if n > self.sample_size:
            self.sample_indices = np.random.choice(n, self.sample_size, replace=False)
        else:
            self.sample_indices = np.arange(n)
        
        # 2. Extract the subset once
        self.X_sample = X_train[self.sample_indices]
        self.y_sample = y_train[self.sample_indices]
    
    def predict(self, X_test):
        predictions = []
        for x in X_test:
            # 3. Search ONLY the subset
            distances = np.linalg.norm(self.X_sample - x, axis=1)
            k_nearest = np.argsort(distances)[:self.k]
            
            # 4. Vote (same as before)
            neighbors = self.y_sample[k_nearest]
            labels, counts = np.unique(neighbors, return_counts=True)
            predictions.append(labels[np.argmax(counts)])
        
        return np.array(predictions)

You've built your KNN. It looks good. But "looks good" isn't data. To truly trust your model, you need to measure how it fails, not just if it succeeds.

Why it matters for KNN: If you have imbalanced data (e.g., 99% Not Spam), a lazy KNN with a huge k might just predict "Not Spam" for everything. It gets 99% accuracy but catches 0 spam. Precision and Recall save you from this trap.

from sklearn.model_selection import KFold, cross_val_score
from sklearn.preprocessing import StandardScaler
from sklearn.pipeline import Pipeline

# Create a pipeline: Scale first, then KNN
pipeline = Pipeline([
    ('scaler', StandardScaler()),
    ('knn', KNN(k=5))  # Your from-scratch or sklearn KNN
])

# K-Fold handles the splitting automatically
kf = KFold(n_splits=5, shuffle=True, random_state=42)

# The pipeline ensures scaling happens INSIDE each fold
scores = cross_val_score(pipeline, X, y, cv=kf, scoring='accuracy')

print(f"Mean Accuracy: {scores.mean():.2f} (+/- {scores.std() * 2:.2f})")

By wrapping your scaler and KNN in a pipeline and using cross-validation, you ensure that every evaluation is fair. This is the professional way to validate your KNN model.

You already saw that k is the only true hyperparameter in KNN—it controls how many neighbors vote on each prediction. Changing k directly shapes the bias–variance trade-off. Let's visualize what happens inside that "neighborhood" as we adjust k.

from sklearn.model_selection import StratifiedKFold
import numpy as np

# 1. Define range of k to test
k_values = list(range(1, 31, 2))  # Odd k to avoid ties
cv_scores = []

for k in k_values:
    # Run Cross-Validation for this k
    score = cross_val_score_knn(X, y, k=k)
    cv_scores.append(score)

# 2. Pick best k
best_k = k_values[np.argmax(cv_scores)]
print(f"Best k: {best_k}")

Once you select the best k via CV, re-train your KNN on the full training set (with scaling fitted on all training data) and evaluate once on a held-out test set. This gives your final unbiased performance estimate. Never use the test set during hyperparameter tuning—that would invalidate your evaluation.

You've built a working KNN. But what happens when your training set grows from 100 points to 100,000?

The brute-force approach—calculating the distance from your new point to every single training sample—becomes painfully slow. It's an O(n_train) operation per query. If you have millions of points, a single prediction could take seconds or even minutes.

What this means for you:

• Small, low-dimensional data (e.g., <10,000 samples, <20 features): Brute-force KNN is simple and effective.
• Large or high-dimensional data: You'll need optimizations (like KD-Trees) or you should consider a different algorithm altogether. KNN's simplicity comes at a scalability cost.

Remember: No algorithm is universally best. The "no free lunch" theorem applies. Your choice should be driven by data size, feature types, performance needs, and computational constraints—not just familiarity. KNN is a valuable tool, but knowing when to put it down is part of becoming a skilled practitioner.

You now have a working KNN implementation and understand how to tune k and evaluate performance. But in practice, KNN's simplicity comes with important constraints—ignoring them can lead to models that are slow, inaccurate, or both. Let's look at the two most common pitfalls and when you should reach for a different algorithm instead.

from sklearn.pipeline import Pipeline
from sklearn.preprocessing import StandardScaler

# Always wrap scaling in a pipeline!
pipeline = Pipeline([
    ('scaler', StandardScaler()),
    ('knn', KNN(k=5))
])

Remember: No algorithm is universally best. The "no free lunch" theorem applies. Your choice should be driven by data size, feature types, performance needs, and computational constraints—not just familiarity. KNN is a valuable tool, but knowing when to put it down is part of becoming a skilled practitioner.