機(jī)器學(xué)習(xí)之k-近鄰（kNN）算法與Python實(shí)現(xiàn)

k-近鄰算法（kNN，k-NearestNeighbor），是最簡(jiǎn)單的機(jī)器學(xué)習(xí)分類算法之一，其核心思想在于用距離目標(biāo)最近的k個(gè)樣本數(shù)據(jù)的分類來(lái)代表目標(biāo)的分類（這k個(gè)樣本數(shù)據(jù)和目標(biāo)數(shù)據(jù)最為相似）。

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

1.概念

kNN算法的核心思想是用距離最近的k個(gè)樣本數(shù)據(jù)的分類來(lái)代表目標(biāo)數(shù)據(jù)的分類。

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

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

2.特點(diǎn)

優(yōu)點(diǎn)
（1）監(jiān)督學(xué)習(xí)：可以看到，kNN算法首先需要一個(gè)訓(xùn)練樣本集，這個(gè)集合中含有分類信息，因此它屬于監(jiān)督學(xué)習(xí)。
（2）通過(guò)計(jì)算距離來(lái)衡量樣本之間相似度，算法簡(jiǎn)單，易于理解和實(shí)現(xiàn)。
（3）對(duì)異常值不敏感

缺點(diǎn) （4）需要設(shè)定k值，結(jié)果會(huì)受到k值的影響，通過(guò)上面的例子可以看到，不同的k值，最后得到的分類結(jié)果不盡相同。k一般不超過(guò)20。（5）計(jì)算量大，需要計(jì)算樣本集中每個(gè)樣本的距離，才能得到k個(gè)最近的數(shù)據(jù)樣本。 （6）訓(xùn)練樣本集不平衡導(dǎo)致結(jié)果不準(zhǔn)確問(wèn)題。當(dāng)樣本集中主要是某個(gè)分類，該分類數(shù)量太大，導(dǎo)致近鄰的k個(gè)樣本總是該類，而不接近目標(biāo)分類。

3.kNN算法流程

一般情況下，kNN有如下流程：
（1）收集數(shù)據(jù)：確定訓(xùn)練樣本集合測(cè)試數(shù)據(jù)；
（2）計(jì)算測(cè)試數(shù)據(jù)和訓(xùn)練樣本集中每個(gè)樣本數(shù)據(jù)的距離；

常用的距離計(jì)算公式： 

（3）按照距離遞增的順序排序；
（4）選取距離最近的k個(gè)點(diǎn)；
（5）確定這k個(gè)點(diǎn)中分類信息的頻率；
（6）返回前k個(gè)點(diǎn)中出現(xiàn)頻率最高的分類，作為當(dāng)前測(cè)試數(shù)據(jù)的分類。

二 、Python算法實(shí)現(xiàn)

1.KNN算法分類器

建立一個(gè)名為“KNN.py”的文件，構(gòu)造一個(gè)kＮＮ算法分類器的函數(shù)：

from numpy import *
import operator

#定義KNN算法分類器函數(shù)
#函數(shù)參數(shù)包括：(測(cè)試數(shù)據(jù)，訓(xùn)練數(shù)據(jù)，分類,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 #計(jì)算歐式距離
    sortedDistIndicies=distances.argsort() #排序并返回index
    #選擇距離最近的k個(gè)值
    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中定義一個(gè)生成“訓(xùn)練樣本集”的函數(shù)：

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

在Python控制臺(tái)先將當(dāng)前目錄設(shè)置為“KNN.py”所在的文件目錄，將測(cè)試數(shù)據(jù)[0,0]進(jìn)行KNN算法分類測(cè)試，輸入：

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

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

2.kNN算法用于約會(huì)網(wǎng)站配對(duì)

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

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

完整地?cái)?shù)據(jù)下載地址如下：
約會(huì)網(wǎng)站測(cè)試數(shù)據(jù)
（1）將文本記錄轉(zhuǎn)為成numpy

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

在python控制臺(tái)輸入：

