k-최근접 이웃 (k-Nearest Neighbors, k-NN)

난이도: 초급
선수 지식: 거리 메트릭(유클리드 거리 등), 기초 통계
관련 문서: 차원 축소 | 클러스터링 | 과적합과 과소적합

핵심 요약: k-NN(k-Nearest Neighbors)은 새 데이터가 들어오면 가장 가까운 k개의 이웃에게 물어보고 다수결(Majority Vote)로 결정하는 모델이다. 별도의 학습 단계가 없는 게으른 학습기(Lazy Learner)이며, 거리 기반이므로 반드시 특성 스케일링(Feature Scaling)이 필요하다.

핵심 용어 미리보기:

유클리드 거리 (Euclidean Distance): 두 점 사이의 직선 거리. $\sqrt{\sum(x_i - z_i)^2}$
게으른 학습기 (Lazy Learner): 학습 시에는 데이터를 저장만 하고, 예측 시에 비로소 계산을 수행하는 모델
차원의 저주 (Curse of Dimensionality): 차원이 높아질수록 모든 점 사이의 거리가 비슷해져 “이웃”의 의미가 사라지는 현상
특성 스케일링 (Feature Scaling): 특성들의 범위를 맞춰주는 전처리. 안 하면 범위가 큰 특성이 거리를 지배한다

개요

k-최근접 이웃(k-NN)은 가장 직관적인 머신러닝 알고리즘 중 하나이다. 새로운 데이터 포인트가 주어지면, 훈련 데이터에서 가장 가까운 k개의 이웃을 찾아 다수결 투표(분류) 또는 평균(회귀)으로 예측한다.

k-NN은 명시적 학습 단계가 없는 게으른 학습기(lazy learner) 또는 인스턴스 기반 학습(instance-based learning)의 대표적 사례이다. 훈련 데이터 전체를 저장하고, 예측 시에만 계산을 수행한다.

탄생 배경

k-NN의 역사는 비모수 통계학(Nonparametric Statistics)의 선구적 연구에서 시작된다. Evelyn Fix와 Joseph Hodges (1951)가 UC Berkeley에서 발표한 기술 보고서가 최근접 이웃 분류의 첫 공식적 연구로 인정된다. 이들은 모수적 분포 가정 없이 데이터 자체로부터 직접 분류 규칙을 구성할 수 있음을 보였다.

이 아이디어에 이론적 토대를 마련한 것이 Cover와 Hart (1967)의 기념비적 논문이다. Cover-Hart 정리는 1-NN 분류기의 오류율이 베이즈 최적 오류율의 2배를 넘지 않음을 증명했다. 데이터가 무한히 주어진다면, 가장 단순한 “가까운 것 하나만 보기” 전략만으로도 이론적 최적에 근접할 수 있다는 놀라운 결과였다.

그러나 k-NN의 실용적 한계도 명확했다. 차원의 저주(Curse of Dimensionality) — 고차원 공간에서 모든 점이 서로 비슷하게 멀어지는 현상 — 는 Richard Bellman이 1957년에 명명한 개념인데, k-NN에서 특히 치명적으로 작용한다. 마치 텅 빈 축구장에서 가장 가까운 사람을 찾는 것은 쉽지만, 100차원 초공간에서는 모든 사람이 거의 같은 거리에 있는 것과 같다.

현대에 이르러 FAISS (Facebook AI Similarity Search, 2019), HNSW (Hierarchical Navigable Small World) 등의 근사 최근접 이웃(Approximate Nearest Neighbor) 알고리즘이 등장하면서, k-NN의 핵심 아이디어는 2억 규모의 사용자 임베딩에서도 밀리초 단위의 실시간 검색이 가능한 수준으로 확장되었다.

핵심 개념

1. 알고리즘

분류: k개 최근접 이웃의 다수결 투표

$\hat{y} = \arg\max_c \sum_{i \in N_k(x)} \mathbb{1}(y_i = c)$

