文章目錄

• • • 2.1 k-近鄰算法概述
    • • 2.1.1 準備：使用python導(dǎo)入數(shù)據(jù)
      • 2.1.2 從文本文件中解析數(shù)據(jù)
    • 2.2 示例：使用k-近鄰算法改進約會網(wǎng)站的配對效果
    • • 2.2.1 準備數(shù)據(jù)：從文本文件中解析數(shù)據(jù)
      • 2.2.2 分析數(shù)據(jù)：使用Matplotlib創(chuàng)建散點圖
      • 2.2.3 準備數(shù)據(jù)：歸一化數(shù)值
      • 2.2.4 測試算法：作為完整程序驗證分類器
      • 2.2.5 使用算法：構(gòu)建完整可用系統(tǒng)
    • 2.3 手寫識別系統(tǒng)
    • • 2.3.1 準備數(shù)據(jù)：將圖像轉(zhuǎn)化為測試向量
      • 2.3.2 使用sklearn實現(xiàn)手寫體識別
    • 2.4 KNN算法的優(yōu)缺點
    • • 2.4.1 優(yōu)點
      • 2.4.2 缺點：

2.1 k-近鄰算法概述

簡單的說，k-近鄰算法采用測量不同特征值之間的距離方法進行分類

• 優(yōu)點：精度高、對異常值不敏感、無數(shù)據(jù)輸入假定
• 缺點：計算復(fù)雜度高、空間復(fù)雜度高
• 適用數(shù)據(jù)范圍：數(shù)值型和標稱型
• 數(shù)值型：數(shù)值型目標變量則可以從無限的數(shù)值集合中取值，如0.100，42.001等 (數(shù)值型目標變量主要用于回歸分析)
• 標稱型： 標稱型目標變量的結(jié)果只在有限目標集中取值，如真與假(標稱型目標變量主要用于分類)

k近鄰法(k-nearest neighbor, k-NN)是1967年由Cover T和Hart P提出的一種基本分類與回歸方法。它的工作原理是：存在一個樣本數(shù)據(jù)集合，也稱作為訓(xùn)練樣本集，并且樣本集中每個數(shù)據(jù)都存在標簽，即我們知道樣本集中每一個數(shù)據(jù)與所屬分類的對應(yīng)關(guān)系。輸入沒有標簽的新數(shù)據(jù)后，將新的數(shù)據(jù)的每個特征與樣本集中數(shù)據(jù)對應(yīng)的特征進行比較，然后算法提取樣本最相似數(shù)據(jù)(最近鄰)的分類標簽。一般來說，我們只選擇樣本數(shù)據(jù)集中前k個最相似的數(shù)據(jù)，這就是k-近鄰算法中k的出處，通常k是不大于20的整數(shù)。最后，選擇k個最相似數(shù)據(jù)中出現(xiàn)次數(shù)最多的分類，作為新數(shù)據(jù)的分類。

舉例：利用k-近鄰算法分類愛情片和動作片
圖2-1顯示了5部動作電影的打斗和接吻鏡頭個數(shù)，假如有一部未看過的電影，可以使用KNN來確定其為愛情片還是動作片。

圖中的？是該未知電影出現(xiàn)的鏡頭數(shù)圖形化展示，具體數(shù)字見表2-1

通過計算未知電影與樣本集中其他電影的距離，可以判斷其類型。

按照距離遞增排序，可以找到k個距離最近的電影，假設(shè)k=3，則距離最近的全是愛情片，可以判斷其為愛情片。

k-近鄰算法的一般流程：

計算已知類別數(shù)據(jù)集中的點與當(dāng)前點之間的距離；

按照距離遞增次序排序；

選取與當(dāng)前點距離最小的k個點；

確定前k個點所在類別的出現(xiàn)頻率；

返回前k個點所出現(xiàn)頻率最高的類別作為當(dāng)前點的預(yù)測分類。

距離度量：

2.1.1 準備：使用python導(dǎo)入數(shù)據(jù)

Machine Learning in Action Source Code

from numpy import * import operator # 導(dǎo)入運算符模塊# 創(chuàng)建數(shù)據(jù)集和標簽的函數(shù) def createDataSet():group = array([[1.0, 1.1], [1.0, 1.0], [0, 0], [0, 0.1]])labels = ['A', 'A', 'B', 'B']return group, labelsif __name__ == '__main__':group, labels = createDataSet()print(group)print(labels)

結(jié)果：

[[ 1. 1.1][ 1. 1. ][ 0. 0. ][ 0. 0.1]] ['A', 'A', 'B', 'B']

2.1.2 從文本文件中解析數(shù)據(jù)

利用k-近鄰算法將每組數(shù)據(jù)劃分到某個類中，其偽代碼如下：

對未知類別屬性的數(shù)據(jù)集中的每個點依次執(zhí)行以下操作：

計算已知類別數(shù)據(jù)集中的點與當(dāng)前點之間的距離

按照距離遞增次序排序

選取與當(dāng)前點距離最小的k個點

確定前k個點所在類別的出現(xiàn)頻率

返回前k個點出現(xiàn)頻率最高類別作為當(dāng)前點的預(yù)測分類

import numpy as np import operator""" 函數(shù)說明：KNN算法，文本分類Parameters：inX：用于分類的數(shù)據(jù)（測試集）dataSet：用于訓(xùn)練的數(shù)據(jù)（訓(xùn)練集）labels：分類標簽k：kNN算法參數(shù)，選擇距離最小的k個點returns：分類結(jié)果modify:2018-03-08"""def classify0(inX,dataSet,labels,k):#numpy函數(shù)shape[0]返回dataSet行數(shù)dataSetSize=dataSet.shape[0]#在列向量方向上重復(fù)inX一次（橫向），在行向量方向上重復(fù)inX共dataSetSize次（縱向）#numpy.tile([0,0],(1,1))#在列方向上重復(fù)[0,0]1次，行1次 >>>array([[0, 0]])diffMat=np.tile(inX,(dataSetSize,1))-dataSet#二維特征相減后平方sqDiffMat=diffMat**2#sum()所有元素相加，sum(0)列相加，sum(1)行相加sqDistances=sqDiffMat.sum(axis=1)#開方，計算出距離distances=sqDistances**0.5#返回distances中元素從小到大排序后的索引值sortedDistIndices=distances.argsort()#定一個記錄類別次數(shù)的字典classCount={}for i in range(k):#取出前k個元素的類別voteIlabel=labels[sortedDistIndices[i]]#計算類別次數(shù)# dict.get(key,default=None),字典的get()方法,返回指定鍵的值,如果值不在字典中返回默認值。classCount[voteIlabel]=classCount.get(voteIlabel,0)+1#key=operator.items(1)根據(jù)字典的值進行排序#key=operator.items(0)根據(jù)字典的鍵值進行排序#reverse降序排序字典sortedClassCount=sorted(classCount.items(),key=operator.itemgetter(1),reverse=True)#返回次數(shù)最多的類別，即所要分類的類別return sortedClassCount[0][0]

