K-Nearest Neighbors

What Is KNN?

There is a saying that you become the average of the five people you surround yourself with. This is the main idea behind K-nearest neighbors (KNN).

KNN is a supervised learning algorithm that makes predictions based on the closest data points. It can be used for both classification and regression, and it has no training phase.

In other words: tell me who your neighbors are, and I will tell you what you are.

KNN for Classification

KNN classifies a point by a majority vote of its K nearest neighbors.

Suppose we have a labeled dataset with points from class A, class B, and class C, and we get a new data point. If K is 5, we find the five points closest to the new point. Say four of them are from class A and one is from class C. The new point is classified as class A.

The steps are:

1. Choose K, the number of neighbors.
2. For the new point, compute the distance to all the points in the dataset.
3. Pick the K nearest points.
4. Vote for the most common class among them.

KNN for Regression

In regression, the data points are labeled with continuous values instead of classes. The first three steps stay the same, and only the last step changes:

1. Choose K, the number of neighbors.
2. For the new point, compute the distance to all the points in the dataset.
3. Pick the K nearest points.
4. Take the average of their values, and assign it to the new point.

For example, if K is 3, we find the three nearest data points and give the new point the average of their three values.

Measuring Distance

KNN depends on how we measure distance. Common choices include Euclidean, Manhattan, Minkowski, Hamming, and Mahalanobis distance. Different types of datasets call for different metrics.

In each formula below, $a$ and $b$ are two data points. In two dimensions, $a = (a_1, a_2)$ and $b = (b_1, b_2)$. In $d$ dimensions, $a = (a_1, \dots, a_d)$ and $b = (b_1, \dots, b_d)$.

Euclidean Distance

Euclidean distance is the straight-line distance between two points. In two dimensions:

In $d$ dimensions:

Manhattan Distance

Manhattan distance adds up the difference along each axis. In two dimensions:

In $d$ dimensions:

Minkowski Distance

Minkowski distance adds a parameter $p$. In two dimensions:

In $d$ dimensions:

The interesting thing is that this formula includes other distances as special cases:

• If $p = 1$, we get Manhattan distance.
• If $p = 2$, we get Euclidean distance.
• If $p \to \infty$, we get Chebyshev distance.

Cosine Similarity and Distance

Cosine similarity is a different way to compare points. We treat $a$ and $b$ as $d$-dimensional vectors and measure the angle $\theta$ between them. The similarity is:

The distance between the two vectors is then:

Choosing K

The value of K has a big effect on the results:

• If K is too small, the model overfits the data and the output is noisy.
• If K is too large, the model underfits the data and the decision boundary is smoother.

Let's see this with an example with two classes, blue and orange:

• K = 1: We look at only the single nearest point, which is blue, so we assign blue. But we can't be sure of this, since one neighbor is very little evidence.
• K = 5: Among the five nearest points, three are orange and two are blue, so we assign orange.
• K = 25: This is almost the whole dataset. We get 15 blue points and 10 orange points, so we assign blue. But by looking at the plot, we can see that the point should be orange.

When K is large, KNN stops focusing on the local neighborhood. Instead of asking who the closest neighbors are, it asks what the majority of the entire dataset looks like.

Why K Is Often Odd

In classification, we often choose an odd K to avoid ties.

Suppose K is 4 and there are two classes. We could get two neighbors from class A and two from class B. With two votes each, KNN can't decide the class without an extra tie-breaking rule, which introduces bias and randomness.

With K = 5, one of the two classes must get a majority, so a tie can't happen.

Ties are most likely in binary classification, and with two classes, an odd K rules them out completely. Regression doesn't depend on K being odd or even, because it takes an average rather than a vote.

Cross-Validation

The most reliable way to choose K is to experiment using cross-validation. We try multiple values of K, evaluate the performance of each one, and choose the K that gives the highest accuracy or the lowest error.

When Not to Use KNN

The Dataset Is Large

KNN must compute the distance to every data point at prediction time, which makes prediction very slow. The time complexity of a prediction is $O(n \times d)$, where $n$ is the number of samples and $d$ is the number of dimensions.

This makes KNN unsuitable for real-time systems, and it isn't useful when $n$ is large.

The Data Is High-Dimensional

When there are many features, all the points become similarly far apart. Distances lose their meaning, and accuracy drops dramatically. Two points can be the same distance from a new point even though they belong to different classes.

KNN doesn't work well here unless we first reduce the dimensions using PCA or another dimensionality reduction technique.

The Features Are Not Scaled

KNN relies on distance. If one feature dominates, the distances become distorted and the wrong neighbors are selected. Without normalization, KNN becomes unreliable.

The Data Is Noisy or Has Outliers

With noisy data, a small K overfits and a large K underfits, so predictions become unstable.

Suppose we have class A and class B, with a few class A outliers inside the class B region. A new point lands in this region. With K = 5, three of its neighbors are class A outliers and only two are class B. The point looks like it should be class B, but the outliers cause it to be misclassified as class A.

The Classes Are Imbalanced

Suppose 90% of the data is class A and only 10% is class B. The neighbors will usually favor the majority class, so the minority class is rarely predicted correctly.

For a new point, four of the five nearest neighbors might be from class A and only one from class B. Most of the time, KNN simply predicts the majority class.

Memory Is Limited

KNN stores the entire dataset. This makes it memory-heavy and expensive for large datasets, and it isn't ideal for edge devices or other systems where RAM is restricted.

Other Cases

We should also avoid KNN when:

• We need fast predictions.
• We need explainability.
• Distance doesn't capture similarity for the problem.

Advantages

KNN also has real strengths:

• It is simple and intuitive.
• It has no training time, because we only need the labeled dataset and the new data points.
• It works well with small datasets.
• It handles multiclass classification easily.

Summary

The key ideas are:

• KNN predicts from the K closest data points, using a majority vote for classification and an average for regression.
• It relies on a distance metric, such as Euclidean, Manhattan, Minkowski, or cosine distance.
• A small K overfits, a large K underfits, and cross-validation is the most reliable way to choose K.
• An odd K avoids ties in binary classification.
• KNN is simple and needs no training, but it struggles with large, high-dimensional, unscaled, noisy, or imbalanced data.