【博客的主要內(nèi)容主要是自己的學(xué)習(xí)筆記，并結(jié)合個(gè)人的理解，供各位在學(xué)習(xí)過(guò)程中參考，若有疑問(wèn)，歡迎提出；若有侵權(quán)，請(qǐng)告知博主刪除，原創(chuàng)文章轉(zhuǎn)載還請(qǐng)注明出處?！?/p>

1.什么是kNN#

k-近鄰算法（kNN k-NearestNeighbor）采用測(cè)量不同特征值之間的距離方法進(jìn)行分類(lèi)。在確定分類(lèi)決策上僅依據(jù)最鄰近的一個(gè)或多個(gè)樣本的類(lèi)別來(lái)決定待分樣本所屬類(lèi)別。

2.用途#

kNN算法主要被用于文本分類(lèi)、相似推薦.

3. kNN工作原理#

存在一個(gè)樣本數(shù)據(jù)集合（即訓(xùn)練樣本集），并且樣本集中每個(gè)數(shù)據(jù)都存在標(biāo)簽（即每個(gè)數(shù)據(jù)與所屬分類(lèi)的對(duì)應(yīng)關(guān)系）。輸入沒(méi)有標(biāo)簽的新數(shù)據(jù)之后，將新數(shù)據(jù)的每個(gè)特征與樣本集中數(shù)據(jù)對(duì)應(yīng)的特征進(jìn)行比較，算法將提取出樣本集中特征最相似數(shù)據(jù)（最近鄰）的分類(lèi)標(biāo)簽。

一般選擇樣本數(shù)據(jù)集中前K個(gè)最相似的數(shù)據(jù)，k一般不大于20的整數(shù)。

說(shuō)明：圖中綠色圓點(diǎn)表示新數(shù)據(jù)，藍(lán)色正方形和紅色三角形表示已分類(lèi)的樣本集。
如果K=3，由于紅色三角形所占比例為2/3，綠色圓點(diǎn)則屬于“紅色三角形”分類(lèi)；
如果K=5，由于藍(lán)色正方形所占比例為3/5，綠色圓點(diǎn)則屬于“藍(lán)色正方形”分類(lèi)。

4. kNN算法流程#

使用K-近鄰算法將每組數(shù)據(jù)劃分到某個(gè)類(lèi)中：
1）計(jì)算已知類(lèi)別數(shù)據(jù)集中的點(diǎn)與當(dāng)前點(diǎn)之間的距離；

2）按照距離遞增次序排序；
3）選取與當(dāng)前點(diǎn)距離最小的K個(gè)點(diǎn)；
4）確定前K個(gè)點(diǎn)所在類(lèi)別的出現(xiàn)頻率；
5）返回前K個(gè)點(diǎn)出現(xiàn)頻率最高的類(lèi)別作為當(dāng)前點(diǎn)的預(yù)測(cè)分類(lèi)。

5. kNN算法Code#

1.Python算法實(shí)現(xiàn)

from numpy import *
import  operator
from os import listdir

def classify0(inX, dataSet, labels,k):        
    #0、獲取數(shù)據(jù)Count
    dataSetSize = dataSet.shape[0]
    
    #1、計(jì)算距離
    diffMat = tile(inX,(dataSetSize,1)) - dataSet
    sqDiffMat = diffMat ** 2
    sqDistances = sqDiffMat.sum(axis=1)
    distances = sqDistances ** 0.5
    
    #2、選擇最小距離的k個(gè)點(diǎn)
    sortedDistIndicies = distances.argsort()
    
    #3、確定前K個(gè)點(diǎn)所在類(lèi)別的出現(xiàn)頻率
    classCount={}
    for i in range(k):
        voteIlabel = labels[sortedDistIndicies[i]]
        classCount[voteIlabel] = classCount.get(voteIlabel,0) + 1
    
    #4、返回前K個(gè)點(diǎn)出現(xiàn)頻率最高的類(lèi)別作為當(dāng)前點(diǎn)的預(yù)測(cè)分類(lèi)
    sortedClassCount = sorted(classCount.iteritems(),key=operator.itemgetter(1),reverse=True)
    
    return sortedClassCount[0][0]  

