k-최근접 이웃

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

k-최근접 이웃(k-Nearest Neighbors, k-NN)은 가장 직관적이고 단순한 기계학습 알고리즘 중 하나이다. 새로운 데이터 포인트를 분류할 때, 훈련 데이터에서 가장 가까운 k개의 이웃들의 클래스를 참고하여 다수결 투표로 분류를 결정한다. k-NN은 “게으른 학습(lazy learning)” 또는 “인스턴스 기반 학습(instance-based learning)“이라고도 불린다.

k-NN의 기본 개념 #

1. 게으른 학습 (Lazy Learning) #

  • 훈련 단계: 실제 모델 학습 없이 데이터를 메모리에 저장만 함
  • 예측 단계: 새로운 데이터가 들어올 때 비로소 계산 수행
  • 모델 없음: 명시적인 모델이나 가중치를 학습하지 않음

2. 인스턴스 기반 학습 (Instance-based Learning) #

  • 일반화된 모델 대신 구체적인 훈련 인스턴스들을 기반으로 예측
  • 지역적 근사를 통한 분류
  • 새로운 데이터와 유사한 과거 데이터를 찾아 예측

k-NN 알고리즘의 작동 원리 #

1. 분류 과정 #

  1. 거리 계산: 새로운 데이터 포인트와 모든 훈련 데이터 간의 거리 계산
  2. 이웃 선택: 가장 가까운 k개의 이웃 선택
  3. 투표: k개 이웃들의 클래스 중 가장 많은 클래스로 분류
  4. 예측: 다수결 결과를 최종 예측값으로 반환

2. 회귀에서의 k-NN #

분류 대신 회귀에서는 k개 이웃들의 값의 평균을 예측값으로 사용한다:

$$\hat{y} = \frac{1}{k} \sum_{i=1}^{k} y_i$$

거리 측정 방법 #

1. 유클리드 거리 (Euclidean Distance) #

가장 일반적으로 사용되는 거리 측정법이다:

$$d(x, x') = \sqrt{\sum_{i=1}^{n} (x_i - x'_i)^2}$$

2. 맨하탄 거리 (Manhattan Distance) #

절댓값의 합으로 계산하는 거리이다:

$$d(x, x') = \sum_{i=1}^{n} |x_i - x'_i|$$

3. 민코프스키 거리 (Minkowski Distance) #

유클리드와 맨하탄 거리를 일반화한 거리이다:

$$d(x, x') = \left(\sum_{i=1}^{n} |x_i - x'_i|^p\right)^{1/p}$$
  • p=1: 맨하탄 거리
  • p=2: 유클리드 거리

4. 해밍 거리 (Hamming Distance) #

범주형 변수에 사용되는 거리로, 다른 값을 가지는 특성의 개수이다.

5. 코사인 유사도 (Cosine Similarity) #

벡터 간의 각도를 측정하여 유사도를 계산한다:

$$\text{similarity} = \frac{x \cdot x'}{||x|| \cdot ||x'||}$$

k값 선택의 중요성 #

1. k값이 작을 때 (k=1) #

  • 장점: 지역적 패턴을 잘 포착, 복잡한 결정 경계 형성 가능
  • 단점: 노이즈에 민감, 과적합 위험

2. k값이 클 때 #

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

3. 최적 k값 선택 방법 #

  • 교차 검증: 다양한 k값으로 성능 평가
  • 홀수 선택: 이진 분류에서 동점 방지
  • 일반적 규칙: k = √n (n은 훈련 데이터 수)

k-NN의 장점 #

  1. 단순성: 이해하기 쉽고 구현이 간단
  2. 모델 가정 없음: 데이터 분포에 대한 가정이 불필요
  3. 다중 클래스: 자연스럽게 다중 클래스 분류 지원
  4. 지역적 패턴: 지역적인 패턴을 잘 포착
  5. 비선형 분류: 복잡한 비선형 결정 경계 형성 가능
  6. 온라인 학습: 새로운 데이터 추가가 쉬움
  7. 해석 가능성: 예측 근거를 명확히 제시 가능

k-NN의 단점 #

  1. 계산 비용: 예측 시마다 모든 데이터와 거리 계산 필요
  2. 메모리 사용량: 모든 훈련 데이터를 메모리에 저장
  3. 차원의 저주: 고차원에서 거리 개념이 무의미해짐
  4. 스케일 민감성: 특성들의 스케일에 민감
  5. 불균형 데이터: 다수 클래스에 편향될 수 있음
  6. 경계 결정: 클래스 경계 근처에서 불안정

차원의 저주 (Curse of Dimensionality) #

고차원 공간에서 k-NN이 직면하는 주요 문제이다:

1. 거리의 의미 퇴색 #

  • 모든 점들이 비슷한 거리를 가지게 됨
  • 가장 가까운 이웃과 가장 먼 이웃의 거리 차이가 줄어듦

2. 데이터 희소성 #

  • 고차원에서는 대부분의 공간이 비어있음
  • 의미 있는 이웃을 찾기 어려움

3. 해결 방법 #

  • 차원 축소: PCA, t-SNE 등을 통한 차원 축소
  • 특성 선택: 중요한 특성만 선별
  • 지역적 민감 해싱: 근사 최근접 이웃 알고리즘 사용

성능 최적화 기법 #

1. 효율적인 이웃 탐색 #

1) kd-tree

  • 공간 분할 트리 구조
  • 저차원(일반적으로 10차원 이하)에서 효과적
  • O(log n) 시간 복잡도

