머신러닝 K-최근접 이웃(KNN)의 개념과 원리

[주인장]

1. K-최근접 이웃법의 개념

1.1 개념

• 지도학습(Supervised Learning) 중 하나로 데이터 분류(classification)를 위한 기계학습 알고리즘 중에 하나
• 사례기반(instance-based) 학습법
• 각 데이터들 간의 거리를 측정하여 가까운 k개의 다른 데이터의 레이블을 참조하여 분류하는 방법
• 거리 측정시 유클리디안 거리 계산법을 사용하나, 자료 특성에 따라 다른 응용된 거리 계산법을 사용하기도 함

1.2 거리 계산 방법

• 적합한 거리방법을 적용하는 것이 첫번째 하이퍼파라미터 과제
• 공간 상에서 두 점의 거리를 계산하기 위해 유클리디안 거리 측정법을 이용함
• Manhattan Distance
  • A에서 B로 이동할 때 각 좌표측 방향으로만 이동할 경우에 계산되는 거리 taxi cab distance 라도고 함
• Mahalanobis Distance
  • 변수 내 분산, 변수 간 공분산을 모두 반영하여 거리를 계산하는 방식
  • 변수 간 상관 관계를 고려한 거리 지표
• Correlation Distance
  • person correlation을 거리 척도로 직접 사용
  • 개별 관측치가 아닌 데이터 전체의 경향성을 비교하기 위한 척도

1.3 최적의 k수

• k 수에 따라 예측도가 달라짐
• 최적의 k를 찾는 것이 하이퍼파라미터의 두 번째 주요 과제
• k가 작을수록 훈련(train) 데이터의 정확도는 높아지나 다른 자료(validation / test)에는 부적합할 수 있음
• k가 클수록 일반화는 가능하나 정확도가 떨어질 수 있음
• 최적의 k수가 가장 좋은 일반화 결과를 가져옴
• bias-variance tradeoff
  • overfitting : k가 클 경우 노이즈 데이터에 의한 변동을 줄일 수 있으나 작짐나 중요한 패턴을 무시할 우려가 있음 - 학습 데이터에만 너무 좋은 결과
  • underfitting : 분류 집단에 영향을 줄 수 있는 노이즈 및 극단값을 허용하여 잘못된 분류 결과를 가져올 우려가 있음
• 최적의 k수는?
  • 일반적 k 수 : 3~10 가량, 기준 변수의 수와 데이터의 수에 따라 다름
  • 계산을 이용한 k수 : 데이터 수의 제곱근 값으로 k로 정하는 방법.
    • 1000개의 자료일 경우 sqrt(1000) = 31.6, 약 32개로 정하는 방법
    • 최적의 k는 보장되지 않음
• 최적의 k 수를 찾기 위해서는 Train data와 Test data에 모두 정확도가 높고, Grid Search 등을 통해 다양한 k의 결과를 확인해보야야 함

1.4 K-최근접 이웃법의 특징

• 장점
  • 알고리즘이 간단하여 구현하기 쉽다.
  • 수치 기반 데이터 분류 작업에서 성능이 좋다.
  • 기준을 잡을 대충의 정확도를 찾기 위해 사용
  • 초반에 정확도의 정도를 알기위한 방법으로 사용
• 단점
  • 데이터의 양이 많으면 계산 속도가 느림 : 게으른 학습법
  • 차원(벡터)의 크기가 크면 계산량이 많아짐
  • 새로운 데이터가 들어오면 그 때 기존 데이터의 거리를 모두 계산한 후에 분류하기 때문에 인스턴트 기반 학습이라고 함