1 背景

1.1 k近鄰算法的概述

（1）k近鄰算法的簡介

k-近鄰算法是屬于一個非常有效且易于掌握的機器學(xué)習(xí)算法，簡單的說就是采用測量不同特征值之間距離的方法對數(shù)據(jù)進行分類的一個算法。

（2）k近鄰算法的工作原理

給定一個樣本的集合，這里稱為訓(xùn)練集，并且樣本中每個數(shù)據(jù)都包含標(biāo)簽。對于新輸入的一個不包含標(biāo)簽的數(shù)據(jù)，通過計算這個新的數(shù)據(jù)與每一個樣本之間的距離，選取前k個，通常k小于20，以k個劇里最近的數(shù)據(jù)的標(biāo)簽中出現(xiàn)次數(shù)最多的標(biāo)簽作為該新加入的數(shù)據(jù)標(biāo)簽。

（3）k近鄰算法的案例

當(dāng)前統(tǒng)計了6部電影的接吻和打斗的鏡頭數(shù)，假設(shè)有一部未看過的電影，如何確定它是愛情片還是動作片呢？

根據(jù)knn算法的原理，我們可以求出，未知電影與每部電影之間的距離(這里采用歐式距離）

以California Man為例

>>>((3-18)**2+(104-90)**2)**(1/2)20.518284528683193

因此我們可以找到樣本中前k個距離最近的電影，假設(shè)k=3，前三部電影均為愛情片，因此我們判定未知電影屬于愛情片。

1.2?用python代碼實現(xiàn)k近鄰算法

（1）計算已知類別數(shù)據(jù)集中的每個點與當(dāng)前點之間的距離

（2）按照距離遞增次序排序

（3）選取與當(dāng)前點距離最小的k個點

（4）確定前k個點所在類別出現(xiàn)的頻率

（5）返回前k個點出現(xiàn)頻率最高的類別作為當(dāng)前點的預(yù)測分類

import numpy as npimport operatordef classify0(inX, dataSet, labels, k):    dataSetSize = dataSet.shape[0]    diffMat = np.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.items(), key=operator.itemgetter(1), reverse=True)    return sortedClassCount[0][0]

（6）案例

>>>group = np.array([[1, 1.1],...                 [1, 1],...                 [0, 0],...                 [0, 0.1]])>>>labels = ["A", "A", "B", "B"]>>>classify0([0,0], group, labels, 3)"B"

1.3?如何測試分類器

正常來說為了測試分類器給出來的分類效果，我們通常采用計算分類器的錯誤率對分類器的效果進行評判。也就是采用分類出錯的次數(shù)除以分類的總次數(shù)。完美的分類器的錯誤率為0，而最差的分類器的錯誤率則為1。

2 使用kNN算法改進約會網(wǎng)站的匹配效果

2.1 案例介紹

朋友海倫在使用約會軟件尋找約會對象的時候，盡管網(wǎng)站會推薦不同的人選，但并不是每一個人她都喜歡，具體可以分為以下三類：不喜歡的人，魅力一般的人，極具魅力的人。盡管發(fā)現(xiàn)了以上的規(guī)律，但是海倫依舊無法將網(wǎng)站推薦的人歸到恰當(dāng)?shù)念悇e，因此海倫希望我們的分類軟件能更好的幫助她將匹配到的對象分配到確切的分類中。

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

以下提供兩種下載數(shù)據(jù)集的渠道：

《機器學(xué)習(xí)實戰(zhàn)官方下載python2版本代碼》

《202xxx的github下載python3版本代碼》

數(shù)據(jù)存放在datingTestSet2.txt中，每個樣本占一行，共1000行數(shù)據(jù)，主要包括了以下三個特征：

每年獲得的飛行?？屠锍虜?shù)，玩視頻游戲所耗時間百分比，每周消費冰淇淋公升數(shù)

在數(shù)據(jù)輸入到分類器之前，需要把數(shù)據(jù)轉(zhuǎn)換成分類器可以識別的樣式

def file2matrix(filename):    fr = open(filename)    numberOfLines = len(fr.readlines())         #get the number of lines in the file    returnMat = np.zeros((numberOfLines,3))        #prepare matrix to return    classLabelVector = []                       #prepare labels return       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

