K Nearest Neighbors - Classification

K Nearest Neighbors - Classification

Unseen Data가 들어 오면, Traning Data를 그대로 사용하여 majority voting을 통해서 class를 결정하는 방법을 말한다.

구현을 위해서 필요한 사항

1) 트레이닝 데이터들을 모두 보관한다.

2) Distance Metric을 사용하여 Unknown record와의 거리를 계산 한다.

3) k개의 neighbor와 반복해서 Distance를 계산 한다.

4) 최종적으로 Majority voting을 통해서 prediction 한다.

입력된 테스트 데이터 (x', y')과 Traning Data (x,y)와의 distance 또는 Similarity를 계산 한다.

그다음 nearest - neighbor list로 구성된 D_z가 발견되면, D_z 내에서 majority voting을 통해서 class를 파악 한다.

Majority voting 방법은 아래와 같다.

위 식에서 

v는 + 또는 -와 같은 어떤 class label을 나타냄.

y_i는 nearest neighbors의 class label이다. 

I() 함수는 true 이면 1을 아니면 0을 return하는 indicator 이다.

 

위와 같은 경우 아래와 같이 된다.

  

는 최대가 되는 argument 즉, v를 return 하는 것이다.

K-NN의 특징

---

결국 Distance metric을 이용해서 nearest neighbor를 계산하는 방법이기 때문에 Distance metrix에 다분히 의존적인 방법이다.

보통 사용하는 Distance Metric은 아래와 같다.

위 Metric 중에서 우리가 Euclidean을 사용 한다면, 아래와 같은 문제점이 생길 수 있다.

□ Scaling issues: Distance measure를 사용 하므로 이러한 문제가 발생 한다.

모든 크기를 0~1 사이로 맞추는 방법을 사용할 수있다.

Mahalanobis distance를 사용하는것이 해결 방법이 될 수도 있다.

□ High Dimensionality: curse of dimensionality

위와 같이 2개의 Euclidean measure는 동일한 값을 나타낸다.

하지만,

0은 의미 없는 값이라고 했을 때 0이 많다고해서 두개가 유사한것은 문제가 된다.

이것을 보정하기 위해서 vector의 길이로 각각을 나누어 준다.

첫번째 vector의 length = 

두 번째 vector의 length = 

이것으로 각각을 계산하면

□ Laze Learner의 방법

명시적으로 model을 생성하지 않으므로 상대적으로 online prediction time이 길어 진다.

performance에 영향을 주는 factors

Distance metric의 종류

K의 수를 얼마로 정할 것인가 이다.