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值，都無法找到好鄰居。