Cálculo de distancia y normalización en KNN.

Los artículos escritos en este blog fueron creados con el objetivo de enseñar. Además, la información del artículo puede ser incorrecta, así que tenga cuidado.

KNN es un algoritmo para encontrar vecinos cercanos. Por tanto, la Métrica de Distancia, que determina lo que se considera cercano, determina el resultado.

distancia euclidiana

La distancia en línea recta entre dos puntos en coordenadas bidimensionales es la siguiente.

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

Esto es natural cuando la distancia real en línea recta es importante en el mundo del juego. Sin embargo, la raíz cuadrada se aplica por igual a todas las distancias, por lo que si solo estás haciendo una comparación simple, el orden es el mismo incluso si solo usas la distancia al cuadrado.

calles de manhattan

La distancia de Manhattan suma las diferencias en cada eje.

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

Es muy adecuado para problemas que se mueven a lo largo de un eje, como una cuadrícula que no se puede mover en diagonal. El coste del camino real con hexágonos u obstáculos requiere reglas separadas, por lo que no debes confiar solo en la distancia de coordenadas.

Por qué necesitamos la normalización

Digamos que los datos del personaje son de nivel 1 ~ 10 y la tenencia de oro es de 0 ~ 100000. Si pones los dos valores directamente en el cálculo de la distancia, la diferencia de oro casi cubre la diferencia de nivel.

Antes de la normalización
Diferencia de nivel: 3
Diferencia de oro: 20000

El oro determina la mayor parte de la distancia.

La normalización Min-Max cambia los valores entre 0 y 1.

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

También debes considerar cuánta influencia debería tener cada característica en los resultados. Se puede dar más peso a las características importantes, pero el peso también debe confirmarse con datos de verificación.

En KNN, el cálculo de la distancia no es una subfunción. Si ignora las unidades de datos y las reglas de movimiento del problema, no podrá encontrar buenos vecinos por mucho que ajuste el valor de K.