[ML] cs4780 / Curse of Dimensionality, 차원의 저주

KNN alogrithm ∈ Classifiers

1. assumption: Similar Inputs have Similar Outputs

 

2. Classification rule: For a test input x, assign the most common label amongst its k most similar training inputs

 

3. 특징

3.1 Distance metric: metric이 label similarity & semantically meaningful notion을 잘 반영할 때 KNN의 효과가 높아짐
- 흔히 Minkowski distance를 사용

민코프스키 거리

3.2 n(=train data points의 개수)가 커질수록, kNN은 더욱 정확해짐 (물론 느려짐)

3.3 d(=각 data의 feature 개수 = 차원)이 너무 커지면, 차원의 저주(curse of dimensionality) 발생하여 모델 성능이 저하됨

- 물론, 차원 수가 늘어나도 그것에 영향을 덜 받는, Data with low dim structure가 있긴 함(digits / 인간 얼굴), 그러나 특이 케이스.

 

---

차원의 저주(curse of dimensionality) (in kNN)

Description

• data의 차원 수; d => d-dimensional space에 매핑됨
• train data가 n개
• hyper-cube: kNN points가 모두 포함된 smallest cube
• l = hyper-cube 모서리 길이
•  

 

차원의 저주 발생 조건

(학습 데이터 수에 비해) 차원 수가 커질수록 = n에 비해 d값이 너무 커지면

* 차원이 증가한다고 반드시 차원의 저주가 발생하는 건 X. number of train data보다 number of features가 많아지는 경우에만 발생

 

- data points 간 모든 distances가 아주 커지고 & concentrate within a very small range

   → 차원이 증가할수록 빈 공간이 많아진다.

   → 개별 차원 내에서 학습할 데이터 수가 적어짐

 

같은 데이터지만 1차원에서는 데이터 밀도가 촘촘했던 것이 2차원, 3차원으로 차원이 커질수록 점점 데이터 간 거리가 멀어짐. 차원이 증가하면 빈 공간이 생기는데 빈 공간은 컴퓨터에서 0으로 채워진 공간. 즉, 정보가 없는 공간이기 때문에 빈 공간이 많을수록 학습 시켰을 때 모델 성능이 저하. ∵ 차원 별 충분한 데이터 수가 존재하지 않으면 과적합이 될 수 있음. 알고리즘 모델링 과정에서 저장 공간과 처리 시간이 불필요하게 증가함.

 

고차원 공간은 이렇게 공간이 많아 훈련 데이터가 서로 멀리 떨어져 있고 새로운 샘플도 훈련 샘플과 멀리 떨어져 있을 가능성이 높다. 

   

   → 이것을 극복하기 위한 두 가지 방법

       (1) train data를 늘리려면, 기하급수적으로 많은 양의 데이터가 필요함: 거의 불가능

       (2) 차원 축소 알고리즘: 현실적

            - PCA, LDA, LLE, MDS, t-SNE etc.

 

 

- 반면, points와 hyperplane 간 distance는 stable하게 유지되거나 & 아주 작은 변화
   → 모든 points가 hyperplane에 매우 가까워져서, classification outcome을 변화시키기 위해 input을 약간 교란시킬 수도 있음

   → hyperplane을 사용하는 classifier ; Perceptron, SVMs, ...

 

 

 

---

이미지 & 내용 Reference

https://datapedia.tistory.com/15

https://for-my-wealthy-life.tistory.com/40

https://www.cs.cornell.edu/courses/cs4780/2018fa/lectures/lecturenote02_kNN.html