k-최근접 이웃(k-Nearest Neighbor, kNN)

kNN 알고리즘은 데이터 분류에 사용되는 아주 간단한 지도학습 알고리즘이다.
 

kNN의 이해

 
kNN 알고리즘은 주변 데이터에게 물어봐서 현재 데이터가 무엇인지 판단하는 알고리즘이라고 할 수 있다. 구체적으로 말하면 기존의 데이터 안에서 현재 데이터로부터 가까운 k개의 데이터를 찾아 k개의 레이블 중 가장 많이 분류된 값으로 현재의 데이터를 분류하는 알고리즘이다.
 
예를 들어서 주변에 가장 가까이있는 5명에게 "여기는 강남일까요, 강북일까요?"라고 물어보는 상황을 생각해보자. 그리고 4명은 강남, 1명은 강북이라고 대답했다면 현재 위치는 강남이라고 판단할 수 있을 것이다. 바로 여기서 k가 5명을 가리키고 이 방법이 kNN 알고리즘이라 한다.
 
그렇다면 실제 데이터 간의 거리는 어떻게 알 수 있을까??
 
우선 대다수의 머신러닝 알고리즘에서 사용되는 공간, 벡터 공간이라는 개념을 알아야한다. 바로 이 벡터 공간의 축이 데이터의 특성으로 지정되어서 데이터 간의 거리를 계산할 수 있다.
 

다음과 같은 데이터가 있다면 "3점슛 성공 횟수", "블로킹 성공 횟수"가 벡터 공간의 축이 되는 것이다. x축, y축이 되는 것이라고 생각해도 되겠다.

선수 이름	3점슛 성공 횟수	블로킹 성공 횟수	선수 포지션
이정하	1	6	센터
유옥중	2	5	센터
오일두	2	7	센터
김제영	3	7	센터

그리고 다음과 같이 피타고라스의 정리를 적용하여 두 데이터 간의 거리를 계산할 수가 있는 것이다.

한 가지 주의할 점은 이진 분류를 할 때 과반수의 대답을 얻기 위해 k를 홀수로 지정하는 것이 좋다는 것이다.
 

kNN의 장ㆍ단점

 

장점

• 다음 머신 러닝 알고리즘보다 이해하기가 상당히 쉽다.
   
• 숫자로 구분된 속성에 우수한 성능을 보인다. 예를 들어 거리, 횟수, 점수와 같이 수치화된 데이터 대해서 높은 정확도를 기대할 수 있다.
   
• 별도의 모델 학습이 필요없다. kNN 알고리즘은 예측하는 시점에 모든 기존 데이터와의 거리를 계산하기 때문에 모델을 따로 학습시킬 필요가 없다. 이러한 특성을 "게으른 학습(lazy learning)"이라고도 한다. 게으른 학습은 데이터베이스의 실시간 데이터를 사용해야 할 때 유용하게 쓰인다.
   

단점

• 예측 속도가 느리다. 전체 데이터와의 거리 계산 때문에 느리다.
   
• 예측값이 지역 정보에 많이 편향될 수 있다. 왜냐하면 오직 가까운 이웃을 통해 예측하기 때문이다. 아무리 좋은 데이터가 있더라도 몇 개의 예외적인 데이터가 존재하면 틀릴 가능성이 높아진다.