이번에는 k-최근접 이웃 알고리즘을 Python으로 시연해 보기로 하였다. k-최근접 이웃 알고리즘의 장점은 높은 정확도와 데이터에 대한 가정이 없다는 것이고, 단점은 계산 비용이 높고 많은 리소스를 요구한다는 것이다. 흔히 매우 간단한 기계학습 알고리즘에 속한다고 한다. 

-------------------------------------------------------------------------------------------

* Numpy 기계학습의 모든 문서는 제가 머신러닝을 공부하고, 제 프로젝트에 필요한 알고리즘을 찾기 위해 정리하는 일종의 '요점정리 노트' 입니다. 혹여나 오해 없으시기 바랍니다. (2016.03.14 추가)

-------------------------------------------------------------------------------------------

훈련 데이터는 각각이 항목 분류명을 갖는 다차원 특징 공간에서의 벡터이다. 알고리즘의 훈련 단계는 오직 훈련 표본의 특징 벡터와 항목 분류명을 저장하는 것이다. 분류 단계에서 k는 사용자 정의 상수이고 분류명이 붙지 않은 벡터(질의 또는 검증점)는 k개의 훈련 표본 사이에서 가장 빈번한 분류명을 할당함으로써 분류된다. 연속 변수에서 가장 흔하게 사용되는 거리 척도는 유클리드 거리이다. 문자 분류와 같은 이산 변수의 경우 중첩 거리(또는 해밍 거리)와 같은 다른 척도가 사용될 수 있다. 예를 들어 유전자 표현 미세 배열 데이터의 경우, k-NN은 피어슨과 스피어만 같은 상관 계수를 사용해 왔다.종종 거리 척도가 큰 여백 최근접 이웃이나 이웃 성분 분석과 같은 특별한 알고리즘으로 학습된다면 k-NN의 분류의 정확성을 상당히 향상시킬 수 있다. (위키피디아 인용)

우선, kNN을 이용한 여러 프로젝트들을 구현하기 위해 파이썬 파일을 생성하고, 소스 코드를 추가할 것이다. 내가 추가한 kNN의 모듈의 소스코드는 아래와 같다. 

from numpy import *
import operator
from os import listdir

def classify0(inX, dataSet, labels, k):
    dataSetSize = dataSet.shape[0]
    diffMat = tile(inX, (dataSetSize,1)) - dataSet
    sqDiffMat = diffMat**2
    sqDistances = sqDiffMat.sum(axis=1)
    distances = sqDistances**0.5
    sortedDistIndicies = distances.argsort()     
    classCount={}          
    for i in range(k):
        voteIlabel = labels[sortedDistIndicies[i]]
        classCount[voteIlabel] = classCount.get(voteIlabel,0) + 1
    sortedClassCount = sorted(classCount.iteritems(), key=operator.itemgetter(1), reverse=True)
    return sortedClassCount[0][0]

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

def file2matrix(filename):
    fr = open(filename)
    numberOfLines = len(fr.readlines())
    returnMat = zeros((numberOfLines,3))
    classLabelVector = []  
    fr = open(filename)
    index = 0
    for line in fr.readlines():
        line = line.strip()
        listFromLine = line.split('\t')
        returnMat[index,:] = listFromLine[0:3]
        classLabelVector.append(int(listFromLine[-1]))
        index += 1
    return returnMat,classLabelVector
    
def autoNorm(dataSet):
    minVals = dataSet.min(0)
    maxVals = dataSet.max(0)
    ranges = maxVals - minVals
    normDataSet = zeros(shape(dataSet))
    m = dataSet.shape[0]
    normDataSet = dataSet - tile(minVals, (m,1))
    normDataSet = normDataSet/tile(ranges, (m,1)) 
    return normDataSet, ranges, minVals
   
def datingClassTest():
    hoRatio = 0.50      #hold out 10%
    datingDataMat,datingLabels = file2matrix('datingTestSet2.txt')
    normMat, ranges, minVals = autoNorm(datingDataMat)
    m = normMat.shape[0]
    numTestVecs = int(m*hoRatio)
    errorCount = 0.0
    for i in range(numTestVecs):
        classifierResult = classify0(normMat[i,:],normMat[numTestVecs:m,:],datingLabels[numTestVecs:m],3)
        print "the classifier came back with: %d, the real answer is: %d" % (classifierResult, datingLabels[i])
        if (classifierResult != datingLabels[i]): errorCount += 1.0
    print "the total error rate is: %f" % (errorCount/float(numTestVecs))
    print errorCount
    
def img2vector(filename):
    returnVect = zeros((1,1024))
    fr = open(filename)
    for i in range(32):
        lineStr = fr.readline()
        for j in range(32):
            returnVect[0,32*i+j] = int(lineStr[j])
    return returnVect

def handwritingClassTest():
    hwLabels = []
    trainingFileList = listdir('trainingDigits')
    m = len(trainingFileList)
    trainingMat = zeros((m,1024))
    for i in range(m):
        fileNameStr = trainingFileList[i]
        fileStr = fileNameStr.split('.')[0]
        classNumStr = int(fileStr.split('_')[0])
        hwLabels.append(classNumStr)
        trainingMat[i,:] = img2vector('trainingDigits/%s' % fileNameStr)
    testFileList = listdir('testDigits')
    errorCount = 0.0
    mTest = len(testFileList)
    for i in range(mTest):
        fileNameStr = testFileList[i]
        fileStr = fileNameStr.split('.')[0]
        classNumStr = int(fileStr.split('_')[0])
        vectorUnderTest = img2vector('testDigits/%s' % fileNameStr)
        classifierResult = classify0(vectorUnderTest, trainingMat, hwLabels, 3)
        print "the classifier came back with: %d, the real answer is: %d" % (classifierResult, classNumStr)
        if (classifierResult != classNumStr): errorCount += 1.0
    print "\nthe total number of errors is: %d" % errorCount
    print "\nthe total error rate is: %f" % (errorCount/float(mTest))

-----------------------------------------------------------------------

나는 이 중, 내가 옛날에 C#으로 개발했었던 Handwriting 알고리즘을 개발하고 싶었다. 이를 kNN을 활용해서 테스트를 해 보았다. 이미지 파일은 아래와 같다.

바이너리 이미지를 쉽게 다루도록 하기 위해 텍스트로 변환하였다.

이를 실제로 돌려 보면 아래와 같이 된다.

이 소스에서는 2000여개 Data 중 11개 오차가 발생했다. (1.2% 오류율)

이 실험을 해 보면서 kNN 알고리즘은 간단하며 데이터를 분류하는 데 효과적인 알고리즘이고, 데이터 구조에 대한 어떠한 정보도 알 수 없다는 것이 가장 큰 단점이라는 결론을 내리게 되었다. 오늘은 여기까지 하기로 하였다. 다음에는 kNN을 이용한 다른 시험도 해 보도록 해야 겠다.