k-Nearest Neighbors

k-nearest neighbors (or k-NN) is a way for a computer to label a new example by comparing it to examples it has already seen before. This is the simplest machine learning algorithm because it has no training step and there are no weights for it to adjust. It figures out how to label a new example by finding the closest points using the Pythagorean Theorem, which is the only math you need to know.

If we take an email's features and write them as a list where x is the number of links and y is the number of exclamation marks, we can represent each email as a coordinate. Repeating this for all of our emails gives us a list of coordinates that we can graph as dots on our chart. To avoid mixing them all together, we can also assign colors to the dots, so every email in our training data now becomes a colorful dot:

This is where our beautiful animations start becoming a bit difficult to understand. In the graph above, we can represent all of our emails as dots because we only have 2 features to think about. The number of links can be the x-axis while the number of exclamation marks becomes the y-axis. However, if we had another feature like the number of recipients (sometimes spam emails are sent to many people), then we can't represent our emails in 2D space anymore. We would now have to make our chart 3D so the z-axis can properly represent our new feature:

Now you can imagine why visualizing data that has 4 features would be hard. We would have to figure out a way to map the data in 4D space, and that wouldn't really make sense to us humans. The visualization problem just continues to grow once you get more features, but we always still assign one axis per feature so the examples can be coordinates. You can now understand why the number of features is called the dimensions (written as d) since data with 2 features means you can map it to 2-dimensional space!

The best part about k-NN for beginners is that the only math you need to know is the Pythagorean Theorem. Since we have mapped all of our examples as coordinates, we need to figure out the distances between them. To do that, we're simply going to draw a right triangle and connect the two points using the triangle's hypotenuse:

The Pythagorean formula is written as the following, where $a$ and $b$ are sides, and $c$ is the hypotenuse:

We can now rewrite this formula with our points to create what's called the Euclidean distance formula. This formula is the same as the one above, but this time we are calculating the value for $a$ and $b$ using the coordinates from our two points:

For 3 features, we can just add another squared difference under the square root. We can do this indefinitely to calculate the distance for any number of features, so for $d$ features we can just add $d$ squared differences:

Imagine we are back in the office acting as a summer intern with the task of labeling a new email as spam or not spam. We turn all of our past training examples (labeled emails) into colorful dots on a chart and do the same thing for our new example that doesn't have a label… but what should the color of our new email be? In other words, what should we label our new incoming email?

The simplest rule we can use is to just find the single closest training example and copy its label. This is called 1-nearest neighbor (or 1-NN), where we will just adopt the label of whatever example happens to be closest to us.

The closest example is (5, 3) at distance 1, and it's labeled spam. So our 1-NN says to label our new email as spam as well. This makes sense and is easy to visualize since we are literally placing our new point close to other points that all share the same color.

The issue with simply copying one neighbor's label is that you can get unlucky and copy a neighbor who's actually wrong. In the real world, data has a lot of odd patterns, exceptions, or just straight up flaws in it. That damn previous intern could've mislabeled some of the emails, or some strange spam email just happened to have zero links in it. If our new email is right next to the strange one, then 1-NN will end up copying its mistakes.

The solution is to ask many neighbors instead of just one. Instead of asking and copying one neighbor's mistake, we can find the k closest points and allow them to vote, where the label with the most votes wins! This is the main idea behind k-nearest neighbors because k is just the number of neighbors that we allow to participate in our vote. Notice how the name of the algorithm is starting to make sense: k-nearest neighbors.

If this formula looks scary, allow me to guide you through it. $N_k(x)$ just means the set of $k$ neighbors that we are looking at, and the $\mathbf{1}(y_i = c)$ is an indicator that only returns 1 or 0. It basically returns 1 when the neighbor's label matches the label $c$ we are checking, or 0 if it doesn't. The $\sum$ means that we are counting all the votes for our label $c$. The arg max simply means we are checking every label and choosing the one that got the most votes, which means $\hat{y}$ is our final answer, or the label we calculated got the most votes.

Here are the steps that the algorithm takes, but notice that step 1 isn't doing much work. This is the reason why k-NN is called a lazy learner: all the effort happens at prediction time. Other machine learning algorithms usually do the opposite and do the heavy lifting during training.

Let's take a look at the code. As mentioned before, distance() is the function from the Euclidean Distance section, calculating the k_nearest is steps 2 and 3, and classify & regress are step 4:

