What is Nearest Neighbor?

250x250

Notice

Recent Posts

Recent Comments

Today

Total

관리 메뉴

ROKO

What is Nearest Neighbor? 본문

Artificial Intelligence/Machine Learning

What is Nearest Neighbor?

RO_KO 2022. 9. 10. 17:41

728x90

Nearest Neighbor(최근접 이웃)은 ML의 대표적인 방법론 중 하나이다. NN을 논하기 전에 필요한 정의부터 살펴보자.

ML은 training set을 통해 inductive learning(귀납적 학습)
최종 목표는 input $x$를 넣었을때 그에 해당하는 결과를 출력하는 함수 $f(x)$
이상적인 알고리즘은 쉽게 찾을수 없으므로 다양한 방법론을 통해 근사
이상적인 함수를 $f$ (target function), 이에 근사하는 함수를 $h$ (hypothesis)

가능한 모든 $h$ 를 모아논 함수들의 공간을 Hypothesis space $H$(가설 공간)이라 하며 최적의 함수 $h$ 를 찾는다. 이를 위해 training set에 대한 error function(손실 함수)나 Misclassification(오류)를 지표로 사용한다.

※ input에 training set에 없던 데이터가 들어오면?

$h$ 구할때 Generalization(일반화) 된 함수를 찾아야 한다. (처음보는 데이터도 예측)
$h$ 가 모든 예제들에 대해서 $f$ 에 잘 근사된다면 consistent(일관성)이라고 한다.

유의점

hypothesis space 불충분, (Ex $f(x) = ax + b + xsin(x), H : polynomials of finite degree$)
현실의 많은 Noisy data (이상치), (Ex 여성 얼굴같은 남자)

$H$ 가 target function을 포함하는 공간이라면 최적의 근사 함수를 찾을수 있으나 아닌 경우 그렇지 못하다. 따라서 처음부터 넓은 가설공간 $H$를 설정한는 것이 좋다. 하지만 $H$가 커질 수록 계산 과정 complexity도 커지므로 trade off 관계에 있다.

데이터 종류 : 이미지, 텍스트, 목소리, 등등 -> 컴퓨터가 학습하므로 벡터화 필요
일반적인 방법 : $R^d$ d-dimension의 input vector로 representation 하여 입력

벡터화로 전처리한 training set은 대체로 " input vector - label " 형태로 구성 (supervised learning 기준)

이제 벡터화한 데이터를 가지고 Nearest Neighbor 알고리즘을 적용해 보자.

NN에 적용하기 앞서 어떤 거리함수를 사용할 것인지 정해야한다. 일반적으로 p-norm = ${\left\|x-y\right\|}_p = \sqrt[p]{\sum_{j=1}^{d}(x_j-y_j)^p}$ 에서 p = 2 형태인 L2 norm (Euclidean metric)을 사용한다. p = 1 일떄는 L1-norm 이라고 한다.

$$L1 - norm = {\left\|x-y\right\|}_1 = \sum_{j=1}^{d}\left|x_j\right|-\left|y_j\right|$$

$$L2 - norm = {\left\|x-y\right\|}_2 = \sqrt{\sum_{j=1}^{d}(x_j-y_j)^2}$$

Nearest Neighbor Algorithm

