k nearest neighbor - k 최근접 이웃

출처: cs231n lecture 2

 

www.youtube.com/watch?v=OoUX-nOEjG0&list=PLC1qU-LWwrF64f4QKQT-Vg5Wr4qEE1Zxk&index=2

 

이미지의 classification 문제중 가장 먼저 떠올릴수 있는 방법중 하나인 최근접이웃 알고리즘이다.

최근접 이웃 알고리즘은 말 그대로 가장 가까운 데이터의 결과값을 그대로 출력한다는것이다.

위와 같이 k=1 인경우 특정 데이터에 대해 점은 train set의 data고 색은 그 결과값(y)라고 할때 영역의 표시이다.

특정점에 대해 가장 가까운 점의 위치를 파악해 그 데이터의 결과값을 가져온다.

하지만 위처럼 섬이 생기게 되고 이는 옳지 못할 가능성이 매우 크다. 특이점에 매우 민감하게 반응하며 위와같은 실수를 범할 수 있게된다.

따라서 k=1이 아닌 k=2, 3, 4... 등 다양한 방법을 생각해 볼 수 있다.

CIFAR10 의 샘플이미지를 이를통해 분석해본다면

각 픽셀간의 거리(여기선 l1거리)를 측정하여 가장 가까운 데이터를 같은 결과로 분류한다.

물론 l2 distance를 사용해도 된다.

l1 distance는 특정 픽셀의 좌표가 고정되어있는경우, 회전을 시킬 수 없는경우 혹은 레이블이 정해져있는경우등에 일반적으로 사용된다.

train 에는 상수시간만큼 걸렸는데 비해 predict에는 선형시간이 걸렸다. 이는 실제로 사용하기에 매우 불리한 구조이다. 실제로는 train에 많은 시간이 걸리더라도 predict에 시간이 적게 걸리는 알고리즘이 필요하다(혹은 유리하다)

 

이 결과는 다음과 같이 나왔는데 보이는것과 같이 이미지의 픽셀값이 유사한 이미지를 가져온다. 결과가 많이 틀리다는것을 알 수 있다. 즉 아래 예에서는 4개만 분류에 성공했다.

즉 k nearest neighbor는 이미지 분류 문제에 좋은 결과를 가져다 주기 어려운것으로 보인다.

특히 아래 세 이미지는 모두 같은 L2 거리를 보이는데 사람이 보았을때와 많이 다르다. 이는 거리를 이용한 분류가 사람의 시각과 얼마나 많이 다른지 단적으로 보여주는 예이다.