[ML] KNN 구현해보기 - Finding Nearest Neighbors

 이전 포스트에서 거리를 구하는 함수와 다수결 값을 구하는 함수를 정의했었고, 이번 포스트에서는 kNN 의 핵심인 가까운 이웃을 찾는 함수를 구현해보고자 한다. 우선 kNN의 처리 과정을 단계별로 써보면

1. 전체 데이터 집단을 살펴보고,
2. 그중 한점과 다른 점간의 거리들을 구한 후
3. 그 거리를 나열해 기준에 적합한 점들을 반환해주면

된다. 이게 kNN이 동작하는 원리다. 예를 들어 이런 케이스를 살펴보자

위와 같이 빨간색 점들이 있는데 파란 점이 왔을때 어떤 빨간점이 파란점과 가깝다고 표현할 수 있을까? 당연히 딱 보기에도 (2, 2)에 있는 점과 (3, 2)에 있는 점이 파란 점에 가깝다고 할 수 있다. 이게 가깝다고 정의한것은 당연하다. 두 점 사이의 거리를 구해 그게 가장 짧은 거리를 찾은 것이다. 실제로 코드를 작성해 결과를 살펴보면

4번째와 7번째 점의 거리가 가장 가까운데 이 점이 바로 (2,2) 과 (3,2) 이고, 이게 결국 어떤 기준에 맞춘 Nearest Neighbor가 되는 것이다. 결국 이런 과정 자체가 kNN 처리 과정이 되는 것이다. 그런데 중간에 보면 거리들을 나열해 기준에 적합한 점을 찾는 과정이 있는데, 이 과정에서 sort가 되어 있어야 점을 찾을 수 있다. Numpy에서는 argsort라는 함수를 통해 해당 배열내의 데이터를 정렬하고, 목적에 맞는 데이터의 인덱스를 얻을 수 있다. 그러면 위의 distances 라는 배열도

와 같이 가장 가까운 점들을 쉽게 확인할 수 있다. 그래서 해당 코드를 함수로 구현하면 다음과 같다.

def find_nearest_neighbors(p, points, k=5):
    """
    Find the k nearest neighbors of point p and return their indices. 
    """
    distances = np.zeros(points.shape[0])
    for i in range(len(distances)):
        distances[i] = distance(p, points[i])
    ind = np.argsort(distances)
    return ind[:k]

 우선 입력으로 기준 점과 전체 데이터, 그리고 k 값을 받게끔 했다. 여기서 말하는 k값이 kNN의 k가 될텐데, 위에서 보다시피 가장 가까운 점들을 나열했을 때 k개만큼 뽑겠다는 것이다. 참고로 위와 같이 k인자를 5로 초기화를 해놓으면 아무 인자가 들어오지 않았을 경우 이 5라는 값이 k로 정의되게 된다. 물론 k가 새로운 인자로 들어오게 되면 해당 값을 k로 인지하게 된다. 

 그래서 위의 코드가 딱 앞에서 정의한 kNN의 처리 과정이 된다. 그런데 딱 보면 위 함수는 가장 가까운 점들을 알려줄 뿐이지, 우리가 원래 구하고자 하는 궁극적인 목표인 점의 종류에 대해서는 확인할 수 없다. 결국 위의 함수와 이전에 정의한 majority_vote()를 섞어서 사용해야 원하는 함수를 정의할 수 있다. 이에 대한 코드는 다음과 같다.

def knn_predict(p, points, outcomes, k=5):
    """
    Predict class of p based on knn
    """
    # find k nearest neighbors
    ind = find_nearest_neighbors(p, points, k)
    # predict the class of p based on majority vote
    return majority_vote(outcomes[ind])

 참고로 outcomes 라고 하는 인자가 추가되었는데, 이 값은 전체 데이터들이 어떤 class라 나눠져있나를 표현해주는 일종의 list이다. 그래서 아까 예로 들었던 9개의 점들의 class를 다음과 같이 임의의 class를 주고 위의 함수를 실행시키면 

def knn_predict(p, points, outcomes, k=5):
    """
    Predict class of p based on knn
    """
    # find k nearest neighbors
    ind = find_nearest_neighbors(p, points, k)
    # predict the class of p based on majority vote
    return majority_vote(outcomes[ind])
 
# Example
outcomes = np.array([0, 0, 0, 0, 1, 1, 1, 1, 1])
knn_predict(np.array([2.5, 2.7]), points, outcomes, k=2)
 

 우리가 아까 확인했던 4번과 7번 점이 속한 1이란 class를 결과로 얻게 된다.

여기까지 대충 kNN이 어떻게 돌아가고 임의의 예제를 통해 특정 class로 구별하는 과정을 설명했다. 그런데 보면 알겠지만 여기까지가 아니다. 잘 보면 지금 outcomes 이라는 list도 임의로 지정해서 정의해 넣었고, k라는 값이 크면 좋은지 작으면 좋은지에 대해서도 논의할 필요가 있다. 이 부분에 대해서는 다음 포스트에서 추가로 언급해보고자 한다.