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 np
import operator

def 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 matplotlib
import matplotlib.pyplot as plt
fig = 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 matplotlib
import matplotlib.pyplot as plt
fig = 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 matplotlib
import matplotlib.pyplot as plt
fig = 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 np
import operator

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

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

def 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?10
ferquent fiter miles earned per year?10000
liters of ice ice crean consumed per year?0.5
You 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: 7
the classifier came back with: 7, the real answer is: 7
the classifier came back with: 9, the real answer is: 9
the classifier came back with: 0, the real answer is: 0
the classifier came back with: 0, the real answer is: 0
the classifier came back with: 4, the real answer is: 4
the classifier came back with: 9, the real answer is: 9
the classifier came back with: 7, the real answer is: 7
the classifier came back with: 7, the real answer is: 7
the classifier came back with: 1, the real answer is: 1
the classifier came back with: 5, the real answer is: 5
the classifier came back with: 4, the real answer is: 4
the classifier came back with: 3, the real answer is: 3
the classifier came back with: 3, the real answer is: 3

the total number of errors is: 11

the 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

《機器學習實戰》