Find example ($x^* , t^*$ (from the stored training set) closet to $x$ (Use L2 - norm)
$x^* = \underset{x^{(i)} \in train set}{argmin}dist(x^{(i)} , x)$
Output $y = t^*$ (choose the largest num of the label of nearest training set data)

$x$의 label을 구할 때 train set data들과 정해진 metric(거리함수)를 이용해 가장 가까운 data를 구하고 그 data의 label을 $x$의 label로 예측하는 알고리즘이다.

※ 여기서 L2-norm 을 사용하였는데 메모리와 시간은 소중한 자원이다. 수식을 보면 제곱한 상태로도 거리를 비교할수 있으므로 square root를 굳이 자원을 낭비하여 계산할 필요가 없다.

위 알고리즘을 적용한 결과를 voronoi diagram을 이용해 표현하면 이렇다. 이때 각 영역을 구분하는 선을 Deicision boundary(결정 경계)라고 한다.

한계점

단순 Nearest Neighbor는 가장 가까운 하나의 데이터만 보기 때문에 trainging data들에 대해 100% 정확도를 보여준다. 그러므로 이상치에 민감하게 반응하여 일반성을 잃고 임의의 dataset에서는 좋은 결과를 보여주지 못한다.
이에 대한 해결책으로 가장 가까운 점을 1개가 아닌 K개를 뽑아 voting형식으로 label을 결정하는 K-nearest neighbor (KNN)을 사용한다.

K - Nearest Neighbor Algorithm

Find k examples $\begin{Bmatrix}(x^{(r)},t^{(r)})\end{Bmatrix}_{r=1}^{k}$ closest to the test instance $x$
Classification output is majority class $y = \underset{t}{argmax}\sum_{r=1}^{k}\mathbb{I}[t=t^{(r)}]$

K값을 15로 설정한 결과를 비교해 보면 일반화가 잘 이루어진 것을 알 수 있다. "일반화가 잘 이루어졌다"는 의미는 결정경계가 매끄럽고 완만하게 각 경계를 나누어 임의의 데이터도 잘 분별하고 K=1인 경우처럼 이상치에 민감하게 반응하지 않는 상태를 말한다.

How to choose K ?

Small K

fine-grained(세밀한) 패턴 파악
Overfitting(과적합) 문제 (결정경계가 너무 복잡)

Large K

평균적인 넓은 패턴 파악
Underfitting 문제 (결정경계가 너무 단순)

따라서 K 값은 학습이 아닌 설계자가 직접 정해야하는 값으로 hyperparameter라 불린다. hyperparameter는 일반화가 잘되는 값으로 설정한다. 이를 위한 방법으로 training set에서 일부를 validation set으로 분리하여 일반성을 검증한다. 그중 validation set에 가장 일반화가 잘되는 (잘 예측하는) 모델을 최종 모델로 정하게 된다.

이후 validation set에 과적합 되는 문제가 발생하는데 전체 데이터셋을 training set / validation set / test set 으로 나누어 학습을 진행한다. 최종 모델이 test set에 예측한 결과 값이 정확도가 된다.

평균적으로 train set : validation set : test set 의 비율은 정해지지 않았으나 8:1:1 정도, 대다수 데이터가 train set에 있다.

KNN Regression (회귀)

KNN 을 이용해서 분류가 아닌 회귀도 해볼수 있을까?

알아내고자 하는 값 x의 주위 K개의 데이터의 값을 평균하여 예측

한계점

군집한 내의 데이터의 경우 괜찮으나 기존 데이터 밖의 새로운 데이터 경우 예측하기 어렵다
예측, 훈련이 동시에 되는 알고리즘으로 데이터가 많을수록 많은 처리시간이 소요되어 비효율적이다.

The Curse of Dimensionality (차원의 저주)

모델이 학습하기 위해서 많은 데이터가 필요하다. 그렇다면 얼마나 많은 데이터가 필요할까?

차원이 증가할수록 데이터 간의 거리가 멀어지는 것을 한눈에 알 수 있다. 앞부분에 다뤘듯이 데이터를 벡터화하여 학습하게 되는데, 이미지의 경우 32x32 흑백 이미지만 하더라도 데이터가 32x32 = 1024으로 표현된다.

$d$차원 공간에 radius(반지름)가 $\varepsilon$인 hypersphere(초구) 안을 채우려면 얼마만큼의 데이터가 필요할까?

전체 부피를 $[0,1]^d = 1$라 할때, $O((\frac{1}{e})^d)$ 만큼의 데이터가 필요하다. 이 결과는 차원이 증가할수록 필요한 데이터가 기하급수적으로 늘어난다는 것을 알려준다.

반대로 10 차원 공간 $[0,1]^10 = 1$에서 10%, 부피 0.1을 이루는 hypercube(초입방체)의 한 변 r 의 길이는 얼마일까?

$$r = 0.1^{\frac{1}{10}} \approx 0.8$$

한 변의 길이가 1인 10차원 hypercube에서 한 변이 0.8인 hypercube가 차지하는 비율은 고작 약 10%밖에 되지 못한다. 차원이 증가할수록 필요한 데이터가 많음을 직접 알아보았다.

현실적으로 많은 데이터를 구하기도 힘들고 그 많은 데이터를 학습에 사용하기도 시간과 하드웨어가 부족하다. 또한 데이터의 일부 값으로 충분히 데이터를 설명할 수 있기 때문에 데이터를 벡터 차원을 고차원에서 저차원으로 낮추어 manifold를 구성한다. NN은 이런 특성을 적용해 고차원에서 좋게 적용되기도 한다.

Normalization (정규화)

NN은 특성에 따라 위치, 거리에 따라 민감하게 반응한다. 따라서 NN의 데이터 위치 구성을 변화시켜 준다면 더 좋은 예측값을 기대할수 있다.

$$ \overset{\sim }{x} = \frac{x_j-\mu_j}{\sigma_j} $$

정규화를 이용해 평균이 0 분산이 1인 데이터 분포로 변화시켜 준다면 더 좋은 결정 경계가 생길 수 있다. 하지만, 특징 값 크기 자체가 중요한 의미를 내포한 경우 함부로 정규화 해서는 안된다.

Nearest Neighbor Computational Cost

Training time : $0$

Test time(per query) : $D-dim (L2 - norm) with N data : O(ND), Sort the distances : O(NlogN)$

하나하나의 테스트에 이만큼의 시간 소모되므로 일반적인 사용으로는 좋지 않다. 또한 모든 데이터를 저장해야할 메모리도 필요하므로 효율적이지 않다. 일반적인 생활에서 에측 모델을 사용함에 있어 훈련 시간이 길더라도 예측 시간이 짧은 모델이 더 유용하고 상품성이 있다. 따라서 K - Nearest Neighbor같은 단순한 알고리즘 모델은 적용하기는 쉬우나 실용성은 없다고 판단한다.