其中，標簽向量的元素數(shù)目和矩陣dataSet行數(shù)相同，上述程序中使用歐氏距離公式，計算兩個向量點之間的距離。
$$d=\sqrt{(x{A}_0?x{B}_0{)}^2+(x{A}_1?x{B}_1{)}^2}$$

整體程序示例：

import numpy as np import operator""" 函數(shù)說明：KNN算法，文本分類Parameters：inX：用于分類的數(shù)據(jù)（測試集）dataSet：用于訓(xùn)練的數(shù)據(jù)（訓(xùn)練集）labels：分類標簽k：kNN算法參數(shù)，選擇距離最小的k個點returns：分類結(jié)果modify:2018-03-08""" def createDataSet():group = np.array([[1, 101], [5, 89], [108, 0], [108, 5]])labels = ['愛情片','愛情片', '動作片', '動作片']return group, labelsdef classify0(inX,dataSet,labels,k):#numpy函數(shù)shape[0]返回dataSet行數(shù)dataSetSize=dataSet.shape[0]#在列向量方向上重復(fù)inX一次（橫向），在行向量方向上重復(fù)inX共dataSetSize次（縱向）#numpy.tile([0,0],(1,1))#在列方向上重復(fù)[0,0]1次，行1次 >>>array([[0, 0]])diffMat=np.tile(inX,(dataSetSize,1))-dataSet#二維特征相減后平方sqDiffMat=diffMat**2#sum()所有元素相加，sum(0)列相加，sum(1)行相加sqDistances=sqDiffMat.sum(axis=1)#開方，計算出距離distances=sqDistances**0.5#返回distances中元素從小到大排序后的索引值sortedDistIndices=distances.argsort()#定一個記錄類別次數(shù)的字典classCount={}for i in range(k):#取出前k個元素的類別voteIlabel=labels[sortedDistIndices[i]]#計算類別次數(shù)# dict.get(key,default=None),字典的get()方法,返回指定鍵的值,如果值不在字典中返回默認值。classCount[voteIlabel]=classCount.get(voteIlabel,0)+1#key=operator.items(1)根據(jù)字典的值進行排序#key=operator.items(0)根據(jù)字典的鍵值進行排序#reverse降序排序字典sortedClassCount=sorted(classCount.items(),key=operator.itemgetter(1),reverse=True)#返回次數(shù)最多的類別，即所要分類的類別return sortedClassCount[0][0]if __name__ == '__main__':#創(chuàng)建數(shù)據(jù)集group, labels = createDataSet()#測試集test = [101,20]#kNN分類test_class = classify0(test, group, labels, 3)#打印分類結(jié)果print(test_class)

輸出：

動作片

看到這里，有人可能會問：“分類器何種情況下會出錯？”或者“答案是否總是正確的？”答案是否定的.

分類器并不會得到百分百正確的結(jié)果，我們可以使用多種方法檢測分類器的正確率。此外分類器的性能也會受到多種因素的影響，如分類器設(shè)置和數(shù)據(jù)集等。不同的算法在不同數(shù)據(jù)集上的表現(xiàn)可能完全不同。

為了測試分類器的效果，我們可以使用已知答案的數(shù)據(jù)，當(dāng)然答案不能告訴分類器，檢驗分類器給出的結(jié)果是否符合預(yù)期結(jié)果。通過大量的測試數(shù)據(jù)，我們可以得到分類器的錯誤率-分類器給出錯誤結(jié)果的次數(shù)除以測試執(zhí)行的總數(shù)。

錯誤率是常用的評估方法，主要用于評估分類器在某個數(shù)據(jù)集上的執(zhí)行效果。完美分類器的錯誤率為0，最差分類器的錯誤率是1.0。同時，我們也不難發(fā)現(xiàn)，k-近鄰算法沒有進行數(shù)據(jù)的訓(xùn)練，直接使用未知的數(shù)據(jù)與已知的數(shù)據(jù)進行比較，得到結(jié)果。因此，可以說k-鄰近算法不具有顯式的學(xué)習(xí)過程。

2.2 示例：使用k-近鄰算法改進約會網(wǎng)站的配對效果

步驟：

收集數(shù)據(jù)：提供文本文件

準備數(shù)據(jù)：使用python解析文本文件

分析數(shù)據(jù)：使用Matplotlib畫二維擴散圖

訓(xùn)練算法：此步驟不適合于k-近鄰算法

測試算法：使用海倫提供的部分數(shù)據(jù)作為測試樣本
測試樣本和非測試樣本的區(qū)別在于：測試樣本是完成分類的數(shù)據(jù)，如果預(yù)測分類與實際類別不同，則標記為一個錯誤

使用算法：產(chǎn)生簡單的命令行程序，然后海倫可以輸入一些特征數(shù)據(jù)以判斷對方是否為自己喜歡的類型

2.2.1 準備數(shù)據(jù)：從文本文件中解析數(shù)據(jù)

每個樣本數(shù)據(jù)占一行，共1000行，存儲在datingTestSet.txt中，樣本包含三種特征：

• 每年獲得的飛行常客里程數(shù)
• 玩游戲所耗時間百分比
• 每周消費的冰淇淋公升數(shù)

將上述特征數(shù)據(jù)輸入到分類器之前，必須將待處理數(shù)據(jù)的格式改變?yōu)榉诸惼骺山邮艿母袷?#xff0c;在KNN.py中創(chuàng)建名為file2matrix的函數(shù)，以此來處理輸入格式問題，輸入為文件名字符串，輸出為訓(xùn)練樣本矩陣和類標簽向量。