By now you realize that k is the only parameter you have control over, and it determines how much nearby examples affect the final prediction. If k = 1, then the prediction just copies the closest example, meaning it follows the training data perfectly, including the mistakes. This is called overfitting, where the model memorizes the training data perfectly but can't apply its learning to new data. For example, a student who completely memorizes a test will get a perfect score on that specific test but will most likely fail any new tests with different questions.

However, if we set k to the highest value, which is the total number of examples in the training set, then it will always just pick the most common label and completely ignore the local detail. This is called underfitting, where the model hasn't learned the patterns in the data at all. This is like a student who learned that "the answer is usually C on multiple choice questions" and just spams that on all tests.

To find the right k value for your data, you need some kind of measurement or score so you know how to improve. In machine learning, the score we use is called the error rate, and it's the percent of predictions that are wrong. For example, if we labeled 20 emails and 5 of them were wrong, then our error rate is 5/20 or 25%. We can measure error rates for both the training data and real world test data.

Training error is the model's error rate on examples that it has already seen, or in k-NN's case, examples that it has stored. Think of it like grading a student who has already seen the answers to a test. For k-NN where k = 1, the error rate is exactly 0. Why do you think that happens?

This is because in k-NN models, the training data is literally stored during the training step. When a 1-NN model is asked to predict the label for an email it's already seen, it looks up that closest email, finds the exact same one where distance = 0, and copies the label from the same email. Of course, this means that the training error for 1-NN models is 0 since it's right every time. As we increase k, the training error rises since now we don't just copy the same email's label but rather allow the nearby emails to have a vote and affect the final prediction.

This is one of the greatest questions I've ever been asked during a tutoring session, and it genuinely improved my own understanding of machine learning. If a model has already seen the answers to the training data, why doesn't it just score perfectly every time? I'd expect a student who has seen the answers to a test to score perfectly, right? The training error is zero for 1-NN because it literally acts like a hashmap to look up the answers, but a model that only adjusts a couple of numbers can't do that.

Let's imagine a bunch of scattered points on a graph. Your job is to draw a straight line that gets as close as possible to the points, also known as the line of best fit. A straight line only has two parameters that you can tweak: where it crosses the y-axis, and the slope of the line. Since you only have access to these two parameters, no matter what numbers you use, a straight line won't be able to bend and touch every point, which means you will have training error left over no matter what you do.

A large neural network that can simulate complex lines can drive the training error to zero by creating a squiggle that touches every point, but that means it's overfitting by learning the mistakes and noise of the data. As a matter of fact, if you assign random labels to your training data (like assigning "Cat" to a picture of a truck), meaning there are no patterns to learn, Zhang and colleagues showed in 2017 that a large network can literally just memorize the training data and get the training error to zero. This is why low training error doesn't say much about quality and why we use test error to tell the full story.

Test error is the error rate the model achieves on examples it has never seen, known as the test data. In order to get test data, we usually split our labeled data into training and test data. For example, if we have 100 labeled emails from our previous intern, then 80 of them would be used for training and 20 for testing. Since the model has never seen the 20 emails, we can use them to predict how well it would do on future emails. As you might've guessed, the test error is the most important measurement.

We can choose the right value for k by graphing both the training and test error rates for each k value. As mentioned earlier, the training error is at 0% when k = 1 because the model just looks up the answers to the training examples since it has already stored them. However, the training error rate slowly rises as k increases because we are now asking the closest neighbors for input instead of just copying the answer from the same example.

Test error starts high because we are literally just copying the closest example to new data that we've never seen before. For k = 1, the model just looks at the most similar email and copies the answer, which means it also copies the mistakes and flukes from the complex data. However, once we start asking the nearest neighbors for their input as well, the error rate for our test data slowly decreases. But once the k value increases past a certain threshold, we start asking too many neighbors for their input and soon the answer just becomes the most common label, which raises the test error rate once again.

Our voting method is fairly simple since it treats neighbors at distance 1 and distance 4 as equals, so they both get 1 vote each. However, if you want closer neighbors to have more influence, we can weight each vote by 1 / distance. This means that a neighbor at distance 1 (with a weighted vote of 1) counts four times as much as a neighbor at distance 4, which now has a weighted vote of 1 / 4.

