[AI-14] 근접 영역 속에서 나를 찾도록 : k-Nearest Neighbors

k-NN 알고리즘(k-Nearest Neighbors)은 레이블이 지정되어 분류된 기존의 데이터 분포에 새로운 데이터를 배치시키면서 임의의 k값을 기준으로 근처에 위치한 데이터들이 갖는 레이블로 데이터를 분류하는 분류 방법이다. 일단은 레이블 개념이 등장하는 것부터 알 수 있듯이, 기본적으로 지도학습(Supervised Learning)에 속한다.

그런데 분류하는 방법은 위에서 설명한 바와 같이 비지도학습인 군집분석(clustering)과 유사한 방식을 취한다. 즉 특별히 어떤 학습을 거치지 않고 마치 군집화하듯이 데이터 간의 거리를 계산해 그 분포로 데이터를 파악하는데, 이러한 접근이 '비지도학습적'으로 느껴질 수 있어 비지도학습으로 분류하거나 준지도학습(Semi-supervised)으로 따로 보려는 접근도 있다. 물론 개념적으로는, 지도학습으로 보는 게 더 타당하다.

 

towardsdatascience (https://towardsdatascience.com/)

k-NN의 수행 방법은 서두에 언급한 바와 같이 데이터를 분포하고 적당한 k값을 정하는 것으로 진행되는데, 방법 자체는 간단하지만 실제 적용에 있어서는 많은 고민이 필요하다. 위의 도식에서도 보면 k를 3으로 하느냐 6으로 하느냐에 따라 새로운 데이터(빨간 점)의 분류가 달라지는데, 3인 경우 ClasseB가 우세하여 ClasseB로 분류되겠지만 6인 경우에는 반대로 ClasseA에 분류된다. 즉 아주 쉽고 단순한 알고리즘이지만 이 적정한 k값을 정하는 것이 성패를 좌우하게 되는데, 경험적으로는 '총 데이터 크기의 제곱근' 값이 사용된다. 전체 데이터의 크기를 반영하면서도 너무 크지 않은 값이라 분류에 적절하다고 생각되기 때문이다.

위의 예에서는 3과 6이 사용되었지만, 실제로는 짝수보다 홀수가 더 선호되는데, 짝수가 되면 동점 상황이 발생할 수 있기 때문이다. 6개의 이웃 중 3:3의 상황이 발생했을 때 이를 다시 분류하려면 거리 등의 개념이 추가로 계산되어야하고 단순히 거리 등의 개념으로 보완되는지를 다시 살펴야 한다. 홀수로 설정하면 이러한 문제들을 자연스럽게 회피할 수 있어 훨씬 효율적이다.