import numpy as np""" 函數(shù)說明：打開解析文件，對數(shù)據(jù)進行分類，1——喜歡，2——魅力一般，3——極具魅力Parameters：filename:文件名Returns：returnMat：特征矩陣classLabelVector：分類label向量Modify：2018-03-08"""def file2matrix(filename):# 打開文件fr = open(filename)# 讀取文件所有內(nèi)容arrayOLines = fr.readlines()# 得到文件行數(shù)numberOfLines = len(arrayOLines)# 返回的numpy矩陣，解析完成的數(shù)據(jù)：numberOfLines行，3列returnMat = np.zeros((numberOfLines, 3))# 返回的分類標簽向量classLabelVector = []# 行索引值index = 0for line in arrayOLines:# s.strip(rm)，當(dāng)rm為空時，默認刪除空白符（包括'\n','\t','\r',''）line = line.strip()# 使用s.split(str="",num=string,cout(str))將字符串根據(jù)'\t'分隔符進行切片listFromLine = line.split('\t')# 將數(shù)據(jù)前三列提取出來，存放到returnMat的numpy矩陣中，也就是特征矩陣returnMat[index, :] = listFromLine[0:3]# 根據(jù)文本中標記的喜歡程度進行分類，1代表不喜歡，2代表一般，3代表極具魅力if listFromLine[-1] == 'didntLike':classLabelVector.append(1)elif listFromLine[-1] == 'smallDoses':classLabelVector.append(2)elif listFromLine[-1] == 'largeDoses':classLabelVector.append(3)index += 1return returnMat, classLabelVector""" 函數(shù)說明：main函數(shù)Parameters：無 Returns：無 Modify：2018-03-08 """ if __name__=='__main__':# 打開的文件名filename = "datingTestSet.txt"# 打開并處理數(shù)據(jù)datingDataMat, datingLabels = file2matrix(filename)print(datingDataMat)print(datingLabels)

結(jié)果：

上面的矩陣是特征矩陣，下面的向量是標簽向量。

可以看到，我們已經(jīng)順利導(dǎo)入數(shù)據(jù)，并對數(shù)據(jù)進行解析，格式化為分類器需要的數(shù)據(jù)格式。接著我們需要了解數(shù)據(jù)的真正含義。可以通過友好、直觀的圖形化的方式觀察數(shù)據(jù)。

2.2.2 分析數(shù)據(jù)：使用Matplotlib創(chuàng)建散點圖

from matplotlib.font_manager import FontProperties import matplotlib.lines as mlines import matplotlib.pyplot as plt import numpy as np""" 函數(shù)說明:打開并解析文件，對數(shù)據(jù)進行分類：1代表不喜歡,2代表魅力一般,3代表極具魅力Parameters:filename - 文件名 Returns:returnMat - 特征矩陣classLabelVector - 分類Label向量Modify:2017-03-09 """ def file2matrix(filename):#打開文件fr = open(filename)#讀取文件所有內(nèi)容arrayOLines = fr.readlines()#得到文件行數(shù)numberOfLines = len(arrayOLines)#返回的NumPy矩陣,解析完成的數(shù)據(jù):numberOfLines行,3列returnMat = np.zeros((numberOfLines,3))#返回的分類標簽向量classLabelVector = []#行的索引值index = 0for line in arrayOLines:#s.strip(rm)，當(dāng)rm空時,默認刪除空白符(包括'\n','\r','\t',' ')line = line.strip()#使用s.split(str="",num=string,cout(str))將字符串根據(jù)'\t'分隔符進行切片。listFromLine = line.split('\t')#將數(shù)據(jù)前三列提取出來,存放到returnMat的NumPy矩陣中,也就是特征矩陣returnMat[index,:] = listFromLine[0:3]#根據(jù)文本中標記的喜歡的程度進行分類,1代表不喜歡,2代表魅力一般,3代表極具魅力if listFromLine[-1] == 'didntLike':classLabelVector.append(1)elif listFromLine[-1] == 'smallDoses':classLabelVector.append(2)elif listFromLine[-1] == 'largeDoses':classLabelVector.append(3)index += 1return returnMat, classLabelVector""" 函數(shù)說明:可視化數(shù)據(jù)Parameters:datingDataMat：特征矩陣datingLabels：分類Label Returns:無 Modify:2018-03-09 """ def showdatas(datingDataMat, datingLabels):#設(shè)置漢字格式font = FontProperties(fname=r"c:\windows\fonts\simsun.ttc", size=14)#將fig畫布分隔成1行1列,不共享x軸和y軸,fig畫布的大小為(13,8)#當(dāng)nrow=2,nclos=2時,代表fig畫布被分為四個區(qū)域,axs[0][0]表示第一行第一個區(qū)域fig, axs = plt.subplots(nrows=2, ncols=2,sharex=False, sharey=False, figsize=(13,8))numberOfLabels = len(datingLabels)LabelsColors = []for i in datingLabels:if i == 1:LabelsColors.append('black')if i == 2:LabelsColors.append('orange')if i == 3:LabelsColors.append('red')#畫出散點圖,以datingDataMat矩陣的第一(飛行常客例程)、第二列(玩游戲)數(shù)據(jù)畫散點數(shù)據(jù),散點大小為15,透明度為0.5axs[0][0].scatter(x=datingDataMat[:,0], y=datingDataMat[:,1], color=LabelsColors,s=15, alpha=.5)#設(shè)置標題,x軸label,y軸labelaxs0_title_text = axs[0][0].set_title(u'每年獲得的飛行常客里程數(shù)與玩視頻游戲所消耗時間占比',FontProperties=font)axs0_xlabel_text = axs[0][0].set_xlabel(u'每年獲得的飛行常客里程數(shù)',FontProperties=font)axs0_ylabel_text = axs[0][0].set_ylabel(u'玩視頻游戲所消耗時間占',FontProperties=font)plt.setp(axs0_title_text, size=9, weight='bold', color='red')plt.setp(axs0_xlabel_text, size=7, weight='bold', color='black')plt.setp(axs0_ylabel_text, size=7, weight='bold', color='black')#畫出散點圖,以datingDataMat矩陣的第一(飛行常客例程)、第三列(冰激凌)數(shù)據(jù)畫散點數(shù)據(jù),散點大小為15,透明度為0.5axs[0][1].scatter(x=datingDataMat[:,0], y=datingDataMat[:,2], color=LabelsColors,s=15, alpha=.5)#設(shè)置標題,x軸label,y軸labelaxs1_title_text = axs[0][1].set_title(u'每年獲得的飛行常客里程數(shù)與每周消費的冰激淋公升數(shù)',FontProperties=font)axs1_xlabel_text = axs[0][1].set_xlabel(u'每年獲得的飛行常客里程數(shù)',FontProperties=font)axs1_ylabel_text = axs[0][1].set_ylabel(u'每周消費的冰激淋公升數(shù)',FontProperties=font)plt.setp(axs1_title_text, size=9, weight='bold', color='red')plt.setp(axs1_xlabel_text, size=7, weight='bold', color='black')plt.setp(axs1_ylabel_text, size=7, weight='bold', color='black')#畫出散點圖,以datingDataMat矩陣的第二(玩游戲)、第三列(冰激凌)數(shù)據(jù)畫散點數(shù)據(jù),散點大小為15,透明度為0.5axs[1][0].scatter(x=datingDataMat[:,1], y=datingDataMat[:,2], color=LabelsColors,s=15, alpha=.5)#設(shè)置標題,x軸label,y軸labelaxs2_title_text = axs[1][0].set_title(u'玩視頻游戲所消耗時間占比與每周消費的冰激淋公升數(shù)',FontProperties=font)axs2_xlabel_text = axs[1][0].set_xlabel(u'玩視頻游戲所消耗時間占比',FontProperties=font)axs2_ylabel_text = axs[1][0].set_ylabel(u'每周消費的冰激淋公升數(shù)',FontProperties=font)plt.setp(axs2_title_text, size=9, weight='bold', color='red')plt.setp(axs2_xlabel_text, size=7, weight='bold', color='black')plt.setp(axs2_ylabel_text, size=7, weight='bold', color='black')#設(shè)置圖例didntLike = mlines.Line2D([], [], color='black', marker='.',markersize=6, label='didntLike')smallDoses = mlines.Line2D([], [], color='orange', marker='.',markersize=6, label='smallDoses')largeDoses = mlines.Line2D([], [], color='red', marker='.',markersize=6, label='largeDoses')#添加圖例axs[0][0].legend(handles=[didntLike,smallDoses,largeDoses])axs[0][1].legend(handles=[didntLike,smallDoses,largeDoses])axs[1][0].legend(handles=[didntLike,smallDoses,largeDoses])#顯示圖片plt.show()""" 函數(shù)說明:main函數(shù)Parameters:無 Returns:無Modify:2018-03-09 """ if __name__ == '__main__':#打開的文件名filename = "datingTestSet.txt"#打開并處理數(shù)據(jù)datingDataMat, datingLabels = file2matrix(filename)showdatas(datingDataMat, datingLabels)

