[KNN] KNN에 대해 알아보자

woo0_hooo·2021년 4월 7일
0

인공지능 수업 들으면서 공부한 내용

Instance-Based Learing

Nonparametric Methods

  • 데이터 자체를 기반으로
  • no explicit model !
  • 모든 데이터를 저장
    -> 새로운 데이터가 들어왔을때 그제서야 output을 계산하는 lazy learning

Parametric Methods

  • 대부분은 Parametric Methods
  • concept model is specified with one or more parameters
  • parametric은 data의 분포, output을 내는 parameter를 사용
  • data를 통해 모델을 만들고, 그 모델을 통해서 추론
    e.g. Gaussian distribution

Instance-Based Learning

  • 이전의 observation으로 database 생성
  • 새 input x'd에 대한 예측을 위해서 db에서 가장 유사한 data인 x를 찾아 Output 내보내기
    -> 이를 위해서
  1. Distance Metric : 유사도 측정
  2. Number of neighbour : 몇개를 뽑을지
  3. Method to combine neighbours' outputs : Output을 어떻게 합칠지

를 결정해야 한다.

1-Nearest Neighbour

가장 가까운 neighbour 하나만 찾는 1NN에 대해 먼저 알아보자.

  1. Distance Metric : 대부분 Euclidean
    $d\left( x,x'\right) = \sqrt {\sum {i=1}^{f} \left( x{i}-x'_{i}\right)^2 }$
  2. Number of neighbour : 1
  3. Method to combine neighbours' outputs : 1개만 있어서 합칠 필요 없음

-> 모든 데이터를 기억하고, 가장 유사한 결과를 반환하는 것과 같다.

알고리즘

Training data $(x_1, y_1), ..., (x_n, y_n)$에 대해서 $x_{new}$에 대한 $y_{new}$ 구하기

  1. Euclidean Distance를 이용해서 $x_{new}$와 가장 가까운 값 $x'$을 찾는다.
  2. $y_{new}$ = $y'$

-> 문제점

  • 1개만 반환하므로 output 자체의 정확도가 떨어질 수 있음 (noise 포함)
  • 새 data를 잘 일반화하지 않을 수 있음

K-Nearest Neighbour

1NN의 이러한 문제점을 보완하고자, 1개의 점이 아닌 K개의 가장 가까운 점을 찾는 방법이다.

  1. Distance Metric : 대부분 Euclidean
    $d\left( x,x'\right) = \sqrt {\sum {i=1}^{f} \left( x{i}-x'_{i}\right)^2 }$
  2. Number of neighbour : 1
  3. Method to combine neighbours' outputs
    • Classification
      • Majority Vote : 어느 class가 제일 많은지 단순히 count
        $y_{new} = argmax_c \sum_{k} (y_k = c)$
        -Weighted Majority Vote : 거리 등에 따라 가중치를 줘서 계산
        $y_{new} = argmax_c \sum_{k} w_k(y_k = c)$
    • Regression
      • Average : 가장 가까운 K개의 Output의 평균 내기
        $y_{new} = \sum_{k} \frac{1}{k} y_k$
        -Weighted Average : 거리 등에 따라 가중치 주기
        $y_{new} = \sum_{k} w_k y_k$
    여기서 $argmax_c$는 이 값이 max가 되게 하는 argument c를 반환한다.

특징

  • K 고르기 : KNN의 parameter인 k값에 따라 결과가 달라질 수 있다

    예를 들어, 위와 같은 경우에서 k=3일때는 class B, k=6일때는 class A로 classification의 결과가 달라진다.
  • 복잡도 : time complexity는 $O(n)$이다.
    -> kd-trees를 이용한다면 $O(log n)$으로 줄일 수 있다고 한다.

장점

  • 구현이 쉽고 효과적이다 : 학습- 그냥 data 집어넣기, 추론- $O(n)$
  • 주로 다른 알고리즘의 baseline이 된다
    : 최소한 이정도의 성능은 돼야 한다의 지표
  • 정확도가 높고 data에 대한 가정이 필요없음

단점

  • 대부분의 연산이 추론에 사용된다.
  • data의 수 만큼의 저장공간 : space complexity $O(n)$
  • 성능이 Distance Metric에 영향받는다
    -> 대부분은 Euclidean, Manhathan distance 등을 사용한다
  • K 고르기가 중요함 -> hyper-parameter인 k 설정이 중요함
profile
Hongik CE

0개의 댓글