Welcome to the next stage of our journey into supervised learning. In our previous lessons, we thoroughly explored linear and logistic regression, models that learn a specific mathematical function to map inputs to outputs. We concluded by extending logistic regression to handle multiple classes. Now, we will pivot to a fundamentally different and remarkably intuitive type of algorithm.
This lesson introduces the K-Nearest Neighbors (KNN) algorithm. Instead of learning an explicit function, KNN operates on a simple principle: "you are known by the company you keep." It's our first look at an instance-based or lazy learning algorithm, which makes predictions by directly using the training data points rather than a learned model. We will cover the core logic of KNN, explore how it makes predictions for both classification and regression, understand the critical role of the hyperparameter 'K', and examine the distance metrics that define what it means to be a "neighbor."
The Core Intuition: Learning by Proximity
Imagine you are trying to classify a new, unidentifiable fruit. If you place it on a table with other fruits and notice that the five fruits closest to it are all apples, you would naturally guess that your new fruit is also an apple. This is the essence of K-Nearest Neighbors.
To make a prediction for a new data point, KNN performs a few simple steps:
- Calculates the distance from the new point to every single point in the training dataset.
- Identifies the 'K' closest points in the training data (the "nearest neighbors").
- Makes a prediction based on those neighbors. For a classification task, it takes a majority vote; the new point is assigned the most common class among its K neighbors. For a regression task, it typically takes the average of the neighbors' values.
The following video from Brandon Rohrer provides a wonderful visual introduction using the example of classifying mushrooms as edible or toxic.
This video introduces the KNN concept and uses a clear, practical example to build intuition.
Please watch the first part of the video, from the beginning. It sets up the classification problem and introduces the fundamental idea of looking at the "closest neighbors" to make a decision.
Because KNN doesn't learn a model in a traditional training phase—it simply stores the entire dataset—it is known as a lazy learning algorithm. All the computation (calculating distances) happens at prediction time. This contrasts sharply with models like logistic regression, which are eager learners because they build a generalized model during training and discard the training data afterward.
The image below provides a fantastic summary of the entire KNN workflow, which we will unpack throughout this lesson. For now, focus on the "Core Intuition" section, which recaps what we've just discussed.
The Role of 'K': Finding the Right-Sized Neighborhood
The 'K' in KNN is a hyperparameter that you, the data scientist, must choose. It represents the number of neighbors to consider when making a prediction. The choice of K has a profound impact on the model's behavior and directly influences the bias-variance tradeoff.
- A small K (e.g., K=1) means the model is very localized and sensitive to the immediate neighborhood. This creates a highly flexible and complex decision boundary, but it can also make the model susceptible to noise and outliers. A single mislabeled data point can easily sway the prediction, leading to high variance and overfitting.
- A large K considers a much wider neighborhood. This has a smoothing effect on the decision boundary, making the model more robust to noise. However, if K is too large, the model might consider neighbors from other classes, becoming too generalized and losing the ability to capture local patterns. This leads to high bias and underfitting.
The following segment of the same video explains this tradeoff using a very clear example of a potentially mislabeled data point.
This part of the video illustrates how the choice of K affects the model's ability to handle noise in the data.
Please watch the segment on choosing K. Pay close attention to how a K of 1 versus a K of 5 leads to different classifications in the presence of a noisy data point.
As a practical rule of thumb, especially for binary classification problems, it's common to choose an odd value for K (3, 5, 7, etc.). This prevents ties in the majority vote. The optimal value of K is typically found through experimentation and cross-validation, which we will cover in a future practical lesson.
Measuring Nearness: Distance Metrics
The concept of "nearest" is defined by a distance metric. The choice of metric determines how the "closeness" between two data points in the feature space is calculated. Your background in computational mathematics will make these concepts familiar.
The most common metrics are special cases of a generalized metric called the Minkowski distance. For two points, and , the Minkowski distance is defined as:
The parameter in this formula determines the specific distance metric.
Euclidean Distance ()
When we set , we get the Euclidean distance, which is the most common default for KNN. This is the straight-line distance between two points—what you would measure with a ruler. It is also known as the L2 norm.
Manhattan Distance ()
When we set , we get the Manhattan distance. It measures distance by summing the absolute differences of the coordinates, as if you were navigating a city grid and could only travel along horizontal and vertical streets. It is also known as the L1 norm.
The image below offers a great visualization of these two metrics, along with the generalized Minkowski formula.
The following short video provides a quick, animated recap of how these distances are calculated and their relationship to the Minkowski metric.
Intuition and Math Behind KNN Classifier in ML Explained
This segment offers a concise mathematical and visual explanation of the distance metrics used in KNN.
Watch the portion of the video explaining the distance metrics. It quickly clarifies the formulas for Minkowski, Manhattan, and Euclidean distance.
While Euclidean distance is intuitive and works well in many low-dimensional problems, Manhattan distance is often preferred in high-dimensional spaces or when features have different scales or units, as it is less sensitive to large differences in a single dimension.
To dive a bit deeper into the formal definitions and see how this logic translates to code, the following article provides clear explanations. While it includes Python code that implements these from scratch, focus on the textual descriptions that formalize what we've just discussed.
Exploring KNN with Different Distance Metrics | by Abdullah Siddique
This article explains the mathematical intuition behind the key distance metrics and shows how they are calculated.
Please read the descriptions for the three distance metrics. Start with the paragraph explaining Euclidean distance. Then, review the explanation of Minkowski distance as a generalization. Finally, read the description of Manhattan distance and its properties.
A Critical Prerequisite: The Importance of Feature Scaling
There's a critical catch to using distance-based algorithms like KNN: they are extremely sensitive to the scale of the features.
Imagine you have a dataset with two features: a person's height in centimeters and their weight in kilograms. A 10 cm difference in height results in a squared difference of 100 for the Euclidean calculation, while a 10 kg difference in weight also results in a squared difference of 100. Now, what if height was measured in meters? A 0.1 m difference (10 cm) results in a squared difference of only 0.01.
In this scenario, the weight feature, with its larger numerical range, would completely dominate the distance calculation. The height feature would become almost irrelevant. This would lead the algorithm to find neighbors based almost entirely on weight, ignoring height, which is likely not what you want.
Therefore, feature scaling is mandatory for KNN. Before applying the algorithm, you must scale your features so that they are all on a comparable range. The Standardization (Z-score) and Normalization (Min-Max scaling) techniques you learned in Module 2 are essential here.
The final segment of the Brandon Rohrer video provides an unforgettable illustration of this exact problem.
This segment clearly demonstrates why feature scaling is non-negotiable when using KNN.
Watch the clip on feature scaling. The visual of the data being "squished" and how it changes the "nearest" neighbors is a powerful lesson on this topic.
Conclusion
In this lesson, we have deconstructed the K-Nearest Neighbors algorithm, a simple yet powerful instance-based classifier. You've moved from the world of parametric models to a "lazy" algorithm that relies entirely on the principle of proximity.
Key Takeaways:
- KNN is a non-parametric, instance-based algorithm that classifies new data based on a majority vote from its 'K' nearest neighbors.
- It's considered a "lazy learner" because it stores the entire training dataset and performs all calculations at prediction time.
- The choice of 'K' is a critical hyperparameter that controls the bias-variance tradeoff. Small K leads to high variance, while large K leads to high bias.
- "Nearness" is calculated using a distance metric, most commonly Euclidean (L2) or Manhattan (L1) distance, which are both special cases of the generalized Minkowski distance.
- Feature scaling is mandatory for KNN. Without it, features with larger scales will unfairly dominate the distance calculations.
In our next lesson, we will build directly on this foundation to analyze the practical strengths and weaknesses of KNN. We'll discuss why it can suffer from the "curse of dimensionality," evaluate its computational cost, and understand when it is—and is not—a good choice for a machine learning problem.