kNN

feature space에서 거리가 가장 가까운 k개를 찾고

이들의 평균값으로 y'을 예측

"즉, 지도학습임"

k-means는 비지도학습이며, clustering을 수행

 

predictor f(x')

        |𝜙(x) - 𝜙(x')|의 min을 찾기

 

• 훈련이 필요 없음 – 즉, lazy model
  • SVM 혹은 선형회귀보다 빠름
• 거리 구하기
  • 1) Euclidean distance
    • sqrt(∑ (p1i – p2i)^2)
  • 2) Manhattan distance
    • ∑ | p1i – p2i |

 

예측 방법에서 가장 ideal

성능면에서 kNN이 잘 설계 되어 있다면 이보다 더 좋을 순 없음

이 경우 DNN 을 사용할 필요가 없음

DNN은 이를 흉내

 

kNN 특징

non-linear를 다 근사

prediction의 boundary가 Voronoi diagram 형태 (성당의 유리창 그림)

k가 늘수록 boundary가 smooth 해짐

 

kNN 문제

1) prediction time

training time이 없음

그런데, prediction time이 많음

 

30만개의 데이터를 가지고 prediction 수행

즉, 느림

 

DNN은 traingin을 통해 KNN이 하고자 하는 것을 수행

training time이 걸리지만, prediction time이 거의 없음

 

2) feature space

feature space를 직접 design 해야 함

|pi(x) - pi(x')|  <- 유사도를 학습하는 것이 어려움

유사도를 학습하는 matrix을 학습