[인공지능] Nearest neighbor methods(이웃 알고리즘), KNN

Nearest neighbor mothod란?

학습과 분류 과정 중 하나로써, 현재까지의 training data가 존재하고 새로운 data x가 주어졌을 때, x에 대한 결과값을 x에 가장 가까운 data들을 이용하여 구하는 방법이다.

새로운 데이터인 녹색원이 빨간세모인지 파란 네모인지 분류해내는 방법                             출처 : (https://ko.wikipedia.org/wiki/K-최근접_이웃_알고리즘)

새로운 데이터와 가장 가까운 i번째 data를 찾아서, i번째x의 label(y_i)에 따라 새로운 데이터의 label을 정한다.

 

이는 분류가 Classification으로 이루어지고 있는 경우와 Regression으로 나누어지고 있는 경우로 나누어볼 수 있다.

 

 

 

Classification

x_new의 위치가 노란색 부분에 위치한다면, y(x_new)는 class3으로 정할 수 있다.

 

 

 

Regression

x_new의 위치가 다음과 같다면 x_new의 y값은 y₂로 결정된다.

 

 

 

k-Nearest neighbor method(최근접 이웃 알고리즘, KNN)

가장 가까운 1개의 data를 보는 것이 아니고, 가장 가까운 k개의 data를 본다. 이를 사용하면 보다 안정적으로 data를 분류할 수 있게된다.

 

Classification

y값이 근접 값들의 다수결(majority)에 의해 정해진다.

k=3일 경우, 위 그림에서 실선이 boundary로, 빨간 삼각형이 2개, 파란 사각형이 1개 이기 때문에, 초록 원은 빨간 삼각형이 된다.

k=5일 경우, 위 그림에서 점선이 boundary로, 빨간 삼각형이 2개, 파란 사각형이 3개 이기 때문에, 초록 원은 파란 사각형이 된다.

 

 

Regression

새로운 data 가까이에 i_1 ~ i_k 번째의 data가 존재한다면

주변 k개의 data의 y값들의 평균이 새로운 y값이 된다.

 

 

 

Bayes Optimal Classifier

새로운 data에 대해 가장 알맞는 예측을 하는 확률 적 모델이다.

p₁과 p₂는 각각 class1, class2에 대한 density function(확률 밀도 함수)이다.

새로운 데이터 x_new가 들어왔을 때, p₁의 확률이 더 높다면 class1, p₂의 확률이 더 높다면 class2로 분류된다고 하자.

이 값들은 모두 확률로 정하기 때문에, p₁의 확률이 높지만 실제 값은 class2이거나, p₂의 확률이 높지만 실제 값은 class1인 경우도 존재한다. 이러한 경우의 error는 각각 다음과 같다.

위 error를 바탕으로, 전체 확률 p(x)에 대한 Risk(R)의 expectation 을 구해보면

(R=integral(error_function * p(x))로 생각해도 좋을 듯 하다. 아래 k-nearest neighbor classification과 비교.)

 

이때, 이 R값을 "bayes optimal error"라고 부른다. 

일반적인 경우, 데이터가 들어오면 그로부터 p₁, p₂ 함수를 구하고 그를 이용해 classification한다.

bayes optimal classifier은 p₁, p₂함수를 정확히 알고있는 상태에서 classification한다. 결국, 이때가 가장 정확하게 p₁,p₂를 예측하여 classification한 것이기 때문에 error가 가장 적은 경우고, optimal하다고 할 수 있다.

 

일반적인 classifier은 최대한 bayes optimal error에 가깝게 만드는 것이 목표라고 볼 수 있다.

 

 

특징

데이터의 개수가 무수히 많아지면(∞) x_NN(nearest neighbor data)는 x_new에 uniform하게 가까워 진다.

uniform하게 가까워진다는 의미는 x_new로부터 가장 먼 nearest data조차도 x_new와 가깝게 된다. (같다고 봐도 무방 할 정도)

 

error rate = (x가 class1일 확률) * (x_NN이 class2일 확률)+(x가 class2일 확률) * (x_NN이 class1일 확률) 로 본다면

 

k-Nearest neighbor classification사용 시 Error

주어진 데이터가 무수히 많고, nearest방법을 사용한다면, 그때의 error값은 다음과 같다. 

즉, k=1일 때 error는 optimal한 bayes error보다 2배정도만 나쁘게 되고, 이는 매우 근사치로 예측했다는 것이다.

k값이 커질수록 error는 줄어들게 되고, k가 ∞까지 된다면(data수 보다는{" 적다) R은 R*과 같게된다.

 

Regression 사용 시 Error

regression방식을 사용했을 때, 최선의 결과를 낼 수 있는 optimal 값을 얻기 위해선, p(x,y) (density function)를 알고 있다는 것을 전제로 한다. density function을 알고있으므로, 그 density function들의 expectation값을 y라 하고, 그들을 모두 연결 한 함수를 y(x)라 했을 때

error를 구하기 위해, 오차의 제곱에 대해 평균을 취하는 방법인 Mean Square Error(MSE)를 사용하면

다음과 같은 식을 만들 수 있다. ( y(x)는 prediction function, y는 p에 의해 realized된 값이다. ) 이 식을 변경 후 정리하면

y(x)가 prediction 함수이기 때문에, error값에 영향을 미치는 것이 y(x)인데(우리가 control할 수 있는 값이다), 두 번째 항에 y(x)가 존재하지 않기 때문에 두 번째 항은 더이상 줄일 수 없는 값이다. 또한 첫째 항은 0이상의 값이다. 

 

따라서 Error가 최소가 되기 위해선 y(x) = E[y|x]인 경우이고, 그때의 Error값이 optimal한 Error가 된다.