2.2.3 準備數(shù)據(jù)：歸一化數(shù)值

表2-3給出了提取的四組數(shù)據(jù)，如果想要計算樣本3和4之間的距離，可以使用下面的方法：
$$\sqrt{(0?67{)}^2+(20000?32000{)}^2+(1.1?0.1{)}^2}$$

但是式中差值最大的屬性對計算結(jié)果的影響最大，也就是該特征對結(jié)果的影響遠遠超過了其他的兩種，所以要使用一種方法使得該三種特征同等重要，所以采用歸一化的方式來處理。

• 歸一化 newValue=(oldValue-min)/(max-min)
  其中min和max分別是數(shù)據(jù)集中的最小特征值和最大特征值。雖然改變數(shù)值取值范圍增加了分類器的復(fù)雜度，但為了得到準確結(jié)果，我們必須這樣做。在kNN_test2.py文件中編寫名為autoNorm的函數(shù)，用該函數(shù)自動將數(shù)據(jù)歸一化。代碼如下：

import numpy as np""" 函數(shù)說明:打開并解析文件，對數(shù)據(jù)進行分類：1代表不喜歡,2代表魅力一般,3代表極具魅力Parameters:filename - 文件名 Returns:returnMat - 特征矩陣classLabelVector - 分類Label向量Modify:2018-03-09 """ def file2matrix(filename):#打開文件fr = open(filename)#讀取文件所有內(nèi)容arrayOLines = fr.readlines()#得到文件行數(shù)numberOfLines = len(arrayOLines)#返回的NumPy矩陣,解析完成的數(shù)據(jù):numberOfLines行,3列returnMat = np.zeros((numberOfLines,3))#返回的分類標簽向量classLabelVector = []#行的索引值index = 0for line in arrayOLines:#s.strip(rm)，當(dāng)rm空時,默認刪除空白符(包括'\n','\r','\t',' ')line = line.strip()#使用s.split(str="",num=string,cout(str))將字符串根據(jù)'\t'分隔符進行切片。listFromLine = line.split('\t')#將數(shù)據(jù)前三列提取出來,存放到returnMat的NumPy矩陣中,也就是特征矩陣returnMat[index,:] = listFromLine[0:3]#根據(jù)文本中標記的喜歡的程度進行分類,1代表不喜歡,2代表魅力一般,3代表極具魅力if listFromLine[-1] == 'didntLike':classLabelVector.append(1)elif listFromLine[-1] == 'smallDoses':classLabelVector.append(2)elif listFromLine[-1] == 'largeDoses':classLabelVector.append(3)index += 1return returnMat, classLabelVector""" 函數(shù)說明:對數(shù)據(jù)進行歸一化Parameters:dataSet - 特征矩陣 Returns:normDataSet - 歸一化后的特征矩陣ranges - 數(shù)據(jù)范圍minVals - 數(shù)據(jù)最小值Modify:2018-03-09 """ def autoNorm(dataSet):#獲得數(shù)據(jù)的最小值minVals = dataSet.min(0)maxVals = dataSet.max(0)#最大值和最小值的范圍ranges = maxVals - minVals#shape(dataSet)返回dataSet的矩陣行列數(shù)normDataSet = np.zeros(np.shape(dataSet))#返回dataSet的行數(shù)m = dataSet.shape[0]#原始值減去最小值normDataSet = dataSet - np.tile(minVals, (m, 1))#除以最大和最小值的差,得到歸一化數(shù)據(jù)normDataSet = normDataSet / np.tile(ranges, (m, 1))#返回歸一化數(shù)據(jù)結(jié)果,數(shù)據(jù)范圍,最小值return normDataSet, ranges, minVals""" 函數(shù)說明:main函數(shù)Parameters:無 Returns:無Modify:2018-03-09 """ if __name__ == '__main__':#打開的文件名filename = "datingTestSet.txt"#打開并處理數(shù)據(jù)datingDataMat, datingLabels = file2matrix(filename)normDataSet, ranges, minVals = autoNorm(datingDataMat)print(normDataSet)print(ranges)print(minVals)

