Implementing K-Nearest Neighbors (KNN)

Hello! Let's dive into our next lesson.

Introduction

In our previous session, we built a Decision Tree from scratch, an example of a "model-based" learner. The algorithm learned an explicit set of rules (the tree structure) from the training data. Today, we're going to explore a fundamentally different approach with the K-Nearest Neighbors (KNN) algorithm.

KNN is what's known as an instance-based or "lazy" learner. It doesn't build a model during the training phase; instead, it simply memorizes the entire training dataset. All the real work happens at prediction time. This lesson is designed to help you achieve the learning outcome: Implement the K-nearest neighbors (KNN) algorithm.

We will cover:

1. The intuitive logic behind KNN for both classification and regression.
2. The importance of distance metrics, focusing on the standard Euclidean distance.
3. A complete, from-scratch implementation of the KNN algorithm in Python, building a class with the familiar fit and predict methods.
4. The critical role of feature scaling when using distance-based algorithms like KNN.

Let's begin by visualizing how KNN makes decisions.

1. The Core Idea: "Tell me who your friends are..."

The principle behind KNN is simple: a data point is likely to be similar to the points closest to it in the feature space. To classify a new, unseen data point, KNN performs three steps:

1. Calculates the distance from the new point to every single point in the training data.
2. Identifies the 'K' closest points (its "nearest neighbors").
3. Assigns a label by taking a majority vote among those K neighbors.

The image below shows the decision boundaries created by a KNN classifier with K=5. Notice how the boundaries are not simple lines but complex shapes that adapt to the local distribution of the training data.

This video provides an excellent introduction to the mechanics of KNN, its non-parametric nature, and the importance of choosing the right value for K.

2. Measuring Distance with Euclidean Distance

The "nearness" in KNN is determined by a distance metric. While several metrics exist, the most common is the Euclidean distance, which is a straight-line distance between two points. Given your math background, you'll recognize this as a generalization of the Pythagorean theorem.

For two points, ${\mathbf{x}}_1$ and ${\mathbf{x}}_2$, in an $n$-dimensional space, the Euclidean distance is:

where $x_{1i}$ and $x_{2i}$ are the $i$-th components (features) of the points.

Your experience with Python and NumPy allows for a very efficient, vectorized implementation of this formula, avoiding explicit loops over the feature dimensions.

import numpy as np

def euclidean_distance(x1, x2):
    return np.sqrt(np.sum((x1 - x2)**2))

This function will be the workhorse of our KNN implementation.

3. Implementing KNN from Scratch

We are now ready to build the algorithm. We'll structure our code as a Python class, similar to our DecisionTree implementation. This video provides a clear, step-by-step guide to creating a KNN class from scratch.

After following the video, you should have a complete, working KNN class. The implementation cleanly separates the main steps:

• fit(): Memorizes the data.
• predict(): Orchestrates prediction for a set of samples.
• _predict() (or a similar helper):
  • Calculates all distances.
  • Finds the nearest neighbor indices using np.argsort().
  • Retrieves the corresponding labels.
  • Performs a majority vote using collections.Counter.

4. A Crucial Detail: Feature Scaling

There's one critical aspect of using KNN that the implementation videos don't emphasize: feature scaling.

The Euclidean distance formula treats all dimensions equally. If one feature has a much larger scale than another (e.g., house prices in millions vs. number of bedrooms from 1-5), the distance calculation will be completely dominated by the feature with the larger range.

Consider this example:

• Point A: [2 bedrooms, $500,000]
• Point B: [4 bedrooms, $510,000]

The squared distance is $(4-2{)}^2+(510000-500000{)}^2=4+100,000,000$. The difference in price almost entirely determines the distance, making the bedrooms feature practically irrelevant.

To prevent this, it's standard practice to scale your features before fitting a KNN model. Common techniques include:

• Standardization (Z-score normalization): Rescales features to have a mean of 0 and a standard deviation of 1.
• Min-Max Scaling: Rescales features to a fixed range, usually [0, 1].

Since you have already covered data preprocessing steps like train-test splits, you can integrate feature scaling into that pipeline. You would fit the scaler on the training data and then use it to transform both the training and test data.

Conclusion

In this lesson, we've implemented the K-Nearest Neighbors algorithm, a cornerstone of classical machine learning. You've seen that despite its simplicity, it introduces powerful concepts like instance-based learning and highlights the importance of data preprocessing.

Key Takeaways:

• KNN is a non-parametric, lazy learner that makes predictions based on the majority class of its 'K' nearest neighbors.
• The implementation involves three main steps: calculating distances, finding the nearest neighbors (efficiently done with np.argsort), and performing a majority vote (using collections.Counter).
• Unlike model-based algorithms like Decision Trees, KNN's fit method is trivial; the computation happens during predict.
• Feature scaling is a mandatory preprocessing step for distance-based algorithms like KNN to ensure all features contribute fairly.

For a deeper dive, I recommend exploring the K-Nearest Neighbors (KNN) Classifier: Step-by-Step Python Implementation... article from kenwuyang.com (resource LINK). It shows how to build a KNN classifier that is compatible with the scikit-learn API, a great next step for a software engineer.

Preview of the next lesson:
We have now built several individual predictive models (SVM, Decision Tree, KNN). But what if we could combine them to create something even more powerful? In the next lesson, we will explore the principles of ensemble learning. We'll start with bagging, a technique that forms the foundation of one of the most popular and effective algorithms: the Random Forest.