[머신러닝 3강] Supervised Learning(2)

1. K-NN Classifier

비모수 밀도 추정에 기반한 방법

• 확률분포모델을 미리 가정하지 않고 데이터 집합을 이용하여 확률밀도함수를 표현
• 새로운 데이터 x가 주어졌을 때
  • 이웃한 k개의 학습 데이터를 찾음
  • 찾아진 이웃들이 많이 속한 클래스로 할당
• 모든 학습데이터를 저장

비모수밀도추정 (Non-Parametric Density Estimation)

$p(x|C_i) = \frac{1}{V_i(x)}\frac{K}{N}$

• $V_i(x)$
  • $C_i$에 속하는 데이터들 중에서
    x에서 k번째로 가까운 데이터 $x^i_k$까지의 거리를
    반경 $r_i(x)$으로 하는 초구 (hypershpere)

결정 규칙

• $y(x) = argmin_i(r_i(x))$

K=1인 K-NN Classifier

• $y(x) = argmin\{r1, r2\} = 1$ 이라면,
  • $x \in C_1$

일반화

• $x_{min} = argmin_{x_i \in X}\{d(x, x_i)\}$
  • 모든 데이터 집합 $X$에 대하여,
    새로 들어온 데이터와 학습데이터의 거리 d 중 최소값을 갖는 데이터
• $y(x) = y(x_{min})$

수행 단계

• 주어진 데이터 $x$와 모든 학습 데이터 $\{x_1, x_2, ...x_N\}$과의 거리를 계산

• 거리가 가장 가까운 데이터를 찾아 $x_{min}$으로 둔다.

  • $x_{min} = argmin_{x_i \in X }\{d(x, x_i)\}$

• $x_{min}$이 속하는 클래스에 할당한다.
  즉, $y(x_{min})$과 같은 값을 가지도록 $y(x)$를 결정한다.

  • $y(x) = y(x_{min})$

만약 noise가 있다면,
해당 noise에 영향을 받기가 너무 쉽다는 특성을 가지게 된다.

문제점

• 학습데이터에 대하여 Overfitting될 가능성이 있다.

2. K-NN vs Gausian

K-NN

• 비모수적 밀도 추정 방법에 기반
• 새 데이터가 주어질 때마다 학습 데이터 전체와의 거리 계산 필요
  • 항상 학습 데이터 저장 -> 비용 문제 (계산량, 메모리, CPU 등) 초래

가우시안

• 모수적 밀도 추정 방법에 기반
• 학습데이터로 평균과 표준편차만 계산하여 활용
  • 분류 과정에서 학습데이터가 불필요

3. K-NN 설계 고려 사항

• 적절한 K값의 설정
• 거리 함수

적절한 K값의 설정

• $K = 1$

  • 바로 이웃한 데이터에만 의존하여 클래스가 결정
    • 데이터의 noise에 민감하고 과다적합 발생

• $K >> 1$

  • 주어진 데이터 주변 영역이 아닌 전체 데이터 영역에서
    각 클래스가 차지하는 비율( 선험확률, 사전확률 )에 의존하게 된다.

• 주어진 데이터 분포 특성에 의존

  • 데이터를 활용한 분류를 통해 가장 좋은 성능을 주는 값을 선택.

거리 함수

주어진 데이터화 학습 데이터 간의 거리 계산

• 유클리디안 (2차 노름)
• 맨하튼 거리 (1차 노름)
• p차 노름
• 내적
• 코사인 거리
• 정규화된 유클리디안 거리
• 마할라노비스 거리