K-최근접 이웃 (KNN)

AI/ML 엔지니어링 · 머신러닝 기초 #6

K-최근접 이웃
(KNN)

가장 가까운 이웃들의 다수결 — 모델 없이 데이터만으로 예측하는 게으른 학습자 완전 정복

AI/ML Engineering

머신러닝 기초

읽는 데 약 11분

목차

1. KNN이란? — Lazy Learning의 철학
2. KNN 작동 원리
3. 거리 측정 방법
4. K 값 선택의 중요성
5. KNN 회귀
6. 차원의 저주 (Curse of Dimensionality)
7. 장단점과 사용 시나리오
8. Python 구현 예제

Section 01

KNN이란? — Lazy Learning의 철학

KNN(K-Nearest Neighbors)은 가장 단순하면서도 직관적인 머신러닝 알고리즘 중 하나입니다. 핵심 아이디어는 놀랍도록 간단합니다: 새로운 데이터는 가장 비슷한(가까운) K개의 훈련 데이터와 같은 클래스에 속할 것이다.

KNN은 게으른 학습(Lazy Learning)이라고도 불립니다. 훈련 단계에서 아무런 모델도 만들지 않고 데이터를 그대로 저장합니다. 예측 시에야 비로소 거리 계산을 수행합니다.

직관: "비슷한 것은 비슷한 결과를 낳는다(Similar things yield similar results)." — KNN은 이 단순한 가정을 그대로 구현합니다. 새 환자의 병을 진단할 때, 가장 비슷한 증상을 가진 과거 환자들의 진단을 참고하는 것과 같습니다.

Section 02

KNN 작동 원리

인터랙티브: K 값에 따른 KNN 분류 결과 변화

K 값: 3

K=3: 파란 이웃 2개 + 빨간 이웃 1개 → 파란 클래스 예측

KNN의 예측 알고리즘은 다음과 같습니다:

1. 새 데이터 포인트 x*와 모든 훈련 데이터 간의 거리를 계산합니다.
2. 거리가 가장 가까운 K개의 이웃을 선택합니다.
3. (분류) K개 이웃 중 가장 많은 클래스를 예측 클래스로 선택합니다.
4. (회귀) K개 이웃 출력값의 평균을 예측값으로 사용합니다.

Section 03

거리 측정 방법

거리 지표	수식	특징
유클리디안	√Σ(xᵢ − yᵢ)²	직선 거리. 가장 일반적. 연속 수치 데이터에 적합. sklearn 기본값.
맨해튼	Σ|xᵢ − yᵢ|	격자 이동 거리. 이상치에 덜 민감. 고차원에서 유클리디안보다 유리할 수 있음.
민코프스키	(Σ|xᵢ−yᵢ|ᵖ)^(1/p)	일반화된 거리. p=1이면 맨해튼, p=2이면 유클리디안.
코사인 유사도	1 − (x·y / ‖x‖‖y‖)	방향 기반 유사도. 텍스트, 추천 시스템에 적합.

스케일링 필수! KNN은 거리 기반 알고리즘이므로 특성 스케일에 매우 민감합니다. 예를 들어 나이(0~100)와 연봉(0~10,000만원)을 그대로 사용하면 연봉이 거리를 지배합니다. 반드시 StandardScaler 또는 MinMaxScaler로 전처리해야 합니다.

Section 04

K 값 선택의 중요성

K는 KNN에서 가장 중요한 하이퍼파라미터입니다. 최적의 K를 찾는 것이 성능의 핵심입니다.

K = 1

가장 가까운 1개만 참조. 극단적 과적합. 노이즈에 매우 취약.

K = 적절한 값

일반적으로 √n(훈련 데이터 수의 제곱근) 부근에서 시작. 홀수 권장 (동점 방지).

K = 전체

모든 데이터 참조. 항상 다수 클래스 예측. 극단적 과소적합.

가중 KNN (Weighted KNN): 모든 이웃에 동일한 가중치를 주는 대신, 가까울수록 높은 가중치를 부여합니다. 일반적으로 거리의 역수를 가중치로 사용합니다. sklearn에서 weights='distance'로 설정합니다.

Section 05

KNN 회귀

