본 포스트는 고려대학교 김성범 교수님의 Youtube 강의 "[핵심 머신러닝] K-nearest neighbors & Distance Measures"을 참고하였습니다.

분류/예측을 위한 학습 방법

분류와 예측 문제를 풀기 위한 머신러닝 기법들을 아래와 같이 크게 2가지 approach로 나눌 수 있다.

Model-based Learning (모델 기반 학습)

• 데이터로부터 모델을 생성하여 분류/예측 진행 (즉, 분류/예측 모델을 학습)
• linear regression, logistic regression, decision tree, SVM, neural network, ...

Instance-based Learning (사례 기반 학습)

• 별도의 모델 생성없이 데이터 베이스에 있는 자료들을 분류/예측에 사용
• 각각의 관측치 (instance) 만을 이용하여 새로운 데이터에 대한 예측을 진행
• 대표적으로 KNN 알고리즘이 있음.

KNN 알고리즘 요약

• 알고리즘의 동작은 매우 단순함.
  - 새로운 데이터가 들어오면 데이터 베이스에 저장되어 있는 데이터(학습 데이터)와 비교하여 가장 거리가 가까운 (즉, 가장 유사도가 높은) $k$의 데이터로 예측 또는 분류를 수행
  - 기존 데이터와 단순 비교이기 때문에 별도의 모델을 학습하지 않음. 때문에 lazy learning이라고 부름.
• 비선형 분류와 회귀에 모두 사용할 수 있음.
• 모든 데이터를 전부 dB에 저장할 수 없는 경우 언더 샘플링 된 데이터만 저장 (연산 속도를 위해서라도 언더 샘플링이 필요)

[그림 1] 회귀문제(좌측)와 분류문제(우측)에서의 KNN 사용 예시 (k=3)

회귀

• 가장 가까운 $k$개의 데이터의 산술 평균으로 예측
• 예를 들어, [그림 1]의 좌측 그림과 같이 파란색 점들의 ($x, y$)값이 데이터 베이스에 있을 경우, $x_{test}$와 가까운 $x$값을 갖는 $k$개의 점들 선택하여 이들의 $y$ 값의 평균으로 $y_{test}$를 추정
• 평균 뿐만 아니라 중간값, 최대값 등을 대표값으로 사용해도 되지만 산술평균을 사용하는 것이 가장 성능이 좋은 것으로 알려져 있음.

분류

• 가장 가까운 $k$개의 데이터 중 다수 범주로 분류
• 예를 들어, [그림 1]의 우측 그림과 같이 두 범주의 학습 데이터가 있을 때, 새롭게 주어진 테스트 데이터(검정색 동그라미)가 어느 범주에 속하는지 결정하기 위해 가장 가까운 $k$개의 포인트를 찾고 그 중 다수에 해당하는 범주(파란색 +)로 분류

Weighted KNN

• 기본적인 KNN 알고리즘에서 $k$개의 이웃한 데이터들 중 거리가 가까운 데이터와 거리가 먼 데이터에 모두 동일한 가중치를 적용하고 있는 것의 한계를 극복하기 위해 고안
• 테스트 데이터 $\mathbf{x}_{test}$와 $i$번째 학습 데이터 간의 거리를 $d(\mathbf{x}_{test}, \mathbf{x}_i)$라고 할 때, weight 값을 다음과 같이 거리 제곱의 반비례하도록 정의 (가까운 데이터에 더 많은 가중치를 주기 위해)
  $w_i=\frac{1}{d(\mathbf{x}_{test}, \mathbf{x}_i)^2}$
• 회귀에 적용
  $\hat{y}_{test}=\frac{\sum_i{w_iy_i}}{\sum_i{w_i}}$

• 분류에 적용 ($c$는 클래스를 의미하고, $I(A)$는 indicator function을 의미(즉, A가 참일 때는 1, 그렇지 않으면 0))
  $\hat{c}_{test}=\max_{c}\sum_iw_iI(\mathbf{x}_i \in c)$

장점과 한계

• 데이터 내 노이즈의 영향을 크게 받지 않음.(특히, Mahalanobis distance와 같이 데이터의 분산을 고려할 경우)
• 학습 데이터의 수가 많을 경우에 효과적일 수 있으나, 새로운 관측치와 모든 학습 데이터 간의 거리를 측정하여야 하므로 계산 시간이 오래 걸림.
• 학습 데이터의 수가 적으면서 회귀에 적용할 경우, 새로운 샘플이 학습 데이터의 범위를 벗어나면 엉뚱한 값을 예측할 수 있음.
• $k$ 값을 설정해야 함.
• 어떠한 거리측도를 사용하는 것이 적합한지 불분명한 경우가 많음.
• 고차원 데이터에는 잘 동작하지 않음. (차원이 커질수록 거리측도의 유효성이 떨어짐.)
• 많은 문제에서 메모리 요구사항, 처리시간, 성능 등의 면에서 한계가 명확함.
  - 상식선에서는 알고 있어야 하겠으나 실제 시스템에 적용할 일은 거의 없다고 봐도 무방함.