使用file2matix讀取到的特征數(shù)據(jù)(datingDataMat)如下

array([[4.0920000e+04, 8.3269760e+00, 9.5395200e-01],        [1.4488000e+04, 7.1534690e+00, 1.6739040e+00],        [2.6052000e+04, 1.4418710e+00, 8.0512400e-01],        ...,        [2.6575000e+04, 1.0650102e+01, 8.6662700e-01],        [4.8111000e+04, 9.1345280e+00, 7.2804500e-01],        [4.3757000e+04, 7.8826010e+00, 1.3324460e+00]]

標(biāo)簽數(shù)據(jù)(datingLabels)如下

[3,2,1,1,1,1,3,3,...,3,3,3]

2.3?數(shù)據(jù)分析：使用Matplotlib創(chuàng)建散點圖

（1）玩視頻游戲所耗時間百分比與每周消費冰淇淋公升數(shù)之間的相關(guān)關(guān)系圖

import matplotlibimport matplotlib.pyplot as pltfig = plt.figure()ax = fig.add_subplot(111)ax.scatter(datingDataMat[:,0], datingDataMat[:,1], 15.0*np.array(datingDLabels), 15.0*np.array(datingDLabels))plt.show()

其中，y軸為每周消費冰淇淋公升數(shù)，x軸為玩視頻游戲所耗時間百分比

紫色為不喜歡，綠色為魅力一般，黃色為極具魅力

（2）飛行常客里程數(shù)與玩視頻游戲所耗時間百分比之間的相關(guān)關(guān)系圖

import matplotlibimport matplotlib.pyplot as pltfig = plt.figure()ax = fig.add_subplot(111)ax.scatter(datingDataMat[:,0], datingDataMat[:,1], 15.0*np.array(datingDLabels), 15.0*np.array(datingDLabels))plt.show()

其中，y軸為玩視頻游戲所耗時間百分比，x軸為飛行?？屠锍虜?shù)

紫色為不喜歡，綠色為魅力一般，黃色為極具魅力

（3）飛行?？屠锍虜?shù)與每周消費冰淇淋公升數(shù)之間的相關(guān)關(guān)系圖

import matplotlibimport matplotlib.pyplot as pltfig = plt.figure()ax = fig.add_subplot(111)ax.scatter(datingDataMat[:,0], datingDataMat[:,2], 15.0*np.array(datingDLabels), 15.0*np.array(datingDLabels))plt.show()

其中，y軸為每周消費冰淇淋公升數(shù)，x軸為飛行?？屠锍虜?shù)

紫色為不喜歡，綠色為魅力一般，黃色為極具魅力

?2.4?數(shù)據(jù)準(zhǔn)備：歸一化數(shù)值

?由于通過歐式距離計算樣本之間的距離時，對于飛行?？屠锍虜?shù)來說，數(shù)量值巨大，會對結(jié)果影響的權(quán)重也會較大，而且遠遠大于其他兩個特征，但是作為三個等權(quán)重之一，飛行?？屠锍虜?shù)并不應(yīng)該如此嚴(yán)重影響結(jié)果，例子如下

((0-67)**2+(20000-32000)**2+(1.1-0.1)**2)**1/2

通常我們在處理不同取值范圍的特征時，常常采用歸一化進行處理，將特征值映射到0-1或者-1到1之間，通過對（列中所有值-列中最小值）/（列中最大值-列中最小值）進行歸一化特征

def autoNorm(dataSet):    minVals = dataSet.min(0)    maxVals = dataSet.max(0)    ranges = maxVals - minVals    normDataSet = np.zeros(np.shape(dataSet))    m = dataSet.shape[0]    normDataSet = dataSet - np.tile(minVals, (m,1))    normDataSet = normDataSet/np.tile(ranges, (m,1))   #element wise divide    return normDataSet, ranges, minVals

?2.5?測試算法：作為完整程序驗證分類器

評估正確率是機器學(xué)習(xí)算法中非常重要的一個步驟，通常我們會只使用訓(xùn)練樣本的90%用來訓(xùn)練分類器，剩下的10%用于測試分類器的正確率。為了不影響數(shù)據(jù)的隨機性，我們需要隨機選擇10%數(shù)據(jù)。

