K-최근접 이웃 (K-NN)

K-최근접 이웃 알고리즘의 핵심은 새로운 데이터 포인트와 학습 데이터 내 다른 포인트들 사이의 '거리'를 계산하여 가장 가까운 이웃을 찾는 것이다. 이때 사용되는 거리 측정 방법은 알고리즘의 성능에 직접적인 영향을 미친다. 가장 일반적으로 사용되는 거리는 유클리드 거리이다. 이는 우리가 일상적으로 생각하는 직선 거리로, 2차원 공간에서는 피타고라스 정리를 통해 계산된다. n차원 공간에서 두 점 A(x₁, x₂, ..., xₙ)와 B(y₁, y₂, ..., yₙ) 사이의 유클리드 거리는 √((x₁-y₁)² + (x₂-y₂)² + ... + (xₙ-yₙ)²) 공식으로 구한다.

다른 중요한 거리 측정법으로는 맨해튼 거리가 있다. 이는 격자 모양의 도시에서 블록을 따라 걸을 때의 거리와 유사하여 택시 거리라고도 불린다. 계산 공식은 |x₁-y₁| + |x₂-y₂| + ... + |xₙ-yₙ| 이다. 유클리드 거리가 대각선 이동을 허용한다면, 맨해튼 거리는 좌표축 방향으로만 이동한 거리의 합이다. 이는 특성들이 독립적으로 작용하는 경우에 유용할 수 있다. 더 일반화된 형태로 민코프스키 거리가 있으며, 이는 유클리드 거리와 맨해튼 거리를 하나의 공식으로 통합한다.

분류 문제에서 범주형 데이터를 다룰 때는 해밍 거리가 자주 사용된다. 이는 두 문자열이나 범주형 벡터가 서로 다른 위치의 개수를 세는 방식으로 거리를 측정한다. 예를 들어, 'apple'과 'apply'의 해밍 거리는 마지막 문자만 다르므로 1이다. 또한, 고차원 데이터나 특성의 스케일이 매우 다를 경우에는 코사인 유사도를 거리 대신 사용하기도 한다. 코사인 유사도는 두 벡터 간의 각도의 코사인 값을 계산하여 방향의 유사성을 측정하며, 문서 간 유사도 분석 등에 널리 적용된다[1].

적절한 거리 측정 방법을 선택하는 것은 문제의 도메인과 데이터의 특성에 달려 있다. 모든 특성의 스케일이 동일하지 않다면, 거리 계산에 앞서 표준화나 정규화를 수행하는 것이 필수적이다. 그렇지 않으면 스케일이 큰 특성이 거리 계산을 지배하게 되어 알고리즘의 성능이 저하된다.

K 값은 K-최근접 이웃 알고리즘의 핵심 하이퍼파라미터로, 분류 또는 회귀를 수행할 때 참고할 가장 가까운 이웃 데이터 포인트의 수를 결정한다. K 값의 선택은 모델의 복잡도와 일반화 성능에 직접적인 영향을 미친다. 너무 작은 K 값(예: K=1)을 선택하면 모델은 훈련 데이터의 지역적 특성과 노이즈에 지나치게 민감해져 과적합이 발생할 수 있다. 반대로, 너무 큰 K 값(예: K=전체 데이터 수)을 선택하면 결정 경계가 과도하게 평탄해져 중요한 패턴을 놓칠 수 있으며, 이는 과소적합으로 이어질 수 있다.

적절한 K 값을 선택하기 위한 일반적인 방법은 교차 검증을 사용하는 것이다. 가장 널리 쓰이는 방법은 k-겹 교차 검증으로, 훈련 데이터를 여러 부분으로 나누어 다양한 K 값에 대해 모델의 성능을 평가하고, 평균 검증 오차가 가장 낮은 K 값을 선택한다. K 값에 따른 모델 성능 변화를 시각적으로 확인하기 위해 아래와 같은 표를 활용할 수 있다.

K 값 선택 시 고려해야 할 다른 요소로는 데이터셋의 크기와 클래스 불균형이 있다. 데이터 포인트 수가 매우 적을 때는 작은 K 값이, 매우 많을 때는 상대적으로 큰 K 값이 적합할 수 있다. 또한, 데이터의 특성 공간 차원이 높을수록 차원의 저주 현상으로 인해 적절한 K 값을 찾기가 더 어려워진다. 이 경우, K 값을 선택하기 전에 차원 축소 기법을 적용하는 것이 도움이 될 수 있다.

