KNN의 거리 계산과 정규화

본 블로그 작성 글들은, 강의를 목표로 하고 제작되었습니다. 또한 작성된 글의 정보도 틀렸을 수 있으니, 주의해주세요.

KNN은 가까운 이웃을 찾는 알고리즘이다. 그러므로 무엇을 가깝다고 볼 것인지 정하는 Distance Metric(거리 척도)이 결과를 좌우한다.

유클리드 거리

2차원 좌표에서 두 점 사이의 직선거리는 다음과 같다.

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 값을 아무리 조절해도 좋은 이웃을 찾을 수 없다.