KNNの距離計算と正規化

本ブログ作成文は、講義を目指して製作されました。 また、作成された文章の情報も間違っている可能性がありますので、ご注意ください。

KNNは近い隣人を見つけるアルゴリズムです。 したがって、何に近いと思うかを決めるDistance Metric（距離尺度）が結果を左右する。

ユークリッド通り

２次元座標における２点間の直線距離は次の通りである。

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

通りの大部分を金が決める

Min-Max正規化は値を0と1の間で変更します。

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

各特徴が結果にどの程度影響を与えるべきか考えるべきである。 重要な特徴には重みをさらに与えることができるが、重みも検証データで確認しなければならない。

KNNでは、距離計算は付属機能ではありません。 データの単位と問題の移動規則を無視すると、K値をいくら調整しても良い隣人が見つかりません。