3. 확률 분포 추정 - 최근접 이웃 분류기(k-nearest neighbour(k-NN) classifier)

$\circ$ 최근접 이웃 추정과 유사하다.

$\circ$ 훈련집합 $X=\{(\mathscr x_1,t_1),\cdots,(\mathscr x_N,t_N)\}$이 주어져 있다. 훈련샘플중에 $w_i$에 속하는것의 개수를 $N_i$라 한다. 미지의 샘플 $X$를 분류하는 문제가 주어젔을때 $X$를 중심을 창을 씌우고 훈련샘플중 $k$개가 들어올때까지 창의 크기를 확장해 나간다. $k$개가 들어온 순간 창의 크기가 $h_{\mathscr x}$ 이면 창의 부피는 $h_{\mathscr x}^{d}$가 된다. 창안에 들어온 샘플중 $w_i$에 속하는 것의 갯수를 $k_i$라 한다.

$k$ : 창안에 들어와야 할 샘플의 수

$h_{\mathscr x}$ : $k$개가 들어온 순간 창의 크기

$h_{\mathscr x}^{d}$ : 창의 부피

$k_i$ : 창안에 들어온 샘플 중 $w_i$에 속하는 것의 갯수

이제 베이스 공식을 구성하는 확률을 아래처럼 적을 수 있다.

$\displaystyle p(\mathscr x|w_i)=\cfrac{k_i}{{h_{\mathscr x}}^{d}N_i}$

$\displaystyle p(w_i)=\cfrac{N_i}{N}$

$\displaystyle p(\mathscr x)=\cfrac{k}{{h_{\mathscr x}}^{d}N}$

$\displaystyle p(w_i|\mathscr x)=\cfrac{p(\mathscr x|w_i)p(w_i)}{p(\mathscr x)}=\frac{k_i}{k}$

위 식을 이용하여 아래와 같은 $k-NN$ 분류기를 만들 수 있다.

$$\left. \begin{array}{l l} k-NN\;classifier: &\mathscr x를\;w_q로\;분류하라.\\& 이때\;q=\underset{i}{argmax}\;k_i\end{array} \right\}$$

위식의 뜻은 훈련샘플중에서 $\mathscr x$에 가장 가까운 $k$개를 구하고 그들이 가장 많은 빈도를 보인 부류로 분류하라는 것이다.

위 그림은 $3-NN$ 분류기의 작동 방식을 보여준다. 파란색과 하늘색 2개의 부류가 존재하며 $\mathscr x$에 가장가까운 샘플 3개중 빈도가 가장 높은 부류는 파란색이므로 $\mathscr x$는 파란색으로 분류한다.

 

이러한 규칙을 가상 코드로 쓰면 아래와 같다.

라인1을 구현하기 위해선 가까운 샘플을 찾기 위한 거리척도가 있어야 한다. 이는 유클리디언거리나 마할라 노비드 중에서 적당한것을 쓰면된다. 모든샘플을 조사할 경우 시간복잡도가 $\Theta(kdN)$이므로 탐색시간을 줄이기 위한 대책이 필요하다. $N$을 줄이는 방법과 특징공간을 미리 분할하는 방법이 있으며 후자의 경우는 보르노이도형을 이용한다. 효율적인 계산법은 아래 논문을 참고할것

J. McNames, "A fast nearest-neighbor algorithm based on a principal axis search tree," IEEE transactions on Pattern Analysis and Machine Intelligence, Vol.23 No.9, pp.964~976, 2001.

 

 $N \rightarrow \infty$인 경우 $1-NN$ 분류기의 오류 확률 $E_{1-NN}$은 베이시언 분류기의 오류확률 $E_B$에 대하여 아래와 같은 범위에 있다.

$E_B \leq E_{1-NN} \leq 2E_B$

$\displaystyle E_B=\frac{1}{2}\left( \int_{-\infty}^{t}p(\mathscr x|w_2)d \mathscr x + \int_{t}^{\infty} p(\mathscr x|w_1)d \mathscr x\right)$

즉, 베이시언 분류기가 최적인 점을 감안하면 아주 괜찮은 성능임을 알 수 있다. 물론 $N \rightarrow \infty$이어야 하며 이는 실제적으로 충분히 큰 $N$인 경우에 우리가 앞서 추정한 $p(\mathscr x|w_i),p(w_i),p(\mathscr x),p(w_i|\mathscr x)$ 확률이 실제 확률과 같아짐을 기대할 수 있다는 뜻이다.

아래는 $k>1$ 일 경우의 오류확률이다.

$\displaystyle E_B \leq E_{k-NN} \leq E_B + \sqrt{\frac{2E_{1-NN}}{k}}$