2、kNN算法測(cè)試

def createDataSet():
    group = array([[1.0,1.1],[1.0,1.0],[0,0],[0,0.1]])
    labels = ['A','A','B','B']
    return group,labels

6. kNN算法特點(diǎn)#

優(yōu)點(diǎn)
1、簡(jiǎn)單，易于理解，易于實(shí)現(xiàn)，無(wú)需估計(jì)參數(shù)，無(wú)需訓(xùn)練；
2、適合對(duì)稀有事件進(jìn)行分類(lèi)；
3、適用于多分類(lèi)問(wèn)題。
缺點(diǎn)
1、計(jì)算復(fù)雜度高、空間復(fù)雜度高；
2、可理解性差，無(wú)法給出像決策樹(shù)類(lèi)的規(guī)則。

7. kNN示例分析#

7.1 示例1：使用k-近鄰算法改進(jìn)約會(huì)網(wǎng)站的配對(duì)效果##

1.背景
海倫通過(guò)在線(xiàn)約會(huì)網(wǎng)尋找自己合適的約會(huì)對(duì)象。根據(jù)自己一番總結(jié)將約會(huì)對(duì)象分為三類(lèi)：
1、不喜歡的人；
2、魅力一般的人；
3、極具魅力的人.

海倫收集網(wǎng)站中每位約會(huì)對(duì)象的以下數(shù)據(jù)來(lái)劃分其約會(huì)類(lèi)型：
1、每年獲得的飛行公里數(shù)；
2、玩視頻游戲所耗時(shí)間百分比；
3、每周消費(fèi)的冰淇淋公升數(shù).

編寫(xiě)個(gè)小程序，海倫輸入會(huì)員特征值程序顯示該會(huì)員所屬分類(lèi)。

2. 分析
1）收集數(shù)據(jù)：提供文本文件
2）準(zhǔn)備數(shù)據(jù)：使用Python解析文本文件
3）分析數(shù)據(jù)：使用Matplotlib畫(huà)二維擴(kuò)散圖
4）訓(xùn)練數(shù)據(jù)：不適合kNN
5）測(cè)試數(shù)據(jù)：使用海倫提供的部分?jǐn)?shù)據(jù)作為測(cè)試樣本
6）使用算法：產(chǎn)生簡(jiǎn)單的命令行程序，然后海倫可以輸入一些特征數(shù)據(jù)以判斷是否為自己喜歡的類(lèi)型。

3. Code
使用Python解析文本文件

def file2matrix(filename):
     fr = open(filename)
     numberOfLines = len(fr.readlines())
     
     #初始化矩陣
    returnMat = zeros((numberOfLines,3))
         
     #初始化標(biāo)簽矩陣
     classLabelVector = []
         
     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

4. 使用Matplotlib畫(huà)二維擴(kuò)散圖

#讀取樣本數(shù)據(jù)   
datingDataMat,datingLabels = file2matrix('H:\workspacePy\machinelearninginaction\Ch02\datingTestSet2.txt')
             
#散點(diǎn)圖顯示樣本數(shù)據(jù)
import matplotlib
import matplotlib.pyplot as plt
import matplotlib.font_manager 
             
fig = plt.figure()
ax = fig.add_subplot(111)
             
##1、散點(diǎn)圖顯示“玩視頻游戲所耗時(shí)間百分比”、“每周消費(fèi)的冰淇淋公升數(shù)”
ax.scatter(datingDataMat[:,1], datingDataMat[:,2], 15.0*array(datingLabels),15.0*array(datingLabels))
plt.show()
             
