파이썬 코딩으로 말하는 데이터 분석 - 9. k-NN (최근접이웃,분류문제)

데이터 분석에 대한 기본적인 감과 덤으로 파이썬 코딩에 대한 감을 익히기 위한 강좌입니다. 
개발자는 코드로 이해하는게 가장 빠른 길이며, 오래 기억하는 길이라 믿습니다.
이 글의 소스인  "밑바닥부터 배우는 데이터과학" 및 "밑바닥부터 시작하는 딥러닝" 은  그런 기본적인 코드를 주요 매개체로 머신러닝을 설명해주는 훌륭한 서적이니 데이터사이언스에 관심있는 개발자라면 추천해드립니다. (수학도 미분,편미분 정도만 알면 되며, 바닥부터 쉽게 설명해줌) 

순서 

1. 통계 - 카운팅,min,max,평균,중앙값,산포도,분산,편차,공분산,상관관계 

2. 가설과 추론 (베이지언 - 사후확률,우도) 

3. 군집화 (K-Means)

4. 연관 (Apriori)

5. 함수형으로 데이터 다루기 

6.경사하강법

7. 회귀분석

8. 은닉 마코프법 (HMM) 

9. k-NN 

10. DTW 

 * 참고로 "밑바닥부터 배우는 데이터과학" 서적은 numpy,scikit-learn 등의 외부라이브러리를 활용은 배제되었습니다.

k-NN 이란?

k-NN 알고리즘은 가장 쉬운 머신러닝 알고리즘 중의 하나이다. "분류"를 하기위한 알고리즘인데 

예를들어보면 

(1,축구), (2,축구), (3,축구) (7,야구),(8,야구)(10,배구) 이런 데이터 목록들이 있다고 할때 

내가 가지고 있는 데이터인 "3번" 은 축구,야구,배구 중 어디로 분류 될까?  

당연히 축구로 분류 될 것이다.

그럼 4번은 어디로 분류 될까? 4는 3과 가깝고 3번이 축구니깐 또 축구 일 것이다.

축하한다. 당신은 이제 k-NN 알고리즘을 이해했다.!!

그렇다 k-NN 알고리즘은 가까운 거리에 가장 많이 분포하는 것으로 나의 데이터를 분류 하는 알고리즘이다. 따라서 k-NN 알고리즘은 

- 거리를 재는 방법
- 서로 가까운 점들은 유사하다는 가정
- 어느 정도 가까운 거리로 할 것인가? 

정도만 필요하다.

이미지를 통해서 다시 확실히 이해해보자.

자 분류하고 싶은 데이터는 연두색으로 아직 미정이다.
이 데이터는 파랑사각형과 빨강삼각형 중 어디로 분류될까?
자신과 가장 가까운 거리에 있는 것으로 분류를 하면 파랑 사각형으로 분류 될 것이고 
거리를 k=3 으로 정한다면 k=3 이내에 가장 많은 있는 빨강 삼각형으로 분류 될 것이다.
만약  k=3 거리에 동일한 숫자의 사각형,삼각형이 있다면, 거리를 k=2.5 로 접혀서 다시 계산하면 둘 중 하나가 더 많아 질것이다. 혹시 그래도 같다면 k=2 로 줄이고~ 그러는 것이쥐~

 코드로 말해요.

함수1)

def raw_majority_vote(labels):
    votes = Counter(labels)
    winner,_ = votes.most_common(1)[0]
    return winner

위 코드는 데이터목록들을 받아서 , 가장 많이 존재하는 이름을 리턴해준다.
즉 (1,축구),(2,축구)(3,야구) 이런 데이터목록을 받으면 축구를 리턴해준다.

함수2)

def majority_vote(labels):
    vote_counts = Counter(labels):
    winner, winner_count = vote_counts.most_common(1)[0]
    num_winners = len([count 
                                        for count in vote_counts.values() 
                                        if count == winner_count])
    if num_winners == 1:
        return winner
    else:
        return majority_vote(labels[:-1])

위 코드는 데이터목록들을 받아서 , 가장 많이 존재하는 이름을 찾는데, 하나 뿐이라면 그것을 리턴해주고, 
만약 축구,야구가 둘 다 동일한 숫자가 k거리 이내에 있다면 , 제일 멀리 있는 놈을 제외하고 다시 찾는다.

함수3)

* 마지막으로 위의 코드를 이용하여 k-NN 알고리즘을 만들자.

def knn_classify(k, lebeled_points, your_point):
    by_distance = sorted(lebeled_points, 
                                        key=lambda (point, _): distance(point, your_point()))
    k_nearest_labels = [label for _, label in by_distance[:k]]
    
    return majority_vote(k_nearest_labels)

매개변수) 

k : 어느정도 가까운 것들을 찾는가?
labeled_points : 분류에 사용 될 데이터목록들 
your_point : 분류하고 싶은 데이터

설명)

1. 분류에 사용될 데이터들을 분류 될 데이터와 거리 순으로 정렬한다.
2. 정렬된 데이터 중에서 k 거리 이내에 있는 데이터 목록만 따로 majority_vote 에 넘겨서 k 거리이내의 데이터들 중에 가장 많이 포함되 있는 라벨(야구 혹은 축구?) 을 찾는다.

 

이렇게 당신은 k-NN 알고리즘을 이해하였으며, 구현까지 할 수 있게 되었다.
자신감이 붙었다면 다른 "머신러닝" 알고리즘의 세계로 진출해보자~
다음으로 쉬운 알고리즘으로는 K-Means 를 추천해드린다.