KNN (K-Nearest Neighbors)

개요

KNN(K-Nearest Neighbors, K-최근접 이웃)은 가장 단순하면서도 효과적인 지도 학습 알고리즘 중 하나다. 새로운 데이터를 분류하거나 예측할 때, 가장 가까운 k개의 이웃 데이터의 정보를 활용하는 방식으로 동작한다. 1951년 Evelyn Fix와 Joseph Hodges가 처음 개발했으며, 이후 1967년 Thomas Cover에 의해 확장되었다¹.

KNN은 머신러닝의 입문 알고리즘으로 자주 사용되지만, 벡터 검색의 기초가 되는 중요한 개념이기도 하다. 현대의 근사 최근접 이웃(ANN) 알고리즘들은 KNN의 효율성을 개선하기 위해 개발되었다.

작동 원리

분류(Classification)

1. 거리 계산: 새로운 데이터 포인트와 모든 학습 데이터 간의 거리를 계산
2. 이웃 선택: 가장 가까운 k개의 데이터 포인트 선택
3. 다수결 투표: k개 이웃 중 가장 많은 클래스로 분류

회귀(Regression)

1. 거리 계산: 새로운 데이터 포인트와 모든 학습 데이터 간의 거리를 계산
2. 이웃 선택: 가장 가까운 k개의 데이터 포인트 선택
3. 평균 계산: k개 이웃의 값을 평균하여 예측값 결정

거리 메트릭

KNN의 성능은 사용하는 거리 메트릭에 따라 크게 달라진다.

유클리드 거리 (Euclidean Distance)

연속형 변수에 가장 많이 사용되는 거리 메트릭이다.

$d(p,q)=\sqrt{{\sum }_{i=1}^n(p_i-q_i{)}^2}$

맨해튼 거리 (Manhattan Distance)

격자 형태의 데이터나 차원 간 독립성이 높을 때 유용하다.

$d(p,q)={\sum }_{i=1}^n|p_i-q_i|$

코사인 유사도 (Cosine Similarity)

벡터의 방향성이 중요한 경우 사용한다. 텍스트 분류나 추천 시스템에서 자주 활용된다.

$\text{similarity}=\frac{p\cdot q}{||p||\cdot ||q||}$

해밍 거리 (Hamming Distance)

범주형 변수나 이진 데이터에 적합하다.

하이퍼파라미터: k 값 선택

k 값은 KNN 알고리즘의 핵심 하이퍼파라미터다.

k 값의 영향

• 작은 k (k=1~3):
  • 노이즈에 민감
  • 복잡한 결정 경계
  • 과적합(overfitting) 위험
• 큰 k (k>10):
  • 노이즈에 강건
  • 단순한 결정 경계
  • 과소적합(underfitting) 위험

k 값 선택 전략

1. 홀수 선택: 이진 분류에서 동점을 방지
2. 교차 검증: 다양한 k 값으로 성능 평가
3. 규칙적 접근: $k=\sqrt{N}$ (N은 학습 데이터 수)
4. 도메인 지식: 문제 특성에 따라 조정

복잡도 분석

시간 복잡도

연산	복잡도	설명
학습	$O(1)$	단순히 데이터 저장만 함
예측 (단순 구현)	$O(N\cdot D)$	모든 데이터와 거리 계산
예측 (최적화)	$O(\log N)$	KD-Tree 등 자료구조 사용

• $N$: 학습 데이터 개수
• $D$: 특징(차원) 수

공간 복잡도

$O(N\cdot D)$ - 모든 학습 데이터를 메모리에 저장

장점과 단점

장점

• 단순성: 구현과 이해가 쉬움
• 비모수적: 데이터 분포에 대한 가정 불필요
• 다목적: 분류와 회귀 모두 가능
• 적응성: 새로운 데이터 추가가 간단
• 다중 클래스: 복잡한 다중 클래스 문제에도 자연스럽게 적용

단점

• 계산 비용: 대규모 데이터셋에서 예측이 느림
• 메모리 사용: 모든 학습 데이터를 저장해야 함
• 차원의 저주: 고차원 데이터에서 성능 저하
• 불균형 데이터: 클래스 불균형에 민감
• 특징 스케일링: 거리 기반이므로 정규화 필수

특징 스케일링의 중요성

KNN은 거리 기반 알고리즘이므로 특징들의 스케일이 다르면 큰 값을 가진 특징이 결과를 지배한다.

정규화 기법

• Min-Max Scaling: 0~1 범위로 변환
• 표준화(Standardization): 평균 0, 표준편차 1로 변환
• 정규화(Normalization): 벡터의 길이를 1로 조정

from sklearn.preprocessing import StandardScaler
 
scaler = StandardScaler()
X_train_scaled = scaler.fit_transform(X_train)
X_test_scaled = scaler.transform(X_test)

최적화 기법

게으른 학습(Lazy Learning)

KNN은 “게으른 학습” 알고리즘이다. 학습 단계에서 모델을 구축하지 않고, 예측 시점에 모든 계산을 수행한다. 이는 학습은 빠르지만 예측이 느린 특성으로 이어진다.

자료구조 기반 최적화

대규모 데이터셋에서 KNN의 성능을 개선하기 위한 자료구조들:

KD-Tree

• 공간을 재귀적으로 분할하여 검색 공간 축소
• 저차원 데이터(<20차원)에서 효과적
• 시간 복잡도: $O(\log N)$

Ball Tree

