K Nearest Neighbor
ML의 주요 기법 KNN Linear Model SVM Kernel Trick Decision Tree Ensemble
K Nearest Neighbor X의 값으로 Y를 예측할 때 기존 데이터에서 X가 가장 비슷한 데이터(NN) k개를 찾는다 local method의 일종
N = 30 K = 1
N = 30 K = 5
N = 1,000 K = 100
True Model vs. kNN
kNN의 장점 간단하고 직관적 특별한 수학적/통계적 가정이 필요 없음 모형 적합 과정이 필요 X 전체 데이터가 많고(N ∞), 이웃이 많고(k ∞), 이웃이 전체 의 일부라면(k/N 0) 정확도 높음
knn의 단점 과적합(overfitting)의 위험성이 큼 주변부로 가면 왜곡되는 경향 거리를 계산하는 비용이 큼 이산 변수의 거리
Bias-Variance 문제 𝑀𝑆𝐸 =𝐸 𝑦− 𝑦 2 =𝐸 𝑦 2 −2 𝑦 𝑦+ 𝑦 2 = 𝑦 2 −2𝑦𝐸( 𝑦 )+𝐸 𝑦 2 = 𝑦 2 −2𝑦𝐸 𝑦 + 𝐸 𝑦 2 +𝐸 𝑦 2 − 𝐸 𝑦 2 = (𝑦−𝐸 𝑦 ) 2 +𝑉𝑎𝑟 𝑦 = 𝐵𝑖𝑎𝑠( 𝑦 ) 2 +𝑉𝑎𝑟 𝑦
Bias-Variance 문제 오차(Error) = 편향(Bias)2 + 분산(Var)
차원의 저주 길이 10인 선에서 가운데 9가 차지하는 비율 90% 10x10인 사각형에서 가운데 9x9인 사각형의 비율 81% 10x10x10인 정육면체에서 가운데 9x9x9…의 비율 약 73% 차원이 커질 수록 껍질이 두꺼워진다
NN과 차원의 저주 중심부에 데이터가 적어짐 주변부에는 데이터가 많아짐 중심부에서는 이웃끼리 멀어짐 분산 증가 오차 증가 주변부에는 데이터가 많아짐 NN은 주변부에서 왜곡 편향 증가 오차 증가