Again, these equations look scary, but they are very simple once you understand what the terms are. The first equation is just defining the weight $w_i$. We are essentially saying that weight is just 1 divided by the distance to a neighbor, so the weight gets bigger if the neighbor is closer. The second equation is the same voting formula from earlier but this time we are adding the weight $w_i$ instead of just adding 1 for each neighbor. For example, a neighbor with distance 3 will add 1 / 3 while a neighbor with distance 1 will add one whole vote. The $\operatorname*{arg\,max}$ is doing the same job of choosing the label with the largest total and returning our final prediction $\hat{y}$.

Exhausted from your ML summer internship, you try some archery in your downtime and realize you're actually a very good shot. In perfect conditions, you are able to hit a bullseye almost every time. As you get tired, your arm starts shaking and your shots become more spread out and scatter further away from the bullseye. This would be an example of variance, which measures how much your shots jump around or scatter. High variance implies that you're still aiming at the bullseye, but now your shots aren't closely clustered together. If you took enough shots and averaged them, you could technically cancel the variance out.

After a quick break to give your arm a rest, the wind starts picking up. You aim at the center of the target once again, but now your arrows constantly shift to the right. All your shots are clustered together, but they are no longer near the center and instead sit off to the right side. This is an example of bias, which measures how far off you are even after you average all of your shots. High bias implies there is some kind of offset, where even after taking a million shots and averaging them out, you are still clearly wrong by a certain amount.

Inspired by your insights in archery, you try to measure bias and variance in your own algorithms. At your ML internship, you get a fresh batch of training emails every single day. They all come from the same source, but they are different specific emails (the data isn't identical but it's relatively similar). You decide to choose a special email with 4 links and 3 exclamation marks (4, 3) to measure your algorithm. Every day, you build a new k-NN model using the new batch of emails as training data, then use that model to label your special email. Put simply, you have a lot of predictions for your one special email, one prediction per batch.

Now notice the relationship your predictions have with the k value. When k = 1, your prediction for (4, 3) depends entirely on the email that is the closest. If you swap Monday's batch of emails with Tuesday's, the closest email can change, so your prediction can switch from spam to not spam. This is an example of high variance in your algorithm, which is not great. However, if we take the average over many batches, copying the closest point actually tracks the border between spam and not spam, so the bias is low.

If we set the k value extremely high, the prediction is always just going to be the most common label. That most likely does not change from Monday to Tuesday, so the variance is extremely small. However, the algorithm ignores email (4, 3) and its surrounding neighbors, which means it's wrong for every email on every batch. We would say that this algorithm has low variance but high bias since its prediction doesn't switch a lot but is consistently wrong.

The bias-variance tradeoff is basically an equation. The mistakes the model makes on new data come from both variance and bias added together, but they have a give-and-take relationship:

Your only control is the k value, and that drives variance and bias in opposite directions. If you decrease k, you're lowering bias but adding variance. Increasing your k value will introduce bias but decrease variance. You can't bring them both down to zero by just controlling this single parameter, so you have to find the k value where the error is the smallest. If we take a look at the graph from earlier, you can see that variance is actually what's causing the error on the left of the optimal k value since we are overfitting. The error starts increasing again on the right side because we start underfitting the data as the k value increases.

If we take a look at the distance formula from earlier, you can see that every feature basically gets treated the same way. This is actually not great for us since the formula doesn't really understand that numerical values for square feet will be inherently larger than the number of bedrooms. If we treat these categories of numbers the same, then the feature with larger numbers will have far too much influence, essentially ignoring the feature with smaller numbers.

