機器學習之k-近鄰（kNN）算法與Python實現

k-近鄰算法（kNN，k-NearestNeighbor），是最簡單的機器學習分類算法之一，其核心思想在于用距離目標最近的k個樣本數據的分類來代表目標的分類（這k個樣本數據和目標數據最為相似）。

一 k-近鄰（kNN）算法概述

1.概念

kNN算法的核心思想是用距離最近的k個樣本數據的分類來代表目標數據的分類。

其原理具體地講，存在一個訓練樣本集，這個數據訓練樣本的數據集合中的每個樣本都包含數據的特征和目標變量（即分類值），輸入新的不含目標變量的數據，將該數據的特征與訓練樣本集中每一個樣本進行比較，找到最相似的k個數據，這k個數據出席那次數最多的分類，即輸入的具有特征值的數據的分類。

例如，訓練樣本集中包含一系列數據，這個數據包括樣本空間位置（特征）和分類信息（即目標變量，屬于紅色三角形還是藍色正方形），要對中心的綠色數據的分類。運用kNN算法思想，距離最近的k個樣本的分類來代表測試數據的分類，那么：
當k=3時，距離最近的3個樣本在實線內，具有2個紅色三角和1個藍色正方形**，因此將它歸為紅色三角。
當k=5時，距離最近的5個樣本在虛線內，具有2個紅色三角和3個藍色正方形**，因此將它歸為藍色正方形。

2.特點

優點
（1）監督學習：可以看到，kNN算法首先需要一個訓練樣本集，這個集合中含有分類信息，因此它屬于監督學習。
（2）通過計算距離來衡量樣本之間相似度，算法簡單，易于理解和實現。
（3）對異常值不敏感

缺點 （4）需要設定k值，結果會受到k值的影響，通過上面的例子可以看到，不同的k值，最后得到的分類結果不盡相同。k一般不超過20。（5）計算量大，需要計算樣本集中每個樣本的距離，才能得到k個最近的數據樣本。 （6）訓練樣本集不平衡導致結果不準確問題。當樣本集中主要是某個分類，該分類數量太大，導致近鄰的k個樣本總是該類，而不接近目標分類。

3.kNN算法流程

一般情況下，kNN有如下流程：
（1）收集數據：確定訓練樣本集合測試數據；
（2）計算測試數據和訓練樣本集中每個樣本數據的距離；

常用的距離計算公式： 

（3）按照距離遞增的順序排序；
（4）選取距離最近的k個點；
（5）確定這k個點中分類信息的頻率；
（6）返回前k個點中出現頻率最高的分類，作為當前測試數據的分類。

二 、Python算法實現

1.KNN算法分類器

建立一個名為“KNN.py”的文件，構造一個kＮＮ算法分類器的函數：

from numpy import *
import operator

