K Nearest Neighbor.

Presentation on theme: "K Nearest Neighbor."— Presentation transcript:

1 K Nearest Neighbor

2 ML의 주요 기법 KNN Linear Model SVM Kernel Trick Decision Tree Ensemble

3 K Nearest Neighbor X의 값으로 Y를 예측할 때 기존 데이터에서 X가 가장 비슷한 데이터(NN) k개를 찾는다
local method의 일종

4

5

6

7

8

9 N = 30 K = 1

10 N = 30 K = 5

11 N = 1,000 K = 100

12 True Model vs. kNN

13 kNN의 장점 간단하고 직관적 특별한 수학적/통계적 가정이 필요 없음 모형 적합 과정이 필요 X
전체 데이터가 많고(N  ∞), 이웃이 많고(k  ∞), 이웃이 전체 의 일부라면(k/N  0) 정확도 높음

14 knn의 단점 과적합(overfitting)의 위험성이 큼 주변부로 가면 왜곡되는 경향 거리를 계산하는 비용이 큼
이산 변수의 거리

15 Bias-Variance 문제 𝑀𝑆𝐸 =𝐸 𝑦− 𝑦 2 =𝐸 𝑦 2 −2 𝑦 𝑦+ 𝑦 2 = 𝑦 2 −2𝑦𝐸( 𝑦 )+𝐸 𝑦 2 = 𝑦 2 −2𝑦𝐸 𝑦 + 𝐸 𝑦 2 +𝐸 𝑦 2 − 𝐸 𝑦 2 = (𝑦−𝐸 𝑦 ) 2 +𝑉𝑎𝑟 𝑦 = 𝐵𝑖𝑎𝑠( 𝑦 ) 2 +𝑉𝑎𝑟 𝑦

16 Bias-Variance 문제 오차(Error) = 편향(Bias)2 + 분산(Var)

17 차원의 저주 길이 10인 선에서 가운데 9가 차지하는 비율  90%
10x10인 사각형에서 가운데 9x9인 사각형의 비율  81% 10x10x10인 정육면체에서 가운데 9x9x9…의 비율  약 73% 차원이 커질 수록 껍질이 두꺼워진다

18 NN과 차원의 저주 중심부에 데이터가 적어짐 주변부에는 데이터가 많아짐
중심부에서는 이웃끼리 멀어짐  분산 증가  오차 증가 주변부에는 데이터가 많아짐 NN은 주변부에서 왜곡  편향 증가  오차 증가