2.2.4 測試算法：作為完整程序驗證分類器

機器學(xué)習(xí)算法一個很重要的工作就是評估算法的正確率，通常我們只提供已有數(shù)據(jù)的90%作為訓(xùn)練樣本來訓(xùn)練分類器，而使用其余的10%數(shù)據(jù)去測試分類器，檢測分類器的正確率。需要注意的是，10%的測試數(shù)據(jù)應(yīng)該是隨機選擇的，由于海倫提供的數(shù)據(jù)并沒有按照特定目的來排序，所以我么你可以隨意選擇10%數(shù)據(jù)而不影響其隨機性。
為了測試分類器效果，在kNN_test2.py文件中創(chuàng)建函數(shù)datingClassTest，編寫代碼如下：

import numpy as np import operator""" 函數(shù)說明:kNN算法,分類器Parameters:inX - 用于分類的數(shù)據(jù)(測試集)dataSet - 用于訓(xùn)練的數(shù)據(jù)(訓(xùn)練集)labes - 分類標簽k - kNN算法參數(shù),選擇距離最小的k個點 Returns:sortedClassCount[0][0] - 分類結(jié)果Modify:2018-03-09 """ def classify0(inX, dataSet, labels, k):#numpy函數(shù)shape[0]返回dataSet的行數(shù)dataSetSize = dataSet.shape[0]#在列向量方向上重復(fù)inX共1次(橫向),行向量方向上重復(fù)inX共dataSetSize次(縱向)diffMat = np.tile(inX, (dataSetSize, 1)) - dataSet#二維特征相減后平方sqDiffMat = diffMat**2#sum()所有元素相加,sum(0)列相加,sum(1)行相加sqDistances = sqDiffMat.sum(axis=1)#開方,計算出距離distances = sqDistances**0.5#返回distances中元素從小到大排序后的索引值sortedDistIndices = distances.argsort()#定一個記錄類別次數(shù)的字典classCount = {}for i in range(k):#取出前k個元素的類別voteIlabel = labels[sortedDistIndices[i]]#dict.get(key,default=None),字典的get()方法,返回指定鍵的值,如果值不在字典中返回默認值。#計算類別次數(shù)classCount[voteIlabel] = classCount.get(voteIlabel,0) + 1#python3中用items()替換python2中的iteritems()#key=operator.itemgetter(1)根據(jù)字典的值進行排序#key=operator.itemgetter(0)根據(jù)字典的鍵進行排序#reverse降序排序字典sortedClassCount = sorted(classCount.items(),key=operator.itemgetter(1),reverse=True)#返回次數(shù)最多的類別,即所要分類的類別return sortedClassCount[0][0]""" 函數(shù)說明:打開并解析文件，對數(shù)據(jù)進行分類：1代表不喜歡,2代表魅力一般,3代表極具魅力Parameters:filename - 文件名 Returns:returnMat - 特征矩陣classLabelVector - 分類Label向量Modify:2018-03-09 """ def file2matrix(filename):#打開文件fr = open(filename)#讀取文件所有內(nèi)容arrayOLines = fr.readlines()#得到文件行數(shù)numberOfLines = len(arrayOLines)#返回的NumPy矩陣,解析完成的數(shù)據(jù):numberOfLines行,3列returnMat = np.zeros((numberOfLines,3))#返回的分類標簽向量classLabelVector = []#行的索引值index = 0for line in arrayOLines:#s.strip(rm)，當(dāng)rm空時,默認刪除空白符(包括'\n','\r','\t',' ')line = line.strip()#使用s.split(str="",num=string,cout(str))將字符串根據(jù)'\t'分隔符進行切片。listFromLine = line.split('\t')#將數(shù)據(jù)前三列提取出來,存放到returnMat的NumPy矩陣中,也就是特征矩陣returnMat[index,:] = listFromLine[0:3]#根據(jù)文本中標記的喜歡的程度進行分類,1代表不喜歡,2代表魅力一般,3代表極具魅力if listFromLine[-1] == 'didntLike':classLabelVector.append(1)elif listFromLine[-1] == 'smallDoses':classLabelVector.append(2)elif listFromLine[-1] == 'largeDoses':classLabelVector.append(3)index += 1return returnMat, classLabelVector""" 函數(shù)說明:對數(shù)據(jù)進行歸一化Parameters:dataSet - 特征矩陣 Returns:normDataSet - 歸一化后的特征矩陣ranges - 數(shù)據(jù)范圍minVals - 數(shù)據(jù)最小值Modify:2018-03-09 """ def autoNorm(dataSet):#獲得數(shù)據(jù)的最小值minVals = dataSet.min(0)maxVals = dataSet.max(0)#最大值和最小值的范圍ranges = maxVals - minVals#shape(dataSet)返回dataSet的矩陣行列數(shù)normDataSet = np.zeros(np.shape(dataSet))#返回dataSet的行數(shù)m = dataSet.shape[0]#原始值減去最小值normDataSet = dataSet - np.tile(minVals, (m, 1))#除以最大和最小值的差,得到歸一化數(shù)據(jù)normDataSet = normDataSet / np.tile(ranges, (m, 1))#返回歸一化數(shù)據(jù)結(jié)果,數(shù)據(jù)范圍,最小值return normDataSet, ranges, minVals""" 函數(shù)說明:分類器測試函數(shù)Parameters:無 Returns:normDataSet - 歸一化后的特征矩陣ranges - 數(shù)據(jù)范圍minVals - 數(shù)據(jù)最小值Modify:2018-03-09 """ def datingClassTest():#打開的文件名filename = "datingTestSet.txt"#將返回的特征矩陣和分類向量分別存儲到datingDataMat和datingLabels中datingDataMat, datingLabels = file2matrix(filename)#取所有數(shù)據(jù)的百分之十hoRatio = 0.10#數(shù)據(jù)歸一化,返回歸一化后的矩陣,數(shù)據(jù)范圍,數(shù)據(jù)最小值normMat, ranges, minVals = autoNorm(datingDataMat)#獲得normMat的行數(shù)m = normMat.shape[0]#百分之十的測試數(shù)據(jù)的個數(shù)numTestVecs = int(m * hoRatio)#分類錯誤計數(shù)errorCount = 0.0for i in range(numTestVecs):#前numTestVecs個數(shù)據(jù)作為測試集,后m-numTestVecs個數(shù)據(jù)作為訓(xùn)練集classifierResult = classify0(normMat[i,:], normMat[numTestVecs:m,:],datingLabels[numTestVecs:m], 4)print("分類結(jié)果:%d\t真實類別:%d" % (classifierResult, datingLabels[i]))if classifierResult != datingLabels[i]:errorCount += 1.0print("錯誤率:%f%%" %(errorCount/float(numTestVecs)*100))""" 函數(shù)說明:main函數(shù)Parameters:無 Returns:無Modify:2018-03-09 """ if __name__ == '__main__':datingClassTest()