$k$값 결정 하기

• $k$가 작으면 국부적인 데이터의 변화에 민감하므로 오버피팅되기 쉽고, $k$가 너무 크게 되면 언더피팅의 위험이 있음.
• 최적의 $k$를 결정하기 위한 어떠한 이론적 모델이 존재하지 않으며 오로지 실험적으로 결정하여야 함.
• 일정 범위 내로 $k$ 값을 조정해가며 분류/예측 결과를 관찰하고 가장 좋은 결과를 보이는 $k$ 값을 선정함. (그리드 서치)
  - 분류문제는 오분류율 등으로 판단하고, 회귀문제는 SSE(Sum of Squared Error)로 판단
  - (테스트 데이터의) 오분류/예측오차의 개선이 미미하거나 역으로 증가하는 $k$ 값을 최적의 $k$로 판단

[그림 2] 최적의 k값 결정 예시

거리 측도

• 데이터 간의 거리를 측정하는 방법은 매우 다양
• 보통 특성 간 값의 범위와 분산 등이 다르기 때문에 측정 단위의 영향력을 없애기 위해 거리 측정 이전에 반드시 정규화 혹은 표준화 등의 데이터 스케일링이 필요

Euclidean Distance

• 두 점 간의 기하학적 거리를 측정
  $d(\mathbf{x},\mathbf{y})=\sqrt{\sum_i |x_i-y_i|^2}$

Manhattan Distance

• block 또는 city-block이라고도 함.
• 두 관찰치 사이의 거리로 각 feature간 차이의 절대값의 합
  $d(\mathbf{x},\mathbf{y})=\sum_i{|x_i-y_i|}$

Mahalanobis Distance

• 변수 내 분산, 변수 간 공분산을 모두 반영
• 공분산을 고려함으로써 기하학적으로는 더 멀리 떨어져있음에도 불구하고, 통계적으로는 더 가까울 수 있음.
• 변수 간 correlation이 없을 경우, Euclidean distance와 동일
• 정의식은 다음과 같음. ($C$는 공분산 행렬)
  $d(\mathbf{x},\mathbf{y})=\sqrt{(\mathbf{x}-\mathbf{y})^T C^{-1} (\mathbf{x}-\mathbf{y})}$

Cosine Similarity

• 두 벡터의 코사인 유사도, $S(\mathbf{x},\mathbf{y})$를 측정하고 $1-S(\mathbf{x},\mathbf{y})$와 같은 방식으로 거리를 측정
• cosine similarity는 곧 내적과 같기 때문에 $1-S(\mathbf{x},\mathbf{y})$는 0~2 사이 값을 가짐.
  $S(\mathbf{x},\mathbf{y})=\frac{\sum_ix_iy_i}{\sqrt{\sum_ix_i^2\sum_iy_i^2}}$

Correlation Distance

• Cosine Similarity와 같이 데이터 간 Pearson correlation($r$)을 먼저 구하고 $1-r$을 거리측도로 사용하여 데이터 패턴의 유사도를 반영
• 0~2 사이의 값을 가짐.
• 참고로 Pearson correlation의 정의는 아래와 같음. (KNN 문제에서는 $\mu_x$와 $\mu_y$ 모두 feature의 평균 $\mu_i$로 대체하여야 하는건가?)
  $r=\frac{\sum_i(x_i-\mu_x)(y_i-\mu_y)}{\sqrt{\sum_i(x_i-\mu_x)^2}\sqrt{\sum_i(y_i-\mu_y)^2}}$

Spearman Correlation Distance

• 김성범 교수님 강의에서 다룬 내용인데 당장 쓸일이 없을 것 같아 생략함. (그렇지만 나중을 위해 제목은 남겨 놓음.)
• 순위 등의 feature에 적합한 방식

Chebyshev Distance

• 두 관찰치의 거리측도를 feature 간 최대 거리 차의 절대값으로 정의
  $d(\mathbf{x},\mathbf{y})=\max|x_i-y_i|$

Minkowski Distance

• 민코브스키 거리
• $p$-norm으로 계산
  $d(\mathbf{x},\mathbf{y})=\bigg(\sum_i |x_i-y_i|^p\bigg)^{1/p}$

참고자료

[1][핵심 머신러닝] k-nearest neighbors & Distance Measures (url: https://www.youtube.com/watch?v=W-DNu8nardo&list=PLpIPLT0Pf7IoTxTCi2MEQ94MZnHaxrP0j&index=19)
[2] https://towardsdatascience.com/how-to-find-the-optimal-value-of-k-in-knn-35d936e554eb
[3] 박해선, 혼자공부하는 머신러닝+딥러닝, 한빛미디어.