Feature scaling, as the name suggests, helps resize the values in our features so they are all in a similar range before we start processing them for machine learning purposes (this isn't just for k-NN). There are a lot of feature scaling techniques, and they each have their own reasons to be utilized based on your data. I'll cover some popular ones that I find great for k-NN.

The simplest feature scaling method is min-max scaling. For each feature, we simply find its smallest (min) and largest (max) values within our training data. The minimum value will be placed at 0 while the largest will be placed at 1, meaning the rest of the data will fall in between 0 and 1:

Pretty simple! $x$ represents one of the values in the feature that we run through our min-max scaling. We simply subtract the minimum value we found in the data from our $x$ value to ensure that the lowest possible value is just going to be 0. The result then gets divided by the difference of the maximum and minimum values, $\text{max} - \text{min}$, so we can ensure that even the largest values can be squeezed within 1. This ensures that all values, no matter how small or large, will be between 0 and 1.

The next common choice is called standardizing. This requires finding the mean $\mu$ value, or the average, of the feature first. We will use the mean $\mu$ to find the standard deviation, or how far a value is from the mean, using the following equations:

These equations are slightly more complex than the ones we saw for min-max scaling, but once you understand the general gist you won't forget it. To calculate the standard deviation $\sigma$, we subtract the mean from every value in the feature. Since some values can now become negative, we square all the values because we only care about how far away they are from the mean. Now, we can take the average of our squared values, but our units are now also squared from our previous step. For example, if our units at the beginning were square feet for houses, we now have squared square feet, which is confusing, so we take the square root of our values to undo the previous squaring.

The second equation is responsible for standardizing. We are simply going to subtract the mean from our values to ensure that values close to the average are basically 0. The difference then gets divided by the standard deviation $\sigma$ that we just calculated to measure how far away the value is from the mean. This means that average values are incredibly small or near-zero, while outliers are much larger, usually closer to -2 or 2.

As mentioned earlier, each scaling method has its reason to be picked depending on your data. If you know the range of your data, then min-max will work incredibly well. For example, if you are building a machine learning model for hardware, then an analog sensor read through an Arduino's 10-bit converter will always land within 0 to 1023. However, if you can't conclude the range for your data, then standardizing is a good default since outliers can really mess with min-max's simple formula.

A quick heads up: make sure to apply the same min and max (or mean and standard deviation) from the training data to every new example that you want to predict. Don't recalculate these values for the new data because that will produce values that the current model won't understand.

For k-NN algorithms, training doesn't cost anything, but prediction is where all the effort happens. Every time we want to predict a label for a new example, we have to compute the distance to every one of the n stored examples, and each of their d features. This means the Big-O time complexity is O(n × d) per prediction. If we dig deeper, then we have to also consider that sorting all n distances adds O(n log n), or if we use a heap to track the k best, then we can get it down to O(n log k).

There are certain data structures that are very helpful here, and they use trees to organize the stored points so our algorithm can actually efficiently skip a lot of them. The most common tree structure for this is called a KD-tree. They are good when the number of features d is small (under 20), but the complexity catches up and it stops helping as it grows. Fun Fact! scikit-learn's docs say that KD-tree operations are about O(d log n) when we have below 20 dimensions, but then it becomes O(n × d) again once it goes over that value.

If this was perfect, my friend, we wouldn't have another 33 pages of machine learning content. When we have a lot of features, points start becoming so far apart that voting actually starts being random. Imagine our data is perfectly scattered on a chart (like you might've seen earlier), and we want to draw a box around one of our points so that it captures 1% of our data, so we can look at its neighbors. How wide does the box have to be to contain 1% of the data? We can actually calculate this pretty quickly with a simple equation:

We are essentially calculating the volume of the box. If we draw a box in $d$ dimensions with side $s$, we can calculate the volume with $s^d$. Assuming the data is spread evenly, to hold a fraction $f$ of the data, we will need a box with side $s = f^{1/d}$.

Unfortunately, even with 100 features the box has to be nearly 95% of the full range on every axis to just contain 1% of the data. I wish I could show you a visualization, but again, each feature gets its own axis, meaning we are dealing with a shape in the 100th dimension. All of the points are so incredibly far apart that asking for a neighbor's vote is the equivalent of asking random points. This is the full extent of the curse of dimensionality, and the only solution is to keep the number of features small by either compressing them or just being smarter about which ones to keep.

Cover and Hart proved in 1967 that if you train with enough data, a simple 1-NN makes at most twice as many mistakes as the best model that could ever exist. Imagine that $R^*$ is the error rate for the best classifier, also known as the Bayes error, and $R_1$ is the error rate of our 1-NN with unlimited data. We can rewrite this as an incredible equation:

Stone showed in 1977 that k-NN can actually do even better and compete with the best possible classifier as long as you make certain changes as the data grows. You have to first keep including more neighbors in your votes so their average actually cancels out the noise. Then you can grow k slower than the data so those neighbors continue to stay nearby. For example, a common choice is $k = \sqrt{n}$, where we check 10 neighbors at 100 examples and 1,000 neighbors at a million. The percentage of the data we check actually goes from 10% to 0.1%. If we follow these changes to k as the data grows, then the error rate can mathematically be the best it can ever be:

Before we wrap this up, make sure you understand why training error is 0 when k = 1, and why we need to feature scale to ensure that our k-NN algorithms work. Over the years, I've also collected these best practices and tips & tricks to ensure you don't make small mistakes that can ruin your machine learning fun: