Nearest neighbor regression

예를 들어 Square feet에 따라 집값을 예측하는 모델을 만든다고 가정하면 그 집값은 분명히 비슷한 크기의 Square feet를 가지는 집과 가격이 비슷할 것이다. 만약 아래와 같이 4개의 집에 대한 데이터를 알고 있다고, 가장 비슷한 크기의 Square feet와 집값이 같다고 하면 우리의 모델은 아래의 주황색 선과 같을 것이다.

 

 

이렇듯 가장 가까운 1개의 데이터만 찾는 문제의 경우 1-NN(Nearest neighbor)이라 하며 아래와 같이 정의된다.

 

x, y는 위의 그래프에 따르며 x_q는 현재 내가 찾고자 하는 데이터이며 x_i는 데이터 셋의 i번째 데이터이다. 이때 predict는

이다.

그렇다면 distance는 어떻게 계산할 수 있을까? 만약 좌표평면 위라면 아래와 같이 각 데이터 간의 거리를 Voronoi tessellation으로 표현할 수 있을 것이다.

 

 

Voronoi tessellation은 평면을 특정 점까지의 거리가 가장 가까운 점의 집합으로 분할한 그림이다. 만약 1차원이라면 distance는 Euclidean distance로 간단하게 표현할 수 있다.

 

고차원의 경우 즉, feature수가 더 많은 경우 각 feature의 가중치를 달리 주어 distance를 계산할 수 있을 것이다.

 

이밖에도 Mahalanobis, rank-based, correlation-based, cosine similarity, Manhattan, Hamming 등등 다양한 방식으로 distance를 계산할 수 있다. 예를 들어 Euclidean과 Manhattan 방식을 시각적으로 비교하면 아래와 같다.

 

 

이제 본격적으로 1-NN 알고리즘을 적용해보자. 우선 아래와 같은 예시를 이용하면

 

1-NN 알고리즘은 다음과 같이 표현된다.

 

 

nearest neighbor까지의 거리를 무한대로 설정하고 모든 데이터에 대해 거리를 측정하여 가장 짧은 거리를 계산해 nearest neighbor를 찾는 간단한 알고리즘이다.

 

실제로 이 알고리즘을 아래의 첫 번째 그래프와 같이 노이즈가 적고 빽빽한 데이터셋에 적용하면 비교적 정확한 모델(초록색 선)이 된다.

 

 

하지만 중간 그래프와 같이 데이터셋이 비어있다면 정확한 예측이 어려우며 오른쪽 그래프처럼 데이터셋에 노이즈가 있다면 더욱더 그렇다. 이 문제를 해결하기 위한 방법이 바로 k-Nearest neighbors(k-NN)이다.

 

집값 예측으로 돌아와서 분명히 1개의 가장 가까운 집을 고려하는 것보다 비슷한 k개의 집을 고려해 집값을 예측하는 것이 더 합리적일 것이다. 그래서 k-NN 알고리즘은 우선 가장 거리가 짧은 k개의 데이터 집합을 찾는다.

 

이 집합은 거리에 대해 오름차순으로 정렬되어있으며 따라서 임의의 i>k인 i에 대해 다음 조건을 만족한다.

 

또한 predict는

 

로 결정된다.

k-NN의 알고리즘은 아래와 같이 표현된다.

 

이제 1-NN과 마찬가지로 k-NN 알고리즘을 적용한 그래프를 살펴보자.

 

 

빨간색 세로선은 우리가 예측하고자 하는 데이터의 위치이며 노란색 상자는 k개의 가장 가까운 점들이 위치한 거리를 의미한다. 빨간색 점들은 이 k개의 데이터(여기서 k=30)를 의미하며 초록색 선은 predict이다. 분명히 1-NN에 비해 노이즈가 포함된 데이터셋에 대해 합리적인 예측모델을 제공한다. 하지만 양쪽 boudary에 predict가 되지 않는 영역이 존재하며 predict가 discontinuous하다는 문제가 존재한다.

 

앞서 발생한 k-NN의 문제점을 해결하기 위해 weight k-NN이라는 수정된 k-NN 알고리즘을 고려할 수 있다. 만약 C_qNNj를 j번째 데이터의 distance의 weight라 하고 이 값이 거리에 반비례한다 가정하면 새로운 predict는 아래와 같이 표현된다.

 

이렇게 거리에 따라 weight를 적용하는 것을 kernel이라 하는데 일반적으로 사용되는 kernel들의 종류는 다음과 같다.

 

대부분의 kernel들이 거리가 lamda 이상이 되면 weight를 0으로 만드는데 특이하게 gaussian kernel은 거리에 상관없이 weight가 0이 되지 않는다. 위의 kernel를 사용해 weight를 다시 정의하면

 

 

이다. 따라서 predict는

 

이다. (이를 Kernel regression이라 한다.)

앞에 소개한 kernel들 중 Epanechnikov kernel을 lambda=0.2로 그려본 그래프는 다음과 같다.

 

확실히 kernel를 사용하면 boudary에 predict가 되지 않는 영역의 문제와 predict가 discontinuous 하다는 문제가 해결됨을 확인할 수 있다. 또한 lambda의 크기를 조절하여 모델의 복잡도를 조절할 수 있는데 아래와 같이 lambda를 0.04, 0.4로 변화시켜보면 그 차이를 확실히 알 수 있다.

 

lambda = 0.04

lambda = 0.4

 

lambda가 작을수록 모델의 복잡도가 증가하여 overfitting 되며, 람다가 클수록 모델의 복잡도가 감소한다.

 

k-NN과 kernel regression은 nonparametric approaches이다.

Parametric approaches는 미리 pdf(probability density function)에 대한 모델을 정해놓고 데이터들로부터 모델의 파라미터만 추정하는 방식이다. 예를 들어, '일일 교통량'이 정규분포를 따른다고 가정해 버리면 관측된 데이터들로부터 평균과 분산만 구하면 되기 때문에 비교적 간단한 문제가 되어 버린다. 그런데 현실 문제에서 이렇게 모델이 미리 주어지는 경우는 많지 않다. 이 경우 어떠한 사전 정보나 지식 없이 순수하게 관측된 데이터만으로 확률 밀도 함수를 추정해야 하는데 이를 nonparametric approaches라 부른다.

 

nonparametric은 parametric에 비해 고차원의 데이터를 좀 더 유연하게 regression 할 수 있다는 장점이 있다. 하지만 일반적으로 높은 성능을 위해서는 N=O(exp(d))의 많은 데이터 포인트 필요하다는 단점이 있다.