K-최근접 이웃 알고리즘의 학습 단계는 다른 많은 지도 학습 모델과는 달리 명시적인 모델을 구축하지 않는다. 이 단계는 단순히 훈련 데이터 세트를 메모리에 저장하는 과정으로 이루어진다. 모든 특징 벡터와 그에 대응하는 레이블이 그대로 보존되어, 이후 예측 단계에서 참조할 수 있는 준비를 마친다.

이러한 방식을 게으른 학습 또는 사례 기반 학습이라고 부른다. 알고리즘이 훈련 데이터로부터 일반화된 패턴이나 함수를 추출하여 모델 파라미터를 학습하는 대신, 원본 데이터 자체를 지식으로 삼는다. 따라서 학습 과정의 계산 비용은 매우 낮으며, 기본적으로는 데이터 저장 작업에 불과하다.

학습 단계에서 수행될 수 있는 유일한 전처리 작업은 데이터 정규화나 표준화이다. K-NN이 유클리드 거리와 같은 거리 기반 측정을 사용하기 때문에, 특성들의 스케일이 다르면 특정 특성이 거리 계산에 과도하게 영향을 미칠 수 있다. 이를 방지하기 위해 모든 특성을 동일한 스케일로 조정하는 작업이 종종 선행된다. 그러나 이 작업 자체가 모델을 학습하는 것은 아니며, 단지 예측의 정확도를 높이기 위한 데이터 준비 과정에 해당한다.

K-최근접 이웃 알고리즘의 예측 단계는 새로운 데이터 포인트의 클래스 또는 값을 결정하는 과정이다. 이 단계는 학습 단계에서 저장된 모든 데이터를 기반으로 수행된다.

먼저, 분류 문제의 경우, 새로운 데이터 포인트와 학습 데이터셋 내 모든 점 사이의 거리를 계산한다. 가장 일반적으로 사용되는 거리는 유클리드 거리이다. 계산된 거리를 기준으로 가장 가까운 K개의 이웃을 선택한다. 최종적으로는 이 K개의 이웃 중에서 다수결 투표를 통해 가장 빈번하게 등장하는 클래스를 새로운 데이터 포인트의 예측 클래스로 할당한다. 만약 회귀 문제라면, 선택된 K개의 이웃의 목표 변수 값들의 평균을 계산하여 예측값으로 사용한다.

K 값의 선택은 예측 결과에 직접적인 영향을 미친다. K 값이 너무 작으면(예: K=1) 과적합에 취약해져 데이터의 지역적 노이즈나 이상치에 민감해진다. 반대로 K 값이 너무 크면 과소적합될 수 있으며, 결정 경계가 과도하게 평탄해져 분류 정확도가 떨어질 수 있다. 적절한 K 값은 일반적으로 교차 검증을 통해 결정한다.

예측 단계는 모든 학습 데이터에 대한 거리 계산이 필요하므로, 데이터셋의 크기가 커질수록 계산 비용이 크게 증가한다는 단점이 있다. 이를 완화하기 위해 KD-트리나 볼 트리와 같은 공간 분할 자료구조를 활용하여 최근접 이웃 탐색 효율을 높이는 방법이 사용된다.

K-최근접 이웃 알고리즘의 가장 큰 장점은 구현이 단순하고 직관적이라는 점이다. 알고리즘의 기본 개념은 새로운 데이터 포인트 주변의 가장 가까운 이웃들을 찾아 그들의 레이블을 기반으로 분류하거나 값을 예측하는 것이며, 이는 수학적 배경이 부족해도 쉽게 이해할 수 있다. 또한, 명시적인 모델 학습 단계가 존재하지 않는다[3]. 새로운 데이터에 대한 예측이 필요할 때까지 실제 계산을 미루기 때문에 학습 과정이 빠르다는 특징도 있다.

이 알고리즘은 비모수적 방법에 속한다. 즉, 데이터의 기본 분포에 대한 강한 가정을 하지 않으며, 데이터 자체의 패턴에 의존하여 결정을 내린다. 이로 인해 복잡한 결정 경계를 가진 문제에도 유연하게 적용될 수 있다. 특히, 결정 경계가 비선형적인 경우에도 효과적으로 대응할 수 있다는 점이 큰 강점이다.

다른 장점으로는 새로운 학습 데이터가 추가될 때 모델을 처음부터 다시 구축할 필요가 없다는 점을 들 수 있다. 기존의 저장된 데이터에 새로운 데이터를 추가하기만 하면 되므로, 증분 학습이 자연스럽게 가능하다. 또한, 다중 클래스 분류 문제에 별도의 수정 없이 적용할 수 있는 범용성을 지닌다.

K-최근접 이웃 알고리즘은 계산 비용이 매우 높은 편이다. 모든 예측 시점에 전체 훈련 데이터에 대해 거리를 계산하고 정렬해야 하므로, 데이터셋의 크기가 커질수록 예측 속도가 현저히 느려진다. 이는 실시간 응용 프로그램에는 적합하지 않을 수 있다.

