[데이터분석개론] K-Nearest Neighbors

K-Nearest Neighbors ( KNN )

 

• 말 그대로 최근접 이웃을 찾는 알고리즘이다.
• 지도학습의 한 종류로 거리기반 분류분석 모델이다.
• model-driven 한 모델이 아닌 data-driven 한 모델이다. 즉 데이터를 가지고 알아서 모델이 만들어지므로 식이 존재하지않는다.

 

 

K-NN 알고리즘은 유유상종 알고리즘인데,

예를들어 A라는 사람과 가장 가까운 속성을 가진 사람이 영웅이라면,

A도 영웅이겠지~ 하고 예측하는 방법이다.

 

즉 내가 구분하고 있는 데이터와 가장 가까운 곳에 있는 이웃이 누구냐 ? 를 보고 판단하는 방법이다.

 

그럼 가장 가까운 이웃은 수학적으로 어떻게 구할 수 있을까 ? 

바로 Euclidean Distance 를 사용한다.

 

 

Euclidean Distance

 

두 점 사이간의 거리 ( d ) 는

이렇게 표현할 수 있다.

 

만약 p개의 dimensions 이 존재하는 경우엔

이렇게 표현할 수 있다.

 

유클리드 거리를 구할때에도 PCA 처럼 normalization 을 꼭 한 후에 구해줘야한다.

예를들어 나이와 거리라는 feature 가 있을때 나이는 스케일이 작지만 거리는 스케일이 크기때문에 왜곡이 일어날 수 있기 때문이다.

 

Choosing K

 

K-NN 알고리즘에서 'K'는 그래서 내가 분류하고자 하는 데이터와 가까운 애를 몇명 찾을까 ? 에 관한 값이다.

 

K=1 인 경우, 단 한개의 가장 가까운 데이터를 찾아, 얘가 어떤 class에 들어있는지 보고 이 class로 똑같이 분류하면된다.

K=3  인 경우, 3개의 가까운 데이터를 찾아서 다수의 클래스가 어떤것인지 판단하고 이 class로 똑같이 분류한다.

 

이때 K는 항상 홀수로 결정한다. K를 짝수로 정하는경우엔 클래스 1 과 클래스 2의 갯수가 똑같이 나와서 어느쪽으로도 분류할 수가 없는 문제가 생기곤 하기 때문이다.

 

그럼 K는 어떻게 가장 적합하게 고를 수 있을까 ?

 

이건 정해진 답이 없기 때문에, K를 최대한 여러개를 대입해보고 가장 좋은 성능이 나오는것으로 결정해야한다.

 

k 값이 작은경우 : local structure 만 찾아낸다. 즉 범위가 너무 작기때문에 잘못된 결정을 내릴 가능성이 높아진다.

k 값이 큰 경우 : 단순히 데이터 갯수가 많은 클래스로 계속 분류해버리는 문제가 발생한다.

 

때문에 데이터에 맞는 적당한 K값을 선택해야하고, 이를 위해선 여러번의 테스트가 통해 가장 적합한 K를 선택해야한다.

 

 

K-NN 알고리즘의 장점

• simple 하다.
• 데이터가 어떻게 생겼는지에 대한 고민이 필요없다.

K-NN 알고리즘의 한계

• 가지고있는 데이터의 양이 적은경우엔 좋은 결과가 나오기 힘들다.