（1）使用file2matrix函數(shù)導(dǎo)入數(shù)據(jù)樣本

（2）使用autoNorm對數(shù)據(jù)進行歸一化處理

（3）使用classify0對90%的數(shù)據(jù)進行訓(xùn)練，對10%的數(shù)據(jù)進行測試

（4）輸出測試集中的錯誤率

def datingClassTest():    hoRatio = 0.50      #hold out 10%    datingDataMat,datingLabels = file2matrix("datingTestSet2.txt")       #load data setfrom file    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)

最后得到分類器處理的約會數(shù)據(jù)集的錯誤率為2.4%，這是一個相當(dāng)不錯的結(jié)果，同樣我們可以改變hoRatio的值，和k的值，檢測錯誤率是否隨著變量的變化而增加

?2.5?使用算法：構(gòu)建完整可用的系統(tǒng)

通過上面的學(xué)習(xí)，我們嘗試給海倫開發(fā)一套程序，通過在約會網(wǎng)站找到某個人的信息，輸入到程序中，程序會給出海倫對對方的喜歡程度的預(yù)測值：不喜歡，魅力一般，極具魅力

import numpy as npimport operatordef file2matrix(filename):    fr = open(filename)    numberOfLines = len(fr.readlines())         #get the number of lines in the file    returnMat = np.zeros((numberOfLines,3))        #prepare matrix to return    classLabelVector = []                       #prepare labels return       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,classLabelVectordef autoNorm(dataSet):    minVals = dataSet.min(0)    maxVals = dataSet.max(0)    ranges = maxVals - minVals    normDataSet = np.zeros(np.shape(dataSet))    m = dataSet.shape[0]    normDataSet = dataSet - np.tile(minVals, (m,1))    normDataSet = normDataSet/np.tile(ranges, (m,1))   #element wise divide    return normDataSet, ranges, minValsdef classify0(inX, dataSet, labels, k):    dataSetSize = dataSet.shape[0]    diffMat = np.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.items(), key=operator.itemgetter(1), reverse=True)    return sortedClassCount[0][0]def classifyPerson():    resultList = ["not at all", "in small doses", "in large doses"]    percentTats = float(input("percentage of time spent playing video games?"))    ffMiles = float(input("ferquent fiter miles earned per year?"))    iceCream = float(input("liters of ice ice crean consumed per year?"))    datingDataMat,datingLabels = file2matrix("knn/datingTestSet2.txt")       #load data setfrom file    normMat, ranges, minVals = autoNorm(datingDataMat)    inArr = np.array([percentTats, ffMiles, iceCream])    classifierResult = classify0((inArr-minVals)/ranges, normMat, datingLabels,3)    print ("You will probably like this person:", resultList[classifierResult-1])if __name__ == "__main__":    classifyPerson()#10    10000    0.5

輸入測試數(shù)據(jù)：

percentage of time spent playing video games?10ferquent fiter miles earned per year?10000liters of ice ice crean consumed per year?0.5You will probably like this person: not at all

3 使用kNN算法制作手寫識別系統(tǒng)

3.1 案例介紹

以下案例以數(shù)字0-9的分類為例，簡述如何采用k近鄰算法對手寫數(shù)字進行識別。

?通常手寫輸入的數(shù)字都是圖片格式，我們需要將圖片轉(zhuǎn)換成knn算法可以識別的結(jié)構(gòu)化數(shù)據(jù)，簡單來說就是讀取圖片中的像素點，像素點值通常在0-255之間，0為黑色，255為白色，因此可以將值大于250的像素點標(biāo)記為1，其余標(biāo)記為0，手寫數(shù)字1可以用以下數(shù)據(jù)集表示：

3.2?數(shù)據(jù)準(zhǔn)備：將圖像轉(zhuǎn)換為測試向量

?以下提供兩種下載數(shù)據(jù)集的渠道：

《機器學(xué)習(xí)實戰(zhàn)官方下載python2版本代碼》

《202xxx的github下載python3版本代碼》

