KNN과 거리 측정 — 가까운 이웃에게 물어보기

케이엔엔, K-Nearest Neighbors는 머신러닝에서 가장 직관적인 알고리즘이에요.

원리가 정말 간단해요. 새로운 데이터가 들어오면, 기존 데이터 중 가장 가까운 K개를 찾아요.

그 K개 이웃들의 다수결 투표로 새 데이터의 클래스를 결정하는 거예요.

그림 왼쪽을 보세요. 케이엔엔은 게으른 학습, Lazy Learning이라고 불려요.

학습 단계가 따로 없어요. 데이터를 그냥 메모리에 저장만 해두는 거죠.

그래서 메모리 복잡도는 O(n × d), 데이터 수 곱하기 차원 수예요.

예측할 때 모든 학습 데이터와의 거리를 계산하니까, 예측 시간도 O(n × d)가 돼요.

그림 가운데를 보면 Eager Learning과 비교가 되어 있어요.

로지스틱 회귀나 에스브이엠 같은 Eager 모델은 학습 시 파라미터를 미리 최적화해둬요.

그래서 예측할 때는 세타 트랜스포즈 x 계산만 하면 돼서 매우 빨라요.

그림 오른쪽에 다수결 투표 과정이 보이시죠? K가 5일 때 예시예요.

다섯 개 이웃 중 클래스 A가 3표, 클래스 B가 2표를 받았어요.

다수결로 A가 승리하고, 확률은 3/5, 즉 60%가 되는 거죠.

하단의 파이프라인을 보세요. 케이엔엔 예측은 5단계로 진행돼요.

새 데이터 입력, 전체 거리 계산, K개 이웃 선택, 다수결 투표, 그리고 예측 출력이에요.

이 알고리즘은 1951년 Fix와 Hodges가 비모수 판별 분석으로 최초 제안했어요.

1967년에는 Cover와 Hart가 유명한 오류 경계 정리를 증명했어요.

케이엔엔의 오류율은 최적 베이즈 오류율의 2배를 넘지 않는다는 놀라운 결과였죠.

2009년 넷플릭스 프라이즈에서도 케이엔엔 기반 협업 필터링이 핵심 역할을 했어요.

현재는 이상 탐지, Few-shot Learning의 기초 모듈로도 활발히 사용되고 있어요.

케이엔엔은 단순하지만, 거리 측정, K 선택, 스케일링 같은 설계 결정이 성능을 좌우해요.

이번 레슨에서 이 모든 핵심 요소를 하나씩 깊이 파고들어 볼 거예요.