#定義KNN算法分類器函數
#函數參數包括：(測試數據，訓練數據，分類,k值)
def classify(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() #排序并返回index
    #選擇距離最近的k個值
    classCount={}
    for i in range(k):
        voteIlabel=labels[sortedDistIndicies[i]]
        #D.get(k[,d]) -> D[k] if k in D, else d. d defaults to None.
        classCount[voteIlabel]=classCount.get(voteIlabel,0)+1
    #排序
    sortedClassCount=sorted(classCount.items(),key=operator.itemgetter(1),reverse=True)
    return sortedClassCount[0][0]

在KNN.py中定義一個生成“訓練樣本集”的函數：

#定義一個生成“訓練樣本集”的函數，包含特征和分類信息
def createDataSet():
    group=array([[1,1.1],[1,1],[0,0],[0,0.1]])
    labels=['A','A','B','B']
    return group,labels

在Python控制臺先將當前目錄設置為“KNN.py”所在的文件目錄，將測試數據[0,0]進行KNN算法分類測試，輸入：

import KNN
#生成訓練樣本
group,labels=KNN.createDataSet()
#對測試數據[0,0]進行KNN算法分類測試
KNN.classify([0,0],group,labels,3)
Out[3]: 'B'

可以看到該分類器函數將[0,0]分類為B組，符合實際情況，分入了符合邏輯的正確的類別。但如何知道KNN分類的正確性呢？

2.kNN算法用于約會網站配對

2.1準備數據
該數據在文本文件datingTestSet2.txt中，該數據具有1000行，4列，分別是特征數據（每年獲得的飛行?？屠锍虜?，玩視頻游戲所耗時間百分比，每周消費的冰淇淋公升數），和目標變量/分類數據（是否喜歡（1表示不喜歡，2表示魅力一般，3表示極具魅力）），部分數據展示如下：

0920   8.326976    0.953952    3
14488   7.153469    1.673904    2
26052   1.441871    0.805124    1
75136   13.147394   0.428964    1
38344   1.669788    0.134296    1
72993   10.141740   1.032955    1
35948   6.830792    1.213192    3
42666   13.276369   0.543880    3
67497   8.631577    0.749278    1
35483   12.273169   1.508053    3
50242   3.723498    0.831917    1
63275   8.385879    1.669485    1
5569    4.875435    0.728658    2

完整地數據下載地址如下：
約會網站測試數據
（1）將文本記錄轉為成numpy

#定義一個將文本轉化為numpy的函數
def file2matrix(filepath):
    fr=open(filepath)#讀取文件
    arraylines=fr.readlines()
    numberOfLines=len(arraylines)#得到行數
    returnMat=zeros((numberOfLines,3))#構造全為0的零矩陣
    classLabelVector= []
    index=0
    #解析文件
    for line in arraylines:
        line=line.strip() #刪除空白符（包括'\n', '\r',  '\t',  ' ')
        listFromLine=line.split('\t') #按照('\t')進行拆分
        returnMat[index,:]=listFromLine[0:3] #得到特征變量
        classLabelVector.append(listFromLine[-1]) #得到目標分類變量
        index+=1
    return returnMat,classLabelVector

在python控制臺輸入：

in [5]:datingDataMat,datingLabels=KNN.file2matrix('G:\Workspaces\MachineLearning\machinelearninginaction\Ch02\datingTestSet2.txt')#括號是文件路徑
in [6]:datingDataMat
out[6]:

array([[  4.09200000e+04,   8.32697600e+00,   9.53952000e-01],
       [  1.44880000e+04,   7.15346900e+00,   1.67390400e+00],
       [  2.60520000e+04,   1.44187100e+00,   8.05124000e-01],
       ...,
       [  2.65750000e+04,   1.06501020e+01,   8.66627000e-01],
       [  4.81110000e+04,   9.13452800e+00,   7.28045000e-01],
       [  4.37570000e+04,   7.88260100e+00,   1.33244600e+00]])
in [7]:datingLabels[:10]
Out[7]:
['3', '2', '1', '1', '1', '1', '3', '3', '1', '3']

(2)可視化分析數據
運用Matplotlib創建散點圖來分析數據：

import matplotlib
import matplotlib.pyplot as plt
#對第二列和第三列數據進行分析：
fig=plt.figure()
ax=fig.add_subplot(111)
ax.scatter(datingDataMat[:,1],datingDataMat[:,2],c=datingLabels)
plt.xlabel('Percentage of Time Spent Playing Video Games')
plt.ylabel('Liters of Ice Cream Consumed Per Week')

#對第一列和第二列進行分析：
fig=plt.figure()
ax=fig.add_subplot(111)
ax.scatter(datingDataMat[:,0],datingDataMat[:,1],c=datingLabels)
plt.xlabel('Miles of plane Per year')
plt.ylabel('Percentage of Time Spent Playing Video Games')
ax.legend(loc='best')

可以看到不同的約會對象的喜歡程度按照特征有明顯的類別區分。
因此可以使用KNN算法進行分類和預測。

（3）數據歸一化
由于不同的數據在大小上差別較大，在計算歐式距離，整體較大的數據明細所占的比重更高，因此需要對數據進行歸一化處理。

#對第一列和第二列進行分析：
fig=plt.figure()
ax=fig.add_subplot(111)
ax.scatter(datingDataMat[:,0],datingDataMat[:,1],c=datingLabels)
plt.xlabel('Miles of plane Per year')
plt.ylabel('Percentage of Time Spent Playing Video Games')
ax.legend(loc='best')

在Python控制臺輸入：

reload(KNN)

Out[145]: <module 'KNN' from 'G:\\Workspaces\\MachineLearning\\KNN.py'>

normMat,ranges,minVals=KNN.autoNorm(datingDataMat)


normMat

Out[147]:
array([[ 0.44832535,  0.39805139,  0.56233353],
       [ 0.15873259,  0.34195467,  0.98724416],
       [ 0.28542943,  0.06892523,  0.47449629],
       ...,
       [ 0.29115949,  0.50910294,  0.51079493],
       [ 0.52711097,  0.43665451,  0.4290048 ],
       [ 0.47940793,  0.3768091 ,  0.78571804]])

ranges

Out[148]: array([  9.12730000e+04,   2.09193490e+01,   1.69436100e+00])

minVals

Out[149]: array([ 0.      ,  0.      ,  0.001156])

數據的準備工作完成，下一步對算法進行測試。

2.2 算法測試

kNN算法分類的結果的效果，可以使用正確率/錯誤率來衡量，錯誤率為0，則表示分類很完美，如果錯誤率為1，表示分類完全錯誤。我們使用1000條數據中的90%作為訓練樣本集，其中的10%來測試錯誤率。

#定義測試算法的函數
def datingClassTest(h=0.1):
    hoRatio=h #測試數據的比例
    datingDataMat,datingLabels=file2matrix('G:\Workspaces\MachineLearning\machinelearninginaction\Ch02\datingTestSet2.txt') #準備數據
    normMat,ranges,minVals=autoNorm(datingDataMat) #歸一化處理
    m=normMat.shape[0] #得到行數
    numTestVecs=int(m*hoRatio) #測試數據行數
    errorCount=0 #定義變量來存儲錯誤分類數
    for i in range(numTestVecs):
        classifierResult=classify(normMat[i,:],normMat[numTestVecs:m,:],datingLabels[numTestVecs:m],3)
        print('the classifier came back with: %d,the real answer is: %d'%(int(classifierResult),int(datingLabels[i])))
        if (classifierResult!=datingLabels[i]): errorCount+=1
    print('the total error rate is : %f'%(errorCount/float(numTestVecs)))

在控制臺輸入命令來測試錯誤率：

reload(KNN)

Out[150]: <module 'KNN' from 'G:\\Workspaces\\MachineLearning\\KNN.py'>

KNN.datingClassTest()

the classifier came back with: 3,the real answer is: 3
the classifier came back with: 2,the real answer is: 2
the classifier came back with: 1,the real answer is: 1
... ...
the classifier came back with: 2,the real answer is: 2
the classifier came back with: 1,the real answer is: 1
the classifier came back with: 3,the real answer is: 1
the total error rate is : 0.050000

可以看到KNN算法分類器處理約會數據的錯誤率是5%，具有較高額正確率。
可以在datingClassTest函數中傳入參數h來改變測試數據比例，來看修改后Ration后錯誤率有什么樣的變化。

KNN.datingClassTest(0.2)

the classifier came back with: 3,the real answer is: 3
the classifier came back with: 2,the real answer is: 2
the classifier came back with: 1,the real answer is: 1
... ...
the classifier came back with: 2,the real answer is: 2
the classifier came back with: 3,the real answer is: 3
the classifier came back with: 2,the real answer is: 2
the total error rate is : 0.080000

減小訓練樣本集數據，增加測試數據，錯誤率增加到8%。

2.3 使用KNN算法進行預測

def classifypersion():
    resultList=['not at all','in small doses','in large doses']
    percentTats=float(input('percentage of time spent playing video games?')) #raw_input->input，錄入數據
    ffMiles=float(input('frequent flier miles earned per year?'))
    iceCream=float(input('liters of ice creamconsued per year?'))
    datingDataMat,datingLabels =file2matrix('G:\Workspaces\MachineLearning\machinelearninginaction\Ch02\datingTestSet2.txt')
    normMat,ranges,minVals=autoNorm(datingDataMat)
    inArr=array([ffMiles,percentTats,iceCream])
    classifierResult=classify((inArr-minVals/ranges),normMat,datingLabels,3)
    print('You will probably like this persion :%s'%resultList[int(classifierResult)-1])

測試一下：

reload(KNN)

Out[153]: <module 'KNN' from 'G:\\Workspaces\\MachineLearning\\KNN.py'>

KNN.classifypersion()


percentage of time spent playing video games?10

frequent flier miles earned per year?10000

liters of ice creamconsued per year?0.5
You will probably like this persion :not at all

3. KNN算法用于手寫識別系統

已經將圖片轉化為32*32 的文本格式，文本格式如下：

00000000000111110000000000000000
00000000001111111000000000000000
00000000011111111100000000000000
00000000111111111110000000000000
00000001111111111111000000000000
00000011111110111111100000000000
00000011111100011111110000000000
00000011111100001111110000000000
00000111111100000111111000000000
00000111111100000011111000000000
00000011111100000001111110000000
00000111111100000000111111000000
00000111111000000000011111000000
00000111111000000000011111100000
00000111111000000000011111100000
00000111111000000000001111100000
00000111111000000000001111100000
00000111111000000000001111100000
00000111111000000000001111100000
00000111111000000000001111100000
00000011111000000000001111100000
00000011111100000000011111100000
00000011111100000000111111000000
00000001111110000000111111100000
00000000111110000001111111000000
00000000111110000011111110000000
00000000111111000111111100000000
00000000111111111111111000000000
00000000111111111111110000000000
00000000011111111111100000000000
00000000001111111111000000000000
00000000000111111110000000000000

3.1數據準備
（1）將32*32的文本格式轉為成1*2014的向量

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

在控制臺中輸入命令測試下函數：

reload(KNN)

Out[156]: <module 'KNN' from 'G:\\Workspaces\\MachineLearning\\KNN.py'>

testVector=KNN.img2vector('G:\\Workspaces\\MachineLearning\\machinelearninginaction\\Ch02\\trainingDigits\\0_13.txt')


testVector

Out[158]: array([[ 0.,  0.,  0., ...,  0.,  0.,  0.]])

testVector[0,0:31]

Out[159]: array([ 0.,  0.,  0., ...,  0.,  0.,  0.])

3.2 算法測試
使用kNN算法測試手寫數字識別

#引入os模塊的listdir函數，列出給定目錄的文件名
from os impor listdir

def handwritingClassTest():
    hwLabels=[]
    trainingFileList=listdir('G:/Workspaces/MachineLearning/machinelearninginaction/Ch02/trainingDigits')#列出文件名
    m=len(trainingFileList) #文件數目
    trainMat=zeros((m,1024))
    #從文件名中解析分類信息，如0_13.txt
    for i in range(m):
        fileNameStr=trainingFileList[i]
        fileStr=fileNameStr.split('.')[0]
        classNumber=int(fileStr.split('_')[0])
        hwLabels.append(classNumber)
        trainMat[i]=img2vector('G:/Workspaces/MachineLearning/machinelearninginaction/Ch02/trainingDigits/%s'%fileNameStr)
    testFileList=listdir('G:/Workspaces/MachineLearning/machinelearninginaction/Ch02/testDigits')
    errorCount=0
    #同上，解析測試數據的分類信息
    mTest=len(testFileList)
    for i in range(mTest):
        fileNameStr=testFileList[i]
        fileStr=fileNameStr.split('.')[0]
        classNumber=int(fileStr.split('_')[0])
        vectorUnderTest=img2vector('G:/Workspaces/MachineLearning/machinelearninginaction/Ch02/testDigits/%s'%fileNameStr)
        classifierResult=classify(vectorUnderTest,trainMat,hwLabels,3)
        print('the classifier came back with :%d,the real answer is:%d'%(classifierResult,classNumber))
        if(classifierResult!=classNumber):errorCount+=1
    print('\n the total number of errors is: %d'%errorCount)
    print('\n total error rate is %f'%(errorCount/float(mTest)))

接下來在Python控制臺輸入命令來測試手寫數字識別：

reload(KNN)
KNN.handwritingClassTest()

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 :0,the real answer is:0
... ...
the classifier came back with :9,the real answer is:9
the classifier came back with :9,the real answer is:9
the classifier came back with :9,the real answer is:9

 the total number of errors is: 10

 total error rate is 0.010571

錯誤利率1.057%，具有較高的準確率。