[머신러닝 12-1주차] K-NN(K-Nearest Neighbor) 알고리즘

📌 K-NN 알고리즘이란?

K-NN 알고리즘은 지도학습 중 분류(classification) 알고리즘입니다.

비슷한 특성(피쳐)를 가진 데이터는 비슷한 범주(label)에 속한다는 아이디어를 토대로,
주변의 가장 가까운 K개의 데이터를 보고 데이터가 속하는 그룹을 판단하는 알고리즘입니다.

어떤 z라는 데이터가 주어졌다고 가정하여 봅시다.

K-NN의 작동원리는 거리를 기반으로 가장 가까운 K개의 훈련 데이터 포인트들을 찾고, majority vote(과반수)를 이용하여 분류하는 작업입니다.
즉 K개의 이웃을 이용하여 분류 해주는 알고리즘입니다.


K-NN 알고리즘은 훈련 데이터 셋을 만들어서 비용이 저렴한(cheap training) 알고리즘이라고도 불리우는데요.

훈련 데이터를 그대로 가지고 있어 특별히 다른 훈련을 하지 않기 때문에 훈련 단계가 매우 빠르게 수행됩니다.

특정 모델을 생성하지 않기 때문에, 변수와 클래스 간의 관계를 파악하고 있어야 이를 적용할 수 있습니다.

데이터가 많아지면 모든 훈련 예시에 대한 모든 거리들을 계산해야 하므로 많은 비용과 공간할당이 필요합니다. 분류 단계가 느려지는 한계도 존재합니다.

'이웃'을 판단하는 기준으로는 다음과 같은 3개의 기준을 이용합니다.

1. 거리 기반(distance-based)
   • 유클리드 거리(Euclidean distance)
   • 맨해튼 거리(Manhattan distance)
   • 민코스키 거리(Minkowski distance)
   • 체비시브 거리(Chevyshev distance)
2. 유사도 기반(similarity-based)
   • 코신
3. 기타

K-NN 알고리즘의 구현 방법

---

Step 1. 특성들(feature)에 대하여, $\mu = 0$ , $\sigma^2 = 1$ 로 가우시안 분포 형태로 normalize 시킵니다.

Step2. 훈련 인스턴스에 가장 '가까운' K개의 예시들을 찾습니다.

Step3. 과반수 클래스로서 나온 분류 결과값을 도출합니다.

$\hat{y}= \argmax\sum_{\substack{i=1 ~to~k}}I(y_z=y_i)$
- $y_z$ = 훈련 데이터 $x_z$의 결과값(레이블)
- $y_i$ = 가장 가까운 K개의 이웃의 결과값(레이블)

K값을 정해보자!

K값이 작아질수록, 예측의 정확도가 높아지므로 낮은 bias를 보이나 노이즈가 그대로 반영되어 높은 variance를 보입니다.(error rate = 0)
반면 K값이 커질수록, 예측의 정확도는 낮아져 높은 bias를 보이고 노이즈는 반영되지 않아 낮은 variance를 보입니다.(resillent to outliers)