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
'AI > Data Science' 카테고리의 다른 글
[통계] R-squared, Correlation /Covariance (0) | 2023.07.08 |
---|---|
GPU 서버 접속 (0) | 2023.07.08 |
헷갈리는 수학기호 정리 (0) | 2023.06.30 |
[머신러닝] 앙상블 (1) | 2023.06.07 |
[선형대수학] Norm, 행렬곱, 내적 (0) | 2023.05.30 |