What is the K Nearest Neighbor Algorithm?

The articles written on this blog were created with the goal of teaching. Also, the information in the article may be incorrect, so please be careful.

K-Nearest Neighbors, or KNN for short, is an algorithm that determines the result by finding the K pieces of data that are closest to new data. In Korean, it is called the K nearest neighbor algorithm.

Follow the majority around you

Let's say we already have weight and color data for apples and oranges. When a new fruit comes in, the closest fruits are found among the existing data.

5 new fruits nearby
4 apples
1 orange

Predicted result: apple

Here, if K is 5, check 5 nearby pieces of data. In classification problems, you can select the class with the largest number of classes, and in regression problems, you can use the average of close values.

Closer to search than learning

KNN rarely requires the process of creating complex models in advance. The training data is kept as is and the distance to new data is calculated each time a prediction is made.

Learning phase: Save the data.
Prediction step: Calculate all data and distances.

So the implementation is simple, but the more data there is, the slower the prediction becomes. If there are N data and D features, a simple implementation would need to calculate approximately N distances during one prediction.

The value of K changes the result

If K is 1, only the closest data is trusted. Even small noise can easily change the results.

If K is too large, local features are lost, including distant data. If two classes exist in similar numbers, odd numbers may be selected to reduce ties, but odd numbers are not always the correct answer.

The core of KNN is the assumption that nearby data have similar properties. Therefore, it is a good algorithm to test first in problems where the meaning of distance is clear and the size of the data is not excessively large.