KNN

K-최근접이웃(K-Nearest Neighbor, KNN) 알고리즘

출저: 블로그 https://ratsgo.github.io/ 내 다음 글 기반으로 요약 정리 하였습니다.

https://ratsgo.github.io/machine%20learning/2017/04/17/KNN/

K-Nearest Neighbor Algorithm · ratsgo's blog

---

KNN 이란

• 새로운 데이터가 주어졌을 때 기존 데이터 가운데 가장 가까운 k개 이웃의 정보로 새로운 데이터를 예측하는 방법론
• k값에 따른 classification(분류) 기법 (if k=1 then 녹색, if k=2 then 파란색)
• 학습 절차가 없어, 모델을 별도로 구축하지 않음. 새로운 데이터가 들어왔을 때, 그제야 기존 데이터 사이의 거리를 재서 이웃들을 뽑음 → 게이른 모델(Lazy model) 또는 Instance-based Learning 이라고도 함
• 데이터로부터 모델을 생성해 과업을 수행하는 Model-based learning과 대비되는 개념
• 별도 모델 생성과정 없이 각각의 관측치(instance)만을 이용하여 분류/회귀 등 과업을 수행

KNN의 하이퍼파라메터(Hyper parameter)

•  탐색할 이웃 수(kk), 거리 측정 방법
• k가 작을 경우 데이터의 지역적 특성을 지나치게 반영(overfitting) (경계가 너무 복잡해짐)
• k가 매우 클 경우 모델이 과하게 정규화되는 경향이 있음(underfitting). (경계가 너무 단순해짐)

 

거리 지표

Euclidean Distance

가장 흔히 사용하는 거리 척도. 두 관측치 사이의 직선 최단거리

 

Manhattan Distance

A에서 B로 이동할 때 각 좌표축 방향으로만 이동할 경우에 계산되는 거리

 

그 외 출저의 블로그 참조..

Mahalanobis Distance, Correlation Distance, Rank Correlation Distance

 

Best K 찾기

Best K는 데이터마다 다르기 때문에 탐욕적인 방식으로 찾아야 함

→ k를 1부터 10까지 1씩 증가시키면서 오분류율을 점검하여 그 결과 best K는 7로 확인 됨

 

KNN 수행시 주의점

KNN 수행 전 반드시 변수를 정규화(Normalization)해 주어야 함

 

KNN의 장단점

Pros

1. 학습데이터 내에 끼어있는 노이즈의 영향을 크게 받지 않으며 학습데이터 수가 많다면 꽤 효과적인 알고리즘이다.
2. 마할라노비스 거리와 같이 데이터의 분산을 고려할 경우 매우 강건(robust)한 방법론으로 알려져 있다.
3. 네이버, 카카오 등 현업에서도 KNN을 두루 사용하고 있는 것으로 전해진다.
4. kk가 1인  1-NN에 한해서는 모델 성능을 어느 정도 보장할 수 있다.

Cons

1. 최적 이웃의 수(k)와 어떤 거리척도가 분석에 적합한지 불분명해 데이터 각각의 특성에 맞게 연구자가 임의로 선정해야 한다.
2. 새로운 관측치와 각각의 학습 데이터 사이의 거리를 전부 측정해야 하므로 계산 시간이 오래 걸리는 한계점이 존재한다.