Nearest Neighbor Method

 

NN과 같은 경우는 데이터가 풍부하고 양질이라고 하면 충분히 다양한 환경에서 좋은 성능을 내고 있다. 알고리즘 자체가 쉽고 직관적이라서 좋고, 또 다양한 방법으로 연구도 진행중인 알고리즘이다.

 

오늘 살펴볼 nearest neighbor 는 회귀, 로지스틱회귀, 나이브베이즈 등과 같은 이론적인 배경이 있어야 하는데, NN의 경우에는 직관적이고 복잡하지 않아서 쉽게 이해할 수 있다.

 

NN은 classification 이든 regression이든 둘 다 사용이 가능하다. 

핵심은 새로운 관측치가 왔을 때 관측치의 output은 train 샘플 중 가장 가까운 샘플을 찾고 그 샘플의 output을 가지고 예측값을 생성한다.

NN 방식에는 여러가지 있는데, 먼저 kNN 부터 살펴보자.

 

kNN에서 k는 사용자가 직접 설정하는 hyperparameter이다.

아래의 그림처럼 새로운 데이터 초록색이 들어왔을 때, 어떤 class에 들어갈까 하는 문제를 말한다. 이 때 초록색을 k 기준으로 가장 가까운 샘플을 찾아서 그들의 output을 사용한다. 가장 많이 사용하는 것은 Majorty voting(다수결)이다. 그래서 k가 3이라 하면 초록색 주변 가까운 3개를 보고 다수의 빨간색 점을 선택한다. 만약 k가 5면은 파란색 점으로 초록점을 예측한다. 

 회귀 같은 경우에는 가장 간단한 방법으로 가장 가까운 이웃을 찾고 이웃들의 평균값을 할당하는 식의 예측값을 낸다.

 

그래서 데이터마다 k를 잘 설정해주어야 하는 것은 중요한 문제이다. 이런 문제를 parameter tunning이라고 한다.

 

 회귀나 로지스틱회귀나 나이브베이즈 알고리즘과의 차이점을 생각해보면 이 NN알고리즘은 non-parametric 알고리즘이다. hyperparameter는 있지만 알고리즘 학습을 통해 추정해야할 parameter가 존재하지 않는다는 것이다. 함수의 형태가 이미 결정돼있는 parametric 알고리즘들은 그러한 결정된 형태에 가장 들어맞는 쪽으로 예측을 한다. 반면에 non-parametric은 함수의 형태가 고정되어 있지 않다. 관찰한 데이터 자체에서부터 계산해나가는 방식으로 추정을 하는 것이다. 

parametric 알고리즘의 장점은 새로운 데이터가 들어오면, 고정된 함수에 대입만 하면 되니 계산이 간단해진다. 그러나 실제로 데이터가 우리가 학습으로 만들어 놓은 함수에 들어맞지 않게 되면 성능이 떨어진다. 반면에 non-parametric의 경우에는 잘못된 가정을 할 염려는 할 필요가 없다. 하지만 새로운 데이터가 들어오면 매번 그때마다 계산을 다시 해주어야 해서 계산량이 과도해질 수 밖에 없다.

 

 

 자 이제 다시 돌아가서 NN에서 핵심은 NN을 어떻게 정의할 것인가 이다. 보통 거리를 기반으로 해서 측정을 하게 된다. 보통 아래의 유클리디안 거리를 계산한다.

 

Manhattan distance

p-norm distance

 

거리 측정 지표로 사용하려면 아래의 조건을 만족해야한다.

1. 거리는 음의 값을 가질 수 없다. (non-negativity)

2. x 지점과 y지점의 거리가 0이면 둘은 같은 지점이다. (identity of indiscernibles)

3. x 지점에서 y 지점까지의 거리는 반대로 구해도 동일하다. (symmetry)

4. 삼각형 두 변의 합은 나머지 한 변의 길이 보다 항상 크거나 같다. (triangle inequality)

 

 

 

만약에 변수가 수치형 변수가 아니라 범주형 변수라면 거리를 어떻게 구해야하나?

 

범주형 변수에 특화된 거리 측정 지표들 중하나는 아래와 같다.

 

- Hamming distance

각각의 범주형 변수가 속한 카테고리가 동일한지를 본다. 카테고리가 다르다고 하면은 1을 주고 동일하면 0이 된다. 이들의 총 합으로 서로 다른 카테고리의 비율이라고 생각하면 된다. 카테고리가 다른게 많을 수록 값이 커지니 거리도 멀어진다고 할 수 있다.