이 알고리즘은 차원의 저주에 취약하다. 입력 특성(차원)의 수가 증가하면, 데이터 포인트 간의 거리가 점점 비슷해져서 유의미한 이웃을 찾기 어려워진다. 결과적으로 성능이 저하되며, 고차원 데이터에서는 사전에 차원 축소 기법을 적용해야 하는 경우가 많다.

데이터의 불균형이 심할 경우, 다수 클래스에 편향된 예측을 할 위험이 있다. 또한, 모든 특성이 동등하게 취급되기 때문에, 예측에 중요한 특성과 불필요한 특성을 구분하지 못한다. 적절한 특성 스케일링과 가중치 부여가 필요하다.

가중 K-NN은 표준 K-최근접 이웃 알고리즘의 한계를 보완하기 위해 도입된 변형 기법이다. 표준 K-NN은 가장 가까운 K개의 이웃을 찾은 후, 다수결 투표나 평균을 통해 예측을 수행한다. 이 과정에서 모든 이웃이 동일한 중요도(가중치)를 가지게 된다. 그러나 실제로는 거리가 다른 이웃들이 예측에 미치는 영향이 동일하지 않을 수 있다. 가까운 이웃일수록 더 신뢰할 수 있고, 먼 이웃일수록 노이즈나 관련성이 낮은 정보를 제공할 가능성이 높다. 가중 K-NN은 이러한 직관을 반영하여, 각 이웃 표본에 거리에 반비례하는 가중치를 부여함으로써 예측의 정확도를 향상시키려는 접근법이다.

가중치를 부여하는 가장 일반적인 방법은 역거리 가중치를 사용하는 것이다. 이 방법에서는 각 이웃의 투표나 기여도에 (1 / d) 또는 (1 / d²)와 같은 가중치를 곱한다. 여기서 d는 분류 또는 회귀를 수행하려는 질의 점수와 해당 이웃 사이의 거리이다. 예를 들어, 분류 문제에서는 각 클래스별로 가중치를 합산한 후, 가중 합이 가장 큰 클래스를 예측 결과로 선택한다. 회귀 문제에서는 이웃들의 목표값에 가중치를 곱한 가중 평균을 계산하여 예측값을 도출한다. 이를 통해 매우 가까운 이웃 하나의 강한 의견이 여러 먼 이웃들의 약한 의견을 압도하는 것을 방지하면서도, 가까운 이웃의 영향력을 적절히 반영할 수 있다.

가중치 함수는 응용 분야와 데이터 특성에 따라 다양하게 선택될 수 있다. 역거리 가중치 외에도, 가우시안 커널을 기반으로 한 가중치나 사용자가 정의한 커널 함수를 사용하기도 한다. 표로 정리하면 다음과 같다.

이 기법은 특히 데이터의 분포가 불균일하거나 노이즈가 있을 때 유용하다. 그러나 모든 이웃까지의 거리를 계산해야 하므로 기본 알고리즘보다 계산 오버헤드가 약간 증가할 수 있으며, 최적의 가중치 함수와 매개변수를 선택하는 추가적인 고려가 필요하다는 단점도 있다.

K-최근접 이웃 알고리즘은 고차원 데이터에서 성능이 저하되는 차원의 저주 문제에 취약하다. 고차원 공간에서는 모든 데이터 포인트 간의 거리가 비슷해져 유의미한 이웃을 찾기 어려워지고, 계산 비용도 크게 증가한다. 이를 완화하기 위해 주성분 분석이나 t-SNE, UMAP 등의 차원 축소 기법을 사전에 적용하는 방법이 널리 사용된다.

차원 축소는 원본 데이터의 정보를 최대한 보존하면서 특징(feature)의 수를 줄이는 과정이다. 예를 들어, 주성분 분석은 데이터의 분산을 최대화하는 새로운 직교 축을 찾아 저차원 공간으로 투영한다. 이를 통해 노이즈를 제거하고 주요 패턴을 강조할 수 있어, K-NN의 분류 정확도를 향상시키고 계산 효율성을 높이는 데 기여한다.

다음은 주요 차원 축소 기법과 K-NN에 적용 시의 고려사항을 정리한 표이다.

차원 축소를 적용할 때는 정보 손실과 계산 비용 간의 트레이드오프를 고려해야 한다. 과도하게 차원을 줄이면 원본 데이터의 중요한 패턴이 사라져 오히려 성능이 떨어질 수 있다. 따라서 교차 검증 등을 통해 최적의 축소 차원 수를 결정하는 것이 중요하다.