2-1. K-Nearest Neighbors

1) 정의

이해하기 쉬운 분류기(Classifier) 중 하나인 K-Nearest Neighbors 분류 알고리즘을 살펴보자.

KNN알고리즘은 (이름 그대로) 가장 가까운 K개의 데이터를 고른 뒤, 그 중 가장 major한 클래스로 분류한다.

예를 들어 K값이 3이라면, 분류하고자 하는 데이터와 가장 가까운 3개의 데이터를 찾는다. 찾아낸 3개의 데이터의 클래스가 각각 토끼, 토끼, 거북이 라고 하면 우리가 지금 분류하고자 하는 데이터의 클래스는 토끼가 되는 것이다.

위의 예를 수도코드도 간단히 작성하면 다음과 같다.

이미 주어진 샘플 데이터는 X, 우리가 클래스를 정해주고자 하는 데이터를 C라고 하자.

X안의 아이템들과 C의 거리를 계산하고

그 중 계산된 거리 값이 가장 작은 3개의 아이템을 추려낸 뒤

그 3개의 아이템들의 클래스 중에 가장 메이저한 값을 찾는다.

return 예측 값으로 위의 메이저 값을 반환

클래스를 예측하고 싶은 데이터에 대해 이 과정을 반복해주면 된다.

2)Numpy

http://doongkibangki.tistory.com/15 <--설치방법

Numpy를 이용해 행렬을 표현할 것인데, 그 전에 기본적인 Numpy 요소를 정리해보면 아래와 같다.

	기능	비고
ones((n,m))	모든 원소가 1로 이루어진 n*m 행렬을 반환한다.
zeros((n,m))	모든 원소가 0으로 이루어진 n*m 행렬을 반환한다.
eye(n)	n*n 단위행랼을 반환한다.
tile(A,(n,m))	A행렬을 세로로 n개 가로로 m개 이어붙인 행렬을 반환한다.
tile(A,n)	A 행렬을 가로로 n개 이어붙인 행렬을 반환한다.

3)kNN구현

설치 후 파이썬 콘솔창으로 넘어와서, 분류기에서 사용할 데이터를 편리하게 만들기 위해 createDataSet 함수를 선언해보자.

from numpy import *
import operator
def createDataSet():
    group=array([[1.0,1.1],[1.0,1.0],[0,0],[0,0.1]])
    labels=['A','A','B','B']
    return group, labels

createDataSet()은 kNN에서 알고리즘을 지도할 때 쓰일 (1.0,1.1), (1.0,1.0)의 A클래스 데이터 두 개,

                                           (0.0,0.0), (0.0,0.1)의 B클래스 데이터 두 개를 생성해주는 함수이다.

이제 분류를 수행할 kNN함수를 선언해보자.

def kNN(inX,trainingData,labels,k):
    dataSetSize=trainingData.shape[0]             #지도에 사용할 트레이닝 데이터의 개수
    diff=tile(inX,(dataSetSize,1))-trainingData    #분류하고자 하는 데이터와 트레이닝 데이터의 값 차이 
    sqDiff=diff**2                                
    sqDistance=sqDiff.sum(axis=1)
    distance=sqDistance**0.5
    sortedDist=distance.argsort()                #계산된 거리값이 증가하는 순으로 인덱스 정렬
    classCount={}                                #가장 가까운 3개의 데이터의 클래스를 모아서 살펴보기 위해 딕셔너리 선언
    for i in range(k):
        candidateLabel=labels[sortedDist[i]]
        classCount[candidateLabel]=classCount.get(candidateLabel,0)+1
    sortedClassCount=sorted(classCount.items(),
                            key=operator.itemgetter(1),reverse=True)
    return sortedClassCount[0][0]

2~7번 라인은 inX와 트레이닝 데이터의 거리를 계산해서, 어느 것이 가장 가까운지 나열해주는 부분이다.

각각의 코드는 아래의 행렬 계산식으로 표현할 수 있다.

diff=tile(inX,(dataSetSize,1))-trainingData

sqDiff=diff**2 

sqDistance=sqDiff.sum(axis=1)

distance=sqDistance**0.5

sortedDist=distance.argsort()

값이 작은 원소의 인덱스가 순서대로 나열되었다. 

4)kNN테스트

group,labels=createDataSet()
kNN(array([[0.0,0.0]]),group,labels,3)
#'B'

이제 위의 코드처럼 (0.0,0.0)에 있는 데이터의 클래스를 예측하기 위해 가장 가까운 3개의 데이터를 확인하자.

labels[2]='B', labels[3]='B', labels[1]='A' 중에서 major한 클래스를 반환하면 새로운 값에 대한 클래스 예측이 끝난다.

B클래스가 가장 major하므로 예측된 클래스는 B이다.