Python3《機器學習實戰》學習筆記(一):k-近鄰演算法(史詩級乾貨長文)
轉載請註明作者和出處:https://zhuanlan.zhihu.com/ml-jack
CSDN同步更新地址:http://blog.csdn.net/c406495762/article/details/75172850
Github代碼獲取:https://github.com/Jack-Cherish/Machine-Learning/
Python版本: Python3.x
運行平台: Windows
IDE: Sublime text3
一、簡單k-近鄰演算法
本文將從k-近鄰演算法的思想開始講起,使用python3一步一步編寫代碼進行實戰訓練。並且,我也提供了相應的數據集,對代碼進行了詳細的注釋。除此之外,本文也對sklearn實現k-近鄰演算法的方法進行了講解。實戰實例:電影類別分類、約會網站配對效果判定、手寫數字識別。
本文出現的所有代碼和數據集,均可在我的github上下載,歡迎Follow、Star:https://github.com/Jack-Cherish/Machine-Learning/tree/master/kNN
如果對於代碼理解不夠的,可以結合本文,觀看由南京航空航天大學碩士:深度眸,為大家免費錄製的視頻:
- 視頻:http://pan.baidu.com/s/1i55VVM1 密碼:qllk
- 視頻交流群:ML與DL視頻分享群(678455658),歡迎提出寶貴意見。
1、k-近鄰法簡介
k近鄰法(k-nearest neighbor, k-NN)是1967年由Cover T和Hart P提出的一種基本分類與回歸方法。它的工作原理是:存在一個樣本數據集合,也稱作為訓練樣本集,並且樣本集中每個數據都存在標籤,即我們知道樣本集中每一個數據與所屬分類的對應關係。輸入沒有標籤的新數據後,將新的數據的每個特徵與樣本集中數據對應的特徵進行比較,然後演算法提取樣本最相似數據(最近鄰)的分類標籤。一般來說,我們只選擇樣本數據集中前k個最相似的數據,這就是k-近鄰演算法中k的出處,通常k是不大於20的整數。最後,選擇k個最相似數據中出現次數最多的分類,作為新數據的分類。
舉個簡單的例子,我們可以使用k-近鄰演算法分類一個電影是愛情片還是動作片。
表1.1 每部電影的打鬥鏡頭數、接吻鏡頭數以及電影類型
表1.1 就是我們已有的數據集合,也就是訓練樣本集。這個數據集有兩個特徵,即打鬥鏡頭數和接吻鏡頭數。除此之外,我們也知道每個電影的所屬類型,即分類標籤。用肉眼粗略地觀察,接吻鏡頭多的,是愛情片。打鬥鏡頭多的,是動作片。以我們多年的看片經驗,這個分類還算合理。如果現在給我一部電影,你告訴我這個電影打鬥鏡頭數和接吻鏡頭數。不告訴我這個電影類型,我可以根據你給我的信息進行判斷,這個電影是屬於愛情片還是動作片。而k-近鄰演算法也可以像我們人一樣做到這一點,不同的地方在於,我們的經驗更"牛逼",而k-近鄰演算法是靠已有的數據。比如,你告訴我這個電影打鬥鏡頭數為2,接吻鏡頭數為102,我的經驗會告訴你這個是愛情片,k-近鄰演算法也會告訴你這個是愛情片。你又告訴我另一個電影打鬥鏡頭數為49,接吻鏡頭數為51,我"邪惡"的經驗可能會告訴你,這有可能是個"愛情動作片",畫面太美,我不敢想像。 (如果說,你不知道"愛情動作片"是什麼?請評論留言與我聯繫,我需要你這樣像我一樣純潔的朋友。) 但是k-近鄰演算法不會告訴你這些,因為在它的眼裡,電影類型只有愛情片和動作片,它會提取樣本集中特徵最相似數據(最鄰近)的分類標籤,得到的結果可能是愛情片,也可能是動作片,但絕不會是"愛情動作片"。當然,這些取決於數據集的大小以及最近鄰的判斷標準等因素。
2、距離度量
我們已經知道k-近鄰演算法根據特徵比較,然後提取樣本集中特徵最相似數據(最鄰近)的分類標籤。那麼,如何進行比較呢?比如,我們還是以表1.1為例,怎麼判斷紅色圓點標記的電影所屬的類別呢? 如圖1.1所示。
圖1.1 電影分類
我們可以從散點圖大致推斷,這個紅色圓點標記的電影可能屬於動作片,因為距離已知的那兩個動作片的圓點更近。k-近鄰演算法用什麼方法進行判斷呢?沒錯,就是距離度量。這個電影分類的例子有2個特徵,也就是在2維實數向量空間,可以使用我們高中學過的兩點距離公式計算距離,如圖1.2所示。
通過計算,我們可以得到如下結果:
- (101,20)->動作片(108,5)的距離約為16.55
- (101,20)->動作片(115,8)的距離約為18.44
- (101,20)->愛情片(5,89)的距離約為118.22
- (101,20)->愛情片(1,101)的距離約為128.69
通過計算可知,紅色圓點標記的電影到動作片 (108,5)的距離最近,為16.55。如果演算法直接根據這個結果,判斷該紅色圓點標記的電影為動作片,這個演算法就是最近鄰演算法,而非k-近鄰演算法。那麼k-近鄰演算法是什麼呢?k-近鄰演算法步驟如下:
- 計算已知類別數據集中的點與當前點之間的距離;
- 按照距離遞增次序排序;
- 選取與當前點距離最小的k個點;
- 確定前k個點所在類別的出現頻率;
- 返回前k個點所出現頻率最高的類別作為當前點的預測分類。
比如,現在我這個k值取3,那麼在電影例子中,按距離依次排序的三個點分別是動作片(108,5)、動作片(115,8)、愛情片(5,89)。在這三個點中,動作片出現的頻率為三分之二,愛情片出現的頻率為三分之一,所以該紅色圓點標記的電影為動作片。這個判別過程就是k-近鄰演算法。
3、Python3代碼實現
我們已經知道了k-近鄰演算法的原理,那麼接下來就是使用Python3實現該演算法,依然以電影分類為例。
(1)準備數據集
對於表1.1中的數據,我們可以使用numpy直接創建,代碼如下:
# -*- coding: UTF-8 -*-import numpy as np"""函數說明:創建數據集Parameters: 無Returns: group - 數據集 labels - 分類標籤Modify: 2017-07-13"""def createDataSet(): #四組二維特徵 group = np.array([[1,101],[5,89],[108,5],[115,8]]) #四組特徵的標籤 labels = ["愛情片","愛情片","動作片","動作片"] return group, labelsif __name__ == "__main__": #創建數據集 group, labels = createDataSet() #列印數據集 print(group) print(labels)
運行結果,如圖1.3所示:
圖1.3 運行結果
(2)k-近鄰演算法
根據兩點距離公式,計算距離,選擇距離最小的前k個點,並返回分類結果。
# -*- coding: UTF-8 -*-import numpy as npimport operator"""函數說明:創建數據集Parameters: 無Returns: group - 數據集 labels - 分類標籤Modify: 2017-07-13"""def createDataSet(): #四組二維特徵 group = np.array([[1,101],[5,89],[108,5],[115,8]]) #四組特徵的標籤 labels = ["愛情片","愛情片","動作片","動作片"] return group, labels"""函數說明:kNN演算法,分類器Parameters: inX - 用於分類的數據(測試集) dataSet - 用於訓練的數據(訓練集) labes - 分類標籤 k - kNN演算法參數,選擇距離最小的k個點Returns: sortedClassCount[0][0] - 分類結果Modify: 2017-07-13"""def classify0(inX, dataSet, labels, k): #numpy函數shape[0]返回dataSet的行數 dataSetSize = dataSet.shape[0] #在列向量方向上重複inX共1次(橫向),行向量方向上重複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() #定一個記錄類別次數的字典 classCount = {} for i in range(k): #取出前k個元素的類別 voteIlabel = labels[sortedDistIndices[i]] #dict.get(key,default=None),字典的get()方法,返回指定鍵的值,如果值不在字典中返回默認值。 #計算類別次數 classCount[voteIlabel] = classCount.get(voteIlabel,0) + 1 #python3中用items()替換python2中的iteritems() #key=operator.itemgetter(1)根據字典的值進行排序 #key=operator.itemgetter(0)根據字典的鍵進行排序 #reverse降序排序字典 sortedClassCount = sorted(classCount.items(),key=operator.itemgetter(1),reverse=True) #返回次數最多的類別,即所要分類的類別 return sortedClassCount[0][0]if __name__ == "__main__": #創建數據集 group, labels = createDataSet() #測試集 test = [101,20] #kNN分類 test_class = classify0(test, group, labels, 3) #列印分類結果 print(test_class)
運行結果,如圖1.4所示:
圖1.4 運行結果
可以看到,分類結果根據我們的"經驗",是正確的,儘管這種分類比較耗時,用時1.4s。
到這裡,也許有人早已經發現,電影例子中的特徵是2維的,這樣的距離度量可以用兩 點距離公式計算,但是如果是更高維的呢?對,沒錯。我們可以用歐氏距離(也稱歐幾里德度量),如圖1.5所示。我們高中所學的兩點距離公式就是歐氏距離在二維空間上的公式,也就是歐氏距離的n的值為2的情況。
圖1.5 歐氏距離公式
看到這裡,有人可能會問:「分類器何種情況下會出錯?」或者「答案是否總是正確的?」答案是否定的,分類器並不會得到百分百正確的結果,我們可以使用多種方法檢測分類器的正確率。此外分類器的性能也會受到多種因素的影響,如分類器設置和數據集等。不同的演算法在不同數據集上的表現可能完全不同。為了測試分類器的效果,我們可以使用已知答案的數據,當然答案不能告訴分類器,檢驗分類器給出的結果是否符合預期結果。通過大量的測試數據,我們可以得到分類器的錯誤率-分類器給出錯誤結果的次數除以測試執行的總數。錯誤率是常用的評估方法,主要用於評估分類器在某個數據集上的執行效果。完美分類器的錯誤率為0,最差分類器的錯誤率是1.0。同時,我們也不難發現,k-近鄰演算法沒有進行數據的訓練,直接使用未知的數據與已知的數據進行比較,得到結果。因此,可以說k-近鄰演算法不具有顯式的學習過程。
二、k-近鄰演算法實戰之約會網站配對效果判定
上一小結學習了簡單的k-近鄰演算法的實現方法,但是這並不是完整的k-近鄰演算法流程,k-近鄰演算法的一般流程:
- 收集數據:可以使用爬蟲進行數據的收集,也可以使用第三方提供的免費或收費的數據。一般來講,數據放在txt文本文件中,按照一定的格式進行存儲,便於解析及處理。
- 準備數據:使用Python解析、預處理數據。
- 分析數據:可以使用很多方法對數據進行分析,例如使用Matplotlib將數據可視化。
- 測試演算法:計算錯誤率。
- 使用演算法:錯誤率在可接受範圍內,就可以運行k-近鄰演算法進行分類。
已經了解了k-近鄰演算法的一般流程,下面開始進入實戰內容。
1、實戰背景
海倫女士一直使用在線約會網站尋找適合自己的約會對象。儘管約會網站會推薦不同的任選,但她並不是喜歡每一個人。經過一番總結,她發現自己交往過的人可以進行如下分類:
- 不喜歡的人
- 魅力一般的人
- 極具魅力的人
海倫收集約會數據已經有了一段時間,她把這些數據存放在文本文件datingTestSet.txt中,每個樣本數據佔據一行,總共有1000行。datingTestSet.txt數據下載: https://github.com/Jack-Cherish/Machine-Learning/blob/master/kNN/2.%E6%B5%B7%E4%BC%A6%E7%BA%A6%E4%BC%9A/datingTestSet.txt
海倫收集的樣本數據主要包含以下3種特徵:
- 每年獲得的飛行常客里程數
- 玩視頻遊戲所消耗時間百分比
- 每周消費的冰淇淋公升數
這裡不得不吐槽一句,海倫是個小吃貨啊,冰淇淋公斤數都影響自己擇偶標準。打開txt文本文件,數據格式如圖2.1所示。
圖2.1 datingTestSet.txt格式
2、準備數據:數據解析
在將上述特徵數據輸入到分類器前,必須將待處理的數據的格式改變為分類器可以接收的格式。分類器接收的數據是什麼格式的?從上小結已經知道,要將數據分類兩部分,即特徵矩陣和對應的分類標籤向量。在kNN_test02.py文件中創建名為file2matrix的函數,以此來處理輸入格式問題。 將datingTestSet.txt放到與kNN_test02.py相同目錄下,編寫代碼如下:
# -*- coding: UTF-8 -*-import numpy as np"""函數說明:打開並解析文件,對數據進行分類:1代表不喜歡,2代表魅力一般,3代表極具魅力Parameters: filename - 文件名Returns: returnMat - 特徵矩陣 classLabelVector - 分類Label向量Modify: 2017-03-24"""def file2matrix(filename): #打開文件 fr = open(filename) #讀取文件所有內容 arrayOLines = fr.readlines() #得到文件行數 numberOfLines = len(arrayOLines) #返回的NumPy矩陣,解析完成的數據:numberOfLines行,3列 returnMat = np.zeros((numberOfLines,3)) #返回的分類標籤向量 classLabelVector = [] #行的索引值 index = 0 for line in arrayOLines: #s.strip(rm),當rm空時,默認刪除空白符(包括"
","
"," "," ") line = line.strip() #使用s.split(str="",num=string,cout(str))將字元串根據" "分隔符進行切片。 listFromLine = line.split(" ") #將數據前三列提取出來,存放到returnMat的NumPy矩陣中,也就是特徵矩陣 returnMat[index,:] = listFromLine[0:3] #根據文本中標記的喜歡的程度進行分類,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 += 1 return returnMat, classLabelVector"""函數說明:main函數Parameters: 無Returns: 無Modify: 2017-03-24"""if __name__ == "__main__": #打開的文件名 filename = "datingTestSet.txt" #打開並處理數據 datingDataMat, datingLabels = file2matrix(filename) print(datingDataMat) print(datingLabels)
運行上述代碼,得到的數據解析結果如圖2.2所示。
圖2.2 數據解析結果
可以看到,我們已經順利導入數據,並對數據進行解析,格式化為分類器需要的數據格式。接著我們需要了解數據的真正含義。可以通過友好、直觀的圖形化的方式觀察數據。
3、分析數據:數據可視化
在kNN_test02.py文件中編寫名為showdatas的函數,用來將數據可視化。編寫代碼如下:
# -*- coding: UTF-8 -*-from matplotlib.font_manager import FontPropertiesimport matplotlib.lines as mlinesimport matplotlib.pyplot as pltimport numpy as np"""函數說明:打開並解析文件,對數據進行分類:1代表不喜歡,2代表魅力一般,3代表極具魅力Parameters: filename - 文件名Returns: returnMat - 特徵矩陣 classLabelVector - 分類Label向量Modify: 2017-03-24"""def file2matrix(filename): #打開文件 fr = open(filename) #讀取文件所有內容 arrayOLines = fr.readlines() #得到文件行數 numberOfLines = len(arrayOLines) #返回的NumPy矩陣,解析完成的數據:numberOfLines行,3列 returnMat = np.zeros((numberOfLines,3)) #返回的分類標籤向量 classLabelVector = [] #行的索引值 index = 0 for line in arrayOLines: #s.strip(rm),當rm空時,默認刪除空白符(包括"
","
"," "," ") line = line.strip() #使用s.split(str="",num=string,cout(str))將字元串根據" "分隔符進行切片。 listFromLine = line.split(" ") #將數據前三列提取出來,存放到returnMat的NumPy矩陣中,也就是特徵矩陣 returnMat[index,:] = listFromLine[0:3] #根據文本中標記的喜歡的程度進行分類,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 += 1 return returnMat, classLabelVector"""函數說明:可視化數據Parameters: datingDataMat - 特徵矩陣 datingLabels - 分類LabelReturns: 無Modify: 2017-03-24"""def showdatas(datingDataMat, datingLabels): #設置漢字格式 font = FontProperties(fname=r"c:windowsfontssimsun.ttc", size=14) #將fig畫布分隔成1行1列,不共享x軸和y軸,fig畫布的大小為(13,8) #當nrow=2,nclos=2時,代表fig畫布被分為四個區域,axs[0][0]表示第一行第一個區域 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矩陣的第一(飛行常客常式)、第二列(玩遊戲)數據畫散點數據,散點大小為15,透明度為0.5 axs[0][0].scatter(x=datingDataMat[:,0], y=datingDataMat[:,1], color=LabelsColors,s=15, alpha=.5) #設置標題,x軸label,y軸label axs0_title_text = axs[0][0].set_title(u"每年獲得的飛行常客里程數與玩視頻遊戲所消耗時間佔比",FontProperties=font) axs0_xlabel_text = axs[0][0].set_xlabel(u"每年獲得的飛行常客里程數",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矩陣的第一(飛行常客常式)、第三列(冰激凌)數據畫散點數據,散點大小為15,透明度為0.5 axs[0][1].scatter(x=datingDataMat[:,0], y=datingDataMat[:,2], color=LabelsColors,s=15, alpha=.5) #設置標題,x軸label,y軸label axs1_title_text = axs[0][1].set_title(u"每年獲得的飛行常客里程數與每周消費的冰激淋公升數",FontProperties=font) axs1_xlabel_text = axs[0][1].set_xlabel(u"每年獲得的飛行常客里程數",FontProperties=font) axs1_ylabel_text = axs[0][1].set_ylabel(u"每周消費的冰激淋公升數",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矩陣的第二(玩遊戲)、第三列(冰激凌)數據畫散點數據,散點大小為15,透明度為0.5 axs[1][0].scatter(x=datingDataMat[:,1], y=datingDataMat[:,2], color=LabelsColors,s=15, alpha=.5) #設置標題,x軸label,y軸label axs2_title_text = axs[1][0].set_title(u"玩視頻遊戲所消耗時間佔比與每周消費的冰激淋公升數",FontProperties=font) axs2_xlabel_text = axs[1][0].set_xlabel(u"玩視頻遊戲所消耗時間佔比",FontProperties=font) axs2_ylabel_text = axs[1][0].set_ylabel(u"每周消費的冰激淋公升數",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") #設置圖例 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()"""函數說明:main函數Parameters: 無Returns: 無Modify: 2017-03-24"""if __name__ == "__main__": #打開的文件名 filename = "datingTestSet.txt" #打開並處理數據 datingDataMat, datingLabels = file2matrix(filename) showdatas(datingDataMat, datingLabels)
運行上述代碼,可以看到可視化結果如圖2.3所示。
圖2.3 數據可視化結果
通過數據可以很直觀的發現數據的規律,比如以玩遊戲所消耗時間佔比與每年獲得的飛行常客里程數,只考慮這二維的特徵信息,給我的感覺就是海倫喜歡有生活質量的男人。為什麼這麼說呢?每年獲得的飛行常客里程數表明,海倫喜歡能享受飛行常客獎勵計劃的男人,但是不能經常坐飛機,疲於奔波,滿世界飛。同時,這個男人也要玩視頻遊戲,並且佔一定時間比例。能到處飛,又能經常玩遊戲的男人是什麼樣的男人?很顯然,有生活質量,並且生活悠閑的人。我的分析,僅僅是通過可視化的數據總結的個人看法。我想,每個人的感受應該也是不盡相同。
4、準備數據:數據歸一化
表2.1給出了四組樣本,如果想要計算樣本3和樣本4之間的距離,可以使用歐拉公式計算。
表2.1 約會網站樣本數據
計算方法如圖2.4所示。
圖2.4 計算公式
我們很容易發現,上面方程中數字差值最大的屬性對計算結果的影響最大,也就是說,每年獲取的飛行常客里程數對於計算結果的影響將遠遠大於表2.1中其他兩個特徵-玩視頻遊戲所耗時間佔比和每周消費冰淇淋公斤數的影響。而產生這種現象的唯一原因,僅僅是因為飛行常客里程數遠大於其他特徵值。但海倫認為這三種特徵是同等重要的,因此作為三個等權重的特徵之一,飛行常客里程數並不應該如此嚴重地影響到計算結果。
在處理這種不同取值範圍的特徵值時,我們通常採用的方法是將數值歸一化,如將取值範圍處理為0到1或者-1到1之間。下面的公式可以將任意取值範圍的特徵值轉化為0到1區間內的值:
其中min和max分別是數據集中的最小特徵值和最大特徵值。雖然改變數值取值範圍增加了分類器的複雜度,但為了得到準確結果,我們必須這樣做。在kNN_test02.py文件中編寫名為autoNorm的函數,用該函數自動將數據歸一化。代碼如下:
# -*- coding: UTF-8 -*-import numpy as np"""函數說明:打開並解析文件,對數據進行分類:1代表不喜歡,2代表魅力一般,3代表極具魅力Parameters: filename - 文件名Returns: returnMat - 特徵矩陣 classLabelVector - 分類Label向量Modify: 2017-03-24"""def file2matrix(filename): #打開文件 fr = open(filename) #讀取文件所有內容 arrayOLines = fr.readlines() #得到文件行數 numberOfLines = len(arrayOLines) #返回的NumPy矩陣,解析完成的數據:numberOfLines行,3列 returnMat = np.zeros((numberOfLines,3)) #返回的分類標籤向量 classLabelVector = [] #行的索引值 index = 0 for line in arrayOLines: #s.strip(rm),當rm空時,默認刪除空白符(包括"
","
"," "," ") line = line.strip() #使用s.split(str="",num=string,cout(str))將字元串根據" "分隔符進行切片。 listFromLine = line.split(" ") #將數據前三列提取出來,存放到returnMat的NumPy矩陣中,也就是特徵矩陣 returnMat[index,:] = listFromLine[0:3] #根據文本中標記的喜歡的程度進行分類,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 += 1 return returnMat, classLabelVector"""函數說明:對數據進行歸一化Parameters: dataSet - 特徵矩陣Returns: normDataSet - 歸一化後的特徵矩陣 ranges - 數據範圍 minVals - 數據最小值Modify: 2017-03-24"""def autoNorm(dataSet): #獲得數據的最小值 minVals = dataSet.min(0) maxVals = dataSet.max(0) #最大值和最小值的範圍 ranges = maxVals - minVals #shape(dataSet)返回dataSet的矩陣行列數 normDataSet = np.zeros(np.shape(dataSet)) #返回dataSet的行數 m = dataSet.shape[0] #原始值減去最小值 normDataSet = dataSet - np.tile(minVals, (m, 1)) #除以最大和最小值的差,得到歸一化數據 normDataSet = normDataSet / np.tile(ranges, (m, 1)) #返回歸一化數據結果,數據範圍,最小值 return normDataSet, ranges, minVals"""函數說明:main函數Parameters: 無Returns: 無Modify: 2017-03-24"""if __name__ == "__main__": #打開的文件名 filename = "datingTestSet.txt" #打開並處理數據 datingDataMat, datingLabels = file2matrix(filename) normDataSet, ranges, minVals = autoNorm(datingDataMat) print(normDataSet) print(ranges) print(minVals)
運行上述代碼,得到結果如圖2.4所示。
圖2.4 歸一化函數運行結果
從圖2.4的運行結果可以看到,我們已經順利將數據歸一化了,並且求出了數據的取值範圍和數據的最小值,這兩個值是在分類的時候需要用到的,直接先求解出來,也算是對數據預處理了。
5、測試演算法:驗證分類器
機器學習演算法一個很重要的工作就是評估演算法的正確率,通常我們只提供已有數據的90%作為訓練樣本來訓練分類器,而使用其餘的10%數據去測試分類器,檢測分類器的正確率。需要注意的是,10%的測試數據應該是隨機選擇的,由於海倫提供的數據並沒有按照特定目的來排序,所以我么你可以隨意選擇10%數據而不影響其隨機性。
為了測試分類器效果,在kNN_test02.py文件中創建函數datingClassTest,編寫代碼如下:
# -*- coding: UTF-8 -*-import numpy as npimport operator"""函數說明:kNN演算法,分類器Parameters: inX - 用於分類的數據(測試集) dataSet - 用於訓練的數據(訓練集) labes - 分類標籤 k - kNN演算法參數,選擇距離最小的k個點Returns: sortedClassCount[0][0] - 分類結果Modify: 2017-03-24"""def classify0(inX, dataSet, labels, k): #numpy函數shape[0]返回dataSet的行數 dataSetSize = dataSet.shape[0] #在列向量方向上重複inX共1次(橫向),行向量方向上重複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() #定一個記錄類別次數的字典 classCount = {} for i in range(k): #取出前k個元素的類別 voteIlabel = labels[sortedDistIndices[i]] #dict.get(key,default=None),字典的get()方法,返回指定鍵的值,如果值不在字典中返回默認值。 #計算類別次數 classCount[voteIlabel] = classCount.get(voteIlabel,0) + 1 #python3中用items()替換python2中的iteritems() #key=operator.itemgetter(1)根據字典的值進行排序 #key=operator.itemgetter(0)根據字典的鍵進行排序 #reverse降序排序字典 sortedClassCount = sorted(classCount.items(),key=operator.itemgetter(1),reverse=True) #返回次數最多的類別,即所要分類的類別 return sortedClassCount[0][0]"""函數說明:打開並解析文件,對數據進行分類:1代表不喜歡,2代表魅力一般,3代表極具魅力Parameters: filename - 文件名Returns: returnMat - 特徵矩陣 classLabelVector - 分類Label向量Modify: 2017-03-24"""def file2matrix(filename): #打開文件 fr = open(filename) #讀取文件所有內容 arrayOLines = fr.readlines() #得到文件行數 numberOfLines = len(arrayOLines) #返回的NumPy矩陣,解析完成的數據:numberOfLines行,3列 returnMat = np.zeros((numberOfLines,3)) #返回的分類標籤向量 classLabelVector = [] #行的索引值 index = 0 for line in arrayOLines: #s.strip(rm),當rm空時,默認刪除空白符(包括"
","
"," "," ") line = line.strip() #使用s.split(str="",num=string,cout(str))將字元串根據" "分隔符進行切片。 listFromLine = line.split(" ") #將數據前三列提取出來,存放到returnMat的NumPy矩陣中,也就是特徵矩陣 returnMat[index,:] = listFromLine[0:3] #根據文本中標記的喜歡的程度進行分類,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 += 1 return returnMat, classLabelVector"""函數說明:對數據進行歸一化Parameters: dataSet - 特徵矩陣Returns: normDataSet - 歸一化後的特徵矩陣 ranges - 數據範圍 minVals - 數據最小值Modify: 2017-03-24"""def autoNorm(dataSet): #獲得數據的最小值 minVals = dataSet.min(0) maxVals = dataSet.max(0) #最大值和最小值的範圍 ranges = maxVals - minVals #shape(dataSet)返回dataSet的矩陣行列數 normDataSet = np.zeros(np.shape(dataSet)) #返回dataSet的行數 m = dataSet.shape[0] #原始值減去最小值 normDataSet = dataSet - np.tile(minVals, (m, 1)) #除以最大和最小值的差,得到歸一化數據 normDataSet = normDataSet / np.tile(ranges, (m, 1)) #返回歸一化數據結果,數據範圍,最小值 return normDataSet, ranges, minVals"""函數說明:分類器測試函數Parameters: 無Returns: normDataSet - 歸一化後的特徵矩陣 ranges - 數據範圍 minVals - 數據最小值Modify: 2017-03-24"""def datingClassTest(): #打開的文件名 filename = "datingTestSet.txt" #將返回的特徵矩陣和分類向量分別存儲到datingDataMat和datingLabels中 datingDataMat, datingLabels = file2matrix(filename) #取所有數據的百分之十 hoRatio = 0.10 #數據歸一化,返回歸一化後的矩陣,數據範圍,數據最小值 normMat, ranges, minVals = autoNorm(datingDataMat) #獲得normMat的行數 m = normMat.shape[0] #百分之十的測試數據的個數 numTestVecs = int(m * hoRatio) #分類錯誤計數 errorCount = 0.0 for i in range(numTestVecs): #前numTestVecs個數據作為測試集,後m-numTestVecs個數據作為訓練集 classifierResult = classify0(normMat[i,:], normMat[numTestVecs:m,:], datingLabels[numTestVecs:m], 4) print("分類結果:%d 真實類別:%d" % (classifierResult, datingLabels[i])) if classifierResult != datingLabels[i]: errorCount += 1.0 print("錯誤率:%f%%" %(errorCount/float(numTestVecs)*100))"""函數說明:main函數Parameters: 無Returns: 無Modify: 2017-03-24"""if __name__ == "__main__": datingClassTest()
運行上述代碼,得到結果如圖2.5所示。
圖2.5 驗證分類器結果
從圖2.5驗證分類器結果中可以看出,錯誤率是3%,這是一個想當不錯的結果。我們可以改變函數datingClassTest內變數hoRatio和分類器k的值,檢測錯誤率是否隨著變數值的變化而增加。依賴於分類演算法、數據集和程序設置,分類器的輸出結果可能有很大的不同。
6、使用演算法:構建完整可用系統
我們可以給海倫一個小段程序,通過該程序海倫會在約會網站上找到某個人並輸入他的信息。程序會給出她對男方喜歡程度的預測值。
在kNN_test02.py文件中創建函數classifyPerson,代碼如下:
# -*- coding: UTF-8 -*-import numpy as npimport operator"""函數說明:kNN演算法,分類器Parameters: inX - 用於分類的數據(測試集) dataSet - 用於訓練的數據(訓練集) labes - 分類標籤 k - kNN演算法參數,選擇距離最小的k個點Returns: sortedClassCount[0][0] - 分類結果Modify: 2017-03-24"""def classify0(inX, dataSet, labels, k): #numpy函數shape[0]返回dataSet的行數 dataSetSize = dataSet.shape[0] #在列向量方向上重複inX共1次(橫向),行向量方向上重複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() #定一個記錄類別次數的字典 classCount = {} for i in range(k): #取出前k個元素的類別 voteIlabel = labels[sortedDistIndices[i]] #dict.get(key,default=None),字典的get()方法,返回指定鍵的值,如果值不在字典中返回默認值。 #計算類別次數 classCount[voteIlabel] = classCount.get(voteIlabel,0) + 1 #python3中用items()替換python2中的iteritems() #key=operator.itemgetter(1)根據字典的值進行排序 #key=operator.itemgetter(0)根據字典的鍵進行排序 #reverse降序排序字典 sortedClassCount = sorted(classCount.items(),key=operator.itemgetter(1),reverse=True) #返回次數最多的類別,即所要分類的類別 return sortedClassCount[0][0]"""函數說明:打開並解析文件,對數據進行分類:1代表不喜歡,2代表魅力一般,3代表極具魅力Parameters: filename - 文件名Returns: returnMat - 特徵矩陣 classLabelVector - 分類Label向量Modify: 2017-03-24"""def file2matrix(filename): #打開文件 fr = open(filename) #讀取文件所有內容 arrayOLines = fr.readlines() #得到文件行數 numberOfLines = len(arrayOLines) #返回的NumPy矩陣,解析完成的數據:numberOfLines行,3列 returnMat = np.zeros((numberOfLines,3)) #返回的分類標籤向量 classLabelVector = [] #行的索引值 index = 0 for line in arrayOLines: #s.strip(rm),當rm空時,默認刪除空白符(包括"
","
"," "," ") line = line.strip() #使用s.split(str="",num=string,cout(str))將字元串根據" "分隔符進行切片。 listFromLine = line.split(" ") #將數據前三列提取出來,存放到returnMat的NumPy矩陣中,也就是特徵矩陣 returnMat[index,:] = listFromLine[0:3] #根據文本中標記的喜歡的程度進行分類,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 += 1 return returnMat, classLabelVector"""函數說明:對數據進行歸一化Parameters: dataSet - 特徵矩陣Returns: normDataSet - 歸一化後的特徵矩陣 ranges - 數據範圍 minVals - 數據最小值Modify: 2017-03-24"""def autoNorm(dataSet): #獲得數據的最小值 minVals = dataSet.min(0) maxVals = dataSet.max(0) #最大值和最小值的範圍 ranges = maxVals - minVals #shape(dataSet)返回dataSet的矩陣行列數 normDataSet = np.zeros(np.shape(dataSet)) #返回dataSet的行數 m = dataSet.shape[0] #原始值減去最小值 normDataSet = dataSet - np.tile(minVals, (m, 1)) #除以最大和最小值的差,得到歸一化數據 normDataSet = normDataSet / np.tile(ranges, (m, 1)) #返回歸一化數據結果,數據範圍,最小值 return normDataSet, ranges, minVals"""函數說明:通過輸入一個人的三維特徵,進行分類輸出Parameters: 無Returns: 無Modify: 2017-03-24"""def classifyPerson(): #輸出結果 resultList = ["討厭","有些喜歡","非常喜歡"] #三維特徵用戶輸入 precentTats = float(input("玩視頻遊戲所耗時間百分比:")) ffMiles = float(input("每年獲得的飛行常客里程數:")) iceCream = float(input("每周消費的冰激淋公升數:")) #打開的文件名 filename = "datingTestSet.txt" #打開並處理數據 datingDataMat, datingLabels = file2matrix(filename) #訓練集歸一化 normMat, ranges, minVals = autoNorm(datingDataMat) #生成NumPy數組,測試集 inArr = np.array([precentTats, ffMiles, iceCream]) #測試集歸一化 norminArr = (inArr - minVals) / ranges #返回分類結果 classifierResult = classify0(norminArr, normMat, datingLabels, 3) #列印結果 print("你可能%s這個人" % (resultList[classifierResult-1]))"""函數說明:main函數Parameters: 無Returns: 無Modify: 2017-03-24"""if __name__ == "__main__": classifyPerson()
在cmd中,運行程序,並輸入數據(12,44000,0.5),預測結果是"你可能有些喜歡這個人",也就是這個人魅力一般。一共有三個檔次:討厭、有些喜歡、非常喜歡,對應著不喜歡的人、魅力一般的人、極具魅力的人。結果如圖2.6所示。
圖2.6 預測結果
三、k-近鄰演算法實戰之sklearn手寫數字識別
1、實戰背景
對於需要識別的數字已經使用圖形處理軟體,處理成具有相同的色彩和大小:寬高是32像素x32像素。儘管採用本文格式存儲圖像不能有效地利用內存空間,但是為了方便理解,我們將圖片轉換為文本格式,數字的文本格式如圖3.1所示。
圖3.1 數字的文本格式
與此同時,這些文本格式存儲的數字的文件命名也很有特點,格式為:數字的值_該數字的樣本序號,如圖3.2所示。
圖3.2 文本數字的存儲格式
對於這樣已經整理好的文本,我們可以直接使用Python處理,進行數字預測。數據集分為訓練集和測試集,使用上小結的方法,自己設計k-近鄰演算法分類器,可以實現分類。數據集和實現代碼下載地址:https://github.com/Jack-Cherish/Machine-Learning/tree/master/kNN/3.%E6%95%B0%E5%AD%97%E8%AF%86%E5%88%AB
這裡不再講解自己用Python寫的k-鄰域分類器的方法,因為這不是本小節的重點。接下來,我們將使用強大的第三方Python科學計算庫Sklearn構建手寫數字系統。
2、sklearn簡介
Scikit learn 也簡稱sklearn,是機器學習領域當中最知名的python模塊之一。sklearn包含了很多機器學習的方式:
- Classification 分類
- Regression 回歸
- Clustering 非監督分類
- Dimensionality reduction 數據降維
- Model Selection 模型選擇
- Preprocessing 數據與處理
使用sklearn可以很方便地讓我們實現一個機器學習演算法。一個複雜度演算法的實現,使用sklearn可能只需要調用幾行API即可。所以學習sklearn,可以有效減少我們特定任務的實現周期。
3、sklearn安裝
在安裝sklearn之前,需要安裝兩個庫,即numpy+mkl和scipy。不要使用pip3直接進行安裝,因為pip3默安裝的是numpy,而不是numpy+mkl。第三方庫下載地址:http://www.lfd.uci.edu/~gohlke/pythonlibs/
這個網站的使用方法,我在之前的文章里有講過:http://blog.csdn.net/c406495762/article/details/60156205
找到對應python版本的numpy+mkl和scipy,下載安裝即可,如圖3.3和圖3.4所示。
圖3.3 numpy+mkl
圖3.4 scipy
使用pip3安裝好這兩個whl文件後,使用如下指令安裝sklearn。
pip3 install -U scikit-learn
4、sklearn實現k-近鄰演算法簡介
官網英文文檔:http://scikit-learn.org/stable/modules/generated/sklearn.neighbors.KNeighborsClassifier.html
sklearn.neighbors模塊實現了k-近鄰演算法,內容如圖3.5所示。
圖3.5 sklearn.neighbors
我們使用sklearn.neighbors.KNeighborsClassifier就可以是實現上小結,我們實現的k-近鄰演算法。KNeighborsClassifier函數一共有8個參數,如圖3.6所示。
圖3.6 KNeighborsClassifier
KNneighborsClassifier參數說明:
- n_neighbors:默認為5,就是k-NN的k的值,選取最近的k個點。
- weights:默認是uniform,參數可以是uniform、distance,也可以是用戶自己定義的函數。uniform是均等的權重,就說所有的鄰近點的權重都是相等的。distance是不均等的權重,距離近的點比距離遠的點的影響大。用戶自定義的函數,接收距離的數組,返回一組維數相同的權重。
- algorithm:快速k近鄰搜索演算法,默認參數為auto,可以理解為演算法自己決定合適的搜索演算法。除此之外,用戶也可以自己指定搜索演算法ball_tree、kd_tree、brute方法進行搜索,brute是蠻力搜索,也就是線性掃描,當訓練集很大時,計算非常耗時。kd_tree,構造kd樹存儲數據以便對其進行快速檢索的樹形數據結構,kd樹也就是數據結構中的二叉樹。以中值切分構造的樹,每個結點是一個超矩形,在維數小於20時效率高。ball tree是為了克服kd樹高緯失效而發明的,其構造過程是以質心C和半徑r分割樣本空間,每個節點是一個超球體。
- leaf_size:默認是30,這個是構造的kd樹和ball樹的大小。這個值的設置會影響樹構建的速度和搜索速度,同樣也影響著存儲樹所需的內存大小。需要根據問題的性質選擇最優的大小。
- metric:用於距離度量,默認度量是minkowski,也就是p=2的歐氏距離(歐幾里德度量)。
- p:距離度量公式。在上小結,我們使用歐氏距離公式進行距離度量。除此之外,還有其他的度量方法,例如曼哈頓距離。這個參數默認為2,也就是默認使用歐式距離公式進行距離度量。也可以設置為1,使用曼哈頓距離公式進行距離度量。
- metric_params:距離公式的其他關鍵參數,這個可以不管,使用默認的None即可。
- n_jobs:並行處理設置。默認為1,臨近點搜索並行工作數。如果為-1,那麼CPU的所有cores都用於並行工作。
KNeighborsClassifier提供了以一些方法供我們使用,如圖3.7所示。
圖3.5 KNeighborsClassifier的方法
由於篇幅原因,每個函數的怎麼用,就不具體講解了。官方手冊:http://scikit-learn.org/stable/modules/generated/sklearn.neighbors.KNeighborsClassifier.html#sklearn.neighbors.KNeighborsClassifier 已經講解的很詳細了,各位可以查看這個手冊進行學習,我們直接講手寫數字識別系統的實現。
5、sklearn小試牛刀
我們知道數字圖片是32x32的二進位圖像,為了方便計算,我們可以將32x32的二進位圖像轉換為1x1024的向量。對於sklearn的KNeighborsClassifier輸入可以是矩陣,不用一定轉換為向量,不過為了跟自己寫的k-近鄰演算法分類器對應上,這裡也做了向量化處理。然後構建kNN分類器,利用分類器做預測。創建kNN_test04.py文件,編寫代碼如下:
# -*- coding: UTF-8 -*-import numpy as npimport operatorfrom os import listdirfrom sklearn.neighbors import KNeighborsClassifier as kNN"""函數說明:將32x32的二進位圖像轉換為1x1024向量。Parameters: filename - 文件名Returns: returnVect - 返回的二進位圖像的1x1024向量Modify: 2017-07-15"""def img2vector(filename): #創建1x1024零向量 returnVect = np.zeros((1, 1024)) #打開文件 fr = open(filename) #按行讀取 for i in range(32): #讀一行數據 lineStr = fr.readline() #每一行的前32個元素依次添加到returnVect中 for j in range(32): returnVect[0, 32*i+j] = int(lineStr[j]) #返迴轉換後的1x1024向量 return returnVect"""函數說明:手寫數字分類測試Parameters: 無Returns: 無Modify: 2017-07-15"""def handwritingClassTest(): #測試集的Labels hwLabels = [] #返回trainingDigits目錄下的文件名 trainingFileList = listdir("trainingDigits") #返迴文件夾下文件的個數 m = len(trainingFileList) #初始化訓練的Mat矩陣,測試集 trainingMat = np.zeros((m, 1024)) #從文件名中解析出訓練集的類別 for i in range(m): #獲得文件的名字 fileNameStr = trainingFileList[i] #獲得分類的數字 classNumber = int(fileNameStr.split("_")[0]) #將獲得的類別添加到hwLabels中 hwLabels.append(classNumber) #將每一個文件的1x1024數據存儲到trainingMat矩陣中 trainingMat[i,:] = img2vector("trainingDigits/%s" % (fileNameStr)) #構建kNN分類器 neigh = kNN(n_neighbors = 3, algorithm = "auto") #擬合模型, trainingMat為測試矩陣,hwLabels為對應的標籤 neigh.fit(trainingMat, hwLabels) #返回testDigits目錄下的文件列表 testFileList = listdir("testDigits") #錯誤檢測計數 errorCount = 0.0 #測試數據的數量 mTest = len(testFileList) #從文件中解析出測試集的類別並進行分類測試 for i in range(mTest): #獲得文件的名字 fileNameStr = testFileList[i] #獲得分類的數字 classNumber = int(fileNameStr.split("_")[0]) #獲得測試集的1x1024向量,用於訓練 vectorUnderTest = img2vector("testDigits/%s" % (fileNameStr)) #獲得預測結果 # classifierResult = classify0(vectorUnderTest, trainingMat, hwLabels, 3) classifierResult = neigh.predict(vectorUnderTest) print("分類返回結果為%d 真實結果為%d" % (classifierResult, classNumber)) if(classifierResult != classNumber): errorCount += 1.0 print("總共錯了%d個數據
錯誤率為%f%%" % (errorCount, errorCount/mTest * 100))"""函數說明:main函數Parameters: 無Returns: 無Modify: 2017-07-15"""if __name__ == "__main__": handwritingClassTest()
運行上述代碼,得到如圖3.8所示的結果。
圖3.8 sklearn運行結果
上述代碼使用的algorithm參數是auto,更改algorithm參數為brute,使用暴力搜索,你會發現,運行時間變長了,變為10s+。更改n_neighbors參數,你會發現,不同的值,檢測精度也是不同的。自己可以嘗試更改這些參數的設置,加深對其函數的理解。
四、總結
1、kNN演算法的優缺點
優點
- 簡單好用,容易理解,精度高,理論成熟,既可以用來做分類也可以用來做回歸;
- 可用於數值型數據和離散型數據;
- 訓練時間複雜度為O(n);無數據輸入假定;
- 對異常值不敏感
缺點
- 計算複雜性高;空間複雜性高;
- 樣本不平衡問題(即有些類別的樣本數量很多,而其它樣本的數量很少);
- 一般數值很大的時候不用這個,計算量太大。但是單個樣本又不能太少,否則容易發生誤分。
- 最大的缺點是無法給出數據的內在含義。
2、其他
- 關於algorithm參數kd_tree的原理,可以查看《統計學方法 李航》書中的講解;
- 關於距離度量的方法還有切比雪夫距離、馬氏距離、巴氏距離等;
- 下篇文章將講解決策樹,歡迎各位的捧場!
- 如有問題,請留言。如有錯誤,還望指正,謝謝!
PS: 如果覺得本篇本章對您有所幫助,歡迎關注、評論、贊!
參考文獻:
- 本文中提到的電影類別分類、約會網站配對效果判定、手寫數字識別實例和數據集,均來自於《機器學習實戰》的第二章k-近鄰演算法。
- 本文的理論部分,參考自《統計學習方法 李航》的第三章k近鄰法以及《機器學習實戰》的第二章k-近鄰演算法。
推薦閱讀:
※歷史|從神經元到深度學習
※二維可視圖講解神經元w,b參數的作用
※關於深度學習的機理,優化和網路結構的一些個人觀點(二).
※一個相關濾波跟蹤的簡單教程(附實現demo)