Entfernungsberechnung und Normalisierung in KNN

Die in diesem Blog verfassten Artikel wurden mit dem Ziel erstellt, zu unterrichten. Außerdem können die Informationen im Artikel falsch sein, also seien Sie bitte vorsichtig.

KNN ist ein Algorithmus zum Finden enger Nachbarn. Daher bestimmt die Distanzmetrik, die bestimmt, was als nah gilt, das Ergebnis.

Euklidischer Abstand

Der geradlinige Abstand zwischen zwei Punkten in zweidimensionalen Koordinaten ist wie folgt.

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

Dies ist natürlich, wenn in der Spielwelt die tatsächliche geradlinige Entfernung wichtig ist. Allerdings wird die Quadratwurzel gleichermaßen auf alle Abstände angewendet. Wenn Sie also nur einen einfachen Vergleich durchführen, ist die Reihenfolge dieselbe, auch wenn Sie nur den Quadratabstand verwenden.

Manhattan Straßen

Die Manhattan-Distanz addiert die Unterschiede auf jeder Achse.

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

Es eignet sich gut für Probleme, die sich entlang einer Achse bewegen, beispielsweise ein Gitter, das nicht diagonal verschoben werden kann. Die Kosten für den tatsächlichen Weg mit Sechsecken oder Hindernissen erfordern gesonderte Regeln, Sie sollten sich also nicht nur auf den Koordinatenabstand verlassen.

Warum wir Normalisierung brauchen

Nehmen wir an, die Charakterdaten liegen auf Stufe 1–10 und der Goldbestand beträgt 0–100.000. Setzt man die beiden Werte direkt in die Distanzberechnung ein, deckt der Goldunterschied fast den Pegelunterschied ab.

Vor der Normalisierung
Niveauunterschied: 3
Golddifferenz: 20000

Gold bestimmt den größten Teil der Distanz

Durch die Min-Max-Normalisierung werden die Werte zwischen 0 und 1 verschoben.

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

Sie sollten auch überlegen, wie viel Einfluss jedes Feature auf die Ergebnisse haben soll. Wichtigen Merkmalen kann mehr Gewicht beigemessen werden, allerdings muss das Gewicht auch durch Verifizierungsdaten bestätigt werden.

In KNN ist die Entfernungsberechnung keine Unterfunktion. Wenn Sie die Dateneinheiten und Bewegungsregeln des Problems ignorieren, können Sie keine guten Nachbarn finden, egal wie stark Sie den K-Wert anpassen.