[Data Analysis 개념] KNN(K-Nearest-Neighbors)알고리즘

※ 이 게시글은 KNN분류에 대한 이론만 게시된 게시글입니다. 

 KNN이란, K-Nearest-Neighbors의 약자로, 간단하게 말해서 K개의 이웃한 데이터를 기반으로 대상을 분류/회귀하는 것이다. KNN은 직관적으로 이해하기 쉽고, 수학적으로 풀어도 충분히 이해하기 쉬운 머신러닝 모델이다. 이번 게시글에서는 KNN의 원리에 대해 알아보자.

---

직관적 방법론

 만약 아래와 같은 그림이 있다고 하자. 우리가 보고있는 녹색 점을 빨간색 또는 파란색으로 분류하려면 어떤 방식을 통해서 분류를 해야할까? 

link : https://commons.wikimedia.org/wiki/File:KnnClassification.svg Copyright : https://creativecommons.org/licenses/by-sa/3.0/

  여러 방법이 있겠지만, 이 위의 데이터를 산점도의 샘플이라고 생각한다면, 녹색점이 녹색점 주변의 다른 점들과 유사한 특징을 지닌다고 생각하고, 이를 기반으로 주변 샘플들의 정보를 이용해서 녹색점을 어떤 색으로 분류할 지 정할 수 있다. 

 이제 이 아이디어를 기반으로, 분류를 시작하고자 할 때, 한 가지 문제점이 발생한다. 

 과연 주변의 몇 개의 점을 기준으로 판단을 할 것인가? 위의 그림을 보면, K=3(실선)이라고 판단한다면, 녹색점은 빨간색으로 분류될 것이다. 하지만, K=5(점선)으로 판단한다면, 녹색점은 파란색으로 분류될 것이다. 

 이처럼, 우리는 K를 어떻게 정할지에 대한 문제점이 발생한다. 만약 K가 너무 크다면,  데이터가 무수히 많아지고 주변에 여러 종류의 데이터가 존재할 때, 미세한 경계부분을 잘못 분류할 것이다. 하지만, 반대로 K가 너무 작다면, 샘플 하나하나의 영향을 너무 많이받아 이상치의 영향이 크게 되고, 분류하는 패턴이 직관적이지 못하게 된다. 즉 과적합(Overfitting)이 발생하게 된다. 

---

방법

 우리는 녹색점을 기반으로 1. 거리에 반비례하는 가중치를 부여하거나( 녹색과 가까울 수록 Weighted ), 또는 2. 개수(K)만을 정해서 많이 포함되는 점( 각각 점들의 영향력이 Uniform )을 택하는 판단을 할 수도 있다. 

종속 변수

 

1. 범주형 변수일 경우, K-Nearest Neighbors은 가장 많이 나타나는 범주로 녹색점( = 타겟 = Y )를 추정하고, 50:50으로 K가 나눠지는 경우가 발생하는 Tie문제를 막기 위해, K는 홀수로 정하는 것이 좋다.                                           

2. 연속형 변수일 경우, K-Nearest Neighbors은 대표값(ex, 평균)으로 녹색점( = 타겟 = Y )를 추정해야한다. 그리고 이 경우 연속적인 거리로 측정이 되기에 거리에 반비례하는 가중치(inverse distance weighted average)를 사용할 수 있다.

---

 

거리(Distance)의 기준

 KNN은 기본적으로 가장 가까운 샘플을 찾는 기준인 "거리"에 대한 정의가 필요하다. 이 "거리"에 대한 기준은 설명변수의 특성을 기반으로 판단한다.

1. 설명 변수가 범주형 변수일 경우, Hamming Distance를 주로 사용한다. 수식은 아래와 같다.

Hamming 거리는 같으면 거리가 0이고 다르면 거리가 1씩 증가하는 것이다. 

예시) "1011111"과 "1001001"의 거리는 3이다. (다른 부분이 3개, Bold체)

2. 설명 변수가 연속형 변수일 경우, Eulian distance 또는 Manhattan Distance를 주로 사용한다. 

출처 : https://needjarvis.tistory.com/455

유클리드 거리는 우리가 잘 알고 있는, 가장 가까운 직선거리을 의미한다. 위의 그림을 보면 녹색선이 유클리드 거리이다. 

맨해튼 거리는 길이 존재하는 최단 루트이다. 위의 그림을 보면 빨간선, 파란선, 노란선 모두 맨해튼 거리이다. 

---

수학적 표현

 KNN은 수식적으로 표현하면 아래와 같다. 

범주형 변수

1. 종속변수가 범주형 변수일 때

2. 점 (x,y), N개의 Training 관측치 (Xi,Yi), i = 1,...,N에 대하여,

3.

 좌표상에 (X1,Y1) 부터 (Xn,Yn)까지 있는 데이터를 

4.

 거리에 따른 오름차순으로 분류한다. 즉 (X1,Y1)이 예측하고자하는 변수와 가장 가까운 변수이다.

5.

 그렇기에, Y를 예측하기 위해서, K번째까지 즉 (Xk,x)까지를 사용하여, 그 중에 가장 많은 범주를 선택한다.

6. 

그렇기에 k개 중에서 선택된 범주(m)와 같은 변수 Y(i)의 개수가 곧 확률로 정의된다. 

7.

이를 결과로 표현하면 위의 식과 같아진다.

 

연속형 변수

앞의 범주형 변수와 동일하게 5)까지 줄을 세워놓고 나서

6. 

줄 세워 놓은 Y의 변수들을 k개만 가져와서, 표본평균을 낸다.

7.

Inverse distance weighted average를 고려할 경우, 즉 가까운 변수에 대해서 가중치를 부여할 경우, 거리의 역수를 곱해주어 가까운 거리일 수록 분자가 커지도록 계산하여 평균을 구한다. 

 

이상 KNN에 대해 알아보았다. 다음에는 KNN에 대한 실습을 진행하도록 하겠다.