[AI] K-Nearest Neighbors

Parametric vs Non-Parametric Models

Parametric

• data가 특정한 가우시안 분포를 따른다고 가정하자.
• 고정된 크기의 parameter들의 data 분포를 학습한다.
  • training model의 parameter 수는 data가 늘어나도 고정되어 있다.

Non-Parametric Models

• data 분포를 모델링 할 때 어떠한 가정도 하지 않는다.
• training data을 보관한 것을 기반으로 학습한다.
  • parameter의 수는 training data의 양에 따라 늘어난다.
  • 데이터가 특정 분포를 완벽하게 따르지 않는 경우 더 유연하고 적합하다.

K-Nearest Neighbors

비슷한 point들은 비슷한 label로 모인다.

• x의 k nearest neighbor들을 $S_x$로 정의한다.
• $S_x$는 $S_x \subseteq D$, $|S_x| = k$로 정의된다. 이때 D는 전체 point

Distance Measure

거리를 측정하는 방법은 다양한 방법이 있지만 Minkowski distance을 알아본다.
$dist(x, z) = (\sum_{r=1}^d|x_r-z_r|^p)^\frac{1}{p}$
다음과 같이 나타낸다.

• p = 1 (Manhatttan Distance ($l_1$-norm))
  $dist(x, z) = \sum_{r=1}^d|x_r-z_r|$
• p = 2 (Euclidean Distance ($l_2$-norm))
  $dist(x, z) = \sqrt{\sum_{r=1}^d|x_r-z_r|^2}$

Choosing the Hyperparameter K

k의 값이 증가할 수록 variance는 감소하지만, bias는 증가한다. (high training error, but low test error) 즉, underfitting이 발생한다.
k의 값이 감소할 수록 variance는 증가하지만, bias는 감소한다. (low training error, but high test error) 즉, overfitting이 발생한다.
이산적인 k의 값은 다음과 같다. $k \lt \sqrt{N}$

Scale and Normalization

만약 어떤 feature가 큰 범위를 가진다면, 중요한 정보를 다룬다. 하지만 Euclidean distance는 모든 dimension에 대해 동등한 scale을 가져야 한다. 이를 위해 normalizing scale을 가져야 한다. 이는 [0, 1]의 범위를 갖는다. 이때 공식은 다음과 같다. $\frac{(x_i - \mu)}{\sigma}$

Curse of Dimensionality