in [5]:datingDataMat,datingLabels=KNN.file2matrix('G:\Workspaces\MachineLearning\machinelearninginaction\Ch02\datingTestSet2.txt')#括號(hào)是文件路徑
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)可視化分析數(shù)據(jù)
運(yùn)用Matplotlib創(chuàng)建散點(diǎn)圖來(lái)分析數(shù)據(jù)：

import matplotlib
import matplotlib.pyplot as plt
#對(duì)第二列和第三列數(shù)據(jù)進(jìn)行分析：
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')

#對(duì)第一列和第二列進(jìn)行分析：
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')

可以看到不同的約會(huì)對(duì)象的喜歡程度按照特征有明顯的類別區(qū)分。
因此可以使用KNN算法進(jìn)行分類和預(yù)測(cè)。

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

#對(duì)第一列和第二列進(jìn)行分析：
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控制臺(tái)輸入：

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

數(shù)據(jù)的準(zhǔn)備工作完成，下一步對(duì)算法進(jìn)行測(cè)試。

2.2 算法測(cè)試

kNN算法分類的結(jié)果的效果，可以使用正確率/錯(cuò)誤率來(lái)衡量，錯(cuò)誤率為0，則表示分類很完美，如果錯(cuò)誤率為1，表示分類完全錯(cuò)誤。我們使用1000條數(shù)據(jù)中的90%作為訓(xùn)練樣本集，其中的10%來(lái)測(cè)試錯(cuò)誤率。

#定義測(cè)試算法的函數(shù)
def datingClassTest(h=0.1):
    hoRatio=h #測(cè)試數(shù)據(jù)的比例
    datingDataMat,datingLabels=file2matrix('G:\Workspaces\MachineLearning\machinelearninginaction\Ch02\datingTestSet2.txt') #準(zhǔn)備數(shù)據(jù)
    normMat,ranges,minVals=autoNorm(datingDataMat) #歸一化處理
    m=normMat.shape[0] #得到行數(shù)
    numTestVecs=int(m*hoRatio) #測(cè)試數(shù)據(jù)行數(shù)
    errorCount=0 #定義變量來(lái)存儲(chǔ)錯(cuò)誤分類數(shù)
    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)))

在控制臺(tái)輸入命令來(lái)測(cè)試錯(cuò)誤率：

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算法分類器處理約會(huì)數(shù)據(jù)的錯(cuò)誤率是5%，具有較高額正確率。
可以在datingClassTest函數(shù)中傳入?yún)?shù)h來(lái)改變測(cè)試數(shù)據(jù)比例，來(lái)看修改后Ration后錯(cuò)誤率有什么樣的變化。

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

減小訓(xùn)練樣本集數(shù)據(jù)，增加測(cè)試數(shù)據(jù)，錯(cuò)誤率增加到8%。

2.3 使用KNN算法進(jìn)行預(yù)測(cè)

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，錄入數(shù)據(jù)
    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])

測(cè)試一下：

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算法用于手寫(xiě)識(shí)別系統(tǒng)

已經(jīng)將圖片轉(zhuǎn)化為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數(shù)據(jù)準(zhǔn)備
（1）將32*32的文本格式轉(zhuǎn)為成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

在控制臺(tái)中輸入命令測(cè)試下函數(shù)：

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 算法測(cè)試
使用kNN算法測(cè)試手寫(xiě)數(shù)字識(shí)別

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

def handwritingClassTest():
    hwLabels=[]
    trainingFileList=listdir('G:/Workspaces/MachineLearning/machinelearninginaction/Ch02/trainingDigits')#列出文件名
    m=len(trainingFileList) #文件數(shù)目
    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
    #同上，解析測(cè)試數(shù)據(jù)的分類信息
    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)))

接下來(lái)在Python控制臺(tái)輸入命令來(lái)測(cè)試手寫(xiě)數(shù)字識(shí)別：

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

錯(cuò)誤利率1.057%，具有較高的準(zhǔn)確率。