[ML] KNN 구현해보기 - Introduction

 머신러닝의 수많은 주제 중 아마 제일 잘 다뤄지는 주제가 바로 Classification이 아닐까 생각된다. 물론 어떤 값을 예측한다던가, 어떤 일이 발생할 확률 같이 명확한 수치가 나오는 건 아니지만, 과거의 Data를 통해서 미지의 입력값이 어떤 종류로 분류하는 것 자체도 머신러닝에서 다뤄질 수 있는 주제가 아닐까 생각한다. 물론 이런 Classification 문제를 해결하는 여러 알고리즘들이 있겠지만 이번 포스트를 통해서 다루고자 하는 주제는 흔히 k-NN이라고 불리는 k-Nearest Neighborhood Algorithm 이다. 이름이 사실 거창해서 그렇지 두 점사이의 거리를 구하는 공식(보통 Euclidean Distance라고 표현한다.)만 알고 있으면 그 원리가 명확하게 설명되는 알고리즘이다. 간단하게 설명하면 다음과 같다.

위와 같이 뭔가가 나눠진 형태의 정보들이 있다. 그럼 물음표가 있는 지점은 어떤 정보라고 구별할까? 이게 Classification의 목적이다. 여기서 물음표의 주변 정보를 살펴본 후에 다수의 정보를 물음표의 정보라고 예측하는 것이 kNN의 원리이다. 이름에도 들어가 있다시피 Nearest Neighborhood, 즉 가까운 이웃의 정보를 보고 판별하는 방법이 되겠다. 그래서 위와 같은 그림이 나오면 흔히 물음표 주변으로 원을 그리고 그 원 내의 데이터를 쭉 훑는 작업을 한다.

이 주변의 정보를 삼는 데이터의 갯수를 k라고 표현할 때, k-nearest Neighborhood라고 표현하게 된다. 

 그럼 위와 같은 원리를 봤을때 어떤 정보가 필요할까? 우선 맨처음에 언급했던 바와 같이 두 점 사이의 거리를 구할 수 있어야 하고, 정해진 거리내의 데이터 중 어떤게 다수의 정보를 나타내는지를 표현할 수 있어야 한다. 보통 Majority Vote라고 하는데, 이게 흔히 아는 다수결이라는 것이다. 이 정도를 구현할 수 있으면 kNN을 구현하는데 어려움이 없을 것이다.

 우선 두 점 사이의 거리를 구하는 공식은 매우 간단하다. 두 점이 각각 (x1, y1), (x2, y2) 로 정의되어 있으면 두 점 사이의 거리는 다음과 같다.

Numpy를 이용하면 위의 값도 쉽게 코드로 구현할 수 있다. numpy package 자제에 power 함수와 sqrt를 사용해서 말이다.

def distance(p1, p2):
    """
    Find the distance between points p1 and p2.
    """
    return np.sqrt(np.sum(np.power(p2 - p1, 2)))

 다음은 Majority vote를 구하는 코드인데, 먼저 구하기에 앞서 우리가 받은 데이터의 패턴을 파악해야 한다. 이를 Python에서 제공하는 Dictionary를 사용하면 Key와 Value로 구분해서 관리를 할 수 있다. 일단 이 Dictionary가 정확히 정의되는지를 확인하려면 다음과 같이 작성하고 테스트를 해보면 된다.

def distance(p1, p2):
    """
    Find the distance between points p1 and p2.
    """
    return np.sqrt(np.sum(np.power(p2 - p1, 2)))
 
def majority_vote(votes):
    """
    
    """
    vote_counts = {}
    for vote in votes:
        if vote in vote_counts:
            vote_counts[vote] += 1
        else:
            vote_counts[vote] = 1
    return vote_counts

  예를 들어 입력으로 줄 dataset을 만들고 여기에 넣어주면 어떤 data가 얼만큼 나왔는지를 확인할 수 있을 것이다. 가령 

votes 라는 임의의 자료형 집합을 만들고 넣어주면 각 요소가 전체 중 얼마나 나왔는지를 확인할 수 있게 된다. 그런데 우리가 구하는 목적은 여기서 가장 많이 나온 숫자를 반환해야 되기 때문에 위 함수를 그대로 사용할 수 없다. 이를 위해서 위 코드를 수정한다.

import numpy as np
import random
 
def distance(p1, p2):
    """
    Find the distance between points p1 and p2.
    """
    return np.sqrt(np.sum(np.power(p2 - p1, 2)))
 
def majority_vote(votes):
    """
    Return the most common element in votes.
    """
    vote_counts = {}
    for vote in votes:
        if vote in vote_counts:
            vote_counts[vote] += 1
        else:
            vote_counts[vote] = 1
                       
    winners = []
    max_count = max(vote_counts.values())               
    for vote, count in vote_counts.items():
        if count == max_count:
            winners.append(vote)
        
    return random.choice(winners)

 위에서 22번째 줄과 같이 하게 되면 Dictionary 값 중 Value가 가장 큰 값을 넘겨주게 된다. 그래서 전체 데이터 중 이 값과 같은 값을 고르면 그게 결국 다수결의 값이 되는 것이다. 이때 다수결의 값이 여러개 나올 수도 있으므로 random 함수를 써서 동일 케이스일 경우 하나를 선택하는 과정을 위와 같이 구현하게 된다. 

 사실 위와 같이 가장 많이 나타나는 값을 구하는 코드를 작성했지만, 통계학적 측면으로 봤을때는 위의 데이터는 Mode 값을 구하는 과정과 거의 유사하다. 그리고 이걸 구하는 코드도 사실 이미 구현되어 있어서 그냥 쓰면 된다.

import scipy.stats as ss
 
def majority_vote_short(votes):
    """
    Return the most common element in votes.
    """
    mode, count = ss.mstats.mode(votes)
    return mode

수치해석용 package인 scipy에는 통계 모듈도 있는데 여기에 보면 mode를 구하는 함수가 포함되어 있다. 이를 사용하면 mode 값을 나타내주고 역시 결과는 위에서 구한 majority_vote()와 유사하다. 단 차이가 있다면 앞에서 구한 함수는 만약 다수결의 값이 두 개일때 반환값을 random하게 뽑아주지만 mode 값은 딱 어떤 값이라고 명시적으로 반환한다. 그래서 이거 실제로 확인해보려면 여러번 돌려보면 된다.

 아무튼 여기까지가 kNN을 구현하는데 있어서 필요한 거리 구하는 함수와 다수결의 값을 반환하는 함수의 내부였다. 다음 포스트에서는 이 함수를 사용해서 실제로 kNN을 구현하는 과정을 직접 해보고자 한다.