Hamming distance

 

-Jaccard distance

자카드 거리는 특징 벡터들이 전부 0 이거나 1인 이진 변수인 경우에 사용을 한다. x, y벡터가 0또는 1로 이루어져 있고, 둘다 0인 경우, 하나만 1인 경우, 둘다 1인 경우의 개수를 a,b,c,d로 나타낸 테이블이다. 자카드 거리를 구하는 식은 아래와 같으며, 둘 다 0인 것을 분모에서 빼 고려하지 않고, 둘중에 하나만 1인 것들의 합으로 나타나게 된다. 즉 카테고리가 다른 것의 비율이니 서로 다른 카테고리가 많을 수록 결과 값은 커지므로 그럴수록 거리가 멀다라고 할 수 있다.

 

distance 지표는 dissimilarity라고도 한다. 왜냐하면 값이 커질수록 유사도가 떨어지기 때문이다.

 

 

1. 다른 모든 샘플과 거리를 구한다.

2. 이웃을 찾는다.

3. 이웃의 output을 사용한다.

쉽게 예측값까지 뽑아볼 수 있다.

 

 

하지만 feature들의 scale로 인한 문제가 발생한다. 아래의 그림처럼 x3의 경우 다른 변수들에 비해 scale이 굉장히 큰 것을 알 수 있다. 우측의 그림이 i1과 다른 i들 사이의 거리를 구한 것이다. x3를 보면 i1과 170, 220, 250 순으로 x3에 많이 의존하여 결정이 된 것 처럼 보인다. x1,x2,x4 변수는 상대적으로 작은 scale이라는 것도 볼 수 있다.

 

 

 

 

 그렇기 때문에 Normalization을 진행해주어야 한다. 한 변수 내의 모든 값들을 0~1사이의 값으로 만들어주는 방법이다.

주로 사용되는 정규화 방법에는 아래와 같이 2가지가 있다.

 

 

z-score normalization

표준화라고 불리는데 평균이 0이고 분산이 1이 되게 변수값을 할당하는 것이다.

min-max normalization

각 변수들의 최대/최소 값을 이용해서 변수들의 값이 마찬가지로 0~1사이에 있도록 바꿔준다.

 

 

 

 

normalization하는 것은 각 축의 중요도도 똑같이 맞춰준다는 것이다. 거리체계가 scale을 정규화하면 2차원의 경우 원을 그려서 그안에 모든 포인트들을 다시 찍어 준다고 생각하면 된다. 

 

 

 

거리 체계 자체에서도 분산이 다르거나 혹은 변수사이의 correlation을 고려할 수도 있다. 그러한 거리 체계는 아래와 같다.

Mahalanobis distance

$S^{-1}$ 샘플 공분산행렬의 역행렬을 의미한다. 유클리디안의 경우에는 이 공분산행렬의 역행렬이 identity matrix가 된다. 즉 분산을 고려하지 않는 것이라 공분산행렬의 대각원소가 1이므로 없는 것과 동일하게 된다. 

 공분산행렬은 symmetric matrix이다. 대각행렬의 역행렬은 단순하게 구할 수가 있다. 대각원소들의 역수를 취해주면 된다. 그렇게 되면 그 식은 아래의 두번째 식처럼 각 변수 i별 분산이 분모로 들어가는 것을 알 수 있다.

 

공분산 행렬에서 대각원소에 해당하는 것은 각 feature 자기 자신의 분산과도 같다. 마할라노비스 거리는 이 공분산행렬에서 각 변수들의 분산을 고려한다.

위의 d(x1, x2)는 두 지점 사이의 거리를 구하는 것으로 변수가 p 개일 때를 말한다. 그러므로 이 두 점 사이의 거리를 구하기 위해선 아래와 같은 데이터 셋에서 x1과 x2 두 좌표가 필요하고, p x p 공분산행렬이 필요하다. 위 식을 통해서 x1, x2 두 점 사이의 거리를 구하면 아래와 같다. 

 

 n 개의 샘플 중에서 x1, x2 샘플 두개 사이의 좌표와 각 변수 p가 같는 분산을 담은 공분산행렬을 사용한다.

이를 전개하면 아래와 같다. 이렇게 구하게 되면, 각 좌표가 변수 i 마다 해당하는 분산을 사용하게 된다.

 

 

공분산행렬이 대각행렬도 아니고 단위행렬도 아닐 때, 일반적인 상황일때는 어떨까.

