2-2. k Nearest Neighbor (DEPRECATED)

안내 사항

이 시리즈는 더 이상 업데이트 되지 않습니다. 대신 새롭게 제 github 레포에 jupyter notebook을 기반으로 다시 정리하고 있습니다. 이 작업이 다 끝나고 스스로 이해한 것을 한글로 정리하게 될 때가 오기를 바랍니다.

---

주의

이 글의 내용은 Hastie, Tibshirani 등이 쓴 책 "The Elements of Statistical Learning"의 순서와 내용을 기반으로 정리한 글입니다. 따라서 잘못된 내용이 있을 수도 있으니 그럴 경우 제보해주시면 감사드리겠습니다.

이전 글

• 2-1. Least squares
  

k-Nearest-Neighbor (kNN)

이전 글에서 선형 모델로 맞추듯(fit), kNN을 통한 fitting \(\hat{Y}\)을 다음과 같이 나타낸다.

\[\hat{Y}(x)=\frac{1}{k}\sum_{x_j\in N_k(x)}y_j\]

여기서 \(N_k(x)\)는 \(x\)에서 가장 가까운 \(k\)개 데이터의 집합을 나타낸다. kNN은 사실 단어의 의미에서 바로 어떤 방법인지 직감이 올 수 있는 방법일 것이다. 가까운 것 찾는거지. (\(k=1\)일 때를 생각해보자) "가깝다"라는 것은 거리 개념을 필요로 하는데, 지금 여기서는 그냥 Euclidean distance를 쓴다. 그럼 지난 번에 썼던 그 데이터에 kNN을 적용한 decision boundary \(\lbrace x:\hat{Y}(x)=0.5\rbrace\)를 구경해보자.

k=1일 때의 decision boundary: 어떤 좌표를 집고, 거기서 가장 가까운 색을 칠하면 영역 표시가 된다. 선형 모델을 썼을 때보다 훨씬 못생겼다.

k=15일 때: 평균의 효과로 인해 위와 비교했을 때 훨씬 부드러운 경계가 생긴다.

\(k=1\)일 때의 decision boundary는 잘못 판단한 점이 하나도 없다는 사실에 전혀 기뻐해서는 안 될 것이다. 참고로 \(k=15\)일 때도 선형 모델을 썼을 때보다 오판률이 낮지만 이 역시 대단한 점은 아니다. 사실 \(k\)가 작을 수록 오판률은 반드시 줄어들고, 결국 \(k=1\)이 되면 오판률은 0이 된다. 지금까지의 fitting은 (선형 모델이든 kNN이든) 우리가 가지고 있는 데이터에만 맞춰진 모델이다. fitting이란 단어 자체에서도 그런 의미가 있다고 생각한다. fitting에 사용한 데이터 (training data) 외에 test data를 준비한다면, fitting 모델을 비교하는 데 도움이 될 것이다.

least squares를 이용한 선형 모델은 fitting을 위해서 \(p\)개의 parameter가 필요했었던 반면에, kNN은 단 하나의 parameter \(k\)를 갖고 있다. 하지만 kNN의 실제적인 parameter의 수(effective number of parameter)는 \(N/k\)이고 이 숫자는 보통 선형 모델에서의 \(p\)보다 크다는 것을 알아두자. 왜 \(N/k\)일까? 쉽게 생각해서 만약 neighbor들이 서로 겹치지 않는다고 가정 (하나의 포인트는 딱 하나의 neighbor에만 소속된다고) 하면, 가능한 neighbor의 개수는 \(N/k\)가 되고, 이 neighbor를 하나씩 이용해서 fitting이 계산될 것이다.

kNN은 \(k\)를 고르기 위해 least squares 기준을 사용할 수가 없다. 당연하게도, \(k=1\)일 때 항상 최고일테니까 -- 그리고 이게 최선의 결과가 아니라는 것은 모두가 아는 사실이다. 다음 글에서는 least squares와 kNN과의 관계성을 알아본다.