##2、散點(diǎn)圖顯示“每年獲得的飛行?？屠锍虜?shù)”、“玩視頻游戲所耗時(shí)間百分比”
ax.scatter(datingDataMat[:,0],datingDataMat[:,1],15.0*array(datingLabels),15.0*array(datingLabels))
plt.show()

5.歸一化特征值

特征值數(shù)值間相差較大，在計(jì)算距離時(shí)易產(chǎn)生較大偏差。例如：

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

6.測(cè)試算法

機(jī)器學(xué)習(xí)算法很大重要工作就是評(píng)估算法的正確率，通常將提供已有數(shù)據(jù)的90%作為訓(xùn)練樣本來(lái)訓(xùn)練分類(lèi)器，而使用其余的10%數(shù)據(jù)去測(cè)試分類(lèi)器，檢查分類(lèi)器的正確率。

def datingClassTest():
     hoRatio = 0.10
    datingDataMat,datingLabels = file2matrix('datingTestSet.txt')
     normDataSet,ranges,minVals = autoNorm(datingDataMat)
    m = normDataSet.shape[0]
    numTestVecs = int(m * hoRatio)
    errorCount = 0.0    
    for i in range(numTestVecs):
        classifierResult = classify0(normDataSet[i,:],normDataSet[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))

7.2 示例2：手寫(xiě)識(shí)別系統(tǒng)##

1. 背景
數(shù)字0_{9，通過(guò)32*32位圖來(lái)展現(xiàn)?，F(xiàn)有1900個(gè)位圖數(shù)據(jù)，分別表示了0}9數(shù)字內(nèi)容。需通過(guò)kNN方法能快速分辨出位圖的數(shù)字。

2. 分析
1）收集數(shù)據(jù)：提供文本文件；
2）準(zhǔn)備數(shù)據(jù)：將圖像格式轉(zhuǎn)換為分類(lèi)器使用的list格式；
3）分析數(shù)據(jù)：在Python命令提示符中檢查數(shù)據(jù)，確保它符合要求；
4）訓(xùn)練算法：不適合kNN算法；
5）測(cè)試數(shù)據(jù)：編寫(xiě)函數(shù)使用提供的部分?jǐn)?shù)據(jù)集作為測(cè)試樣本，測(cè)試樣本與非測(cè)試樣本的區(qū)別在于測(cè)試樣本是已經(jīng)完成分類(lèi)的數(shù)據(jù)，如果預(yù)測(cè)分類(lèi)與實(shí)際類(lèi)別不同，則標(biāo)記為一個(gè)錯(cuò)誤。
6）使用算法：省略

3.Code

#將32**32位圖片數(shù)據(jù)轉(zhuǎn)換為1*1024的list
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

4.測(cè)試算法

#測(cè)試算法
def handwritingClassTest():
    #1、獲取樣本數(shù)據(jù)集合，
    hwLabels = []
    path = 'H:\\workspacePy\\machinelearninginaction\\Ch02\\digits\\trainingDigits'
    trainingFileList = listdir(path)
    m = len(trainingFileList)
    trainingMat = zeros((m,1024))
    
    #2、將樣本數(shù)據(jù)并轉(zhuǎn)換為list
    for i in range(m):
        fileNameStr = trainingFileList[i]
        fileStr = fileNameStr.split('.')[0]
        classNumStr = int(fileStr.split('_')[0])
        hwLabels.append(classNumStr)
        
        trainingMat[i,:] = img2vector(path + '/%s' % fileNameStr)
                
    #3、使用測(cè)試樣本進(jìn)行測(cè)試對(duì)比。
    path1 = 'H:\\workspacePy\\machinelearninginaction\\Ch02\\digits\\testDigits'
    testFileList = listdir(path1)
    errorCount = 0.0
    mTest = len(testFileList)
    for i in range(mTest):
        fileNameStr = testFileList[i]
        fileStr = fileNameStr.split('.')[0]
        classNumStr = int(fileStr.split('_')[0])
        
        vectorUnderTest = img2vector(path1 + '/%s' % fileNameStr)
        
        ##knn
        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))