K-NN: Distance-Based Classification

Introduction

Welcome to a new module! We're now shifting gears from the regression models we've been studying. So far, with linear, Ridge, and LASSO regression, our goal was to find a mathematical function (a line or hyperplane) that best fits the data. Today, we venture into a different family of algorithms called instance-based learning.

This lesson introduces the K-Nearest Neighbors (K-NN) algorithm, a simple yet powerful method for classification. Unlike linear models, K-NN doesn't learn an explicit function from the data. Instead, it memorizes the entire training dataset and makes predictions based on the principle of proximity.

Our goal is to understand the core logic of K-NN: its distance-based voting mechanism. You'll learn how it uses the 'K' most similar data points from its memory to decide the class of a new, unseen data point. This concept of a key parameter 'K' will also connect back to our last lesson on hyperparameter tuning with cross-validation.

The Core Intuition of K-NN

At its heart, the K-NN algorithm operates on a simple, real-world idea: "You are defined by the company you keep."

Imagine you move to a new town and want to predict which political party is likely to win the local election. A reasonable strategy would be to ask your closest neighbors who they are voting for. If you ask your 5 closest neighbors (K=5) and 4 of them support Party A, you might predict Party A will win.

K-NN applies this exact logic to data points in a feature space. It assumes that similar things exist in close proximity. To classify a new data point, it looks at the 'K' data points from the training set that are closest to it and takes a majority vote.

The Distance-Based Voting Mechanism

The process is straightforward and can be broken down into a few key steps.

K Nearest Neighbor Classifier, Explained: A Visual Guide with Code ...

The article 'K Nearest Neighbor Classifier, Explained' provides a very clear, step-by-step summary of how the algorithm operates. It perfectly outlines the mechanism we're focusing on.

Please read the section titled 'Main Mechanism'. It breaks down the process into four clear steps that are central to how K-NN works.

As you just read, the process is:

Calculate Distances: When given a new data point to classify, the algorithm calculates its distance to every single point in the training data. A common choice for this is the standard Euclidean distance, which is essentially the straight-line distance between two points. Given your background in data science and math, you'll recognize this as $d (p, q) = \sum_{i = 1}^{n} (q_{i} - p_{i})^{2}$ .
Select K Nearest Neighbors: The algorithm then identifies the 'K' points from the training data that have the smallest distances to the new point.
Take a Majority Vote: It looks at the class labels of these 'K' neighbors and counts how many belong to each class.
Assign the Class: The new data point is assigned the class label that received the most votes.

This entire process is captured wonderfully in the following diagram.

K-Nearest Neighbors (K-NN) Algorithm Explained Visually — This image illustrates the four steps of K-NN. 1. A new point (Xtest) is introduced. 2. Distances to all other points are calculated. 3. The 'k' nearest neighbors are identified (here, k=3). 4. A majority vote of the neighbors' labels determines the new point's class (Purple).

K-NN in Action: A Visual Explanation

Seeing this process dynamically makes it even clearer. The following video provides an excellent visual walkthrough of classifying new data points using different values of K.

StatQuest: K-nearest neighbors, Clearly Explained

The video 'StatQuest: K-nearest neighbors, Clearly Explained' is one of the best resources for building intuition. We'll watch the core part where Josh Starmer demonstrates the voting process.

Please watch from 01:24 to 02:50. This segment covers: How classification works with the simplest case, K=1. How the classification is determined by a majority vote when K is larger (K=11 in the example). What happens when a new point is between two clusters.

As you saw, the choice of 'K' is critical. When K=1, the new point is simply assigned the class of its single nearest neighbor. When K is larger, it's a democratic vote among the neighbors.

The Importance of Choosing 'K'

The value of 'K' is a hyperparameter that you, the data scientist, must choose. This choice has a significant impact on the model's behavior and directly relates to the bias-variance trade-off we discussed in the regression module.

A small K (e.g., K=1) makes the model highly sensitive to individual data points, including noise. It can create a very complex decision boundary, leading to low bias but high variance (overfitting).
A large K makes the model consider many neighbors, smoothing out the decision boundary. This makes it less sensitive to noise but may ignore local patterns, leading to high bias but low variance (underfitting).

Let's see a quick example of how a poorly chosen 'K' can lead to an incorrect classification.

Machine Learning Tutorial Python - 18: K nearest neighbors classification with python code

The video from the 'codebasics' channel gives a great practical example of how choosing a 'K' that is too large can cause problems.

Watch the segment from 02:23 to 03:27. The presenter shows how a small K correctly classifies the point, but increasing K to 20 leads to a clear misclassification.

This highlights that finding the "right" 'K' is a balancing act. In the next lesson, we will use the cross-validation techniques you've already learned to find an optimal value for 'K'.

What if There's a Tie?

In the StatQuest video, you might have wondered what happens if the votes are tied (e.g., for K=4, you find two neighbors of Class A and two of Class B). There are several ways to handle this:

Choose an odd K: For binary (two-class) classification problems, simply choosing an odd number for K (3, 5, 7...) prevents ties. This is a very common practice.
Random choice: Randomly pick one of the tied classes.
Weighted voting: Give more weight to the votes of closer neighbors. A neighbor that is very close would have its vote count more than a neighbor that is further away (but still within the 'K' group).

Conclusion

In this lesson, we introduced our first classification algorithm, K-Nearest Neighbors. We moved away from fitting functions and embraced an instance-based approach.

Key Takeaways:

K-NN is an instance-based, or "lazy learning," algorithm. It doesn't have a traditional training phase; it memorizes the training data.
The core mechanism is distance-based voting: a new point is classified by a majority vote of its 'K' nearest neighbors.
The distance is typically Euclidean distance, measuring the straight-line proximity in the feature space.
'K' is a critical hyperparameter that controls the bias-variance trade-off. Finding the right 'K' is essential for good performance.

Preview of the Next Lesson

Now that you understand the "what" and "why" behind K-NN, the next step is to put it into practice. In our next lesson, we will apply K-NN using scikit-learn. We will train a K-NN classifier, use it to make predictions, and analyze how changing the value of 'K' impacts the model's decision boundary and accuracy.

Recommended resources