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.