K-최근접 이웃(K-Nearest Neighbor; KNN) 알고리즘은 근접한 k개 이웃 데이터를 활용하여 특정 데이터의의 값을 예측한다. 분류와 회귀 문제에 모두 적용 가능하며, 데이터 간 거리를 기반으로 작동하는 비모수(Non-parametric) 모형이다. 아래는 KNN 분류 모형의 예시이다.
위 이미지에서 빨간색 세모는 클래스 A, 파란색 네모가 클래스 B라고 하자. 초록색 동그라미가 검증하려고 하는 대상이다. 동그라미를 중심으로 가장 가까운 3개 데이터 포인트를 살펴보면 클래스 A가 2개 클래스 B가 1개이다. 따라서 k가 3일 때 동그라미는 클래스 A로 분류된다. 그러나 만약 k가 5라면, 클래스 A가 2개 클래스 B가 3개이므로 동그라미는 클래스 B로 분류된다.
어떤 추정 방법이나 통계적 모형, 심지어는 자료 변환도 필요로 하지 않아 매우 간단하다. 데이터만 가지고 학습을 한다는 점에서 게으른(lazy) 학습 또는 사례 기반(instance-based) 학습이라고 한다. 단순한 방법이지만 다른 분류 기법과 비교해 성능이 떨어지지 않는다. 그러나 피처의 개수가 증가하면 문제가 발생하는데, 이를 흔히 ‘차원의 저주’라 한다. 차원의 저주란 차원이 증가할수록 데이터가 매우 희소(sparse)해져, 거리 기반 알고리즘이나 통계적 분석이 어려워지는 현상을 뜻한다.
축의 길이가 1인 d차원 큐브에 균등하게 데이터가 있다고 하자. 이 경우 전체 데이터의 p%를 포함하기 위한 축의 길이는 $(p/100)^{\frac{1}{d}}$로 계산된다. 만약, d=2이고 p=10이면 축의 길이는 $(0.1)^{\frac{1}{2}} \approx 0.32$ 에 해당하지만, d=10이고 p=10이면 축의 길이는 $(0.1)^{0.1} \approx 0.8$ 이다. 다시 말해, 10% 데이터를 표현하기 위해 2차원에서 필요한 축의 길이는 0.32었던 반면, 10차원에서 필요한 축의 길이는 0.8로 크게 증가한다.
거리 기반 알고리즘
KNN은 관측치 간 거리를 기반으로 작동하는 알고리즘이다. 데이터 포인트 간 거리를 계산하여 이웃, 즉 가장 가까운 k개의 점을 찾는다. 주로 유클리드 거리, 맨해튼 거리, 혹은 다른 거리 척도를 사용한다. 따라서 민코프스키(Minkowski) 거리 개념을 활용할 수 있다. 민코프스키 거리는 다양한 거리 척도를 일반화한 형태로, p라는 파라미터를 조정함으로써 다양한 거리 척도를 사용할 수 있다. p=1 이면 맨해튼 거리, p=2 이면 유클리드 거리이다. p가 무한대일 때는 체비셰프 거리가 된다.
$$ d(x_{i}, x_{j}) = \Big(\sum_{k=1}^{d}|x_{ik}-x_{jk}|^p\Big)^{1/p} $$
- 유클리드 거리(Euclidean Distance) : 우리가 흔히 알고 있는, 가장 일반적인 거리 측정 방식이다. 피타고라스의 정리에 기반한 두 점 사이 직선 거리를 의미한다. 데이터가 연속적이고, 차원 간의 거리 차이가 일관된 경우 유용하다.
- 맨해튼 거리(Manhattan Distance) : 두 점 사이의 거리를 각 차원에서의 절대 거리 차이를 합산하여 측정한다. 도시의 거리 지도 같이 그리드 구조일 때 사용한다. Taxicab 거리라고도 한다.
- 체비셰프 거리(Chebyshev Distance) : 두 점 간의 축 방향 거리 차이 중 최대값을 측정한다. 체스 게임에서 왕이 한 점에서 다른 점으로 이동할 때 필요한 최소 이동 횟수와 같다는 점에서 체스판 거리(Chessboard distance)라고도 한다.
최적의 k 선택
최근접 이웃의 수, 즉 k가 클수록 모델은 단순해지고 훈련 데이터 정확도는 줄어든다. 반면 k가 지나치게 작은 경우에는 복잡도가 증가해 훈련 데이터에 과적합(Overfitting)될 가능성이 높다. 극단적인 예로 k가 1이면, 당연히 훈련 데이터에 지나치게 맞춰져 일반화 성능이 떨어질 수 있다. 따라서 훈련 정확도와 테스트 정확도의 차이가 너무 크지 않은 지점에서 적절한 k를 선택하는 것이 중요하다.
다음은 k가 증가함에 따라 훈련 정확도와 테스트 정확도가 변화하는 추이를 표현한 그래프이다. 훈련 정확도와 테스트 정확도가 교차하는 지점인 7-8 정도로 k를 설정하는 것이 타당해 보인다.
장단점
- 단순성 : 이해하기 쉽고 구현이 간단하다. 예측 과정이 상당히 직관적이어서 분석이나 모델 설명이 용이하다.
- 비모수적 방법 : 분포에 대한 가정이 필요하지 않으므로, 데이터가 어떤 분포를 따르더라도 적용할 수 있다.
- 훈련 불필요 : 모형 훈련 과정 없이 새로운 데이터가 들어오면 즉시 예측을 수행한다. 데이터 업데이트가 잦은 경우 유리하다.
- 계산 복잡도 : 새로운 데이터가 들어올 때마다 모든 데이터와의 거리를 계산하므로 계산 복잡도가 높다. 이러한 이유로 데이터셋이 크거나 실시간 예측이 필요한 경우 적합하지 않다.
- 차원의 저주 : 데이터 차원이 커지면 예측 성능이 저하될 수 있다. 이로 인해 적절한 차원 축소 기법이 필요하다.
- 메모리 요구량 증가 : 훈련 데이터 전체를 메모리에 저장하기 때문에 데이터셋이 커질수록 메모리 요구량이 증가한다.
- 이상치에 민감 : 가장 가까운 k개의 이웃을 참조하여 예측을 수행하므로, 데이터셋에 이상치나 노이즈가 포함된 경우 예측 성능이 저하될 수 있다.
Reference
Aurélien Géron, Hands-On Machine Learning with Scikit-Learn, Keras, and TensorFlow