從圖2.6驗證分類器結(jié)果中可以看出，錯誤率是3%。我們可以改變函數(shù)datingClassTest內(nèi)變量hoRatio和分類器k的值，檢測錯誤率是否隨著變量值的變化而增加。依賴于分類算法、數(shù)據(jù)集和程序設(shè)置，分類器的輸出結(jié)果可能有很大的不同。

2.2.5 使用算法：構(gòu)建完整可用系統(tǒng)

我們可以給海倫一個小段程序，通過該程序海倫會在約會網(wǎng)站上找到某個人并輸入他的信息。程序會給出她對男方喜歡程度的預(yù)測值。

在kNN_test2.py文件中創(chuàng)建函數(shù)classifyPerson，代碼如下：

import numpy as np import operator""" 函數(shù)說明:kNN算法,分類器Parameters:inX - 用于分類的數(shù)據(jù)(測試集)dataSet - 用于訓(xùn)練的數(shù)據(jù)(訓(xùn)練集)labels - 分類標簽k - kNN算法參數(shù),選擇距離最小的k個點 Returns:sortedClassCount[0][0] - 分類結(jié)果Modify:2018-03-09 """ def classify0(inX, dataSet, labels, k):#numpy函數(shù)shape[0]返回dataSet的行數(shù)dataSetSize = dataSet.shape[0]#在列向量方向上重復(fù)inX共1次(橫向),行向量方向上重復(fù)inX共dataSetSize次(縱向)diffMat = np.tile(inX, (dataSetSize, 1)) - dataSet#二維特征相減后平方sqDiffMat = diffMat**2#sum()所有元素相加,sum(0)列相加,sum(1)行相加sqDistances = sqDiffMat.sum(axis=1)#開方,計算出距離distances = sqDistances**0.5#返回distances中元素從小到大排序后的索引值sortedDistIndices = distances.argsort()#定一個記錄類別次數(shù)的字典classCount = {}for i in range(k):#取出前k個元素的類別voteIlabel = labels[sortedDistIndices[i]]#dict.get(key,default=None),字典的get()方法,返回指定鍵的值,如果值不在字典中返回默認值。#計算類別次數(shù)classCount[voteIlabel] = classCount.get(voteIlabel,0) + 1#python3中用items()替換python2中的iteritems()#key=operator.itemgetter(1)根據(jù)字典的值進行排序#key=operator.itemgetter(0)根據(jù)字典的鍵進行排序#reverse降序排序字典sortedClassCount = sorted(classCount.items(),key=operator.itemgetter(1),reverse=True)#返回次數(shù)最多的類別,即所要分類的類別return sortedClassCount[0][0]""" 函數(shù)說明:打開并解析文件，對數(shù)據(jù)進行分類：1代表不喜歡,2代表魅力一般,3代表極具魅力Parameters:filename - 文件名 Returns:returnMat - 特征矩陣classLabelVector - 分類Label向量Modify:2018-03-09 """ def file2matrix(filename):#打開文件fr = open(filename)#讀取文件所有內(nèi)容arrayOLines = fr.readlines()#得到文件行數(shù)numberOfLines = len(arrayOLines)#返回的NumPy矩陣,解析完成的數(shù)據(jù):numberOfLines行,3列returnMat = np.zeros((numberOfLines,3))#返回的分類標簽向量classLabelVector = []#行的索引值index = 0for line in arrayOLines:#s.strip(rm)，當(dāng)rm空時,默認刪除空白符(包括'\n','\r','\t',' ')line = line.strip()#使用s.split(str="",num=string,cout(str))將字符串根據(jù)'\t'分隔符進行切片。listFromLine = line.split('\t')#將數(shù)據(jù)前三列提取出來,存放到returnMat的NumPy矩陣中,也就是特征矩陣returnMat[index,:] = listFromLine[0:3]#根據(jù)文本中標記的喜歡的程度進行分類,1代表不喜歡,2代表魅力一般,3代表極具魅力if listFromLine[-1] == 'didntLike':classLabelVector.append(1)elif listFromLine[-1] == 'smallDoses':classLabelVector.append(2)elif listFromLine[-1] == 'largeDoses':classLabelVector.append(3)index += 1return returnMat, classLabelVector""" 函數(shù)說明:對數(shù)據(jù)進行歸一化Parameters:dataSet - 特征矩陣 Returns:normDataSet - 歸一化后的特征矩陣ranges - 數(shù)據(jù)范圍minVals - 數(shù)據(jù)最小值Modify:2018-03-09 """ def autoNorm(dataSet):#獲得數(shù)據(jù)的最小值minVals = dataSet.min(0)maxVals = dataSet.max(0)#最大值和最小值的范圍ranges = maxVals - minVals#shape(dataSet)返回dataSet的矩陣行列數(shù)normDataSet = np.zeros(np.shape(dataSet))#返回dataSet的行數(shù)m = dataSet.shape[0]#原始值減去最小值normDataSet = dataSet - np.tile(minVals, (m, 1))#除以最大和最小值的差,得到歸一化數(shù)據(jù)normDataSet = normDataSet / np.tile(ranges, (m, 1))#返回歸一化數(shù)據(jù)結(jié)果,數(shù)據(jù)范圍,最小值return normDataSet, ranges, minVals""" 函數(shù)說明:通過輸入一個人的三維特征,進行分類輸出Parameters:無 Returns:無Modify:2018-03-09 """ def classifyPerson():#輸出結(jié)果resultList = ['討厭','有些喜歡','非常喜歡']#三維特征用戶輸入precentTats = float(input("玩視頻游戲所耗時間百分比:"))ffMiles = float(input("每年獲得的飛行常客里程數(shù):"))iceCream = float(input("每周消費的冰激淋公升數(shù):"))#打開的文件名filename = "datingTestSet.txt"#打開并處理數(shù)據(jù)datingDataMat, datingLabels = file2matrix(filename)#訓(xùn)練集歸一化normMat, ranges, minVals = autoNorm(datingDataMat)#生成NumPy數(shù)組,測試集inArr = np.array([precentTats, ffMiles, iceCream])#測試集歸一化norminArr = (inArr - minVals) / ranges#返回分類結(jié)果classifierResult = classify0(norminArr, normMat, datingLabels, 3)#打印結(jié)果print("你可能%s這個人" % (resultList[classifierResult-1]))""" 函數(shù)說明:main函數(shù)Parameters:無 Returns:無Modify:2018-03-09 """ if __name__ == '__main__':classifyPerson()