숫자로 이해하기

2D 평면에서 새 점 (3, 4)의 클래스를 예측해 보자 ( $k = 3$ ).

이웃 점	클래스	거리 (유클리드, Euclidean)
(2, 3)	A	$\sqrt{(3-2)^2 + (4-3)^2} = \sqrt{2} \approx 1.41$
(4, 5)	A	$\sqrt{(3-4)^2 + (4-5)^2} = \sqrt{2} \approx 1.41$
(5, 4)	B	$\sqrt{(3-5)^2 + (4-4)^2} = 2.0$

3개 이웃 중 A가 2표, B가 1표 → 다수결로 클래스 A로 예측한다. 만약 $k = 1$ 이면 (2,3)이나 (4,5) 하나만 보고 A, $k = 5$ 로 늘리면 더 많은 이웃을 참고하여 결정 경계(Decision Boundary)가 부드러워진다.

회귀: k개 최근접 이웃의 평균 (또는 가중 평균)

$\hat{y} = \frac{1}{k}\sum_{i \in N_k(x)} y_i$

2. 거리 메트릭 (Distance Metrics)

메트릭	수식	특징
유클리드 (Euclidean, L2)	$d = \sqrt{\sum(x_i - z_i)^2}$	가장 일반적, 등방(isotropic) 가정
맨해튼 (Manhattan, L1)	$d = \sum \\|x_i - z_i\\|$	고차원/희소 데이터에 유리
민코프스키 (Minkowski)	$d = (\sum\\|x_i - z_i\\|^p)^{1/p}$	L1( $p=1$ ), L2( $p=2$ )의 일반화
코사인 유사도 (Cosine)	$1 - \frac{\mathbf{x} \cdot \mathbf{z}}{\\|\mathbf{x}\\|\\|\mathbf{z}\\|}$	방향 기반, 텍스트에 유용
마할라노비스 (Mahalanobis)	$d = \sqrt{(\mathbf{x}-\mathbf{z})^T\mathbf{S}^{-1}(\mathbf{x}-\mathbf{z})}$	특성 간 상관 고려
해밍 (Hamming)	$d = \sum \mathbb{1}(x_i \neq z_i)$	범주형 특성

3. k의 선택

k의 값은 모델의 편향-분산 트레이드오프를 직접 제어한다:

k 값	결정 경계	편향	분산	위험
작은 k (예: 1)	복잡, 불규칙	낮음	높음	과적합, 노이즈에 민감
큰 k (예: 50)	단순, 매끄러움	높음	낮음	과소적합

경험 법칙: $k = \sqrt{n}$ , 이진 분류에서는 홀수 선택 (동점 방지)

최적 k 선택: 교차 검증(cross-validation)으로 결정

4. 차원의 저주 (Curse of Dimensionality)

k-NN에서 가장 중요한 제한 사항이다:

차원이 증가하면 모든 점 간의 거리가 점점 비슷해짐
공간의 부피가 기하급수적으로 증가하여 데이터가 희소(sparse)해짐
초구(hypersphere)와 초입방체(hypercube)의 부피 비율: $d \to \infty$ 일 때 $\to 0$

시연: $d$ 차원에서 단위 초입방체 내 가장 가까운 이웃까지의 중앙 거리:

$d_{\text{median}} \approx \left(1 - \frac{1}{2}^{1/n}\right)^{1/d}$

$d$ 가 커지면 이 값이 1에 가까워져 “이웃”의 의미가 사라진다.

완화 방법

차원 축소: PCA, UMAP 등 (차원 축소 참조)
특성 선택: 관련 없는 특성 제거
적절한 거리 메트릭: 맨해튼 거리가 고차원에서 더 유용할 수 있음

5. 계산 고려사항

