[8] K-최근접 이웃(KNN) 이해하기

KNN

KNN은 전형적인 게으른 학습기(Lazy learner)에 속한다. 즉, 훈련데이터에서 판별함수를 학습하는 대신 훈련 데이터셋을 메모리에 저장하여 학습을 진행한다. 덕분에 학습 과정에서 비용이 전혀 들지 않는다. 대신 예측 단계에서의 계산 비용이 높다.

 

메모리 기반 방식의 분류기는 수집된 새로운 훈련 데이터에 즉시 적응할 수 있다는 장점이 있다. 하지만 대규모 데이터 셋에서 작업한다면 저장 공간에 문제가 생길 수 있다.

 

 

 

모수 모델과 비모수 모델

모수 모델은 새로운 데이터 포인트를 분류할 수 있는 함수를 학습하기 위해 훈련 데이터셋에서 모델 파라미터를 추정(타깃을 예측)하는 모델을 말한다. 대표적인 모수 모델에는 퍼셉트론, 로지스틱 회귀, 선형 SVM이 있다.

 

비모수 모델은 고정된 개수의 파라미터로 설명될 수 없는 모델을 말한다. 훈련 데이터가 늘어나면 파라미터의 개수도 늘어난다. 대표적인 비모수 모델에는 의사결정나무와 랜덤포레스트, 커널 SVM(비선형)이 있다. KNN 또한 여기에 속한다.

 

추가적으로 KNN은 인스턴스 기반 모델로 분류된다. 인스턴스 모델은 훈련 데이터셋을 메모리에 저장하는 것이 특징이다. 게으른 학습은 인스턴스 기반 모델에 속한다.

 

 

KNN알고리즘 학습 과정
1. 숫자 k와 거리 측정 기준을 선택한다.

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

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

 

학습과정에서 알 수 있듯이 KNN알고리즘을 학습하기 위해선 'K'와 '거리 측정 기준'만 지정해주면 된다. 일반적으로 거리 측정 기준은 '유클라디안 거리'를 사용한다.

맨해튼 거리 : \( \sum_{i=0}^{n}|p_i - q_i| \)

유클라디안 거리 : \( \sqrt{ \sum_{i=0}^{n}(p_i - q_i)^2 }  \)

민코우스키 거리 : \( _p\sqrt{ \sum_{k}|x_{k}^{i} - x_{k}^{i}|^p }  \) 

* 민코우스키 거리는 p가 1일 때, 맨해튼 거리가 되고 p가 2일 때 유클라디안 거리가 된다.

 

해당 측정 방식을 사용하기 이전에 각 특성이 동일하게 취급되도록 표준화를 해주는 과정이 매우 중요하다. 특성 간의 스케일이 차이나면 스케일이 큰 것이 매우 중요한 특성으로 여기게 되기 때문이다. 

 

 

KNN의 장점

- 메모리 기반의 학습 알고리즘이기에 수집된 데이터를 바로 적응시킬 수 있다.

- 학습 과정에 비용이 전혀들지 않는다.

 

 

KNN의 단점

- 대용량 데이터셋의 경우 저장 공간에 문제가 발생할 수 있다.

- 표준화하지 않은 데이터 셋으로 학습할 경우 학습이 제대로 이루어지지 않을 가능성이 높다.

- 학습 데이터의 수보다 특성이 많은 경우 *차원의 저주에 걸려 과대적합되기 쉽다.

* 차원의 저주 : 고정된 크기의 훈련 데이터 셋이 차원이 늘어남에 따라 특성 공간이 점점 희소해지는 현상

** 해당 현상을 방지하기 위해 주로 '특성 선택' 및 '차원 축소 기법'을 사용해 해당 알고리즘을 학습한다.