(a)를 보면 유클리디안 거리를 가지고 k를 가지고 원을 그려볼 수 있게 되는데, 두 x, y 축의 분산을 고려하지 않는다 . 하지만 마할라노비스 거리를 가지고 원을 그리게 되면 데이터의 분산을 고려하게 되고, 그렇기 때문에 A, C가 각각 다른 거리였지만 같은 거리로, A,B 가 같은 거리였지만 각각 다른 거리를 띄게 되는 양상을 볼 수 있다. 

 즉 마할라노비스 거리는 변수들 간의 독립성이 보장이 되지 않는 경우 유클리디안 거리보다 더 정확하게 거리를 측정할 수 있다. 

 분산만 다르다고 하면 등원이 가로 혹은 세로로만 길이가 변할텐데, 공분산까지 고려하여 대각선으로도 원의 모양이 변형될 수 있다.

 

 

kNN의 절차

1. k 이웃의 기준을 정의

2. test 셋의 개별 포인트에 대해서 k 개의 이웃을 찾음.

3. 이웃의 output을 가지고 예측값을 생성.

 

kNN을 활용해서 k 가 3일 때, classification 절차를 예제를 통해 살펴보자. 

 

위와 같은 데이터가 있을 때 index 5번의 샘플이 test 데이터라고 하고, x5 번에 대한 예측을 해보자. 

1. x5와 나머지 모두와의 거리를 구한다.

2. k=3 에 의거 이웃을 고른다. 중복시 랜덤 혹은 먼저나온 순서로 채택한다.

3. 이웃의 output을 고려한다.

4. 최종 예측값을 결정한다.

 

 

 

kNN같은 경우는 k 가 정해지고 가까운 k 개를 무조건 찾아야 한다. 이번에는 어떤 범위를 가지고 그 범위 안에 있는 것들을 이웃으로 선정하는 방법에 대해 알아본다.

 

Fixed-Radius of Nearest Neighbors 

 

아래의 그림은 kNN으로 했을 때 문제점을 보여준다. 아래의 경우 무조건 k를 5개 선정해야하기 때문에 쓸데없는 것도 이웃으로 선정하게 된다.

k=5

하지만 Fixed-Radius 의 경우는 아래와 같이 지정한 범위 내에 있는 데이터를 모두 이웃으로 선정한다. 단순히 위와 같은 문제에 대해서 더 Robust하게 작동한다.

 

1. 이웃이라고 판정할 반경을 결정한다.

2. 반경내에 이웃을 찾는다.

3. 이웃들의 output을 조사하여 예측값을 결정한다.

 

 

 

 

Nearest Neighbor 알고리즘은 단순하다. 나와 비슷한 이웃들의 output을 활용하는 것이다.

이 NN 알고리즘이 직관적이고 단순해서 변형할 수 있는 여지가 많다. 그래서 많이 활발하게 연구가 되고 있는 알고리즘 중에 하나이다. 

 어떤 관점에서 연구를 진행하는지 잠시 알아보자.

 

1. 얼마의 k 또는 radius를 선택했을 때 가장 최적인가에 대한 문제.

 -> 하나씩 다 바꿔 가면서 최적의 k 또는 r을 찾는다. 여기서는 시간이 오래 걸린다는 문제가 있다.

 

=> 그래서 데이터의 수치나 분포를 고려해서 최적의 k, r를 찾는다.

cross-validation도 좋은데 global하게 하나만 사용해야 하나라는 문제가 있다. 데이터 분포가 주어지면 영역을 나누고  영역별로 k, r을 지정해주는 방법을 연구하기도 한다.

 

2. 어떻게 class를 결정할 것인가에 대한 문제.

 -> 이웃이 가진 output 에 거리에 따라서 weighting을 주는 연구.

 -> classification의 경우 불균형 데이터에서 관심있는 부분은 도메인에 따라서 minority를 더 찾고자 하는 경우가 있다. 예를 들어 질병 진단하거나 이상치나, 사기탐지 등의 경우를 미리 알아내려고 할 때는 일반적으로 정상보다 적은 빈도로 일어나지만 이것 때문에 발생하는 타격이 정상을 맞추지 못했을 때보다 더 크기 때문에 minority를 잘 맞추는 것이 중요한데, minority가 너무 희소하니까 이웃이 majority가 더 많이 들어갈수도 있으니, 이러한 균형을 조절하기도 한다.

 

3. 이웃을 어떻게 찾을 것인가에 대한 문제. 거리 지표를 어떻게 정의할 것인가?

 -> 더 optimal하게 이웃을 찾는 방법은 무엇이 있을까?