1 寫在前面

前段時(shí)間開(kāi)始看機(jī)器學(xué)習(xí)的相關(guān)知識(shí)谤祖，PLA? break point? dvc? 或是被一堆算法的數(shù)學(xué)公式推導(dǎo)搞得云里霧里涂炎，我開(kāi)始意識(shí)到如果只拘泥于理論部分的學(xué)習(xí)喉悴，我的興趣早晚會(huì)被消磨殆盡允乐，必須在學(xué)習(xí)理論知識(shí)的同時(shí)嘗試使用機(jī)器學(xué)習(xí)的算法解決一些“實(shí)際”問(wèn)題畴椰。一方面瓣喊，讓自己明白機(jī)器學(xué)習(xí)各個(gè)算法是如何解決實(shí)際問(wèn)題的；另一方面芽世，通過(guò)實(shí)際編碼加深對(duì)算法本身的理解挚赊。
今天記錄一個(gè)使用K-緊鄰算法（kNN）解決的問(wèn)題，可以說(shuō)KNN是最簡(jiǎn)單的機(jī)器學(xué)習(xí)算法之一济瓢。

2 kNN原理

kNN屬于監(jiān)督學(xué)習(xí)（supervised learning）的范疇荠割，因?yàn)閗NN的樣本數(shù)據(jù)集中的每個(gè)數(shù)據(jù)都存在標(biāo)簽（label），即我們知道樣本集中每個(gè)數(shù)據(jù)與所屬分類的對(duì)應(yīng)關(guān)系旺矾。輸入沒(méi)有l(wèi)abel的新數(shù)據(jù)后蔑鹦，將新數(shù)據(jù)的每個(gè)特征與樣本集中數(shù)據(jù)對(duì)應(yīng)的特征進(jìn)行比較，然后算法提取樣本集中與新數(shù)據(jù)特征最相似（最近鄰）的前k個(gè)樣本數(shù)據(jù)的label箕宙，最后選擇這k個(gè)最相似數(shù)據(jù)中出現(xiàn)次數(shù)最多的label嚎朽，作為新數(shù)據(jù)的label。

新數(shù)據(jù)與樣本數(shù)據(jù)是如何比較的呢柬帕？

通常輸入的一個(gè)“數(shù)據(jù)”是由多個(gè)特征數(shù)據(jù)（feature）組成的哟忍，我們把這個(gè)“數(shù)據(jù)”放到空間中，一個(gè)特征數(shù)據(jù)代表一個(gè)維度陷寝，受人腦的限制锅很，我們無(wú)法想象多維的情景。為了方便想象凤跑，假定每個(gè)“數(shù)據(jù)”只有兩個(gè)特征爆安，那么放到空間中就是我們最熟悉的二維平面，在這個(gè)平面中兩個(gè)特征可以確定一個(gè)點(diǎn)仔引，新數(shù)據(jù)與樣本數(shù)據(jù)之間的比較就是求兩點(diǎn)之間的“距離”扔仓，通常使用歐式距離，以二維為例：

二維空間中的歐式距離

KNN算法的代碼實(shí)現(xiàn)

最開(kāi)始需要導(dǎo)入兩個(gè)模塊：第一個(gè)是科學(xué)計(jì)算包NumPy，第二個(gè)是運(yùn)算符模塊（operator）耍群。

from numpy import *
import operator

算法的核心代碼：

def k_classify (inX, dataSet, labels, k):
    dataSetSize = dataSet.shape[0]   # 獲取數(shù)據(jù)集第一維度
    diffMat = tile(inX, (dataSetSize, 1)) - dataSet
    sqDiffMat = diffMat ** 2
    sqDistance = sqDiffMat.sum(axis=1)
    distance = sqDistance ** 0.5    # 計(jì)算距離
    sortedDistIndicies = distance.argsort()   # 返回距離從小到大排列后數(shù)值原先的索引值（下標(biāo)）
    classCount = {}
    for i in range(k):    # 選擇距離最小的k個(gè)點(diǎn)义桂，并統(tǒng)計(jì)label
        voteIlabel = labels[sortedDistIndicies[i]]
        classCount[voteIlabel] = classCount.get(voteIlabel, 0) + 1
    sortedClassCount = sorted(classCount.iteritems(), key=operator.itemgetter(1), reverse=True)  # 按label的個(gè)數(shù)，對(duì)其降序排序
    return sortedClassCount[0][0]     # 返回個(gè)數(shù)最大的label

該算法函數(shù)有4個(gè)參數(shù)蹈垢，inX是要測(cè)試的新數(shù)據(jù)慷吊，dataSet是訓(xùn)練樣本集，labels是標(biāo)簽集曹抬，k通常取不大于20的整數(shù)溉瓶。

