K-Nearest Neighbors (KNN) 및 서포트 벡터 머신(SVM) 개요

개요

• KNN: 학습 단계가 없고, 새로운 데이터가 들어오면 학습 데이터와의 거리를 계산해 가장 가까운 K개의 이웃을 찾고 다수결(또는 거리 가중)로 클래스를 결정한다.
• SVM: 데이터 포인트 간의 마진을 최대화하는 결정 경계를 찾는 모델로, 하드/소프트 마진과 커널 트릭을 통해 비선형 분류를 수행한다.

핵심 개념

• 거리 측정
  • 유클리디안 거리
  • 맨해튼 거리
  • 민코프스키 거리 (P값 조정)
• k 값 선택
  • 보통 √(학습 데이터 수) 기준, 홀수로 설정하여 투표 동률 방지
  • 교차 검증으로 최적 k 탐색
• 가중 투표
  • 단순 다수결 → 거리 가중(거리 가깝을수록 투표 가중치 증가)
• 스케일링
  • 거리 기반이므로 각 특성의 범위가 비슷해야 함
• 계산 복잡도
  • O(n·d) (n: 데이터 수, d: 차원) → 대규모 데이터 시 느림
• 트리 기반 가속
  • KD-트리, Ball-트리 등으로 검색 범위 축소
• SVM 핵심 요소
  • 결정 경계: 클래스 구분선
  • 마진: 경계와 가장 가까운 포인트까지 거리 × 2
  • 서포트 벡터: 마진 경계에 놓인 포인트
  • 하드 마진: 오분류 허용 없음
  • 소프트 마진: 오분류 허용, 정규화 파라미터 C 사용
  • 커널 트릭: 비선형 데이터에 대해 고차원 공간으로 매핑 없이 유사하게 동작

상세 노트

KNN 동작 원리

1. 새로운 샘플 xq가 들어오면 학습 데이터 전체와 거리를 계산
2. 거리 정렬 → 가장 가까운 k개의 이웃 선택
3. 클래스 확인 → 다수결(또는 거리 가중)으로 xq의 클래스 결정

중요: 학습 단계가 없으므로 모델 저장만 필요하지만, 예측 시 모든 데이터와 거리 계산이 필요해 대규모에서는 비효율적.

거리 계산 방법

• 유클리디안: √(∑(xi - yi)²)
• 맨해튼: ∑|xi - yi|
• 민코프스키: (∑|xi - yi|^p)^(1/p)
  • p=1 → 맨해튼, p=2 → 유클리디안

k 값 결정

• 일반적으로 k = √N (N: 학습 데이터 수)
• 홀수로 설정해 투표 동률 방지
• 교차 검증(Validation Set)으로 최적 k 탐색 → 테스트 세트로 최종 검증

가중 투표

• 가장 가까운 이웃에 높은 가중치를 부여
• 거리 가중: weight_i = 1 / distance_i (또는 거리의 역수)
• 다수결보다 더 정밀한 분류 가능

스케일링 및 차원

• 스케일링: Min-Max, Standardization 등으로 범위 통일
• 차원의 저주: 차원이 늘어나면 거리 계산이 무의미해짐 → 차원 축소(주성분분석 등) 필요

트리 기반 가속

• KD-트리, Ball-트리 등으로 검색 공간 절약
• Brute-Force: 모든 데이터와 거리 계산 → 가장 느림
• 트리 학습이 필요 → KNN이 아닌 “트리 학습 + KNN” 형태

SVM 기본 구조

• 결정 경계: 두 클래스 사이의 선(또는 하이퍼플레인)
• 마진: 경계와 가장 가까운 포인트까지의 거리 × 2
• 서포트 벡터: 마진 경계에 있는 포인트
• 하드 마진: 오분류 허용 없음 → 완벽히 분리 가능한 경우
• 소프트 마진: 오분류 허용 → 정규화 파라미터 C 조정

커널 트릭

• 비선형 분포를 선형 분류기로 처리하기 위해 고차원 공간에 매핑
• 실제로는 고차원으로 확장하지 않고 커널 함수를 사용해 내부적으로 계산
• 대표 커널: 선형, 다항식, RBF(Radial Basis Function)

Takeaway: KNN은 구현이 단순하고 비선형 데이터에 강하지만, 대규모 데이터에서는 느리고, SVM은 마진을 최대화해 일반화 성능이 뛰어나지만 파라미터 튜닝이 필요하다.

---