KNN(K-Nearest Neighbors)은 머신러닝에서 가장 직관적인 알고리즘입니다.
핵심 아이디어: 새로운 데이터 포인트가 주어지면, 기존 학습 데이터에서 가장 가까운 K개의 이웃을 찾아 다수결 투표로 클래스를 결정합니다.
KNN은 Lazy Learning(게으른 학습)의 대표적 사례입니다:
- 학습 단계(training phase)가 따로 없습니다
- 모든 계산은 예측 시점(inference)에 수행됩니다
- 학습 데이터를 그대로 메모리에 저장합니다 (Instance-based Learning)
이것이 Eager Learning(예: 로지스틱 회귀, SVM)과의 핵심 차이입니다:
- Eager: 학습 시 모델 파라미터를 미리 최적화 → 예측은 빠름
- Lazy: 학습 시 아무것도 안 함 → 예측 시 전체 데이터 탐색 → 느림
다수결 투표(Majority Voting) 과정:
1. 새 데이터 포인트 q가 주어짐
2. 모든 학습 데이터와의 거리 계산
3. 거리 기준 상위 K개 이웃 선택
4. K개 이웃의 클래스 레이블 중 최다 투표 클래스 = 예측값
KNN의 역사적 맥락:
- 1951: Fix & Hodges가 비모수 판별 분석으로 최초 제안
- 1967: Cover & Hart가 이론적 오류 경계 증명 (유명한 Cover-Hart 정리)
- 1970s-80s: 패턴 인식, OCR에 실전 적용
- 2000s: 추천 시스템(Netflix Prize)에서 KNN 기반 협업 필터링 활약
- 현재: 이상 탐지, Few-shot Learning의 기초 모듈로 활용
KNN의 이론적 수렴 성질은 Cover와 Hart가 증명했으며, 샘플 수가 충분할 때 최적 베이즈 오류율의 2배 이내에 수렴함을 보였다 (Cover et al., 1967).