K-Nearest Neighbors(KNN)

원리

Distance metric을 이용해서 가까운 이미지를 K개만큼 찾고, K개의 이미지의 라벨 중 가장 많이 나온 것으로 라벨을 정하는 원리다. (Majority Voting System)

HyperParameter

요소

KNN 분류기 적용 시, 사용자가 직접 조정할 수 있는 요소들을 의미한다. 다음과 같이 두가지가 존재한다.

Distance Metric: 어떤 거리 계산 방식을 선택할 것인가?

L1 Distance 공간구조

K=1 일 때 L1 Distance에 기초해 Class 5개로 나눈 결과

L1 Distance 문서에서 자세한 내용 참조

L2 Distance 공간구조

K=1일 때 L2 Distance에 기초해 Class 5개로 나눈 결과

L2 Distance 문서에서 자세한 내용 참조

K: 유사한 이미지 몇개를 찾을 것인가?

이미지 출처: CS231n Lecture 2 Slides

K값이 증가할 수록, 잡음에 대해 더 잘 대처하고(초록 영역에 떠있는 파란 섬), 영역이 스무스하게 나눠지는 것을 볼 수 있다. 다만, 언제나 K값이 큰 것이 좋은 것은 아니다.

세팅 방법

위 요소들은 사용자가 직접 바꿔가며, 어떤 값이 적합한지를 스스로 판단해야한다. 해당 사이트에서 연습해볼 수 있다.

하이퍼파라미터를 정하기 위해서는, 주어진 데이터를 training set / validation set / test set으로 나눠야한다. 이후, validataion set에 적합한 하이퍼파라미터를 정하고, 그 성능에 대한 테스트는 test set에 대해 진행한다. 즉, 리포트에 기입할 알고리즘의 성능은 ‘test set’에 대한 평가 결과다.

데이터셋이 작을 때에는 Cross-Validation 방법도 쓰인다. 주어진 데이터를 training set / test set으로 나누고, training set을 K개의 fold로 나눈 다음, 하나의 fold를 제외한 나머지 fold에서 훈련을하고, 하나의 fold에서 테스트를 한다. 이를 k번 수행하면, 모델이 훨씬 더 다양한 상황에서 테스트를 진행해 더 좋은 hyperparameter를 선택할 수 있게 된다. 그러나 데이터셋이 큰 딥러닝에서는 학습에 필요한 계산량이 기하급수적으로 늘어나기 때문에 사용하지 않는다.

이미지에서 사용하지 않는 이유

•

테스트를 위해, 테스트 이미지와 훈련용 데이터의 모든 사진 간의 거리를 계산하므로, 예측 과정에서 많은 시간이 소요된다. 

•

이미지 간 거리를 측정하는데 있어, L1, L2 거리가 제대로 적용되지 않음: 픽셀이 많을수록 두 이미지 사이의 거리를 계산할 때 유사성이 떨어진다.

가장 왼쪽 오리지널 이미지를 제외한 다른 이미지들의 차이가 뚜렷함에도 불구하고 오리지널 이미지와의 거리가 모두 같음

•

차원의 저주: KNN의 성능 발휘를 위해서는 공간을 빽빽하게 메울 데이터가 필요하지만, 현실적으로 차원이 늘어날 때마다 필요한 데이터의 개수가 지수적으로 증가하기 때문에 KNN이 만족할만한 데이터 확보가 어렵다. 