k-최근접 이웃(k-Nearest Neighbors, k-NN) 알고리즘은 클래스 소속 여부(Y)와 예측 변수 X1, X2, …, Xn 사이의 관계 구조에 대해 어떠한 가정도 하지 않는 분류 기법입니다.
비모수적 접근 방식
k-NN은 선형 회귀에서 가정하는 것처럼 특정 함수 형태(예: 선형 형태)를 전제로 매개변수를 추정하지 않는 비모수(nonparametric) 방법입니다. 대신 데이터셋 내 예측 변수 값들 간의 유사성을 바탕으로 데이터를 분류합니다.
k-NN 알고리즘의 주요 이점
k-NN 방법의 가장 큰 장점은 단순함과 모수적 가정이 필요 없다는 점입니다. 학습 데이터가 충분히 크고, 각 클래스가 예측 변수 값의 다양한 조합으로 특징지어지는 경우 이 방법은 특히 뛰어난 성능을 발휘합니다.
예를 들어 부동산 데이터베이스에서는 {주택 유형, 방 개수, 인근 지역, 매물 가격 등}의 여러 조합을 통해 빠르게 판매되는 주택과 시장에 오래 머무는 주택을 구분할 수 있습니다.
k-NN 활용 시 마주하는 세 가지 어려움
실제 환경에서 k-NN의 강력한 성능을 온전히 활용하는 데에는 세 가지 난제가 있습니다.
1. 최근접 이웃 탐색에 드는 계산 시간
학습 데이터로부터 매개변수를 계산하는 데에는 시간이 필요하지 않지만(회귀와 같은 모수적 모델과 달리), 거대한 학습 집합에서 최근접 이웃을 찾는 데 걸리는 시간이 제약 요소가 될 수 있습니다. 이 문제를 해결하기 위한 핵심 아이디어는 다음과 같습니다.
- 차원 축소 기법 활용: 주성분 분석(PCA)과 같은 차원 축소 기법을 사용해 저차원 공간에서 작업하면 거리 계산에 소요되는 시간을 크게 줄일 수 있습니다.
- 고급 데이터 구조 활용: 탐색 트리(search tree)와 같은 정교한 데이터 구조를 사용하면 최근접 이웃 식별 속도를 높일 수 있습니다. 이 방법은 속도 향상을 위해 '거의 최근접'인 이웃으로 만족하는 경우가 많습니다. 대표적인 예로 버킷팅(bucketing)이 있으며, 이는 데이터를 버킷 단위로 묶어 각 버킷 내부의 데이터들이 서로 가까운 위치에 있도록 구성하는 방식입니다.
2. 차원의 저주(Curse of Dimensionality)
'큰' 학습 집합으로 인정받기 위해 필요한 데이터의 양은 예측 변수 개수 p에 따라 기하급수적으로 증가합니다. 학습 집합의 크기가 p와 함께 기하급수적으로 늘어나지 않는 한, 최근접 이웃까지의 기대 거리는 p가 커질수록 급격히 증가하기 때문입니다. 이 현상을 차원의 저주(curse of dimensionality)라고 하며, 분류·예측·군집화 등 다양한 기법에 공통적으로 적용되는 근본적인 문제입니다.
3. 게으른 학습자(Lazy Learner)의 한계
k-NN은 '게으른 학습자(lazy learner)'입니다. 시간이 많이 걸리는 계산이 예측 시점까지 미뤄집니다. 예측해야 할 각 데이터에 대해 학습 데이터 전체와의 거리를 예측 시점에 일일이 계산해야 하므로, 실시간으로 다수의 데이터를 동시에 예측해야 하는 상황에서는 이 알고리즘의 활용이 제한됩니다.