2.3 手寫識別系統(tǒng)

預(yù)處理：32*32的黑白圖像
盡管采用本文格式存儲圖像不能有效地利用內(nèi)存空間，但是為了方便理解，我們將圖片轉(zhuǎn)換為文本格式，數(shù)字的文本格式如圖所示。

步驟：
1）收集數(shù)據(jù)：提供文本文件
2）準備數(shù)據(jù)：編寫函數(shù)classify0()，將圖像格式轉(zhuǎn)換為分類器使用的list格式
3）分析數(shù)據(jù)：在python命令提示符中檢查數(shù)據(jù)，確保它符合要求
4）訓(xùn)練算法：此步驟不適合于k-近鄰分類器
5）測試算法：使用提供的部分數(shù)據(jù)集作為測試樣本，測試與非測試樣本的區(qū)別在于測試樣本是已經(jīng)完成分類的數(shù)據(jù)，如果預(yù)測與實際的不同，則標記為一個錯誤。
6）使用算法：可以從圖像中提取數(shù)字，并完成數(shù)字識別。

2.3.1 準備數(shù)據(jù)：將圖像轉(zhuǎn)化為測試向量

對于這樣已經(jīng)整理好的文本，我們可以直接使用Python處理，進行數(shù)字預(yù)測。數(shù)據(jù)集分為訓(xùn)練集和測試集，使用上小結(jié)的方法，自己設(shè)計k-近鄰算法分類器，可以實現(xiàn)分類。

為了使用前面的分類器，必須將圖像格式化處理為也向量，我們將把一個32 * 32的二進制圖像矩陣轉(zhuǎn)換為1*1024的向量。代碼如下：

def img2vector(filename):returnVect =zeros((1,1024))fr=open(filename)for i in range(32):lineSrt=fr.readline()for j in range(32):returnVect[0,32*i+j]=int(lineStr[j])return returnVect

2.3.2 使用sklearn實現(xiàn)手寫體識別

Scikit learn 也簡稱sklearn，是機器學(xué)習(xí)領(lǐng)域當(dāng)中最知名的python模塊之一。sklearn包含了很多機器學(xué)習(xí)的方式：

• Classification 分類
• Regression 回歸
• Clustering 非監(jiān)督分類
• Dimensionality reduction 數(shù)據(jù)降維
• Model Selection 模型選擇
• Preprocessing 數(shù)據(jù)與處理

使用sklearn可以很方便地讓我們實現(xiàn)一個機器學(xué)習(xí)算法。一個復(fù)雜度算法的實現(xiàn)，使用sklearn可能只需要調(diào)用幾行API即可。所以學(xué)習(xí)sklearn，可以有效減少我們特定任務(wù)的實現(xiàn)周期。
sklearn實現(xiàn)k-近鄰算法官網(wǎng)介紹

class sklearn.neighbors.KNeighborsClassifier(n_neighbors=5, weights=’uniform’, algorithm=’auto’, leaf_size=30, p=2, metric=’minkowski’, metric_params=None, n_jobs=1, **kwargs) Parameters: n_neighbors : int, optional (default = 5) Number of neighbors to use by default for kneighbors queries. 默認為5，就是k-NN的k的值，選取最近的k個點。weights : str or callable, optional (default = ‘uniform’) weight function used in prediction. Possible values:‘uniform’ : uniform weights. All points in each neighborhood are weighted equally.‘distance’ : weight points by the inverse of their distance. in this case, closer neighbors of a query point will have a greater influence than neighbors which are further away.[callable] : a user-defined function which accepts an array of distances, and returns an array of the same shape containing the weights.默認是uniform，參數(shù)可以是uniform、distance，也可以是用戶自己定義的函數(shù)。uniform是均等的權(quán)重，就說所有的鄰近點的權(quán)重都是相等的。distance是不均等的權(quán)重，距離近的點比距離遠的點的影響大。用戶自定義的函數(shù)，接收距離的數(shù)組，返回一組維數(shù)相同的權(quán)重。algorithm : {‘a(chǎn)uto’, ‘ball_tree’, ‘kd_tree’, ‘brute’}, optional Algorithm used to compute the nearest neighbors: ‘ball_tree’ will use BallTree ‘kd_tree’ will use KDTree ‘brute’ will use a brute-force search. ‘a(chǎn)uto’ will attempt to decide the most appropriate algorithm based on the values passed to fit method. Note: fitting on sparse input will override the setting of this parameter, using brute force.快速k近鄰搜索算法，默認參數(shù)為auto，可以理解為算法自己決定合適的搜索算法。除此之外，用戶也可以自己指定搜索算法ball_tree、kd_tree、brute方法進行搜索，brute是蠻力搜索，也就是線性掃描，當(dāng)訓(xùn)練集很大時，計算非常耗時。kd_tree，構(gòu)造kd樹存儲數(shù)據(jù)以便對其進行快速檢索的樹形數(shù)據(jù)結(jié)構(gòu)，kd樹也就是數(shù)據(jù)結(jié)構(gòu)中的二叉樹。以中值切分構(gòu)造的樹，每個結(jié)點是一個超矩形，在維數(shù)小于20時效率高。ball tree是為了克服kd樹高緯失效而發(fā)明的，其構(gòu)造過程是以質(zhì)心C和半徑r分割樣本空間，每個節(jié)點是一個超球體。leaf_size : int, optional (default = 30) Leaf size passed to BallTree or KDTree. This can affect the speed of the construction and query, as well as the memory required to store the tree. The optimal value depends on the nature of the problem.默認是30，這個是構(gòu)造的kd樹和ball樹的大小。這個值的設(shè)置會影響樹構(gòu)建的速度和搜索速度，同樣也影響著存儲樹所需的內(nèi)存大小。需要根據(jù)問題的性質(zhì)選擇最優(yōu)的大小。p : integer, optional (default = 2) Power parameter for the Minkowski metric. When p = 1, this is equivalent to using manhattan_distance (l1), and euclidean_distance (l2) for p = 2. For arbitrary p, minkowski_distance (l_p) is used.距離度量公式。在上小結(jié)，我們使用歐氏距離公式進行距離度量。除此之外，還有其他的度量方法，例如曼哈頓距離。這個參數(shù)默認為2，也就是默認使用歐式距離公式進行距離度量。也可以設(shè)置為1，使用曼哈頓距離公式進行距離度量。metric : string or callable, default ‘minkowski’ the distance metric to use for the tree. The default metric is minkowski, and with p=2 is equivalent to the standard Euclidean metric. See the documentation of the DistanceMetric class for a list of available metrics.用于距離度量，默認度量是minkowski，也就是p=2的歐氏距離(歐幾里德度量)。metric_params : dict, optional (default = None) Additional keyword arguments for the metric function.距離公式的其他關(guān)鍵參數(shù)，這個可以不管，使用默認的None即可。n_jobs : int, optional (default = 1) The number of parallel jobs to run for neighbors search. If -1, then the number of jobs is set to the number of CPU cores. Doesn’t affect fit method.并行處理設(shè)置。默認為1，臨近點搜索并行工作數(shù)。如果為-1，那么CPU的所有cores都用于并行工作。