방법	쿼리 시간	제한
무차별 대입 (Brute Force)	$O(nd)$	항상 작동
KD-Tree	$O(d \log n)$	$d < 20$ 에서 효과적
Ball Tree	$O(d \log n)$	KD-Tree보다 고차원에서 유리
근사 NN (LSH, FAISS, HNSW)	$O(1)$ ~ $O(\log n)$	근사, 대규모 데이터용

메모리: 훈련 데이터 전체를 저장해야 함 ( $O(nd)$ )

6. 가중 k-NN (Weighted k-NN)

거리에 따라 가중치를 부여:

$\hat{y} = \frac{\sum_{i \in N_k(x)} w_i \cdot y_i}{\sum_{i \in N_k(x)} w_i}, \quad w_i = \frac{1}{d(\mathbf{x}, \mathbf{x}_i)}$

k 선택에 대한 민감도를 줄임
가까운 이웃일수록 더 큰 영향력

상세 내용

k-NN의 이론적 성질

k-NN은 단순해 보이지만 강력한 이론적 보장을 가진다.

Cover-Hart 정리 (1967): 1-NN 분류기의 오류율 $R_{1\text{-NN}}$ 은 베이즈 최적 오류율 $R^*$ 에 대해 다음 부등식을 만족한다:

$R^* \leq R_{1\text{-NN}} \leq 2R^*(1 - R^*)$

$R^*$ : 베이즈 최적 오류율 (Bayes optimal error rate). 이론적으로 달성 가능한 최소 오류율이다
데이터가 무한히 많으면 1-NN만으로도 베이즈 오류율의 2배 이내에 들어간다
예: $R^* = 0.1$ 이면, $R_{1\text{-NN}} \leq 2 \times 0.1 \times 0.9 = 0.18$

k-NN의 일관성 (Consistency): $k \to \infty$ 이면서 $k/n \to 0$ 인 조건 하에서, k-NN 분류기의 오류율은 베이즈 최적 오류율에 수렴한다. 즉, 충분한 데이터와 적절한 k 선택이 있으면 k-NN은 이론적으로 최적에 도달할 수 있다.

k-NN과 커널 밀도 추정 (Kernel Density Estimation)

k-NN 분류는 비모수적(nonparametric) 밀도 추정과 밀접한 관계를 가진다.

k-NN 분류는 각 클래스의 밀도 $\hat{p}(x|c)$ 를 추정하고 베이즈 규칙을 적용하는 것과 동치이다:

$\hat{p}(x|c) = \frac{k_c}{n_c \cdot V_k(x)}$

여기서 $k_c$ 는 k개 이웃 중 클래스 $c$ 에 속하는 개수, $n_c$ 는 전체 클래스 $c$ 의 개수, $V_k(x)$ 는 $x$ 에서 k번째 이웃까지의 초구(hypersphere) 부피이다.

가중 k-NN은 커널 회귀(Nadaraya-Watson estimator)의 특수한 형태로 볼 수 있다:

$\hat{f}(x) = \frac{\sum_{i=1}^{n} K\left(\frac{x - x_i}{h}\right) y_i}{\sum_{i=1}^{n} K\left(\frac{x - x_i}{h}\right)}$

k-NN에서는 커널 $K$ 가 k번째 이웃 거리 내에서만 활성화되는 적응적 대역폭(adaptive bandwidth) 커널에 해당한다.

결정 경계 분석

k의 값에 따라 결정 경계의 형태가 극적으로 변한다:

k=1: 결정 경계는 보로노이 다이어그램(Voronoi Diagram)을 형성한다. 각 훈련 점이 자신에게 가장 가까운 영역을 지배하며, 경계는 꺾인 직선(구간별 선형)이다
k 증가: 경계가 점진적으로 평활화(smoothing)되어 노이즈에 덜 민감해진다
k=n: 전체 공간이 하나의 클래스(가장 빈번한 클래스)로 예측된다

데이터 전처리의 중요성

