[Density Estimation]K-Nearest Neighbors Estimation과 Classification

• Parametic Methods(단순한 분포를 가정하고 유한한 파라미터를 구하자)
  • ML(Maximum Likelihood) Estimation
  • MAP(Maximum A Posteriori) Estimation
• Non-Parametic Methods(복잡한 분포를 가정하자)
  • 파젠창(Parzen Window)
  • K-Nearest Neighbor Estimation

 

 

 

---

 

 

K-Nearest Neighbors Estimation

 

 

파젠창에서는 h가 고정이고 그 안에 샘플 수 k는 가변적이었다.

 

 

이번에는 반대로 샘플 수 k가 고정, h가 변동되는 값이된다.

 

 

 

샘플의 위치 x를 중심으로 창을 씌우고 k개 샘플이 안에 들어올 때까지 h를 확장해나간다.

 

$$P_k(x) = \frac{1}{h(x)^d}\frac{k}{n}$$

$k$ : 창에 포함시킬 샘플 수

$n$ : total 샘플 수

$d$ : input dimension

 

그렇게 창의 크기 $h$가 클수록 듬성듬성 있다는 것이니 확률이 작아지고,

창의 크기가 작을수록 빽빽하다는 것이니 확률이 커진다.

 

 

그러나,

창 크기 조정을 위한 계산량이 $\theta(kdn)$으로 많은 편이다. 

 

 

그래서 실제 사용에서는 고속화를 위해 훈련집합에 따라 특징공간을 미리 여러 구간으로 나누어놓은

Voronoi Diagram을 사용한다.

 

 

 

---

 

 

K-Nearest Neighbors Classification

 

 

훈련집합 $X=\{(\mathscr x_1,t_1),\cdots,(\mathscr x_N,t_N)\}$가 있다. 정답이 있어 지도학습 알고리즘이다.

test로 샘플이 들어와 이를 분류해야할 때 어떻게 해야할까?

 

 

훈련 샘플에서 새로 들어온 test 샘플 x에 가장 가까운 k개를 찾는다.
그중 가장 많은 빈도를 보인 부류로 분류하라.

 

 

k가 들어온 순간 창의 크기가 $h(x)$, 창의 부피는 $h^d(x)$가 된다.

k개가 속한 class를 조사하여 가장 빈도가 높은 부류를 $\omega_i$라고 한다.

x를 $\omega_i$로 분류한다.

 

 

• 조건부확률(likelihood) $P(X \mid \omega_i) = \dfrac{k_i}{k_X^dN_i}$

 

• 사전확률 $P(\omega_i)=\dfrac{N_i}{N}$

 

• marginal $P(X) = \dfrac{k}{h_x^dN} $

 

• 사후확률 $P(w_i|\mathscr x)=\dfrac{P(\mathscr x|w_i)p(w_i)}{P(\mathscr x)}=\dfrac{k_i}{k}$

 

 

$P(x)$는 여기서 큰 의미를 갖지는 않는다.

$$ \hat{i}= \textrm{arg }\underset{1\leq i\leq c}{\textrm{max}}$$

 

	k	class
	3	B
	4	A
	5	A
	6	B
	7	A

 

k=3인 경우를 보자. 샘플을 3개을 묶어내고 각각의 클래스 샘플 개수를 조사하면

A class 1개, B class 2개다.

 

A<B이므로  ?  샘플은 B class에 해당한다!고 예상하는 것이다.

 

 

 

표를 보면 k값에 따라서 분류 결과가 달라진다.

그래서 k를 여러가지로 실험하여 최적의 class를 정한다.

k를 다섯 경우로 따져서 3개가 A가 나왔으므로  ?  샘플은 A class로 예측되겠다.