k-Nearest Neighbour 알고리즘.(번역)

knn알고리즘에 대해 공부하려고 했는데 대부분 c++의 opencv를 예로 들고 있어서;; 파이썬 opencv 관련 한글자료는 찾기가 힘들기도 하고.. 새로 opencv c++기반 책을 사서 보기엔 귀찮아서 python opencv튜토리얼을 보고 익힐 겸, 직접적인 코드도 보고 영어연습도 할 겸, 모르는단어는 찾아가면서 번역했습니다. 틀린점있으면 수정하겠습니다.

http://opencv-python-tutroals.readthedocs.org/en/latest/py_tutorials/py_ml/py_knn/py_knn_understanding/py_knn_understanding.html?highlight=knn 번역.

k-Nearest Neighbour 알고리즘 이해.

목표.

k-Nearest Neighbour 알고리즘의 개념을 이해한다.

이론.

kNN은 supervised learning를 가능하게 하기 위한 가장 간편한 분류 알고리즘중 하나입니다. 이 아이디어는 특징 공간(feature space)에서 입력한 테스트할 데이터(test data)에 가장 가까운 매칭되는 데이터를 찾기 위한 것입니다. 아래 이미지를 살펴봅시다.

이미지 안에는 파랑색 사각형과 빨간색 삼각형 두 가족이 있습니다. 우리는 각각의 가족을 클래스라고 부를것입니다. 그들의 집은 우리가 특징 공간(feature space)라고 부르는 마을 지도에 보입니다. 

(특징 공간(feature space)를 모든 데이터가 나올 수 있는 공간이라고 고려할수 있습니다. 예를들면 2d의 좌표공간이 있습니다. 각각의 데이터는 x좌표,y좌표라는 두가지 특징들을 가지고 있습니다. 2d 좌표공간에 이 데이터를 표현할수 있습니다. 그렇죠? 이제 그것들이 3가지 특징을 가지고 있다고 상상해봅시다. 아마도 당신은 3d 공간이 필요할 것입니다. 이제 n개의 특징들을 고려해봅시다. 그러면 n개의 차원이 필요할 것입니다. 그렇죠? 이 n차원 공간은 그 자체의 특징 공간(feature space)입니다. 위의 이미지에서 우리는 두개의 특징을 가진 2d의 경우로 고려할수 있을 것입니다.)

이제 새로운 맴버가 마을에 들어와서 녹색 원으로 보이는 새 집을 만들었습니다. 새로운 맴버는 파랑/빨강 가족중에 하나에 추가되야 합니다. 이러한 과정을 분류라고 부르겠습니다. 뭘 해야 할까요? kNN 알고리즘을 다루고있기 때문에 이 알고리즘을 적용시켜봅시다.

하나의 메소드는 누가 새 맴버의 가장 가까운 이웃인지 확인하는 메소드입니다. 위의 이미지에서 빨간색 삼각형 가족이라는건 확실합니다. 그러므로 그(녹색 원)도 빨간색 삼각형에 포함시켜야겠네요. 이 메소드는 분류시 가장 가까운 이웃에 의존하기 때문에 간단하게 Nearest Neighbour라고 불립니다.

하지만 이것엔 문제가 있습니다. 빨간색 삼각형이 가장 가깝긴 합니다만... 많은 파란색 사각형이 새 맴버와 가까이 있다면 어떻게할건가요? 그러면 파란색 사각형은 빨간색 사각형보다 지역성에 대해서 더 큰 힘을 가지게 됩니다. 그러면 단순히 가장 가까운 이웃을 확인하는건 충분하지 않게 됩니다. 대신에 우리는 몇몇의 k nearest families들을 확인해봐야 합니다. 그러면 그 안에서 가장 많은 집단에 새로온 사람이 속하게 됩니다. 우리의 이미지에서 k=3이라고 합시다. 즉 3개의 가장 가까운 가족이요.

