[Practical Statistics for Data Scientists] K-Nearest Neighbors

KNN(K-Nearest Neighbors)

KNN 알고리즘의 원리는 간단합니다.

1. 거리가 가장 가까운 k개의 데이터를 선정합니다.
2. 분류의 경우, 선정한 k개의 데이터 중 제일 많은 데이터가 속한 class로 새로운 데이터를 분류합니다.
3. 예측의 경우, 선정한 k개의 데이터의 평균을 구하여 새로운 데이터를 그 값으로 예측합니다.

https://www.kdnuggets.com/2020/11/most-popular-distance-metrics-knn.html

위의 그림을 예로 들자면, 분류 문제일 때, k = 3일 때 가장 가까운 3개의 데이터는 빨간 별 1개, 초록 세모 2개로, 초록 세모가 더 많은 데이터를 구성하고 있기 때문에 새로운 데이터는 초록 세모로 분류합니다. k = 7일 때, 가장 가까운 데이터는 빨간 별이 4개, 초록 세모가 3개로, 빨간 별이 더 많은 데이터를 구성하고 있기 때문에 새로운 데이터는 빨간 별로 분류됩니다. 예측 문제였을 경우에는, 단순히 k개의 데이터의평균을 구해 그 평균 값으로 새로운 데이터를 예측하게 됩니다.

 

KNN은 별도의 모델을 생성하지 않고 단순히 인접 데이터를 분류/예측에 사용합니다. 모델을 따로 학습하지 않는 이런 특성 때문에 KNN 알고리즘은 lazy algorithm이라고 불리기도 합니다.

 

거리

1번에서 언급된 거리는 어떻게 구할 수 있을까요? 다양한 거리를 구하는 방법을 사용할 수 있습니다. 대표적인 방법으로는 아래 3가지 방법이 있습니다.

• 유클리드 거리(Euclidean Distance)
• 맨하탄 거리(Manhattan Distance)
• 마할라노비스 거리(Mahalanobis Distance)

 

우선 유클리드 거리(Euclidean Distance)는 아래와 같이 계산할 수 있습니다.

 

$d = \sqrt{(a_1-b_1)^2+(a_2-b_2)^2+...+(a_n-b_n)^2}$

 

일상생활에서 쓰이는 거리와 가장 유사한 개념으로, 두 점과 점 사이의 직선 거리를 의미합니다. 가장 흔히 사용되는 거리입니다.

 

맨하탄 거리(Manhattan Distance)는 아래와 같이 계산 가능합니다.

 

$d = |(a_1-b_1)+(a_2-b_2)+...+(a_n-b_n)|$

 

아래 지도에서 흰 사각형을 건물, 회색 선들을 도로라고 본다면, 건물들을 가로지르지 않고 도로로 갔을 경우의 거리입니다.

아무래도 절대값을 사용하다보니, 유클리드 거리보다 outlier에 robust하다는 장점이 있습니다.

https://ko.wikipedia.org/wiki/%EA%B1%B0%EB%A6%AC

위 그림에서 초록색 선은 유클리드 거리를  나타내고, 파란선, 노란선은 시작점에서 끝점까지 갈 수 있는 최단거리들인데, 결국 맨해튼 거리를 나타내는 빨간색 선과 동일합니다. 맨해튼 거리는 항상 유클리드 거리보다 크거나 같다는 특징을 갖습니다.

 

마할라노비스(Mahalanobis Distance)에 대한 설명은 말로 대신 하겠습니다. 마할라노비스 거리는 데이터 분포로부터 점의 거리를 측정합니다. 쉽게 설명하면, 평균과의 거리가 표준편차의 몇 배가 되는지를 나타내는 distance metric입니다. 

 

예를 들어 제가 하루 평균 마시는 커피의 잔수의 평균이 3, 표준편차가 1이라고 가정해봅시다. 제가 어느 날 커피를 5잔을 마셨다면, 마할라노비스 거리는 $\frac{5-3}{1} = 2$로 계산이 됩니다. 즉 제가 커피를 많이 마시면 마실수록 혹은 적게 마시면 마실수록 마할라노비스 거리는 커질 것입니다. 따라서 특정 데이터가 얼마나 희귀한지를 측정하는 값이라고 생각하셔도 무방할 것 같습니다.

 

KNN 알고리즘의 Hyperparameter

KNN알고리즘은 모델이 없기 때문에 당연히 parameter(linear regression에서의 $\beta$와 같이 모델의 학습과정에서 결정되는 것)도 존재하지 않습니다. 다만 2개의 초모수(Hyperparmeter)가 존재합니다.

• K: 인접한 몇 개의 데이터를 이용할 것인지
  
  • K개가 너무 작은 경우 overfitting이 발생할 가능성이 커지고, 반대로 K가 너무 큰 경우, 오분류의 가능성이 커집니다. 아래 그림을 보시면 이해에 도움이 될 것이라 생각합니다. Cross validation을 이용해 K를 조정해가며 가장 좋은 결과를 보이는 값을 찾는 것이 적절한 K를 찾는 방법이 됩니다.

https://rapidminer.com/blog/k-nearest-neighbors-laziest-machine-learning-technique/

•  Distance Metric: 앞서 설명한 3개의 Distance metric, 혹은 그 외의 Distance Metric 중 무엇을 사용할 것인지

KNN 알고리즘 사용 시의 주의점

• 앞서 설명한 거리 공식들은 numerical data에만 적용이 가능하기 때문에 dummy variable을 사용하여 categorical variable들을 수치화 시켜주어야할 필요가 있습니다.
• 마찬가지로 거리 공식을 사용하기 때문에 표준화(standardization)를 해주어야 합니다. 만약 비교하고자 하는 변수들의 분포나 단위가 다르다면, 변수의 차이를 이해하는데 어려움이 생기기 때문입니다. 표준화의 방법은 다음과 같습니다.

$ z = \frac{x - \bar{x}}{s}$

$\bar{x}$는 x의 표본평균, $s$는 표본표준편차를 의미합니다.

KNN 알고리즘의 장점과 단점

장점

• 데이터 내 노이즈에 영향을 크게 받지 않으며, 특히나 마할라노비스 거리를 이용해 데이터의 분산을 고려해주는 경우 더욱 robust 합니다.
• 단순하고 효율적입니다.
• 모델이 없기 때문에 별도의 훈련과정이 요구되지 않습니다.
• 회귀 문제, 분류 문제 모두에 적용이 가능합니다.
• 이해가 쉽고 직관적입니다.

단점

• 적절한 K와 Distance metric을 선택해야합니다.
• 데이터가 많아지면, 새로운 관측치와 데이터 간의 거리를 전부 측정해야하기 때문에 계산이 오래 걸릴 수 있습니다.
• 수치형 데이터가 아닌 경우 dummy variable로 바꾸어주는 추가적인 처리가 요구됩니다.

 

참고한 자료 & 참고하면 좋은 자료:

https://www.youtube.com/watch?v=W-DNu8nardo 

https://towardsdatascience.com/importance-of-distance-metrics-in-machine-learning-modelling-e51395ffe60d

Importance of Distance Metrics in Machine Learning Modelling