3 構(gòu)建手寫識(shí)別系統(tǒng)

收集數(shù)據(jù)

為了簡(jiǎn)單起見(jiàn)，這里構(gòu)造的系統(tǒng)只能識(shí)別0到9的數(shù)字，需要識(shí)別的數(shù)字已經(jīng)使用圖形軟件處理成了寬和高是32x32像素的黑白圖像堰酿，并且將圖像轉(zhuǎn)換為了文本格式疾宏，如下圖1所示。

圖1：數(shù)字6

數(shù)據(jù)集有兩個(gè)触创，一個(gè)為trainningDigits文件中包含2000個(gè)例子坎藐，每個(gè)數(shù)字有200個(gè)樣本，部分樣本如圖2所示哼绑。另一個(gè)為testDigits文件中包含大約900個(gè)測(cè)試數(shù)據(jù)岩馍。

圖2：訓(xùn)練集部分樣本

準(zhǔn)備數(shù)據(jù)

需要識(shí)別的數(shù)字的文本文件有了双谆，接下來(lái)需要將其轉(zhuǎn)化為算法函數(shù)可處理的數(shù)據(jù)類型。
這里將32x32的二進(jìn)制圖像矩陣轉(zhuǎn)換為1x1024的向量励稳，并將其存在1x1024的NumPy數(shù)組中佃乘。

def imgVector(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      # 返回1x1024的數(shù)組

測(cè)試與運(yùn)行算法

def handwritingClassTest():
    hwLabels = []
    trainingFileList = listdir('trainingDigits')      # 讀取訓(xùn)練集
    m = len(trainingFileList)
    trainingMat = zeros((m, 1024))
    for i in range(m):
        fileNameStr = trainingFileList[i]
        fileStr = fileNameStr.split('.')[0]
        classNumStr = int(fileStr.split('_')[0])    # 獲取label
        hwLabels.append(classNumStr)      # 構(gòu)建標(biāo)簽集
        trainingMat[i,:] = imgVector('trainingDigits/%s' % fileNameStr) # 處理訓(xùn)練集數(shù)據(jù)
    errorCount = 0.0
    testFileList = listdir('testDigits')    #讀取測(cè)試集，進(jìn)行測(cè)試
    mTest = len(testFileList)
    for i in range(mTest):
        fileNameStr = testFileList[i]
        fileStr = fileNameStr.split('.')[0]
        classNumStr = int(fileStr.split('_')[0])
        vectUnderTest = imgVector('testDigits/%s' % fileNameStr)
        classifierResult = k_classify(vectUnderTest, trainingMat, hwLabels, 3)    # 使用kNN算法
        if (classifierResult != classNumStr):     # 將kNN輸出label與實(shí)際label對(duì)比
            errorCount += 1.0
    print "the total error number of error is: %d" % errorCount
    print "\nthe total error rate is: %f" % (errorCount/float(mTest)) # 輸出錯(cuò)誤率

運(yùn)行結(jié)果

圖3：運(yùn)行結(jié)果

通過(guò)使用測(cè)試集測(cè)試驹尼，在大約900個(gè)數(shù)字中有11個(gè)數(shù)字趣避，KNN算法識(shí)別錯(cuò)誤，正確率達(dá)98.8%新翎，可見(jiàn)kNN在這個(gè)數(shù)字識(shí)別問(wèn)題上的表現(xiàn)是不錯(cuò)的程帕。

收獲

通過(guò)實(shí)際編碼實(shí)現(xiàn)kNN算法，并將其運(yùn)用在一個(gè)實(shí)際例子中地啰，讓我對(duì)該算法的原理有了更深的理解愁拭。
第一次接觸到了科學(xué)計(jì)算包NumPy，學(xué)習(xí)到了這個(gè)庫(kù)中幾個(gè)重要方法亏吝，如：zeros() shape() tile() sum(axis=*) argsort() 以及使用了python中幾個(gè)方法岭埠，如：listdir() split() strip()
其實(shí)，這個(gè)算法的執(zhí)行效率并不高蔚鸥。測(cè)試集有大約900個(gè)惜论，所以kNN算法要執(zhí)行900次，那每次的計(jì)算量多少呢止喷？由于訓(xùn)練集樣本有2000個(gè)馆类，因此就需要做2000次距離計(jì)算，每個(gè)距離計(jì)算還有1024個(gè)維度浮點(diǎn)運(yùn)算弹谁，可見(jiàn)計(jì)算量不小乾巧，在我電腦上大約運(yùn)行了十幾秒才出結(jié)果...那么有什么方法可以減少計(jì)算時(shí)間的開(kāi)銷呢句喜？這個(gè)之后再說(shuō)。
萬(wàn)事開(kāi)頭難...