1 背景

1.1 k近鄰算法的概述

（1）k近鄰算法的簡介

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

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

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

（3）k近鄰算法的案例

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

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

以California Man為例

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

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

1.2?用python代碼實現k近鄰算法

（1）計算已知類別數據集中的每個點與當前點之間的距離

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

（3）選取與當前點距離最小的k個點

（4）確定前k個點所在類別出現的頻率

（5）返回前k個點出現頻率最高的類別作為當前點的預測分類

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?如何測試分類器

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

2 使用kNN算法改進約會網站的匹配效果

2.1 案例介紹

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

2.2 數據的準備

以下提供兩種下載數據集的渠道：

《機器學習實戰官方下載python2版本代碼》

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

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

每年獲得的飛行常客里程數，玩視頻游戲所耗時間百分比，每周消費冰淇淋公升數

在數據輸入到分類器之前，需要把數據轉換成分類器可以識別的樣式

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讀取到的特征數據(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]]

標簽數據(datingLabels)如下

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

2.3?數據分析：使用Matplotlib創建散點圖

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

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軸為玩視頻游戲所耗時間百分比

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

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

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軸為飛行常客里程數

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

（3）飛行常客里程數與每周消費冰淇淋公升數之間的相關關系圖

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軸為每周消費冰淇淋公升數，x軸為飛行常客里程數

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

?2.4?數據準備：歸一化數值

?由于通過歐式距離計算樣本之間的距離時，對于飛行常客里程數來說，數量值巨大，會對結果影響的權重也會較大，而且遠遠大于其他兩個特征，但是作為三個等權重之一，飛行常客里程數并不應該如此嚴重影響結果，例子如下

((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?測試算法：作為完整程序驗證分類器

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

（1）使用file2matrix函數導入數據樣本

（2）使用autoNorm對數據進行歸一化處理

（3）使用classify0對90%的數據進行訓練，對10%的數據進行測試

（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)

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

?2.5?使用算法：構建完整可用的系統

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

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

輸入測試數據：

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算法制作手寫識別系統

3.1 案例介紹

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

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

3.2?數據準備：將圖像轉換為測試向量

?以下提供兩種下載數據集的渠道：

《機器學習實戰官方下載python2版本代碼》

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

數據集存放在digits.zip中，其中用1代表手寫的區域，用0代表空白區域

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

?通過img2vector函數對數據進行讀取，并且返回數組

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識別手寫數字

（1）使用listdir讀取trainingDigits目錄下所有文件作為訓練數據

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

（3）將訓練數據與測試數據喂入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)))

輸出訓練結果，錯誤率為1.1628%，通過改變k值與訓練樣本都會使得錯誤率發生變化。

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 總結

4.1 k-近鄰算法的優缺點

（1）優點：精度高，對異常值不敏感，無數據輸入假定

（2）缺點：計算復雜度高，空間復雜度高

適用數據范圍：數值型和標稱型

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

（1）收集數據：可以使用任何方法

（2）準備數據：距離計算所需的數值，最好是結構化的數據格式

（3）分析數據L：可以使用任何方法

（4）訓練算法：此步驟不適合與k近鄰算法

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

（6）使用算法：首先需要輸入樣本數據和結構化的輸出結果，然后運行k-近鄰算法判定輸入數據分別屬于哪個分類，最后應用對計算出的分類執行后續的處理。

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

（1）數據特征之間量綱不統一時，需要對數據進行歸一化處理，否則會出現大數吃小數的問題

（2）數據之間的距離計算通常采用歐式距離

（3）kNN算法中K值的選取會對結果產生較大的影響，一般k值要小于訓練樣本數據的平方根

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

5?Reference

《機器學習實戰》