해당 범위에서 두개의 빨간색과 하나의 파랑색을 가지고 있습니다.(같은거리에 두개의 파랑색이 있지만 k=3 이기 때문에 우리는 그들(동일한 거리의 두개의 파랑색사각형)중 하나만 골라야 합니다.) 그러면 다시 새 맴버는 빨간색 가족에 포함되겠네요. 하지만 우리가 k=7로 한다면? 우리는 5개의 파랑색 가족과 2개의 빨간색 가족을 가지게 됩니다.(가장 가까운 7개가 위에서 볼수 있듯이 파랑5,빨강2개네요.) 좋습니다! 이제 새 맴버는 파랑색 가족에 추가되었습니다. 그러므로 k의 값에 따라 모든게 바뀌었습니다. 더 재밌는 것은, k=4일때는요?? 그 범위에는 2개의 빨간색과 2개의 파랑색 이웃을 가지고 있습니다. 동점이네요!! 그러므로 k는 홀수로 놓는 것이 좋습니다. 이 메소드는 분류를 k개의 가까운 이웃들에게 의존하기 때문에 k-Nearest Neighbour 이라고 불리웁니다.

다시 kNN안에서 k개의 이웃을 고려한다는건 사실입니다. 그러나 모두에게 동일한 중요도를 부여했습니다 맞죠? 이게 정당할까요? 예를 들면 k=4로 놓겠습니다. 위에서 동점이라고 말했습니다. 하지만 이걸 살펴봅시다. 두개의 빨간색 가족이 두개의 파란색 가족보다 더 가깝습니다. 그러므로 새 맴버는 빨간색에 추가되는게 더 맞습니다. 그러면 어떻게 수학적으로 설명해야 할까요?? 몇몇 가중치를 새로온 것으로부터 각각의 가족의 거리에 비례해서 부여했습니다.(거리가 가까우면 가중치가 높다는 뜻입니다.) 여기에서 새 맴버와 더 가까이 있는 사람은 더 멀리있는 사람보다 더 높은 가중치를 받습니다. 그리고 각각 가족들의 가중치의 총합을 계산했습니다. 누구던지 더 높은 총 가중치값을 가지게 되면 새로온 사람은 거기로 가게 됩니다. 이것은 수정된 kNN(modified kNN)이라고 부릅니다.

그러면 여기서 봐야 할 중요한 것들은 뭐가 있을까요?

· 모든 집의 정보를 가지고 있어야 합니다. 맞죠? 왜냐하면 존재하는 모든 집들에 대해서 새로온 사람에 대한 거리를 확인해서 가장 가까운 이웃을 찾기 위해서죠. 만약 많은 집과 가족이 있으면 메모리를 많이 소비하고, 또한 계산하는데 오래 걸리겠죠.

· 어떤 종류의 훈련이나 준비로 거의 시간 걸리지 않고 처리할 수 있습니다.

opencv를 봅시다.

OpenCV에서의 kNN.

이제 두 가족으로(클래스로) 위처럼 간단한 예제를 해볼 겁니다. 다음 챕터에서는 더 좋은 예제를 해볼겁니다.

그러니 여기에서, 빨간색 가족을 Class-0이라는 이름으로, 파란색 가족을 Class-1이라는 이름으로 레이블을 붙여봅시다. 25가지의 가족과 25가지의 연습 데이터, 그리고 그것들에 레이블을 붙일 겁니다. Class-0 또는 Class-1둘중 하나에요. Numpy의 난수 생성기의 도움을 받아서 이 전부를 할겁니다.

그러고 Matplotlib라이브러리로 plot할 겁니다.(plot는 그래프로 보여주는거를 말합니다.) 빨간색 가족은 빨간색 삼각형으로, 그리고 파란색 가족은 파란색 사각형으로 보이게끔요.

# -*- encoding: cp949 -*-
import cv2
import numpy as np
import matplotlib.pyplot as plt

# Feature set containing (x,y) values of 25 known/training data
#numpy배열로 0~99사이의 수중 하나를 랜덤으로 잡아 (25,2) 크기로 만듬. 이걸 float32타입으로 변경
trainData = np.random.randint(0,100,(25,2)).astype(np.float32)

# Labels each one either Red or Blue with numbers 0 and 1
#0~1사이의 수중 ~~(25,1)크기로 만듬. 이걸 float32타입으로.
responses = np.random.randint(0,2,(25,1)).astype(np.float32) 

# Take Red families and plot them
#responses값들중 0으로 나온 값은 red로 잡고, 1은 blue로 잡음(아래)
red = trainData[responses.ravel()==0]
plt.scatter(red[:,0],red[:,1],80,'r','^')