• KD-Tree보다 고차원에서 효과적
• 데이터를 중첩된 초구(hypersphere)로 구성
• 시간 복잡도: $O(\log N)$

Locality Sensitive Hashing (LSH)

• 유사한 데이터를 같은 해시 버킷에 저장
• 고차원 데이터에 적합
• 근사 검색 제공

KNN vs ANN (Approximate Nearest Neighbor)

정확한 KNN (Exact KNN)

• 모든 데이터 포인트와 거리를 정확히 계산 (완전 탐색)
• 100% 정확도 보장
• 시간 복잡도: $O(N)$
• 소규모 데이터셋에 적합

근사 최근접 이웃 (ANN)

• 정확도를 약간 희생하여 속도 대폭 향상
• HNSW, FAISS, ScaNN 등의 알고리즘 사용
• 시간 복잡도: $O(\log N)$ 또는 그 이하
• 대규모 벡터 검색에 필수적

대부분의 현대 벡터 데이터베이스는 ANN 알고리즘을 사용한다. 수백만~수십억 개의 벡터에서 실시간 검색을 위해서는 정확한 KNN이 비현실적이기 때문이다.

측면	Exact KNN	ANN
정확도	100%	95~99%
속도	느림 ($O(N)$)	빠름 ($O(\log N)$)
메모리	적음	많음 (인덱스 구조)
확장성	낮음	높음
사용 사례	소규모 데이터	대규모 벡터 검색

활용 사례

추천 시스템

• 사용자나 아이템 간 유사도 계산
• 협업 필터링(Collaborative Filtering)
• 넷플릭스, 스포티파이 등에서 활용

이미지 분류

• 손글씨 인식 (MNIST)
• 얼굴 인식
• 의료 영상 진단

이상 탐지(Anomaly Detection)

• k개 이웃과의 평균 거리가 큰 경우 이상치로 판단
• 네트워크 침입 탐지
• 사기 거래 탐지

자연어 처리

• 문서 분류
• 감성 분석
• 철자 교정

구현 예시

Scikit-learn을 사용한 기본 구현

from sklearn.neighbors import KNeighborsClassifier
from sklearn.model_selection import train_test_split
from sklearn.preprocessing import StandardScaler
 
# 데이터 준비
X_train, X_test, y_train, y_test = train_test_split(X, y, test_size=0.2)
 
# 특징 스케일링
scaler = StandardScaler()
X_train_scaled = scaler.fit_transform(X_train)
X_test_scaled = scaler.transform(X_test)
 
# KNN 모델 학습
knn = KNeighborsClassifier(n_neighbors=5, metric='euclidean')
knn.fit(X_train_scaled, y_train)
 
# 예측
y_pred = knn.predict(X_test_scaled)

거리 가중 KNN

가까운 이웃에 더 높은 가중치를 부여할 수 있다.

knn_weighted = KNeighborsClassifier(
    n_neighbors=5,
    weights='distance'  # 거리의 역수로 가중치 부여
)

개선 및 변형 알고리즘

Weighted KNN

• 거리에 따라 이웃의 투표에 가중치 부여
• 가까운 이웃에 더 높은 영향력

Radius-based Neighbors

• 고정된 k 대신 일정 반경 내 모든 이웃 사용
• 밀도가 다른 데이터에 유용

Condensed Nearest Neighbor (CNN)

• 학습 데이터의 부분집합만 사용
• 메모리와 계산 비용 절감

Edited Nearest Neighbor (ENN)

• 잘못 분류된 데이터 포인트 제거
• 노이즈 감소 효과

실무 적용 팁

전처리

1. 결측치 처리: KNN은 거리 계산이 필수이므로 결측치 처리 필수
2. 이상치 제거: 거리 기반이므로 이상치에 민감
3. 특징 선택: 관련 없는 특징 제거 (차원의 저주 완화)
4. 스케일링: 반드시 수행

성능 평가

• 교차 검증: k-fold cross-validation으로 k 값 선택
• 그리드 서치: k와 거리 메트릭 조합 탐색
• 혼동 행렬: 분류 성능 상세 분석

실전 고려사항

• 데이터 크기: 수만 개 이상이면 ANN 알고리즘 고려
• 실시간 요구사항: 빠른 응답이 필요하면 인덱스 구조 활용
• 메모리 제약: 데이터 압축이나 차원 축소 검토

참고 자료

논문 및 학술 자료

• Cover, T., & Hart, P. (1967). “Nearest neighbor pattern classification” - IEEE Transactions on Information Theory - KNN의 이론적 기반을 확립한 고전 논문
• Fix, E., & Hodges, J. L. (1951). “Discriminatory Analysis. Nonparametric Discrimination: Consistency Properties” - 최초의 KNN 알고리즘 제안

기술 문서 및 튜토리얼

• scikit-learn: Nearest Neighbors - 공식 문서 및 구현 가이드
• IBM: What is the k-nearest neighbors algorithm? - KNN 개념 설명
• GeeksforGeeks: K-Nearest Neighbor Algorithm - 기초부터 구현까지

비교 및 심화

• Milvus: What is the difference between kNN and ANN? - KNN과 ANN 비교
• Microsoft Learn: kNN and ANN algorithm comparison - 벡터 검색에서의 활용

Footnotes

1. 초기 KNN은 1951년 개발되었으나, 1967년 Thomas Cover의 논문 “Nearest neighbor pattern classification”에서 이론적 기반이 확립되었다. ↩