[KNN: K-Nearest Neighbor] 이론

Surf in Data·2022년 4월 3일
0

machine learning

목록 보기
5/7
post-thumbnail

KNN(K-Nearest Neighbors)

  • 별도의 모델 생성 없이 인접 데이터를 분류/예측에 사용하는 기법, 새로운 데이터가 들어왔을때 해당 데이터에 근접 한 K개의 데이터를 통해 예측한다.
  • Instance-based Learning: 각각의 관측치(instance)만을 이용하여 새로운 데이터에 대한 예측을 진행
  • Memory-based Learning: 모든 학습 데이터를 메모리에 저장한 후, 이를 바탕으로 예측 시도
  • Lazy Learning: 모델을 별도로 학습하지 않고 테스트 데이터가 들어와야 비로소 작동하는 게으른(Lazy) 알고리즘
  • classification일 경우 k개의 이웃중에 가장 많이 나타나는 범주로 해당 class를 추정한다. tie문제를 막기 위해 K는 홀수로 정하는것이 좋다.
  • regression일 경우 k개의 이웃들의 대표값(평균)으로 추정한다.

K를 정하는 방법

  • k는 1부터 전체 데이터의 개수만큼 가능하다.
  • 너무큰 k는 underfitting
  • 너무작은 k는 overfitting
  • 적당한 k를 구하는 방법: cross validation을 통하여 error가 제일 작은 최적의 k를 구하면된다.
  • KNN의 error function

여러가지 거리의 측정 방법

  • 거리를 계산하기전의 데이터 내 변수들이 각기 다른 데이터 범위, 분산등을 가질 수 있으므로, 데이터 정규화를 통해 이를 맞추는것이 중요하다.
  • Euclidean Distance:
    • 가장 흔히 사용되는 거리측도
    • 두 관측치 사이의 직선 거리
  • Manhattan Distance:
    • x 에서 y로 이동 시 각 좌표축 방향으로만 이동할 경우에 계산 되는 거리
  • Mahalanobis Distance:
    • 변수 내 분산, 변수 간 공분산을 모두 반영하여 x,y간 거리를 계산하는 방식
    • 데이터의 covarinace matrix가 identity matrix인 경우는 Euclidean Distance와 동일하다.

KNN의 학습

KNN은 모델을 생성하는 것이 아니여서 최적의 k 와 distance 측정 방법을 알아내는것이 KNN을 학습하는 과정이다.

Weighted KNN

  • 일반적인 KNN과는 달리 새 데이터와 기존 학습 관측치 간의 거리를 가중치로 하여 예측결과를 도출한다.

KNN의 장점

  • 데이터 내 노이즈에 영향을 크게 받지 않으며, 특히 Mahalanobis distance와 같이 데이터의 분산을 고려할 경우 강건하다.
  • 학습 데이터의 수가 많을 수록 효과적이다.

KNN의 단점

  • 파라미터 K의 값을 설정해야한다.
  • 어떤 거리 척도가 분석에 적합한 지 불분명하며, 따라서 데이터의 튿성에 맞는 거이측도를 임의로 선정해야한다.
  • 새로운 관측치와 가각의 학습 데이터 간 거리를 전부 측정해야 하므로, 계산시간이 오래 걸리는 단점이 있다.
  • 고차원의 데이터에는 KNN이 잘 작동하지 않는다.
profile
study blog

0개의 댓글