2) Ball tree

  • 구형 영역으로 공간 분할
  • 고차원에서도 상대적으로 효과적
  • 다양한 거리 함수 지원

3) LSH (Locality Sensitive Hashing)

  • 유사한 데이터를 같은 해시 버킷에 매핑
  • 매우 큰 데이터셋에서 근사 이웃 탐색
  • 정확도와 속도의 트레이드오프

2. 데이터 전처리 #

1) 특성 스케일링

# StandardScaler 사용 예시
from sklearn.preprocessing import StandardScaler
scaler = StandardScaler()
X_scaled = scaler.fit_transform(X)

2) 특성 선택

  • 상관관계 분석을 통한 중복 특성 제거
  • 분산이 낮은 특성 제거
  • 도메인 지식을 활용한 특성 선택

3. 가중치 적용 #

거리에 따른 가중치를 적용하여 성능을 개선할 수 있다:

1) 거리 기반 가중치

$$w_i = \frac{1}{d_i + \epsilon}$$

2) 가우시안 가중치

$$w_i = \exp\left(-\frac{d_i^2}{2\sigma^2}\right)$$

클래스 불균형 처리 #

1. 가중치 투표 #

각 클래스의 빈도에 반비례하는 가중치 적용

2. 샘플링 기법 #

  • 오버샘플링: SMOTE, ADASYN 등
  • 언더샘플링: 다수 클래스 데이터 감소

3. 거리 기반 보정 #

클래스별 평균 거리를 고려한 보정 방법

실제 적용 예시 #

1. 추천 시스템 #

  • 사용자 기반 협업 필터링
  • 아이템 기반 협업 필터링
  • 유사한 사용자/상품을 찾아 추천

2. 이미지 분류 #

  • 간단한 이미지 분류 작업
  • 픽셀 값이나 특성 벡터 기반 분류

3. 텍스트 분류 #

  • 문서 유사도 기반 분류
  • TF-IDF 벡터 간 코사인 유사도 활용

4. 이상치 탐지 #

  • 정상 데이터와의 거리 기반 이상치 탐지
  • LOF(Local Outlier Factor) 알고리즘

변형 알고리즘 #

1. 가중 k-NN (Weighted k-NN) #

거리에 반비례하는 가중치를 적용한 투표

2. 적응적 k-NN (Adaptive k-NN) #

지역별로 다른 k값을 사용

3. 퍼지 k-NN (Fuzzy k-NN) #

각 클래스에 대한 소속 정도를 확률로 표현

4. 압축 k-NN (Condensed k-NN) #

중요한 데이터 포인트만 선별하여 저장 공간 감소

성능 평가 및 검증 #

1. 교차 검증 #

  • k-fold 교차 검증으로 k값 선택
  • 시계열 데이터의 경우 시간 순서 고려

2. 그리드 서치 #

  • k값과 거리 함수의 조합 탐색
  • 가중치 방법과 전처리 방법 조합

3. 학습 곡선 분석 #

  • 훈련 데이터 크기에 따른 성능 변화 관찰

다른 알고리즘과의 비교 #

vs 나이브 베이즈 #

  • k-NN: 지역적 패턴, 모델 가정 없음
  • 나이브 베이즈: 전역적 모델, 독립성 가정

vs 결정 트리 #

  • k-NN: 부드러운 결정 경계, 해석 어려움
  • 결정 트리: 명확한 규칙, 계층적 구조

vs SVM #

  • k-NN: 인스턴스 기반, 지역적 결정
  • SVM: 마진 기반, 전역적 최적화

구현 시 고려사항 #

1. 메모리 관리 #

  • 큰 데이터셋의 경우 메모리 사용량 최적화
  • 배치 처리나 스트리밍 방식 고려

2. 병렬화 #

  • 거리 계산을 병렬로 처리
  • 멀티코어 활용으로 성능 향상

3. 캐싱 #

  • 자주 사용되는 거리 계산 결과 캐싱
  • 메모리와 속도의 트레이드오프 고려

최근 발전 동향 #

1. 딥러닝과의 결합 #

  • 딥러닝으로 학습된 특성 공간에서 k-NN 적용
  • 표현 학습과 k-NN의 조합

2. 그래프 기반 k-NN #

  • 데이터를 그래프로 모델링
  • 그래프 구조를 고려한 이웃 탐색

3. 온라인 k-NN #

  • 스트리밍 데이터에 대한 실시간 k-NN
  • 점진적 학습과 망각 메커니즘

k-NN은 단순하지만 매우 강력한 알고리즘으로, 특히 지역적 패턴이 중요한 문제나 복잡한 결정 경계가 필요한 경우에 유용하다. 다만 대용량 데이터나 고차원 데이터에서는 성능과 효율성을 고려하여 적절한 최적화 기법을 적용해야 한다. 또한 특성 스케일링과 적절한 k값 선택이 성능에 미치는 영향이 크므로 신중하게 튜닝해야 한다.

  • Languages