k-NN은 거리 기반 알고리즘이므로 데이터 전처리가 성능을 크게 좌우한다.

스케일링 방법 비교

스케일러	변환	장점	단점	적합한 경우
StandardScaler	$z = \frac{x - \mu}{\sigma}$	평균 0, 분산 1로 표준화	이상치에 민감	정규분포에 가까운 특성
MinMaxScaler	$z = \frac{x - x_{\min}}{x_{\max} - x_{\min}}$	[0, 1] 범위로 변환	이상치에 매우 민감	경계가 명확한 특성
RobustScaler	$z = \frac{x - Q_2}{Q_3 - Q_1}$	중앙값과 IQR 사용	극단적 이상치는 여전히 남음	이상치가 있는 데이터

이상치 처리

k-NN은 이상치(outlier)에 특히 민감하다:

이상치가 이웃으로 선택되면 예측이 왜곡됨
완화 방법:
- 가중 k-NN 사용 — 먼 이웃(이상치일 가능성)의 영향을 줄임
- 이상치 탐지 후 제거 (IQR, Isolation Forest 등)
- RobustScaler 등 이상치에 강건한 스케일링 적용
- k를 충분히 크게 선택하여 이상치의 영향 희석

언제 사용하는가

상황	추천 여부
저차원 데이터	적합
결정 경계가 매우 불규칙한 경우	적합
빠른 프로토타이핑 / 베이스라인	적합
추천 시스템 (유사 아이템 찾기)	적합
고차원 데이터	부적합 (차원의 저주)
대규모 데이터셋	부적합 (느린 예측)
실시간 예측이 필요한 경우	부적합 (또는 근사 NN 필요)
특성의 스케일이 다른 경우	반드시 스케일링 필요

실전 사례

FAISS로 2억 사용자 최근접 이웃 검색을 실시간으로 처리하기

Facebook(현 Meta)은 사용자 추천, 유사 콘텐츠 검색, 중복 이미지 탐지 등 다양한 서비스에서 최근접 이웃 검색을 대규모로 활용한다. 문제는 규모이다: 2억 개 이상의 사용자 임베딩 벡터에서 주어진 쿼리와 가장 유사한 k개를 밀리초 단위로 찾아야 한다.

무차별 대입(Brute Force) k-NN으로는 불가능한 규모이다. $O(nd)$ 의 쿼리 시간으로 2억 x 256차원 벡터를 매번 전수 검색하면, 단일 쿼리에 수십 초가 소요된다. 이 문제를 해결하기 위해 Meta AI Research는 FAISS(Facebook AI Similarity Search)를 개발했다.

FAISS의 핵심 전략은 양자화(Quantization)와 역파일 인덱싱(Inverted File Index, IVF)의 결합이다. 벡터를 압축하여 메모리 사용량을 줄이고, 공간을 보로노이 셀(Voronoi Cell)로 분할하여 검색 대상을 좁힌다. 그 결과 정확도 95% 이상을 유지하면서 쿼리 시간을 밀리초 단위로 줄였다.

이 사례는 k-NN이 “느린 알고리즘”이라는 인식이 반드시 옳지 않음을 보여준다. 적절한 인덱싱과 근사 기법을 적용하면, k-NN의 직관적 아이디어는 수십억 규모의 실시간 서비스에서도 동작할 수 있다.

흔한 오해와 함정

1. “k-NN은 학습이 필요 없으므로 좋다”

학습 시간이 $O(1)$ 인 대신, 예측 시간이 $O(nd)$ 이다. 실시간 서비스에서는 치명적인 단점이다.

2. “k-NN은 스케일링이 필요 없다”

거리 기반 모델이므로 특성 스케일링은 필수이다. 스케일이 큰 특성이 거리를 지배한다.

3. “k를 크게 하면 항상 좋다”

k가 너무 크면 결정 경계가 지나치게 평탄해지고, 극단적으로 $k=n$ 이면 항상 가장 빈번한 클래스를 예측한다.

