k-최근접 이웃 알고리즘(k-NN)은 분류와 회귀에 사용되는 비모수적, 사례 기반 학습 방법이다. 두 경우 모두 입력은 특징 공간에서 가장 가까운 k개의 훈련 예제로 구성된다. 출력은 k-NN이 분류에 사용되는지 회귀에 사용되는지에 따라 달라진다. 분류에서 출력은 k개의 최근접 이웃 간의 다수결 투표로 결정되는 클래스 소속이며, 회귀에서 출력은 k개의 최근접 이웃 값의 평균(또는 가중 평균)이다. k-NN은 지연 학습의 한 유형으로, 함수는 국소적으로만 근사되고 모든 계산은 함수 평가까지 지연된다. 거리 계산을 사용하기 때문에 이 알고리즘은 데이터의 국소 구조와 거리 측정의 선택에 민감하다.
이 알고리즘은 1951년에 미국 공군 항공 의학 학교의 에블린 픽스와 조셉 호지스에 의해 처음 개발되었으며, 원래는 비모수적 분류 기법이었다. 이후 1967년에 토마스 커버와 피터 하트가 확장하고 형식화하여 점근적 오차 경계를 설정했다. 그 이후로 분자-NN은 Machine learning에서 Machine learning의 기초적인 도구가 되었으며, 패턴 인식과 데이터 마이닝에서 더 복잡한 모델의 기준으로 자주 사용된다.
작동 방식
쿼리 점이 주어지면 알고리즘은 학습 예제각각에 대한 거리(일반적으로 유클리드, 맨해턴 또는 민코프스키)를 계산한다. 그런 다음 가장 작은 거리를 가진 k개의 학습 예제를 선택한다. 분류의 경우 예측된 라벨은 이 k개의 이웃에서 가장 빈번한 것이다. 회귀의 경우 예측된 값은 이웃의 목표 값의 평균으로 나타난다. k의 선택은 중요하다. 작은 값(예: 1)의 경우 높은 분산과 노이즈에 대한 민감도를 크게 하고, 큰 값의 경우 국소적인 패턴을 평탄화하여 편향을 늘린다. 일반적으로 교차 검증을 통해 k를 선택하며, 이진 분류에서는 동률을 피하기 위해 홀수 값을 종종 사용한다.
알고리즘은 거리 측정도 필요하다. 유클리드 거리는 연속형 특징에서의 표준이지만, 고차원 또는 범주형 데이터에서는.
특성 및 변형
k-NN은 비모수적이므로 기반 데이터 분포에 대한 강한 가정을 하지 않는다. 또한 "인스턴스 기반" 방식이므로 교육 세트 전체를 저장하고 예측 시는데 직접적으로 사용한다. 이 때문에 반복 학습이 거의 필요하지 않지만(단순히 데이터를 저장), 테스트 시간이 느리며, 쿼리당 시간 복잡도는 O(nd)이다. 여기서 은 n은 샘플 수, d는 특징 수이다.
K-최근접 이웃의 주요 장점은 단순성, 구현의 용이성, 낮은 차원의 작은 데이터에서 중간 정도에서 높은 성능을 내는 것입니다. 훈련 단계가 필요 없어 증가 학습(inkremental learning)에 적합합니다. 그러나 제한 사항은 모든 학습 데이터를 저장해야 하므로 메모리 사용량이 크고 예측 속도가 느립니다. 비관련 특징과 노이즈에 민감하며 고차원 공간에서 크게 성능이 떨어지니다. 그리고 특징이 모두 동등하게 중요하다고 가정하지만 실제로는 드물게 성립합니다.
다음과 같은 해결 방법이 있습니다:
- 가중 k-NN : 가까운 이웃에게 역거리 가중치를 부여합니다.
- 로컬 방정식 회귀 : 이웃 내에서 선형 모델을 적합시키습니다.
- k-d 트리, ball tree, 봤어성 해시(Local Sensitive Hashing)와 같은 근사 근접 이웃 검색 기술을 사용하여 검색 비용을 줄입니다.
- 높은 차원에서는 차원의 저주로 거리가 의미를 잃으므로 차원 축소나 특징 선택을 수행합니다.
응용 분야
이 알고리즘은 Computer vision의 이미지 분류, Natural language processing의 텍스트 분류, 그리고 생선공학 분류의 유전자 표현 분석 등 다양한 분야에서 널리 사용됩니다. 추천 시스템에서도 유사한 사요자의 이웃을 발견하는 데 활용됩니다. 금융에서는 신용 평가와 이상 감지에 사용됩니다. 단순하고 해석 가능한 점이 특징으로 복잡한 모델의 초기 탐색 및 기준 비교 모델(benchmark)으로 흔히 선택됩니다.
장점 및 제한점
k-NN의 주요 강점은 낮은 차원의 비교적 작은 데이터 세트에서 효과적이며 단순하고 해석하기 쉽다는 점입니다. 또한 훈련 단계가 따로 없기 때문에 계산하는 데 드는 비용이 낮은 초기 몇 시간 동안은 오히려 프로세스가 유연합니다. 그러나 모든 훈련 데이터를 저장해야 하기 때문에 메모리 사용량이 크며 예측 시간이 오래 걸리고 고차원 공간에서 성능이 저하되는 등 한계가 존재합니다. 즉, 모든 특징이 동등하게 중요하다고 가정하지만 실제로는 그렇지 않은 경우가 많습니다.
다른 방법과의 관계
k-NN은 의사 결정 트리 및 서포트 벡터 머신 등 다른 비모수적 방법과 함께 사용되기도 합니다. 주로 Machine learning의 기초를 다루는 과목에서 학습하며 Artificial intelligence와 연결됩니다. 또한 Data Augmentation에서 생성된 이웃 샘플을 활용하는 기법, 그리고 Curriculum Learning에서 훈련 예제를 난이도 순으로 정렬하는데 기여합니다. 최근 딥러닝에서는 학습된 임베딩을 최근접 이웃 검색과 함께 비교하는 메트릭 러닝(metric learning) 방식의 최종 레이어로 사용됩니다.
같이 보기
참고 문헌
- Cover, T., & Hart, P. (1967). Nearest neighbor pattern classification. IEEE Transactions on Information Theory.
- Fix, E., & Hodges, J. L. (1951). Discriminatory analysis, nonparametric discrimination: consistency properties. USAF School of Aviation Medicine.
- Altman, N. S. (1992). An introduction to kernel and nearest-neighbor nonparametric regression. The American Statistician.