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

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

개요¶

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

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

핵심 개념¶

1. 알고리즘¶

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

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

2. 거리 메트릭 (Distance Metrics)¶

3. k의 선택¶

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

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

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

graph LR
    subgraph "k=1"
        A1["복잡한 경계<br/>노이즈에 민감"]
    end
    subgraph "k=적정값"
        A2["적절한 경계<br/>일반화 양호"]
    end
    subgraph "k=n"
        A3["가장 빈번한 클래스<br/>항상 같은 예측"]
    end
    A1 -->|k 증가| A2 -->|k 증가| A3

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

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

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

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

\(d\)가 커지면 이 값이 1에 가까워져 "이웃"의 의미가 사라진다.

완화 방법¶

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

5. 계산 고려사항¶

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

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

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

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

상세 내용¶

k-NN의 이론적 성질¶

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

Cover-Hart 정리 (1967): 1-NN 분류기의 오류율 \(R_{1\text{-NN}}\)은 베이즈 최적 오류율 \(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)\)를 추정하고 베이즈 규칙을 적용하는 것과 동치이다:

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

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

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

결정 경계 분석¶

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

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

graph LR
    subgraph "k=1: 보로노이"
        V1["각 점이 영역 지배<br/>꺾인 경계<br/>노이즈에 매우 민감"]
    end
    subgraph "k=중간값: 평활"
        V2["경계가 매끄러워짐<br/>노이즈 흡수<br/>일반화 양호"]
    end
    subgraph "k=n: 상수"
        V3["전체 영역 동일 예측<br/>다수 클래스만 출력<br/>경계 없음"]
    end
    V1 -->|평활화| V2 -->|과평활| V3

데이터 전처리의 중요성¶

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

스케일링 방법 비교¶

이상치 처리¶

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

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

언제 사용하는가¶

흔한 오해와 함정¶

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은 서포트 벡터만 사용하여 효율적

자주 묻는 면접 질문¶

1. k가 편향-분산 트레이드오프에 미치는 영향은?

2. 작은 k: 낮은 편향, 높은 분산 (과적합). 큰 k: 높은 편향, 낮은 분산 (과소적합)

3. k-NN에서 특성 스케일링이 필요한 이유는?

4. 거리 계산에서 스케일이 큰 특성이 결과를 지배하기 때문

5. 매우 고차원에서 k-NN에 무슨 일이 일어나는가?

6. 차원의 저주: 모든 거리가 비슷해져 "이웃"의 개념이 의미를 잃음

7. k-NN vs 다른 모델: 언제 k-NN이 바람직한가?

8. 저차원, 불규칙 경계, 해석 가능성(유사 사례 설명), 비모수적 접근이 필요할 때

9. 훈련 vs 추론의 시간 복잡도는?

10. 훈련: \(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)

용어 정리¶

참고 자료¶

• 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)