고차원에서 국소적 방법(interpolate->extrapolate)

K-NN (k-최근접이웃)

*안정적이지만 편향된 선형 모델 vs 덜 안정적이지만  덜 편향적인 모델

*어떠한 x든지 이에 가까운 관측치의 이웃을 꽤 많이 찾고 평균을 구할 수 있다.

-> 하지만 high dimension에서 이 방식은 통하지 않는다.

 

curse of dimensionality(Bellman, 1961)

 

p차원 유닛의 초입방체내 균일하게 분포된 입력값에 관한 K-NN 모델 가정

$e_{r}$= $r^\frac{1}{p}$

고차원에서 표집의 다른 중요한 점은 모든 표본 지점들이 표본의 모서리와 가깝다는 것이다.

N개의 데이터 지점이 있을 때 원점으로부터 가장 가까운 데이터 지점의 중앙값의 거리를

$d(p,N) = (1 - \frac{1}{2}^(1/N))^(1/p)$

N=500, p=10 d(10,500)=0.52xx 정도 된다.

이는 경계의 절반이상이다. 데이터 지점은 다른 데이터의 점보다도 표본 공간의 경계에 더 많이 분포한다. 따라서 이웃하는 표본 지점들 사이에서 보간법(interpolate)보다 외삽법(extrapolate)을 사용해야 한다.

고차원에서 K-NN clustering 시 경계에 더 많은 데이터가 존재하므로 보간법 보다 외삽법을 사용해야한다.

초입방체 기대 길이 설명 math.stack