[OpenCV] 08-1-1. Understanding k-Nearest Neighbour

< 8-1-1. Understanding k-Nearest Neighbour >

이번 장에서는, kNN 알고리즘에 대해서 이해해 볼 것이다!

Theory

kNN은 지도학습중에서 가장 간단한 분류 알고리즘 중에 하나이다. feature space 에서 test data와 가까운 매치를 찾는 것이 주 아이디어이다. 아래 이미지를 통해 더 쉽게 알아보자.

이미지에서, 파란 사각형과 빨간 삼각형으로 총 두 개의 카테고리가 존재하고 있다. 이 카테고리를 Class라고 부를 것이다. 우리가 feature space라고 부르는 그 곳에 놓여져있다(feature space는 모든 데이터들이 투영되어있는 공간이라고 생각하면 된다. 예를 들어서, 2D 좌표 공간을 생각해보자. 각 데이터는 x,y좌표를 가진다. 이를 2D 공간에 표현할 수 있다. 그리고 3차원 공간을 필요로 한다면 세 번째 좌표까지 상상해보면 된다. N개의 특성들을 고려하면, N차원 공간이 필요할 것이다. 이러한 N-차원 공간을 feature space라고 하는 것이다. 위의 이미지는 x,y좌표만을 갖는 2D 공간이라고 보면 된다.)

이제 초록색 원으로 표시된 새로운 멤버가 들어오게 되어 군집을 이루게 된다. 과연 이 초록색 원은 파란색에 속해야 할까, 빨간색에 속해야 할까? 무조건 둘 중에 하나에는 속해야 한다. 이러한 과정을 Classification(분류)라고 말한다. 우리가 무엇을 해야할까? kNN이라는 알고리즘을 다루고 있으니 이 알고리즘을 적용시켜보자!!

방법중 하나는 누가 가장 가까운 이웃(Nearest Neighbour)인가를 확인해보는 것이다. 이미지에서, 빨간 삼각형과 가까이 있는 것을 확인해 볼 수 있다. 그래서 초록색 원을 빨간 색과 같은 클래스라고 할 수 있는 것이다. 이 방법은 간단하게 Nearest Neighbour이라고 불린다. 왜냐하면 가까운 이웃들에 근거해서 분류하기 때문이다.

하지만 문제가 있다. 빨간 삼각형이 가까운 이웃이지만, 만약 많은 파란색 사각형이 가까이 있었다면 어땠을까? 그러면 파란 사각형은 빨간 삼각형보다 지역적으로 더 영향력이 있었을 것이다. 그래서 가장 가까이 있는 1개를 보는 것은 불충분하다. 대신에 k개의 가까운 이웃들을 확인한다. 그래서 더 많은 쪽에 해당하게 되어, 속해지는 것이다. 이미지에서, k=3이라고 해보자. 그러면 2개의 빨간색, 1개의 파란색이 골라져서 수가 더 많은 빨간색에 속하게 된다.(같은 거리에 파란색이 두 개지만 총 3개를 골라야하기에 그 중에 하나만을 선택해야한다.) 하지만 k=7일 때는 어떨까? 그러면 5개의 파란색, 2개의 빨간색으로 선택이 된다. 그렇다면 지금은 파란색에 속하게 된다. 그래서 이 분류는 k값에 의거해서 변한다는 것을 알아야한다! 더 재밌는 것은 만약에 k=4라면? 파란색,빨간색 각각 2개가 될 것이다. 그렇다면 동률이된다..! 그래서 k값은 홀수로 가져가는 것이 좋다!! 그래야 동률이 나오는 상황을 방지할 수 있다. 그래서 이 방법이 k개의 가까운 이웃들에 의거에 분류하기 때문에 k-Nearest Neighbour이라고 불리는 것이다.

다시 kNN에서, 우리가 k개의 이웃들을 고려하는 것은 사실이지만, 그들에게 동일한 중요도(가중치)를 부여하고 있었다. 과연 이게 공평한 것 일까?

예를 들어서 k=4일 때, 동률이라고 했다. 하지만 2개의 빨간색이 2개의 파란색보다 더 가까운 것을 볼 수 있다. 그래서 초록색은 빨간색에 더 속해지기에 적격인 것이다. 그래서 이를 어떻게 수학적으로 설명할 수 있을까? 그래서 이제 새로 들어오는 요소에 대해 그들의 거리에 의거하여 가중치를 부여하게 되는 것이다. 가까운 것들에게는 높은 가중치를 주고, 멀리 있을 경우에 낮은 가중치를 부여한다. 그리고 각 클래스의 총 가중치를 별도로 추가한다. 가장 높은 가중치를 가지는 누군가와 새로 들어온 요소가 한 클래스가 되는 것이다. 이는 modified kNN이라고 불린다.

중요한 것들을 몇 가지 짚고 넘어가자!

