[기계학습] KNN ( K-Nearest neighborhood ) k-최근접 이웃

KNN (K-Nearest neighborhood) 이란?
K-최근접 이웃

K는 갯수를 의미한다. ( 3NN , 5NN , 10NN )

주변의 관측치들의 정보를 이용해서 새로운 관측치의 분류를 하게 된다.

비지도학습(Unsupervised Learning) 의 간단한 예시

---

아래와 같은 경우, 녹색 원(새로운 관측치)은 무엇으로 분류되어야 할까?

빨강? 파랑?

실선을 기준(K=3)으로 분류를 했을 경우는 빨강의 갯수가 더 많아서 빨강으로 분류

점선을 기준(K=5)으로 분류를 했을 경우는 파랑의 갯수가 더 많아서 파랑으로 분류

이렇게 k를 기준으로 새로운 데이터가 빨간색일지 파랑색일지 분류하는 것이 knn 알고리즘이다.

---

그렇다면 k는 어떻게 정하는 가?

만약 k가 너무 크다면?

• 미세한 경계부분은 잘못 분류할 것이다.
• K를 다 못채워서 범위가 너무 커져버릴 수 있다.

k 가 15인 경우

만약 k가 너무 작다면

• 이상치(점하나)의 영향을 크게 받을 것이다.
• 과적합(overfitting)우려
• 패턴이 직관적이지 않을 것이다.

k 가 1인 경우

KNN은 직관적이지만 어느 부분에서 좀 애매한 경우가 생기게된다.

 

그렇다면 최적의 k를 어떻게 찾을 것인가?

 

Training error

• K=1 에서 가장 낮음
• 과적합의 가능성

Test error

• 데이터에 따라 최적의 k 가 존재.

k의 결정

• Test error를 작게하는 k 를 결정하게 된다.
• cross-vaildation(교차검증)이용.

---

종속변수의 종류의 따라서 KNN의 방법이 달라진다.

 

종속변수가 범주형일 경우

• k-nearest neighbors 중 가장 많이 나타나는 범주로 y를 추정
• Tie 문제를 막기 위해 k는 왠만하면 홀수로 정하는 것이 좋다.
• Why? 짝수일 경우 2:2 혹은 3:3 으로 동일하게 나뉠 수 있기 때문에 홀수가 좋다.

종속변수가 연속형일 경우

• k-nearest neighbors의 대표값 (평균)으로 y를 추정
• Inverse distance weighted average 고려 가능
• 거리가 가까운 관측치들에게 가중치(weight)를 줘서 가중평균으로 구하는 것 

---

그럼 가까운 거리란 무엇을 의미하는가?

거리는 어떻게 구하나?

 

독립변수(설명변수)가 범주형일 경우는

해밍거리(Hamming distance)를 사용한다.

 

 

독립변수(설명변수)가 j개의 연속형 변수일 경우

유클리드 거리와 맨하탄 거리를 사용한다.

 

점과 점 사이의 직선

점과 점 사이의 바둑판모양의 거리

왼쪽 유클리드 거리 오른쪽 맨하탄 거리

KNN을 진행할 때 불필요한 변수는 반드시 제거해야한다.

불필요한 변수를 제거한다는 내용은 당연한 말이지만 KNN은 좀 더 특별한 의미를 갖고 있다.

Y축 정보가 추가됨에 따른 비효율의 예시

먼저 변수가 하나 즉, 차원이 1개 일 경우 노란색박스로 정사영한 값으로 검정색점을 KNN 해서 예측하게 된다.

K=5 니까 5개를 기준으로 초록색이 4개 빨간색이 1개여서 이 점은 초록색으로 분류함.

 

하지만!

변수가 더 하나 증가해서 차원이 2개일 경우 KNN은 노란색 박스가 아닌 검정색 원으로 분류를 하게된다.

K=5 검정색원에 빨간색 3개 초록색 2개 그래서 2차원일 경우에는 이 점을 빨간색으로 분류하게 된다.

 

그래서 KNN을 하기전에 반드시 feature selection 변수선택법과 PCA 차원축소법이 선행되어야한다.

 

KNN 실습 

In [35]:

import cv2
import numpy as np
from matplotlib import pyplot as plt

각 데이터의 위치 : 25 x 2 크기에 각각 0~100¶

In [36]:

trainData = np.random.randint(0, 100, (25,2)).astype(np.float32)

각 데이터는 0 or 1¶

In [37]:

response = np.random.randint(0,2,(25,1)).astype(np.float32)

값이 0 인 데이터를 각각 (x,y) 위치에 빨간색으로 칠합니다.¶

In [38]:

red = trainData[response.ravel()==0]
plt.scatter(red[:,0],red[:,1],80,'r','^')

Out[38]:

<matplotlib.collections.PathCollection at 0x11beedb50>

값이 1인 데이터를 각각 (x,y) 위치에 파란색으로 칠합니다.¶

In [39]:

blue = trainData[response.ravel() == 1]
plt.scatter(blue[:,0],blue[:,1],80,'b','s')

Out[39]:

<matplotlib.collections.PathCollection at 0x11bd5bd10>

(0 - 100,0 - 100) 위치의 데이터를 하나 생성해 칠합니다.¶

In [40]:

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

Out[40]:

<matplotlib.collections.PathCollection at 0x11be72e90>

In [41]:

knn = cv2.ml.KNearest_create()
knn.train(trainData,cv2.ml.ROW_SAMPLE,response)
ret,results, neighbours,dist = knn.findNearest(newcomer,3)

In [42]:

print("result : ", results)
print("neighbours : ", neighbours)
print("distance : ",dist)

result :  [[1.]]
neighbours :  [[0. 1. 1.]]
distance :  [[ 13.  17. 130.]]

빨간색 세모를 0번 레이어로 두고 파란색 네모를 1번 레이어라고 본다.

result : 1 새로운 데이터를 1번 레이어라고 예측했다.
neighbours : [0.1.1] 주변 데이터들의 종류 리스트
distance : 주변 데이터들의 떨어진 거리 데이터 리스트

In [43]:

plt.show()