[Practical Statistics for Data Scientists] A팀: K-Nearest Neighbors

# K-Nearest Neighbors

- KNN은 구현이 간단하면서도 준수한 성능을 가진 Classifcation Algorithm 입니다. 작동 원리는 다음과 같습니다.

  1. 가까운 K개의 이웃을 찾는다.

  2. [분류] K개의 이웃 중 가장 많은 이웃이 속한 집단으로 새로운 데이터를 할당한다.

  3. [예측] K개의 이웃의 평균을 구해 그 값을 새로운 데이터의 값으로 한다.

KNN

 

# Lazy Model

- KNN은 모델을 별도로 구축(학습)할 필요가 없습니다. Decision Boundary를 Train Data 통해 만든 후에 Test Data를 모델에 적용하는 방식이 아니라, 새로운 데이터가 주어지면 그제야 주변의 K개 Data를 보고 새로운 데이터를 분류하는 방식입니다. 이러한 점에서 KNN은 게으른 모델(Lazy Model)이라고 불리기도 하지만, 그만큼 SVM, 선형회귀 등보다 빠르게 작동합니다.

 

# Distance Metrics

- '가까운 K개의 이웃' 에서 '가깝다' 의 기준이 되는 거리를 측정하는 방법은 상당히 다양합니다.  본 글은 책에서 언급한 Euclidean, Manhattan, Mahalanobis 이외에도 다양한 Distance Metrics의 소개 및 비교에 집중하고자 합니다.

 

Minkowski Distance (민코프스키 거리)

- Minkowski Distance는 Euclidean과 Manhattan을 일반화한 것으로 이해하면 쉽습니다. 

[식 1] Minkowski Distance

- 점 n차원 벡터 X와 Y의 길이를 두 벡터의 Lp norm 이라 정의하면

   - p = 1 인 경우는 Manhattan Distance와 동일하고, L1 norm이라고도 합니다.

   - p = 2 인 경우는 Euclidean Distance와 동일하고, L2 norm이라고도 합니다.

   - p =  ∞ 인 경우는 Chebyshev Distance와 동일하고, L max norm 이라고도 합니다.

 

* 부가 설명 : Norm

- Norm은 vector 값을 scalar 값으로 바꿀 수 있는 function의 일종으로, 아래의 세 가지 속성을 동시에 만족한다면 norm(||v||)라 합니다.

1. Zero Vector : v=0
2. Scalar Factor : f(cv)=∣c∣f(v)
3. Triangle Inequality : f(u+v)≤f(u)+f(v)
4.  

Mahalanobis Distance (마할라노비스 거리)

- Mahalanobis Distance는 단순히 주어진 거리만을 계산하지 않고, 데이터의 상관성을 고려해 거리를 계산합니다. 데이터의 상관성은 공분산(Covariance)를 이용하고, 식은 아래와 같습니다. 그 아래는 비교를 위한 Euclidean Distance의 식입니다.

[식 2] Mahalanobis Distance

-

[식 3] Euclidean Distance

- [식 3] 에서 첫번째 식이 우리가 흔히 아는 Euclidean Distance인데, 이는 그 아래의 식처럼 나타낼 수 있습니다. 아래의 식과 [식 2] 에서 제시된 Mahalanobis Distance 사이의 차이점은 (표본)공분산행렬로 나눠주는 것뿐입니다.

 

Mahalanobis Distance Vs Euclidean Distance

- Distance를 측정할 때 Covariance Matrix를 고려하는 과정을 시각화하면 다음과 같습니다.

D(X,A), D(X,B)의 비교

- X와 A 사이의 거리 D(X,A)와 X와 B 사이의 거리 D(X,B)를 비교하고자 합니다. 눈으로 보았을 때에는 D(X,B)가 D(X,A)보다 멀어 보입니다. 하지만 데이터는 XB 방향에 평행하게 길게 늘어져있으므로, 분산을 고려하여 거리를 다시 계산하면 아래와 같습니다.

분산을 고려한 거리 계산

- 분산을 고려하여 눈금을 다시 그리면(파란색, 빨간색) D(X,A)와 D(X,B)는 같은 것을 알 수 있습니다. 이처럼 Mahalinobis Distance는 단순히 거리만을 계산하여 D(X,B)가 D(X,A)보다 크다는 결론을 내리는 Euclidean Distance와 다른 결론을 낼 수 있습니다.

 

Cosine Similarity (코사인 유사도)

- 위에 제시된 Distance Metrics는 모두 그 값이 0에 가까울수록 두 벡터가 유사한 것이었지만, 각(radian) 기반의 Cosine similarity는 값의 범위로 (-1, 1)을 가지며 1에 가까울수록 두 벡터가 유사하다고 할 수 있습니다. 

[식 4] Cosine similarity

* Cosine Similarity Vs Euclidean Distance

[왼쪽] Euclidean Distance, [오른쪽] 코사인 유사도

- 왼쪽 그림 (Euclidean Distance)에 따르면 벡터 X는 Z보다 Y에 가깝다고 할 수 있습니다.

- 오른쪽 그림 (Cosine Similarity)에 따르면 벡터 X는 Y보다 Z에 가깝다고 할 수 있습니다.

 * 식으로 표현하면 아래와 같습니다. 

- 이처럼 거리 기반의 Metric과 각 기반의 Metric을 사용할 때의 결과가 다를 때, 어떤 Metric을 사용할지에 대한 기준 중 하나는 '스케일의 차이가 큰가' 라고 합니다. (다른 기준 또한 있을 수 있습니다)

- 예를 들어, X(1, 1)과 Y(2000, 2000) 의 거리를 측정한다고 가정합니다.

   -> 거리 기반 유사도는 값의 차이를 기반으로 하기 때문에 두 벡터가 '멀다' 라고 판단합니다.

   -> 각 기반 유사도는 기울기와 방향이 같기 때문에 두 벡터가 '가깝다' 라고 판단합니다.