• 먼저 그 feature space에 대한 정보가 필요하다. 왜냐하면 거리를 기반으로 기존 요소들과 새로 들어오는 요소들을 체크해서 가까운 것들을 찾아야하기 때문이다. 만약 기존의 데이터들과 클래스가 많다면, 메모리를 많이 차지하고, 연산에 대한 시간 또한 오래 걸리게 될 것이다.
• 하지만 training이나 준비하는데에는 거의 시간(zero-time)이 들지 않는다.

OpenCV를 통해서 구현해보자.

kNN in OpenCV

두 개의 클래스들 가지는 간단한 경우를 볼 것이다. 그리고 다음 장에서 더 나은 예제를 가지고 다뤄볼 것이다.

이제 빨간색을 Class-0 (0), 파란색을 Class-1 (1) 이라고 라벨링(=레이블링)한다. 총 25개의 데이터를 생성하고, 클래스 0혹은 1의 값을 라벨링해준다. Numpy의 난수 생성 기능을 이용할 것이다!

그리고 Matplotlib를 이용해서 시각화 할 것이다. 빨간 삼각형과, 파란 사각형으로 표시할 것이다!

import numpy as np
import cv2
import matplotlib.pyplot as plt
# 값이 안바뀌게 seed 고정
np.random.seed(43)

# (a,b)형태로 0~99까지의 난수 좌표 생성
trainData = np.random.randint(0,100,(25,2)).astype(np.float32)

# 0,1 의 라벨 생성
label = np.random.randint(0,2,(25,1)).astype(np.float32)

# 라벨이 0인 것만 red로 
red = trainData[label.ravel() == 0]
plt.scatter(red[:,0],red[:,1],80,'r',"^")

# 라벨이 1인 것만 blue로
blue = trainData[label.ravel() == 1]
plt.scatter(blue[:,0],blue[:,1],80,'b','s')
plt.show()

맨 위의 이미지같은 표를 얻었을 것이다. 난수 생성기를 사용했기에 매 코드를 실행할 때마다 다른 값이 나온다. 그래서 여기서 np.random.seed()를 추가하여 값을 고정시켰다.

       < feature space >

다음으로 kNN 알고리즘을 개시하고, trainData와 label을 넘겨서 kNN을 학습시킨다. (search tree를 구성)

그러면 이제 새로운 하나들 데려오고 분류하도록 할 것이다. kNN전에, test data에 대해 알아야 할 것이 있다. 우리의 데이터는 floating point로 test data의 수 X 특성의 수의 크기여야 한다. 그리고 가까운 이웃을 찾는 것이다.

1. kNN에 의해 test data는 라벨링 된다. 만약 그냥 NN을 사용하고 싶다면 k=1로 설정하면 된다.
2. k-Nearest Neighbour의 라벨들 확인
3. 각 가까운 이웃과 test data까지 해당하는 거리를 확인한다.

test data는 초록색으로 표현한다.

import numpy as np
import cv2
import matplotlib.pyplot as plt
# 값이 안바뀌게 seed 고정
np.random.seed(43)

# (a,b)형태로 0~99까지의 난수 좌표 생성
trainData = np.random.randint(0,100,(25,2)).astype(np.float32)

# 0,1 의 라벨 생성
label = np.random.randint(0,2,(25,1)).astype(np.float32)

# 라벨이 0인 것만 red로 
red = trainData[label.ravel() == 0]
plt.scatter(red[:,0],red[:,1],80,'r',"^")

# 라벨이 1인 것만 blue로
blue = trainData[label.ravel() == 1]
plt.scatter(blue[:,0],blue[:,1],80,'b','s')

test_data = np.random.randint(0,100,(1,2)).astype(np.float32)
plt.scatter(test_data[:,0],test_data[:,1],80,'g','o')

# knn 생성
knn = cv2.ml.KNearest_create()

# cv2.ml.ROW_SAMPLE : 배열의 길이을 전체 길이 1로 간주한다는 것
knn.train(trainData,cv2.ml.ROW_SAMPLE,label)
ret, results, neighbours,dist = knn.findNearest(test_data,3)

print("분류 결과 (Class) : ",results)
print("이웃들 (Neighbours Class) : ",neighbours)
print("거리",dist)

k=3으로 설정하여 주변 3개를 보게 했더니 빨간색에 속하게 되었다.(Class = 0)

결과는 아래와 같다. (k=5,7 까지 늘려도 그대로 Class=0)

만약 test data를 여러개로 넣고 싶다면 배열 형태로 넣어주면 된다. 결과 또한 배열에 저장될 것이다.

test_data_add = np.random.randint(0,100,(10,2)).astype(np.float32)
ret,results,neighbours,dist = knn.findNearest(test_data_add,3)
print("분류 결과 (Class) : ",results)
print("이웃들 (Neighbours Class) : ",neighbours)
print("거리",dist)

간략하게 kNN에 대해서 알아보았다. 가장 간단한 분류 알고리즘인 만큼 이해하는 데 어려움이 없을 거라 믿는다!