K-Nearest Neighbour (K-NN) Algorithm for Classification

Have you ever tried to guess the genre of a new song just by looking at the other songs in the same playlist? Or maybe you’ve picked a new restaurant based on what your five closest friends recommend. If you have, you’ve used the basic logic behind one of the most intuitive algorithms in machine learning: K-Nearest Neighbour (K-NN). It’s a powerful idea that operates on a simple, relatable principle: “You are known by the company you keep.”

In the world of data, this translates to: a new, unclassified data point will likely belong to the same group as the data points it is “closest” to. K-NN is a foundational algorithm used for classification (like “is this email spam or not spam?”) and regression (like “what is the likely price of this house?”). In this post, we’ll break down exactly how this algorithm works, how it measures “closeness,” and why it’s a fantastic-but “lazy”-tool in the data science toolkit.

How K-NN actually works (and why it’s ‘lazy’) 🔗

At its heart, K-NN is a supervised learning algorithm. This means we start with a dataset where we already have the “right answers.” Imagine a spreadsheet of customer data, where each row is a customer and columns contain features like ‘age’, ‘monthly spending’, and a final column, ‘customer type’ (e.g., ‘Standard’, ‘Premium’, ‘VIP’). We have the features (the inputs) and the class (the output).

Now, a new customer signs up. We have their age and monthly spending, but we don’t know their ‘customer type’. How do we classify them? K-NN follows a simple, two-step process:

1. Find the neighbors: The algorithm calculates the “distance” from our new customer to every single customer in our existing dataset.
2. Hold a vote: It then identifies the ‘K’ closest customers (the “nearest neighbors”). ‘K’ is a number you choose. If we set K=7, we find the 7 closest customers. The algorithm then looks at their ‘customer type’. If, say, 5 of those 7 are ‘Premium’ and 2 are ‘Standard’, the algorithm predicts ‘Premium’ for our new customer. It’s a simple majority vote.

That’s it. That’s the core logic. But the most interesting part of K-NN is what it *doesn’t* do. Unlike other algorithms, K-NN does no “learning” upfront. It doesn’t try to find a complex formula or build a decision tree from the training data. Instead, it just memorizes the entire dataset. This is why it’s known as an instance-based learning or lazy learning algorithm. It’s “lazy” because it postpones all the real work-the distance calculations-until the very last second when a prediction is actually needed. This makes it incredibly simple to add new data (you just add it to the memory), but as we’ll see, this laziness comes at a cost.

Measuring your neighborhood: The ‘distance’ in K-NN 🔗

The entire algorithm hinges on the concept of “closeness.” But how do you mathematically measure the distance between two customers, or two houses, or two emails? This is done using distance metrics. The metric you choose is critical and depends on the kind of data you have. The two most common are Euclidean and Manhattan.

Euclidean distance: As the crow flies 🔗

This is the one you probably remember from high school geometry. It’s the “straight-line” distance between two points. If we have two data points, A (x1, y1) and B (x2, y2), on a 2D graph, the Euclidean distance is the length of the hypotenuse of the right triangle connecting them.

The formula is: Distance = √((x2 - x1)² + (y2 - y1)²)

Analogy: Imagine two people in an open field. The Euclidean distance is the shortest possible path you could walk in a straight line to get from one person to the other. It’s the most common, go-to distance metric and works very well when your features are continuous and have a “real” spatial relationship.

Manhattan distance: Walking the city blocks 🔗

This metric is named after the grid-like street layout of Manhattan. You can’t just cut through buildings (like in the Euclidean “open field”); you have to travel along the streets (the grid lines).

The Manhattan distance is the sum of the absolute differences of the coordinates. For our same two points, A (x1, y1) and B (x2, y2), the formula is:

Distance = |x2 - x1| + |y2 - y1|

Analogy: If you’re at the corner of 5th Ave & 42nd St and want to get to 8th Ave & 40th St, you have to walk 3 blocks west (8 – 5) and 2 blocks south (42 – 40). The total distance you “walk” is 3 + 2 = 5 blocks. This metric is often preferred over Euclidean distance when dealing with high-dimensional data, as it can be less sensitive to outliers.

A quick note on scaling 🔗

A critical, non-negotiable step before using K-NN is feature scaling. Imagine your customer data has ‘age’ (ranging from 18 to 80) and ‘income’ (ranging from 20,000 to 2,000,000). If you use these raw numbers, the ‘income’ feature will completely dominate the distance calculation. A difference of 2 years in age will be treated as nothing compared to a difference of 20,000 in income. Your algorithm will, in effect, only be paying attention to income.

To fix this, you must scale your features so they are on a comparable range. Common methods include Standardization (rescaling data to have a mean of 0 and a standard deviation of 1) or Normalization (rescaling data to be between 0 and 1). This ensures all features contribute fairly to the distance calculation.

The all-important ‘K’: How many neighbors to ask? 🔗

The ‘K’ in K-NN is the hyperparameter you must choose. It’s the number of neighbors that get to vote. This choice is a balancing act, as ‘K’ has a massive impact on your model’s behavior.

The trouble with a small K 🔗

Let’s say you choose K=1. This means you classify your new data point exactly the same as its single closest neighbor. This approach is extremely sensitive to noise and outliers.