KNN은 분류뿐만 아니라 회귀에도 사용됩니다. K개 이웃의 출력값 평균을 예측값으로 사용합니다.

KNN 회귀 예측 ŷ = (1/K) Σ_{i∈N_K(x*)} yᵢ    또는    ŷ = Σ wᵢyᵢ (가중 평균)

KNN 회귀는 비모수적(non-parametric) 방법이므로 선형 회귀와 달리 복잡한 비선형 관계도 표현할 수 있습니다. 단, 예측 결과가 훈련 데이터 범위를 벗어나지 않는(외삽 불가) 특성이 있습니다.

Section 06

차원의 저주 (Curse of Dimensionality)

KNN의 가장 큰 약점입니다. 특성(차원)이 늘어날수록 두 데이터 포인트 간의 거리 개념이 무의미해집니다.

• 거리 집중 현상: 고차원에서는 가까운 이웃과 먼 이웃의 거리 차이가 거의 없어집니다.
• 데이터 희소성: 같은 수의 데이터가 고차원 공간에서는 매우 드물게 분포합니다.
• 계산 비용: 특성이 늘수록 거리 계산 비용이 선형으로 증가합니다.

해결책: PCA, LDA 등의 차원 축소 기법을 전처리로 적용하거나, 특성 선택(Feature Selection)으로 불필요한 특성을 제거합니다. 일반적으로 특성 수가 20개 이상이면 KNN의 성능이 급격히 저하됩니다.

Section 07

장단점과 사용 시나리오

장점

구현 단순 / 훈련 시간 없음 / 비선형 경계 자연스럽게 처리 / 새 데이터 즉시 적응 / 다중 클래스 자연스럽게 지원

단점

예측 시간 느림 O(nd) / 메모리 많음 (전체 저장) / 스케일링 필수 / 고차원 취약 / 불균형 데이터에 편향

사용 적합	사용 부적합
소~중규모 데이터셋 추천 시스템 (아이템 유사도) 이상치 탐지 비선형 결정 경계 빠른 프로토타이핑	대규모 데이터셋 고차원 데이터 (100차원 이상) 실시간 예측 필요 메모리 제한 환경 특성 중요도 필요

Section 08

Python 구현 예제

Python from sklearn.neighbors import KNeighborsClassifier, KNeighborsRegressor
from sklearn.preprocessing import StandardScaler
from sklearn.pipeline import Pipeline
from sklearn.model_selection import cross_val_score
from sklearn.datasets import load_iris
import numpy as np

# 1. 데이터 로드
X, y = load_iris(return_X_y=True)

# 2. Pipeline: 스케일링 + KNN (스케일링 필수!)
pipe = Pipeline([
    ('scaler', StandardScaler()),
    ('knn', KNeighborsClassifier(
        n_neighbors=5,
        weights='distance',  # 가중 KNN
        metric='euclidean'
    ))
])

# 3. 최적 K 탐색
k_range = range(1, 31, 2)
cv_scores = []
for k in k_range:
    pipe.set_params(knn__n_neighbors=k)
    scores = cross_val_score(pipe, X, y, cv=5, scoring='accuracy')
    cv_scores.append(scores.mean())

best_k = list(k_range)[np.argmax(cv_scores)]
print(f"최적 K: {best_k}, CV 정확도: {max(cv_scores):.4f}")

KD-Tree와 Ball-Tree — 빠른 이웃 탐색

Python — 알고리즘 선택 # algorithm 옵션
# 'ball_tree': 고차원에서 유리, 맨해튼 거리 지원
# 'kd_tree': 저차원에서 빠름 (< 20차원)
# 'brute': 완전 탐색, 소규모 데이터에서 빠를 수 있음
# 'auto': sklearn이 자동 선택 (기본값)
knn = KNeighborsClassifier(
    n_neighbors=5,
    algorithm='ball_tree',
    leaf_size=30     # 트리 분기 크기
)

핵심 정리

학습 유형게으른 학습 (Lazy Learning)

핵심 파라미터K (이웃 수), 거리 지표

훈련 복잡도O(1) (저장만 함)

예측 복잡도O(nd) (n: 샘플, d: 차원)

장점단순함, 비선형 처리, 비모수적

한계예측 느림, 고차원 취약, 스케일링 필수