4. “k-NN은 모든 차원에서 잘 동작한다”

차원의 저주로 인해 고차원에서는 성능이 급격히 하락한다. 차원 축소가 선행되어야 한다.

5. “유클리드 거리가 항상 최선이다”

데이터 특성에 따라 맨해튼, 코사인, 마할라노비스 등이 더 적합할 수 있다.

다른 주제와의 연결

차원 축소: k-NN 전 필수 전처리 (차원의 저주 완화)
클러스터링: k-NN은 분류, K-Means는 클러스터링이지만 둘 다 거리 기반
과적합과 과소적합: k에 따른 편향-분산 트레이드오프
SVM: 두 모델 모두 거리 기반이지만, SVM은 서포트 벡터만 사용하여 효율적

자주 묻는 면접 질문

k가 편향-분산 트레이드오프에 미치는 영향은?
- 작은 k: 낮은 편향, 높은 분산 (과적합). 큰 k: 높은 편향, 낮은 분산 (과소적합)
k-NN에서 특성 스케일링이 필요한 이유는?
- 거리 계산에서 스케일이 큰 특성이 결과를 지배하기 때문
매우 고차원에서 k-NN에 무슨 일이 일어나는가?
- 차원의 저주: 모든 거리가 비슷해져 “이웃”의 개념이 의미를 잃음
k-NN vs 다른 모델: 언제 k-NN이 바람직한가?
- 저차원, 불규칙 경계, 해석 가능성(유사 사례 설명), 비모수적 접근이 필요할 때
훈련 vs 추론의 시간 복잡도는?
- 훈련: $O(1)$ (저장만), 추론: $O(nd)$ per query (무차별 대입). 반대되는 특성이 핵심

코드 예시

from sklearn.neighbors import KNeighborsClassifier, KNeighborsRegressor
from sklearn.preprocessing import StandardScaler
from sklearn.pipeline import Pipeline

# 반드시 스케일링과 함께 사용
knn_clf = Pipeline([
    ('scaler', StandardScaler()),
    ('knn', KNeighborsClassifier(
        n_neighbors=5,
        weights='distance',    # 거리 기반 가중치
        metric='minkowski',    # 기본: 유클리드 (p=2)
        algorithm='auto'       # brute, kd_tree, ball_tree 중 자동 선택
    ))
])
knn_clf.fit(X_train, y_train)

# 최적 k 찾기 (교차 검증)
from sklearn.model_selection import GridSearchCV
param_grid = {'knn__n_neighbors': range(1, 31, 2)}
grid = GridSearchCV(knn_clf, param_grid, cv=5, scoring='accuracy')
grid.fit(X_train, y_train)
print(f"Best k: {grid.best_params_}")

# 근사 최근접 이웃 (대규모 데이터용)
# pip install faiss-cpu
import faiss
index = faiss.IndexFlatL2(d)  # d = 차원 수
index.add(X_train.astype('float32'))
distances, indices = index.search(X_query.astype('float32'), k=5)

용어 정리

영어	한국어
k-Nearest Neighbors	k-최근접 이웃
Lazy Learner	게으른 학습기
Instance-based Learning	인스턴스 기반 학습
Curse of Dimensionality	차원의 저주
Distance Metric	거리 메트릭
Euclidean Distance	유클리드 거리
Manhattan Distance	맨해튼 거리
Cosine Similarity	코사인 유사도
Approximate Nearest Neighbor	근사 최근접 이웃

참고 자료

Cover & Hart (1967) - “Nearest Neighbor Pattern Classification”
Hastie, Tibshirani, Friedman - The Elements of Statistical Learning (Ch. 13)
Beyer et al. (1999) - “When Is ‘Nearest Neighbor’ Meaningful?”
Johnson et al. (2019) - “Billion-scale similarity search with GPUs” (FAISS)