Imagine our customer dataset. What if our new customer’s *single* closest neighbor happens to be a ‘VIP’ who is an outlier-a student who got a one-time large gift and spent a lot, but isn’t a typical VIP? By setting K=1, we would misclassify our new customer as a ‘VIP’. A small K creates a “jagged” and complex decision boundary, a classic sign of overfitting, where the model has memorized the noise in the training data rather than the underlying pattern.

The problem with a large K 🔗

So, why not just use a really large K? Let’s say we have 1,000 customers in our dataset, and we set K=1,000. To classify a new customer, we would take a vote from… everyone. The result would simply be the majority class of the *entire dataset*. If 60% of our customers are ‘Standard’, then *every new customer* will be classified as ‘Standard’, regardless of their age or spending.

This “oversmooths” the decision boundary and leads to underfitting. The model is too simple and has failed to capture any local patterns in the data, making it a poor predictor.

Finding the ‘Goldilocks’ K 🔗

We need a ‘K’ that is “just right.”

• It should be an odd number (like 3, 5, 7) for binary (two-class) problems. This avoids ties in the voting.
• A common (but not a strict rule) heuristic is to set K to be less than or equal to the square root of N (where N is the number of items in your training set). For a dataset of 150 items, a good starting ‘K’ to test would be around √150 ≈ 12. So, you might test K=11 or K=13.

Ultimately, the best way to find the optimal ‘K’ is to test different values and see which one gives you the best predictive accuracy on unseen data, often using a technique called cross-validation.

Dealing with a messy world: Data imperfections 🔗

Our examples so far have used nice, clean numbers. What about real-world data that has text or is missing information?

Handling categorical attributes 🔗

What if one of our features is “Location” (e.g., ‘City A’, ‘City B’, ‘City C’)? We can’t use Euclidean or Manhattan distance directly. The simplest solution is to use a Hamming distance. The logic is:

• If the values match (e.g., ‘City A’ and ‘City A’), the “distance” for that feature is 0.
• If the values do not match (e.g., ‘City A’ and ‘City B’), the “distance” is 1.

This value is then included in the overall distance calculation, often after being converted into “dummy variables” (e.g., columns ‘is_City_A’, ‘is_City_B’, etc.).

Handling missing values 🔗

What if we don’t know a neighbor’s ‘age’? We can’t calculate the distance. A common (and conservative) strategy is to assume the maximum possible difference for that attribute. If ‘age’ in our scaled dataset ranges from 0 to 1, we would assume the difference for that missing value is 1, the maximum possible “penalty.” This ensures the data point with missing info is considered “far away” in that dimension, acknowledging our uncertainty.

The good, the bad, and the optimized 🔗

K-NN is a powerful tool, but it’s not the right tool for every job. Its “lazy” nature creates a very specific set of strengths and weaknesses.

The strengths: Simple and effective 🔗

• Simple to understand: It’s one of the easiest machine learning algorithms to explain. The “vote of your neighbors” logic is highly intuitive.
• No training phase: Because it’s a lazy learner, “training” is as simple as storing the dataset. This makes it incredibly fast to “build” and easy to update with new data on the fly.
• Naturally handles multi-class problems: It’s not limited to just two classes. The majority vote works just as well for 10 classes as it does for 2.
• Non-parametric: K-NN makes no assumptions about the underlying data distribution (like assuming it’s a bell curve). It can capture complex, non-linear patterns that other models might miss.

The weaknesses: The ‘lazy’ algorithm’s price 🔗

• Slow and expensive at prediction time: This is the big one. To classify one new point, K-NN must calculate the distance to every single point in the training set. If your dataset has 10 million customers, that’s 10 million distance calculations for one prediction. This makes it unacceptably slow for many large-scale, real-time applications.
• Requires high memory: You must store the entire training dataset in memory. This is not feasible for massive datasets.
• The Curse of Dimensionality: K-NN’s performance degrades badly in high-dimensional spaces (i.e., when you have many features). As the number of dimensions (features) increases, the “distance” between points becomes less meaningful. In a high-dimensional space, all points start to seem equally “far apart,” and the concept of a “nearest neighbor” breaks down.
• Sensitive to irrelevant features: If you include features that are “noise” (e.g., ‘customer_ID_number’), they will contribute to the distance calculation and pollute your results.

Speeding things up: K-NN optimizations 🔗

Fortunately, data scientists have developed ways to overcome the speed problem. Instead of a “brute-force” search where we check every single point, we can use smarter data structures.

• Search trees: Structures like K-D Trees or Ball Trees are used to partition the data. This allows the algorithm to very quickly find the nearest neighbors without having to check every point, dramatically speeding up prediction time.
• Pruning (or editing): This involves removing data points from the stored dataset that don’t add value. For example, we might remove “outliers” or points in the middle of a large, uniform cluster (since they are redundant). This makes the dataset smaller and the search faster.
• Partial distance calculations: We can stop calculating the distance between two points as soon as we know it’s already larger than the distance to our current K-th neighbor.

What do you think?

Have you ever made a decision (like picking a movie or restaurant) using a ‘K-NN’ style of thinking? How important was ‘K’ (the number of friends you asked)?

Considering its ‘laziness’ and high memory cost, when do you think K-NN would be a better choice for a business than a “model-building” algorithm like a decision tree?

References

1. https://www.ibm.com/think/topics/knn
2. https://www.geeksforgeeks.org/machine-learning/how-to-choose-the-right-distance-metric-in-knn/
3. https://arize.com/blog-course/knn-algorithm-k-nearest-neighbor/
4. https://en.wikipedia.org/wiki/K-nearest_neighbors_algorithm