K-Nearest Neighbor

KNN은 다음과 같은 단계로 요약할 수 있다.

1. 이웃 수 $k$와 거리 측정 기준을 선택한다.
2. 분류하려는 샘플에서 $k$개의 최근접 이웃을 찾는다.
3. 투표를 통해 class label을 결정한다.

이러한 메모리 기반의 classifier는 새로운 데이터에 즉시 적응할 수 있다는 장점이 있다. 하지만 데이터가 추가됨에 따라 최악의 경우 계산 비용이 선형적으로 증가할 수 있다. 이러한 문제를 해결하기 위해 k-d Tree와 같은 구조를 사용한다.