K-Nearest Neighbor

Instance-Based Learning

• 이전의 관측결과로 데이터베이스를 구축
• 새로운 x값에 대한 예측결과를 내기 위해, x와 x의 아웃풋인 f(x)를 사용하여 가장 가까운 데이터베이스를 찾아냄
• target function에 위치적인 예측값을 제공

Instance-Based Learning을 위해선 거리를 측정하는 방법과 neighbors을 몇 개 사용할 것인지, 근사한 neighbors의 아웃풋들로 어떻게 새로운 아웃풋을 도출할것인지를 해결하는 게 필요하다

---

1-Nearest Neighbor

1. 거리 측정법 : Euclidean

2. neighbors의 갯수 : 1

3. Combining neighbors' outputs: N/A (Combining 할 필요 없이 가장 가까운 값 택)

1-NN 알고리즘은 (x, y) ... (xn, yn)까지의 traning data들이 주어지고 새로운 x값에 대한 y값을 도출한다

이를 위해 Euclidean 거리 측정방법을 사용하여 새로운 x값에 대해 가장 가까운 기존 x 데이터를 찾고 이 x값에 대한 y값을 새로운 x값에 대한 y값이라 가정한다

---

k-Nearest Neighbors

1. 거리 측정법 : Euclidean

2. neighbors의 갯수 : k

3. Combining neighbors' outputs: 

    1) Classification

       - majority vote(다수결)

       - 가중치가 부여된 다수결로, 가까울수록 영향력이 크다

    2) Regression

       - 실제값에 대한 평균

       - 가중치가 부여된 평균값으로, 가까울수록 영향력이 크다

 

좌) Classification 우) Regression

가장 가까운 neighbor을 찾는데에는 O(n)만큼의 시간이 걸리며, kd-trees를 이용하여 O(logn)으로 시간을 줄일 수 있다

 

knn 장점

1. knn은 이해하기에 간단하다
2. 다른 알고리즘의 베이스라인으로 종종 사용된다
3. training이 빠르다 -> 그저 새로운 아이템을 데이터베이스에 더하면 되니깐!
4. 높은 정확도, 데이터에 대한 가정이 없음

knn 단점

1. 쿼리시간에 대부분 작업들이 수행되어 계산비용이 많이 들 수 있음
2. 이후 작업을 위해 O(n)데이터를 저장해야함
3. 거리 측정 방법의 선택에 성능이 민감 (+ feature값들을 정규화시키는것도!)