Let's be real: in a production machine learning environment, we all just import scikit-learn
and call it a day. But treating algorithms like black boxes can come back to bite you when those abstractions leak. Building K-Nearest Neighbors (KNN) from scratch is a fantastic exercise to actually understand the mechanics working under the hood.
At its core, KNN relies on a surprisingly simple geometric premise: a data point probably belongs to the same category as its closest spatial neighbors. Rebuilding this classifier from the ground up forces you to tackle some critical engineering challenges, such as:
In this post, we'll walk through the architectural decisions behind a pure Python implementation of KNN, translating textbook math into functional code.
import math
def _check_length(x, y):
"""Ensure both vectors have the same length."""
if len(x) != len(y):
raise ValueError("Vectors must be of same length")
def euclidean_distance(x, y):
"""Compute Euclidean distance between two vectors."""
_check_length(x, y)
sum_of_sq = sum(
(i - j) ** 2
for i, j in zip(x, y)
)
return math.sqrt(sum_of_sq)
Calculate spatial similarity between vectors using Euclidean distance.
KNN is fundamentally a geometry problem. The entire algorithm hinges on quantifying exactly how far apart points are in a given space.
If we're looking at a 2D plane, Euclidean distance comes straight from the Pythagorean theorem:
In machine learning, however, we're rarely dealing with just two dimensions. Fortunately, the formula generalizes neatly to an arbitrary number of dimensions:
Where:
In the euclidean_distance()
function above, notice the generator expression inside sum()
. It evaluates lazily, meaning we avoid constructing an intermediate list of squared differences in memory. This is a deliberate design choice that scales well when working with high-dimensional data.
Also, don't overlook the _check_length()
guard—it is structurally critical. Comparing vectors of different dimensions is mathematically invalid. Since Python's zip()
function silently truncates to the shortest iterable, omitting this check could allow the function to fail silently and return incorrect results.
def _get_majority_vote(neighbors):
vote_count = {}
min_distance_per_label = {}
for neighbor in neighbors:
label = neighbor["label"]
distance = neighbor["distance"]
vote_count[label] = vote_count.get(label, 0) + 1
min_distance_per_label[label] = min(
distance,
min_distance_per_label.get(label, float("inf"))
)
best_label = None
best_vote = -1
best_distance = float("inf")
for label in vote_count:
votes = vote_count[label]
dist = min_distance_per_label[label]
if votes > best_vote or (
votes == best_vote and dist < best_distance
):
best_label = label
best_vote = votes
best_distance = dist
return best_label
Tally the neighbors' labels to determine the final classification while using spatial proximity as a deterministic tie-breaker.
Counting votes is straightforward with a hash map, but robust edge-case management is what separates a demo implementation from production-ready code.
Imagine a scenario where k=4 and your query point sits exactly halfway between two Class A neighbors and two Class B neighbors. A naive implementation might simply choose whichever label appears first. That makes the classifier non-deterministic and biased by data ordering.
To address this, the implementation maintains a secondary dictionary:
min_distance_per_label
As the algorithm iterates through the neighbors, it tracks the minimum distance observed for each class label. If a voting tie occurs,
the algorithm chooses the class whose nearest representative is closest to the query point.
Mathematically:
Where:
This approach anchors tie-breaking in actual spatial proximity rather than arbitrary ordering or randomness.
import numpy as np
def knn_predict(training_data, labels, query_point, k):
distances = [
euclidean_distance(sample, query_point)
for sample in training_data
]
nearest_idx = np.argsort(distances)[:k]
neighbors = [
{
"distance": distances[i],
"label": labels[i]
}
for i in nearest_idx
]
return _get_majority_vote(neighbors)
Create a controller function that computes distances, isolates the top k candidates, and delegates classification to the voting logic.
Although a production implementation would include comprehensive validation and optimization, the core algorithm relies on one key operation:
np.argsort(distances)[:k]
Keeping multiple arrays synchronized during sorting can quickly become messy. Rather than zipping distances and labels together, sorting them, and then unpacking them again, we sort only the distance values and retrieve the corresponding indices.
numpy.argsort()
returns the indices that would sort an array. This allows us to select the nearest neighbors without mutating the original data structures.
Mathematically, we're selecting:
where D is the vector of computed distances.
This is a common scientific-computing pattern because it preserves the relationship between distances and labels while avoiding unnecessary data transformations.
After selecting the nearest indices, we package the neighbors into lightweight dictionaries and pass them directly to the voting mechanism.
K-Nearest Neighbors is a unique machine learning algorithm because it behaves less like a traditional parameter-learning model and more like a combination of geometric reasoning and voting heuristics.
Unlike algorithms such as linear regression or neural networks, KNN performs no explicit training. It simply stores the dataset and uses distance as a proxy for similarity during prediction.
Building algorithms from scratch is one of the fastest ways to demystify machine learning. You quickly discover that much of the perceived complexity comes from standard software engineering concerns:
The mathematics matters, but so does thoughtful implementation.
To explore more machine learning projects and software engineering content: