[통계] 차원의 저주와 K-NN(최근접이웃) 알고리즘

[통계, 머신러닝] 차원의 저주

차원의 저주란 차원이 증가함에 따라 탐색해야될 공간이 급격히 늘어나서 알고리즘 계산에 한계가 오는 경우를 말한다. 또는, 차원이 늘어남에 따라 기존의 데이터의 밀도가 급격히 줄어들어 예측력이 떨어지는 경우도 차원의 저주라고 한다.

예를 들어 아래의 세 점은 D1 차원에서만 설명할 땐 거리가 가까웠지만 D2라는 차원을 이용하는 순간 거리가 멀어졌다. 실제로는 그림보다 훨씬 거리가 늘어날 수 있고, 차원이 늘어날수록 기하급수적으로 데이터가 희박해진다.

이 경우 예측이 불안정해지고 과적합 위험이 커진다. 차원의 저주를 해결하는 방법은 데이터를 충분히 확보하는 것이지만 차원이 많이 증가하면 필요한 훈련 데이터의 수도 기하급수적으로 늘어나는 한계가 있다.

K-최근접이웃회귀와 차원의 저주

KNN 회귀는 주어진 K 값과 x0에 대해 x0에 가장 가까운 K개의 훈련 관측치 을 식별한다. 그다음 내 모든 훈련 관측치들에 대한 반응변수 값들의 평균을 사용하여 f(x0)을 추정한다.

KNN 분류는 가장 가까운 k개의 데이터를 보고 개수가 많은 class로 분류한다.

[출처 : 위키백과]

따라서 새로운 초록 점은 k=3 일땐 빨간색 세모와 같은 클래스가 되고, k=5 일땐 파란색 네모와 같은 클래스가 된다. 이 거리를 구할 때 유클리디안 거리를 사용하고, 단위에 따른 영향을 제거하기 위해 표준화를 한다. 또는, 데이터의 밀도를 고려하여 마할라노비스 거리(Mahalanobis distance)를 사용하기도 한다.

다시 본론으로 돌아와서, KNN 알고리즘은 유클리디안 거리를 사용하기 때문에 차원이 증가할수록 주어진 관측치에 가까운 이웃이 없는 현상이 발생한다. 이로인해 회귀에서는 차원이 4이상이면 선형회귀보다도 못한 성능을 낸다. 차원이 낮은 경우에도 해석력 관점에서 선형회귀를 더 선호할 수도 있다.