머신러닝 - 9. K-최근접 이웃 알고리즘(K-Nearest Neighbor, KNN)

k-NN 이란

 KNN이라고 줄여 부르는 K-최근접 이웃(K-Nearest Neighbor)은 지도 학습 알고리즘으로써, 분류나 회귀에 이용할 수 있는 비모수 모델(Nonparametric Model)이다. 이 알고리즘의 동작 원리는 매우 간단하다.

 

< 그림 1 - '?'로 표시된 미식별 데이터와 푸른색과 붉은색 클래스로 식별된 다른 데이터들 >

 

 위 그림 1을 예시로 들어 KNN 알고리즘에 대해 설명한다. 어떤 데이터들은 푸른색으로, 나머지 데이터들은 붉은색으로 클래스를 나눠 식별되었다. 그렇다면 현재 식별되지 않은, '?'로 표시된 데이터는 푸른색으로 식별해야 되는가, 붉은색으로 식별해야 되는가. 우리는 직관적으로 '?' 데이터는 푸른색 데이터일 것이라고 예측할 수 있다. 왜 그러한가?

 

 '?' 데이터 주위에 있는 데이터들이 모두 푸른색 데이터이기 때문이다. KNN은 바로 이러한 접근에서 출발하였다. KNN 알고리즘은 가장 가까운 몇 개의 데이터를 뽑아, 가장 그럴듯한 클래스로 예측한다. 이런 알고리즘의 특징 때문에, 다른 지도 학습 알고리즘의 모델들은 훈련 데이터를 통해 훈련을 시켜야하지만, KNN은 그저 훈련 데이터를 저장하기만 하면 된다.

---

KNN의 상세 동작과정

 KNN 알고리즘의 동작은 다음의 단계로 이루어진다.

 

1. 숫자 k와 거리 측정 기준 선택

2. 분류하려는 샘플에서 k개의 최근접 이웃을 탐색

3. 다수결 투표를 통해 클래스 레이블 할당

 

 일반적으로 숫자 k에는 동점이 나오지 않도록 홀수를 사용하는 것이 좋다. 이때, k = 1이라면 최근접 이웃 알고리즘이라 부른다. 거리 측정기준으로는 유클리드 거리나 맨해튼 거리를 이용한다.

---

KNN의 약점 및 보완

 앞서 설명했듯 KNN 알고리즘은 훈련 데이터를 저장하는 메모리 기반 방식이기 때문에 샘플의 수 데이터 셋의 특성이 많은 경우 계산 시간이 오래 걸리고, 고차원 데이터에서는 차원의 저주로 인해 과적합하여 제대로 동작하지 않을 수 있다. 이러한 단점을 보완하기 위해 차원 축소를 수행한다.