KNeighborsClassifier提供了以一些方法供我們使用：

k-近鄰實現(xiàn)手寫體分類程序：

import numpy as np import operator from os import listdir from sklearn.neighbors import KNeighborsClassifier as KNN""" 函數(shù)說明：將32*32的二進制圖像轉(zhuǎn)化為1*1024的向量 Parameters：filename：文件名 Returns：returnVect：返回的二進制圖像的1024向量 Modify：2018-03-12"""def img2Vector(filename):# 創(chuàng)建1*1024零向量returnVect = np.zeros((1, 1024))# 打開文件fr = open(filename)# 按行讀取for i in range(32):# 讀取一行數(shù)據(jù)lineStr = fr.readline()# 每一行的前32個元素依次添加到returnVect中for j in range(32):returnVect[0, 32 * i + j] = int(lineStr[j])return returnVect""" 函數(shù)說明：手寫體數(shù)字分類Parameters：filename：無 Returns：無 Modify：2018-03-12"""def handwritingClassTest():# 測試集的labelshwLabels = []# 返回trainingDigits目錄下的文件名trainingFileList = listdir('trainingDigits')# 返回文件夾下文件的個數(shù)m = len(trainingFileList)# 初始化訓(xùn)練的Mat矩陣，測試集trainingMat = np.zeros((m, 1024))# 從文件名中解析出訓(xùn)練集的類別for i in range(m):# 獲得文件的名字fileNameStr = trainingFileList[i]# 獲得分類的數(shù)字classNumber = int(fileNameStr.split('_')[0])# 將獲得的類別添加到hwLabels中hwLabels.append(classNumber)# 將每一個文件的1*1024數(shù)據(jù)存儲到traingingMat矩陣中trainingMat[i, :] = img2Vector('E:/python/machine learning in action/My Code/chap 02/trainingDigits/%s' % (fileNameStr))# 構(gòu)建KNN分類器neigh = KNN(n_neighbors=3, algorithm='auto')# 擬合模型，trainingMat為測試矩陣，hwLabels為對應(yīng)的標簽neigh.fit(trainingMat, hwLabels)# 返回testDigirs目錄下的文件列表testFileList = listdir('testDigits')# 錯誤檢測計數(shù)errorCount = 0.0# 測試數(shù)據(jù)的數(shù)量mTest = len(testFileList)# 從文件中解析出測試集的類別并進行分類測試for i in range(mTest):# 獲得文件的名字fileNameStr = testFileList[i]# 獲得分類的數(shù)字classNumber = int(fileNameStr.split('_')[0])# 獲得測試集的1*1024向量，用于訓(xùn)練vectorUnderTest = img2Vector('testDigits/%s' % (fileNameStr))# 獲得預(yù)測結(jié)果classifierResult = neigh.predict(vectorUnderTest)print("分類返回結(jié)果為%d\t真實結(jié)果為%d" % (classifierResult, classNumber))if (classifierResult != classNumber):errorCount += 1.0print("共錯誤數(shù)據(jù)為%d，錯誤率為%f%%" % (errorCount, errorCount / mTest * 100))""" 函數(shù)說明：main函數(shù)Parameters：無 Returns：無 Modify：2018-03-12""" if __name__ == '__main__':handwritingClassTest()

結(jié)果：

還可以通過修改程序中的參數(shù)來修改不同的距離度量方法和精度等。

2.4 KNN算法的優(yōu)缺點

2.4.1 優(yōu)點

• 簡單好用，容易理解，精度高，理論成熟，既可以用來做分類也可以用來做回歸；
• 可用于數(shù)值型數(shù)據(jù)和離散型數(shù)據(jù)；
• 訓(xùn)練時間復(fù)雜度為O(n)；無數(shù)據(jù)輸入假定；
• 對異常值不敏感。

2.4.2 缺點：

• 計算復(fù)雜性高；空間復(fù)雜性高；
• 樣本不平衡問題（即有些類別的樣本數(shù)量很多，而其它樣本的數(shù)量很少）；
• 一般數(shù)值很大的時候不用這個，計算量太大。但是單個樣本又不能太少，否則容易發(fā)生誤分。
• 最大的缺點是無法給出數(shù)據(jù)的內(nèi)在含義。

總結(jié)

以上是生活随笔為你收集整理的机器学习实战（二）——k-近邻算法的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。