Distance calculation and normalization in KNN

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.

KNN is an algorithm for finding close neighbors. Therefore, the Distance Metric, which determines what is considered close, determines the result.

Euclidean distance

The straight line distance between two points in two-dimensional coordinates is as follows.

d = sqrt((x2 - x1)^2 + (y2 - y1)^2)

float EuclideanDistance(float X1, float Y1, float X2, float Y2)
{
    const float DX = X2 - X1;
    const float DY = Y2 - Y1;
    return std::sqrt(DX * DX + DY * DY);
}

This is natural when actual straight-line distance is important in the game world. However, the square root is applied equally to all distances, so if you are just making a simple comparison, the order is the same even if you only use the square distance.

manhattan streets

Manhattan distance adds up the differences on each axis.

d = |x2 - x1| + |y2 - y1|

It is well suited to problems that move along an axis, such as a grid that cannot be moved diagonally. The cost of the actual path with hexagons or obstacles requires separate rules, so you should not just rely on the coordinate distance.

Why we need normalization

Let's say the character data is level 1~10 and gold holding is 0~100000. If you put the two values ​​directly into the distance calculation, the gold difference almost covers the level difference.

Before normalization
Level difference: 3
Gold difference: 20000

Gold determines most of the distance

Min-Max normalization shifts the values ​​between 0 and 1.

normalized = (value - min) / (max - min)

You should also consider how much influence each feature should have on the results. More weight can be given to important features, but the weight must also be confirmed with verification data.

In KNN, distance calculation is not a subfunction. If you ignore the units of data and the movement rules of the problem, you will not be able to find good neighbors no matter how much you adjust the K value.