KNN中的距离计算和归一化

该博客上撰写的文章是出于教学目的而创建的。 另外，文章中的信息可能不正确，请谨慎。

KNN 是一种寻找近邻的算法。 因此，距离度量决定了什么被认为是接近的，从而决定了结果。

欧氏距离

二维坐标中两点之间的直线距离如下。

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);
}

当实际直线距离在游戏世界中很重要时，这是很自然的。 但是，平方根同样适用于所有距离，因此如果您只是进行简单比较，即使仅使用平方距离，顺序也是相同的。

曼哈顿街道

曼哈顿距离将每个轴上的差异相加。

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

它非常适合沿轴移动的问题，例如不能沿对角线移动的网格。 具有六边形或障碍物的实际路径的成本需要单独的规则，因此您不应仅依赖于坐标距离。

为什么我们需要标准化

假设角色数据为1~10级，金币持有量为0~100000。 如果将这两个值直接放入距离计算的话，金币差异几乎覆盖了等级差异。

正常化前
等级差：3
金币差价：20000

黄金决定大部分距离

最小-最大归一化将值在 0 和 1 之间移动。

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

您还应该考虑每个特征对结果的影响有多大。 重要的特征可以给予更多的权重，但权重也必须通过验证数据来确认。

在KNN中，距离计算不是子函数。 如果忽略数据的单位和问题的移动规则，无论调整多少K值，都无法找到好邻居。