K-Nearest Neighbor(KNN)

cs231n — KNN classifier

k-NN은 분류나 회귀에 사용되는 비모수 방식이다. 두 경우 모두 입력이 특징 공간 내 k개의 가장 가까운 훈련 데이터로 구성되어 있다. 출력은 k-NN이 분류로 사용되었는지 또는 회귀로 사용되었는지에 따라 다르다.

거리

가장 흔하게 사용되는 거리척도는 유클리드 거리이다. 이산 변수의 경우 중첩거리(또는 해밍거리)와 같은 다른 척도가 사용될 수 있다. 종종 거리 척도가 Large Margin Nearest Neighbor or Neighbourhood components analysis 를 통해 학습된다면 k-NN 분류의 정확성을 상당히 향상시킬 수 있다.

cs231n에서 KNN Classifier에 대해 설명하고 있으며 이를 통해 이미지 분류기를 만든다. 위 그림을 보면 NN 분류기의 경우 큰 영역안에 세부영역을 생성하는 것을 볼 수 있으나 5-NN의 경우는 이러한 부분들이 생기지 않고 영역의 경계를 부드럽게 이어주는 것을 볼 수 있다.

k-NN에서 k의 매개변수 선택이 중요하며 이는 데이터에 의존적이다. 일반적으로 k값이 커지면 노이즈의 영향이 줄어들지만 분류 항목들의 경계가 불분명해진다.
최적의 k 값을 찾기 위해 검증 셋을 통해 트레이닝과 검증을 통해 튜닝을 해나가야한다. 그런데 이러한 매개변수를 찾는 과정에서 테스트 셋을 이용하면 안된다. 테스트 셋은 이론적으로 실제 알고리즘을 평가할 때인 가장 마지막 한번을 제외하고는 절대 사용을 해서는 안된다. 테스트 셋에서 잘 동작하도록 매개변수값을 적용하지만 실제 real word data를 적용하게 되면 퍼포먼스가 매우 낮아질 수 있다. 이러한 경우를 테스트 셋에 overfit 되었다고 한다.

이를 해결하기 위해 보유하고 있는 테스트 셋은 건드리지 않고 트레이닝 셋을 두 개로 나눠서 트레이닝 셋과 검증셋(validation set)으로 나눈 후 튜닝을 한다.
그리고 이진 분류 문제에서는 동률의 투표를 피하기 위해 홀수인 k를 선택하는 것이 바람직하다.

이 과정을 통해 가장 잘 분류가 되는 k값을 찾고 실제 테스트 셋에서 평가를 한다.

cs231n에서 이미지 처리할때 느리기 때문에 k-nearest 절대로 안쓴다 라는 말을 하는데 이해가 잘 안되었는데 자료를 보니 아래와 같은 이유 때문이다.

실제 이미지 분류 문제에 적용하게 되면 이미지가 매우 고차원 물체라는 것, 고차원 공간에서의 거리는 매우 직관적이지 않은 경우가 많다.

고차원 데이터에서의 픽셀값 기준 거리는 매우 비직관적인 경우가 많다. 원본 이미지(왼쪽)와 그 옆의 세 이미지는 픽셀값의 L2 거리를 기준으로 모두 같은 거리만큼 떨어져있다. 이를 보아 픽셀값을 기준으로 한 거리는 인지적, 의미적으로 거의 연관이 없다고 생각할 수 있다.

즉, k-NN은 구현하기 쉽고 차원이 낮은 경우에는 활용하기 좋으나 고차원 데이터에 대해서는 적합하지 않다. 이를 해결하기 위해 k-NN 알고리즘을 사용하기 전에 전처리를 통해 차원 축소를 수행하여 축소된 차원 공간에서 군집화를 할 수 있다.
 초고차원의 데이터 집합에서는 다른 고차원 유도 탐색 기법들을 사용한 빠른 근사 k-NN(Approximate Nearest Neighbor,ANN, 근사 최근접 이웃) 탐색을 수행하는 것이 유일하게 실행 가능한 방법일 수 있다.

자료 출처

• http://aikorea.org/cs231n/classification/
• https://en.wikipedia.org/wiki/K-nearest_neighbors_algorithm