K-최근접 이웃(K-Nearest Neighbors, KNN) 알고리즘은 클래스 소속 여부(Y)와 예측 변수 X1, X2, …, Xn 사이의 관계 구조에 대해 어떠한 가정도 하지 않는 분류 기법입니다.
KNN은 비모수적(nonparametric) 접근법
KNN은 선형 회귀에서처럼 특정 함수 형태를 미리 가정하고 그 안에서 매개변수를 추정하는 방식이 아니기 때문에 비모수적(nonparametric) 방법으로 분류됩니다. 대신 이 알고리즘은 데이터셋 내 예측 변수 값들 간의 유사성(similarity)을 기반으로 작동합니다.
KNN의 핵심 아이디어는 다음과 같습니다. 분류해야 할 새로운 데이터가 주어졌을 때, 훈련 데이터셋에서 이 새 데이터와 가장 유사한 k개의 레코드(이웃)를 찾아냅니다. 그런 다음 이 이웃 레코드들이 속한 클래스를 참고하여, 새 데이터를 이웃들 중 가장 많이 나타나는 클래스(다수결)로 할당하는 것입니다. 이때 새 레코드의 예측 변수 값을 X1, X2, …, Xn이라고 표기합니다.
거리 측정: 유클리드 거리(Euclidean Distance)
KNN에서 가장 중요한 질문 중 하나는 예측 변수 값을 기준으로 두 데이터 사이의 거리를 어떻게 계산할 것인가입니다. 가장 널리 알려진 거리 척도는 유클리드 거리(Euclidean distance)입니다. 두 레코드 (X1, X2, …, Xn)와 (U1, U2, …, Un) 사이의 유클리드 거리는 다음과 같이 정의됩니다.
$$\mathrm{\sqrt{(X_1-U_1)^2+(X_2-U_2)^2+...+(X_n-U_n)^2}}$$
KNN 알고리즘은 분류 대상 데이터 하나하나와 훈련 집합의 모든 데이터 사이에서 수많은 거리 계산을 반복해야 합니다. 따라서 계산 비용이 낮은 유클리드 거리가 KNN에서 가장 인기 있는 거리 척도로 자리 잡았습니다.
변수 표준화(Standardization)가 필요한 이유
각 예측 변수는 서로 다른 스케일을 가질 수 있습니다. 예를 들어 '연봉'은 수천만 원 단위인 반면 '나이'는 몇십 단위일 수 있죠. 이런 경우 스케일이 큰 변수가 거리 계산을 지배하게 되므로, 유클리드 거리를 계산하기 전에 대부분의 경우 예측 변수를 표준화해야 합니다.
여기서 중요한 점은, 새로운 데이터를 표준화할 때 사용하는 평균과 표준편차는 훈련 데이터에서 계산된 값이어야 한다는 것입니다. 새로운 데이터나 검증(validation) 데이터는 이 통계량 계산에 포함되어서는 안 됩니다. 이는 모델이 실제 예측 상황에서 본 적 없는 데이터를 다루는 것과 동일한 조건을 유지하기 위함입니다.
분류 규칙과 k값의 역할
분류 대상 데이터와 기존 레코드들 사이의 거리를 모두 계산했다면, 이제 이웃들의 클래스 정보를 바탕으로 새 레코드에 클래스를 부여하는 분류 규칙이 필요합니다.
가장 단순한 경우는 k = 1일 때입니다. 이 경우 가장 가까운 데이터(최근접 이웃) 하나만을 찾아, 새 데이터를 그 이웃과 같은 클래스로 분류합니다.
단순하지만 강력한 1-최근접 이웃
흥미롭게도 이렇게 단순하고 직관적인 아이디어—단 하나의 최근접 이웃만으로 레코드를 분류하는 방식—는 훈련 데이터가 충분히 많을 때 상당히 강력한 성능을 보여줍니다.
실제로 1-최근접 이웃 분류기의 오분류 오차는, 각 클래스의 확률 밀도 함수를 정확히 알고 있다고 가정할 때 얻을 수 있는 최적의 오분류율(베이즈 오류율)의 2배를 넘지 않는다고 알려져 있습니다. 즉, 아무런 모델 가정 없이 단순히 '가장 가까운 이웃을 따른다'는 원리만으로도 이론적 최적 성능에 근접할 수 있는 것이 KNN의 큰 매력입니다.