# Take Blue families and plot them
blue = trainData[responses.ravel()==1]
plt.scatter(blue[:,0],blue[:,1],80,'b','s')

plt.show()

아마도 첫번째 이미지와 비슷한걸 얻었을겁니다.(맨위에 사진을 말합니다.) 난수 생성기를 사용하기 때문에 돌리는 코드에서 매번 다른 데이터를 얻을겁니다.

다음엔 kNN 알고리즘을 초기화하고, 훈련 데이터를 넣은 후 kNN으로 훈련시켜봅시다. (이것은 검색 트리를 구성하게 될겁니다.)

그러고 나서 새로운 사람(위의 녹색 원같은)를 데려와서 OpenCV의 kNN의 도움을 받아 그를 가족들에게 분류할겁니다. kNN에게 가기 전에, 테스트 데이터에 대해 알아야 합니다.(새로올 사람의 데이터) 데이터는 (testdata의 수 * features의 수) 크기의 부동소수점 배열이어야 합니다.

그러고 나서 새로운 사람의 가장 가까운 이웃(nearest neighbours)을 찾아야 합니다. 우리가 원하는 많은 이웃들을 분류할수 있습니다. 그것은 아래의 결과값을 반환합니다.

1. 새로올 사람에게 주어진 별명은 앞에서 본 kNN이론에 기반합니다. 만약 Nearest Neighbour algorithm에 대해서 알고싶다면 이웃들의 수를 가리키는 값인 k를 k=1로 정하세요.

2. k-Nearest Neighbours의 별명.

3. 새로온 사람으로부터 각각의 이웃들에 해당하는 거리.

그러면 이게 어떻게 동작하는지 살펴보죠. 새로온 사람은 녹색으로 표시됩니다.

# -*- encoding: cp949 -*-
import cv2
import numpy as np
import matplotlib.pyplot as plt

# Feature set containing (x,y) values of 25 known/training data
trainData = np.random.randint(0,100,(25,2)).astype(np.float32)

# Labels each one either Red or Blue with numbers 0 and 1
responses = np.random.randint(0,2,(25,1)).astype(np.float32)

# Take Red families and plot them
red = trainData[responses.ravel()==0]
plt.scatter(red[:,0],red[:,1],80,'r','^')

# Take Blue families and plot them
blue = trainData[responses.ravel()==1]
plt.scatter(blue[:,0],blue[:,1],80,'b','s')

#여기 아래부터 추가된 부분.
newcomer = np.random.randint(0,100,(1,2)).astype(np.float32)
plt.scatter(newcomer[:,0],newcomer[:,1],80,'g','o')

knn = cv2.KNearest()
knn.train(trainData,responses)
ret, results, neighbours ,dist = knn.find_nearest(newcomer, 3)

print "result: ", results,"\n"
print "neighbours: ", neighbours,"\n"
print "distance: ", dist

plt.show()

아래와 같은 결과가 나오네요.

result:  [[ 1.]]
neighbours:  [[ 1.  1.  1.]]
distance:  [[ 53.  58.  61.]]

이것은 새로온 사람은 모두 파란색 가족인 3개의 이웃을 갖는다는것을 말합니다. 그러므로 새로운 맴버는 파란색 가족으로 불리우겠네요. 이것은 아래의 plot에서 더 명확히 나타납니다.

(부가설명을 하자면 새로온 사람의 별명은 result : [[1]]에서 1로 정해졌습니다. 그 이유는 이웃들이 모두 [[1. 1. 1.]]이네요. 이 1.은 파란색 사각형을 뜻하며, 3개의 이웃을 봤을때 전부 파란색 이웃이므로, 다수결의 결과에 따라서 파란색 이웃인 1.로 설정되었습니다. distance값은 위에서 설명했듯이 거리값이고요.)

만약 많은 양의 데이터를 가지고 있으면 그냥 배열에 넘기면 됩니다. 결과에 해당하는 것들도 역시 배열로 존재해야겠죠.

# 10명의 새로운 사람이 들어올 경우.
newcomers = np.random.randint(0,100,(10,2)).astype(np.float32)
ret, results,neighbours,dist = knn.find_nearest(newcomer, 3)
# 결과는 10개의 별명을 포함합니다.