KNN(K-Nearest Neighbors) 알고리즘 완벽 가이드

개요

KNN(K-Nearest Neighbors)은 머신러닝의 가장 직관적이고 간단한 알고리즘 중 하나입니다. "유유상종"이라는 속담처럼, 비슷한 특성을 가진 데이터들은 비슷한 결과를 가질 것이라는 가정에 기반합니다.

KNN 알고리즘이란?

KNN은 게으른 학습(Lazy Learning) 알고리즘으로, 별도의 훈련 과정 없이 새로운 데이터가 들어올 때 기존 데이터와의 거리를 계산하여 가장 가까운 K개의 이웃을 찾아 예측을 수행합니다.

주요 특징

• 비모수적(Non-parametric): 데이터의 분포에 대한 가정이 없음
• 인스턴스 기반 학습: 모든 훈련 데이터를 메모리에 저장
• 지연 학습: 예측 시점에 계산 수행

작동 원리

1. 거리 계산

새로운 데이터 포인트와 모든 훈련 데이터 간의 거리를 계산합니다.

유클리드 거리 (가장 일반적)

d = √[(x₁-x₂)² + (y₁-y₂)²]

맨하탄 거리

d = |x₁-x₂| + |y₁-y₂|

민코프스키 거리

d = (Σ|xᵢ-yᵢ|ᵖ)^(1/p)

2. K개의 최근접 이웃 선택

계산된 거리를 기준으로 가장 가까운 K개의 데이터 포인트를 선택합니다.

3. 예측 수행

분류 문제: 다수결 투표

• K개 이웃 중 가장 많은 클래스로 분류

회귀 문제: 평균값 계산

• K개 이웃의 타겟 값 평균 또는 가중 평균

핵심 매개변수

K값 선택

K값이 작을 때 (K=1, 3, 5)

• 장점: 지역적 패턴을 잘 포착
• 단점: 노이즈에 민감, 과적합 위험

K값이 클 때 (K=15, 20+)

• 장점: 노이즈에 강함, 안정적 예측
• 단점: 지역적 패턴 무시, 과소적합 위험

최적 K값 선택 방법

• 교차 검증을 통한 성능 평가
• 일반적으로 √n (n: 훈련 데이터 수)을 시작점으로 사용
• 홀수 선택 (분류에서 동점 방지)

장단점 분석

장점

• 구현 용이성: 알고리즘이 직관적이고 간단
• 범용성: 분류와 회귀 모두 적용 가능
• 비선형 패턴 처리: 복잡한 결정 경계 학습 가능
• 새로운 데이터 적응: 온라인 학습 가능

단점

• 계산 복잡도: O(n) - 모든 훈련 데이터와 거리 계산 필요
• 메모리 사용량: 모든 훈련 데이터를 저장해야 함
• 차원의 저주: 고차원에서 성능 저하
• 불균형 데이터: 다수 클래스에 편향

성능 최적화 방법

1. 데이터 전처리

# 특성 스케일링 (필수!)
from sklearn.preprocessing import StandardScaler
scaler = StandardScaler()
X_scaled = scaler.fit_transform(X)

2. 차원 축소

# PCA를 통한 차원 축소
from sklearn.decomposition import PCA
pca = PCA(n_components=10)
X_reduced = pca.fit_transform(X)

3. 효율적인 탐색 알고리즘

• KD-Tree: 저차원 데이터에 효과적
• Ball Tree: 고차원 데이터에 적합
• LSH (Locality Sensitive Hashing): 근사 최근접 이웃 탐색

실제 적용 예시

1. 추천 시스템

from sklearn.neighbors import NearestNeighbors

# 사용자-아이템 행렬 기반 협업 필터링
model = NearestNeighbors(n_neighbors=5, metric='cosine')
model.fit(user_item_matrix)

# 유사한 사용자 찾기
distances, indices = model.kneighbors(user_profile)

2. 이상치 탐지

from sklearn.neighbors import LocalOutlierFactor

# LOF를 이용한 이상치 탐지
lof = LocalOutlierFactor(n_neighbors=20)
outlier_scores = lof.fit_predict(data)

3. 분류 문제

from sklearn.neighbors import KNeighborsClassifier
from sklearn.model_selection import GridSearchCV

# 하이퍼파라미터 튜닝
param_grid = {
    'n_neighbors': [3, 5, 7, 9, 11],
    'weights': ['uniform', 'distance'],
    'metric': ['euclidean', 'manhattan']
}

knn = KNeighborsClassifier()
grid_search = GridSearchCV(knn, param_grid, cv=5, scoring='accuracy')
grid_search.fit(X_train, y_train)

성능 평가 지표

분류 문제

• 정확도(Accuracy): 전체 예측 중 맞힌 비율
• 정밀도(Precision): 양성 예측 중 실제 양성 비율
• 재현율(Recall): 실제 양성 중 예측한 양성 비율
• F1-Score: 정밀도와 재현율의 조화 평균

회귀 문제

• MAE (Mean Absolute Error): 절대 오차의 평균
• MSE (Mean Squared Error): 제곱 오차의 평균
• RMSE (Root Mean Squared Error): MSE의 제곱근
• R² Score: 결정계수

실전 팁

1. 데이터 전처리가 핵심

• 모든 특성을 동일한 스케일로 정규화
• 범주형 변수는 원-핫 인코딩 적용
• 결측값 처리 필수

2. K값 선택 전략

• 작은 데이터셋: K = 3~7
• 중간 데이터셋: K = √n
• 큰 데이터셋: 교차 검증으로 최적화

3. 거리 메트릭 선택

• 연속형 데이터: 유클리드 거리
• 범주형 데이터: 해밍 거리
• 고차원 데이터: 코사인 유사도

4. 불균형 데이터 처리

• 가중치 적용 (weights='distance')
• SMOTE 등으로 데이터 증강
• 계층적 샘플링 사용

결론

KNN은 간단하면서도 강력한 알고리즘입니다. 특히 지역적 패턴이 중요한 문제나 복잡한 결정 경계를 가진 데이터에서 우수한 성능을 보입니다. 하지만 적절한 전처리와 하이퍼파라미터 튜닝이 성공의 열쇠입니다.

언제 KNN을 사용해야 할까요?

• 데이터의 지역적 패턴이 중요한 경우
• 비선형 관계를 모델링해야 하는 경우
• 해석 가능한 모델이 필요한 경우
• 소규모~중규모 데이터셋을 다루는 경우