KNN Algorithm

K-Nearest Neighbor Algorithm(KNN) 는 Supervised Learning 알고리즘 중 하나로 , 분류(Classification)이나 회귀(Regression)문제에 모두 사용될 수 있는 직관적이고 간단한 모델이다.
핵심 아이디어로 데이터는 다차원 공간에서 비슷한 특성을 가진 데이터끼리 모여 있다는 것이다.
특징으로, KNN은 훈련이 필요없는 Lazy model이다.
KNN은 새로운 데이터가 주어지면 그와 동시에 알고리즘을 실행하여 새로운 데이터를 분류해주기 때문이다.

KNN 기본 원리

새로운 데이터가 주어졌을 때, 기존 데이터 중에서 가장 가까운 $k$ 개의 이웃을 찾는다. 그 이웃의 label을 확인하여 새로운 데이터의 label을 결정한다.

• Classification : $k$ 개의 이웃 중 가장 많이 등장하는 label로 분류한다.
• Regression : $k$개의 이웃들이 가진 값의 평균을 구한다.

KNN Algorithm

1. $k$ 설정 : 몇 개의 이웃을 살펴볼지 결정한다
2. 거리 계산 : 새로운 데이터와 기존의 모든 데이터 사이의 거리를 주로 계산한다.
   • 변수가 연속형 변수일 경우, 주로 유클리드 거리(Euclidean Distance) 또는 맨하튼 거리(Manhattan Distance) 가 많이 사용된다.
     - Euclidian distance : 가장 가까운 직선 거리
     $d(p,q) = \sqrt{\sum_{i = 1}^{n}(q_i - p_i)^2}$
     - Manhattan : 길이 존재하는 최단 루트 거리
     $d(p,q) = \sum_{i=1}^{n}{|q_i - p_i|^2}$
     - 변수가 범주형 변수일 경우, Hamming distance를 주로 사용한다.
     $d(p,q) = \sum_{i=1}^{n}{I(p_i \neq q_i)}$
3. 이웃 선택 : 계산된 거리를 기준으로 가장 가까운 $k$ 개의 데이터를 선택한다.
4. 결과 도출 : 분류 혹은 회귀에 따라 결과를 도출한다.

$k$ 값의 중요성 (Hyperparameter)

$k$ 값을 어떻게 설정하느냐에 따라 성능이 크게 달라진다.

• $k$ 가 너무 작을 때
  - 가장 가까운 데이터에만 의존하므로, Noise & Outlier에 민감해진다.
  - Overfitting 될 위험이 크다.
• $k$ 가 너무 클 때
  - 데이터의 특성을 잃어버릴 수 있다.
  - Underfitting 될 위험이 크다.