數(shù)據(jù)集存放在digits.zip中，其中用1代表手寫的區(qū)域，用0代表空白區(qū)域

（大佬們，中秋快樂！?。。?

?通過img2vector函數(shù)對數(shù)據(jù)進行讀取，并且返回數(shù)組

def img2vector(filename):    returnVect = np.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

3.3 測試算法，使用kNN識別手寫數(shù)字

（1）使用listdir讀取trainingDigits目錄下所有文件作為訓(xùn)練數(shù)據(jù)

（2）使用listdir讀取testDigits目錄下所有文件作為測試數(shù)據(jù)

（3）將訓(xùn)練數(shù)據(jù)與測試數(shù)據(jù)喂入knn算法中

def handwritingClassTest():    hwLabels = []    trainingFileList = listdir("trainingDigits")           #load the training set    m = len(trainingFileList)    trainingMat = np.zeros((m,1024))    for i in range(m):        fileNameStr = trainingFileList[i]        fileStr = fileNameStr.split(".")[0]     #take off .txt        classNumStr = int(fileStr.split("_")[0])        hwLabels.append(classNumStr)        trainingMat[i,:] = img2vector("trainingDigits/%s" % fileNameStr)    testFileList = listdir("testDigits")        #iterate through the test set    errorCount = 0.0    mTest = len(testFileList)    for i in range(mTest):        fileNameStr = testFileList[i]        fileStr = fileNameStr.split(".")[0]     #take off .txt        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)))

輸出訓(xùn)練結(jié)果，錯誤率為1.1628%，通過改變k值與訓(xùn)練樣本都會使得錯誤率發(fā)生變化。

the classifier came back with: 7, the real answer is: 7the classifier came back with: 7, the real answer is: 7the classifier came back with: 9, the real answer is: 9the classifier came back with: 0, the real answer is: 0the classifier came back with: 0, the real answer is: 0the classifier came back with: 4, the real answer is: 4the classifier came back with: 9, the real answer is: 9the classifier came back with: 7, the real answer is: 7the classifier came back with: 7, the real answer is: 7the classifier came back with: 1, the real answer is: 1the classifier came back with: 5, the real answer is: 5the classifier came back with: 4, the real answer is: 4the classifier came back with: 3, the real answer is: 3the classifier came back with: 3, the real answer is: 3the total number of errors is: 11the total error rate is: 0.011628

4 總結(jié)

4.1 k-近鄰算法的優(yōu)缺點

（1）優(yōu)點：精度高，對異常值不敏感，無數(shù)據(jù)輸入假定

（2）缺點：計算復(fù)雜度高，空間復(fù)雜度高

適用數(shù)據(jù)范圍：數(shù)值型和標(biāo)稱型

4.2?k-近鄰算法的一般流程

（1）收集數(shù)據(jù)：可以使用任何方法

（2）準(zhǔn)備數(shù)據(jù)：距離計算所需的數(shù)值，最好是結(jié)構(gòu)化的數(shù)據(jù)格式

（3）分析數(shù)據(jù)L：可以使用任何方法

（4）訓(xùn)練算法：此步驟不適合與k近鄰算法

（5）測試算法：計算錯誤率

（6）使用算法：首先需要輸入樣本數(shù)據(jù)和結(jié)構(gòu)化的輸出結(jié)果，然后運行k-近鄰算法判定輸入數(shù)據(jù)分別屬于哪個分類，最后應(yīng)用對計算出的分類執(zhí)行后續(xù)的處理。

4.3?k-近鄰算法使用需要注意的問題

（1）數(shù)據(jù)特征之間量綱不統(tǒng)一時，需要對數(shù)據(jù)進行歸一化處理，否則會出現(xiàn)大數(shù)吃小數(shù)的問題

（2）數(shù)據(jù)之間的距離計算通常采用歐式距離

（3）kNN算法中K值的選取會對結(jié)果產(chǎn)生較大的影響，一般k值要小于訓(xùn)練樣本數(shù)據(jù)的平方根

（4）通常采用交叉驗證法來選擇最優(yōu)的K值

5?Reference

《機器學(xué)習(xí)實戰(zhàn)》