第2章 k-近鄰算法
http://cdn.mathjax.org/mathjax/latest/MathJax.js?config=default">>
k-近鄰（kNN, k-NearestNeighbor）算法主要是用來進行分類的.
電影可以按照題材分類债朵，那么如何區(qū)分動作片和愛情片呢寨辩？
動作片：打斗次數(shù)更多
愛情片：親吻次數(shù)更多
基于電影中的親吻之碗、打斗出現(xiàn)的次數(shù)，使用 k-近鄰算法構造程序搔体，就可以自動劃分電影的題材類型恨樟。
現(xiàn)在根據(jù)上面我們得到的樣本集中所有電影與未知電影的距離，按照距離遞增排序疚俱，可以找到 k 個距離最近的電影劝术。
假定 k=3，則三個最靠近的電影依次是呆奕， He's Not Really into Dudes 养晋、 Beautiful Woman 和 California Man。
knn 算法按照距離最近的三部電影的類型梁钾，決定未知電影的類型绳泉，而這三部電影全是愛情片，因此我們判定未知電影是愛情片姆泻。
KNN 工作原理
假設有一個帶有標簽的樣本數(shù)據(jù)集（訓練樣本集）零酪，其中包含每條數(shù)據(jù)與所屬分類的對應關系。
輸入沒有標簽的新數(shù)據(jù)后拇勃，將新數(shù)據(jù)的每個特征與樣本集中數(shù)據(jù)對應的特征進行比較四苇。
計算新數(shù)據(jù)與樣本數(shù)據(jù)集中每條數(shù)據(jù)的距離。
對求得的所有距離進行排序（從小到大方咆，越小表示越相似）蛔琅。
取前 k （k 一般小于等于 20 ）個樣本數(shù)據(jù)對應的分類標簽。
求 k 個數(shù)據(jù)中出現(xiàn)次數(shù)最多的分類標簽作為新數(shù)據(jù)的分類峻呛。
KNN 開發(fā)流程
收集數(shù)據(jù)：任何方法
準備數(shù)據(jù)：距離計算所需要的數(shù)值罗售，最好是結構化的數(shù)據(jù)格式
分析數(shù)據(jù)：任何方法
訓練算法：此步驟不適用于 k-近鄰算法
測試算法：計算錯誤率
使用算法：輸入樣本數(shù)據(jù)和結構化的輸出結果，然后運行 k-近鄰算法判斷輸入數(shù)據(jù)分類屬于哪個分類钩述，最后對計算出的分類執(zhí)行后續(xù)處理
KNN 算法特點
優(yōu)點：精度高寨躁、對異常值不敏感、無數(shù)據(jù)輸入假定
缺點：計算復雜度高牙勘、空間復雜度高
適用數(shù)據(jù)范圍：數(shù)值型和標稱型
海倫使用約會網(wǎng)站尋找約會對象职恳。經(jīng)過一段時間之后，她發(fā)現(xiàn)曾交往過三種類型的人:
不喜歡的人
魅力一般的人
極具魅力的人
她希望：
工作日與魅力一般的人約會
周末與極具魅力的人約會
不喜歡的人則直接排除掉
現(xiàn)在她收集到了一些約會網(wǎng)站未曾記錄的數(shù)據(jù)信息方面，這更有助于匹配對象的歸類放钦。
收集數(shù)據(jù)：提供文本文件
準備數(shù)據(jù)：使用 Python 解析文本文件
分析數(shù)據(jù)：使用 Matplotlib 畫二維散點圖
訓練算法：此步驟不適用于 k-近鄰算法
測試算法：使用海倫提供的部分數(shù)據(jù)作為測試樣本。
測試樣本和非測試樣本的區(qū)別在于：
測試樣本是已經(jīng)完成分類的數(shù)據(jù)恭金，如果預測分類與實際類別不同操禀，則標記為一個錯誤。
使用算法：產(chǎn)生簡單的命令行程序横腿，然后海倫可以輸入一些特征數(shù)據(jù)以判斷對方是否為自己喜歡的類型颓屑。
收集數(shù)據(jù)：提供文本文件
海倫把這些約會對象的數(shù)據(jù)存放在文本文件datingTestSet2.txt中斤寂，總共有 1000 行。海倫約會的對象主要包含以下 3 種特征：
每年獲得的飛行尘镜耄客里程數(shù)
玩視頻游戲所耗時間百分比
每周消費的冰淇淋公升數(shù)
文本文件數(shù)據(jù)格式如下：
40920 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
準備數(shù)據(jù)：使用 Python 解析文本文件
將文本記錄轉換為 NumPy 的解析程序
deffile2matrix(filename):"""Desc:導入訓練數(shù)據(jù)parameters:filename: 數(shù)據(jù)文件路徑return:數(shù)據(jù)矩陣 returnMat 和對應的類別 classLabelVector"""fr=open(filename)#獲得文件中的數(shù)據(jù)行的行數(shù)numberOfLines=len(fr.readlines())#生成對應的空矩陣#例如：zeros(2遍搞，3)就是生成一個 2*3的矩陣，各個位置上全是 0returnMat=zeros((numberOfLines,3))#prepare matrix to returnclassLabelVector=[]#prepare labels returnfr=open(filename)? index=0forlineinfr.readlines():#str.strip([chars]) --返回移除字符串頭尾指定的字符生成的新字符串line=line.strip()#以 '\t' 切割字符串listFromLine=line.split('\t')#每列的屬性數(shù)據(jù)returnMat[index, :]=listFromLine[0:3]#每列的類別數(shù)據(jù)器腋，就是 label 標簽數(shù)據(jù)classLabelVector.append(int(listFromLine[-1]))? ? ? index+=1#返回數(shù)據(jù)矩陣returnMat和對應的類別classLabelVectorreturnreturnMat, classLabelVector
分析數(shù)據(jù)：使用 Matplotlib 畫二維散點圖
importmatplotlibimportmatplotlib.pyplotaspltfig=plt.figure()ax=fig.add_subplot(111)ax.scatter(datingDataMat[:,1], datingDataMat[:,2],15.0*array(datingLabels),15.0*array(datingLabels))plt.show()
下圖中采用矩陣的第一和第三列屬性得到很好的展示效果溪猿，清晰地標識了三個不同的樣本分類區(qū)域，具有不同愛好的人其類別區(qū)域也不同纫塌。
歸一化數(shù)據(jù) （歸一化是一個讓權重變?yōu)榻y(tǒng)一的過程诊县，更多細節(jié)請參考：https://www.zhihu.com/question/19951858）
序號玩視頻游戲所耗時間百分比每年獲得的飛行常客里程數(shù)每周消費的冰淇淋公升數(shù)樣本分類
10.84000.51
212134 0000.93
3020 0001.12
46732 0000.12
樣本3和樣本4的距離： $$\sqrt{(0-67)^2 + (20000-32000)^2 + (1.1-0.1)^2 }$$
歸一化特征值护戳，消除特征之間量級不同導致的影響
defautoNorm(dataSet):"""Desc:歸一化特征值翎冲，消除特征之間量級不同導致的影響parameter:dataSet: 數(shù)據(jù)集return:歸一化后的數(shù)據(jù)集 normDataSet. ranges和minVals即最小值與范圍，并沒有用到歸一化公式：Y = (X-Xmin)/(Xmax-Xmin)其中的 min 和 max 分別是數(shù)據(jù)集中的最小特征值和最大特征值媳荒。該函數(shù)可以自動將數(shù)字特征值轉化為0到1的區(qū)間抗悍。"""#計算每種屬性的最大值、最小值钳枕、范圍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))#element wise dividereturnnormDataSet, ranges, minVals
訓練算法：此步驟不適用于 k-近鄰算法
因為測試數(shù)據(jù)每一次都要與全量的訓練數(shù)據(jù)進行比較缴渊，所以這個過程是沒有必要的。
測試算法：使用海倫提供的部分數(shù)據(jù)作為測試樣本鱼炒。如果預測分類與實際類別不同衔沼，則標記為一個錯誤。
kNN 分類器針對約會網(wǎng)站的測試代碼
defdatingClassTest():"""Desc:對約會網(wǎng)站的測試方法parameters:nonereturn:錯誤數(shù)"""#設置測試數(shù)據(jù)的的一個比例（訓練數(shù)據(jù)集比例=1-hoRatio）hoRatio=0.1#測試范圍,一部分測試一部分作為樣本#從文件中加載數(shù)據(jù)datingDataMat, datingLabels=file2matrix('input/2.KNN/datingTestSet2.txt')#load data setfrom file#歸一化數(shù)據(jù)normMat, ranges, minVals=autoNorm(datingDataMat)#m 表示數(shù)據(jù)的行數(shù)昔瞧，即矩陣的第一維m=normMat.shape[0]#設置測試的樣本數(shù)量指蚁， numTestVecs:m表示訓練樣本的數(shù)量numTestVecs=int(m*hoRatio)print'numTestVecs=', numTestVecs? ? errorCount=0.0foriinrange(numTestVecs):#對數(shù)據(jù)測試classifierResult=classify0(normMat[i, :], normMat[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.0print"the total error rate is:%f"%(errorCount/float(numTestVecs))printerrorCount
使用算法：產(chǎn)生簡單的命令行程序，然后海倫可以輸入一些特征數(shù)據(jù)以判斷對方是否為自己喜歡的類型自晰。
約會網(wǎng)站預測函數(shù)
defclasdifyPerson():? ? resultList=['not at all','in small doses','in large doses']? ? percentTats=float(raw_input("percentage of time spent playing video games ?"))? ? ffMiles=float(raw_input("frequent filer miles earned per year?"))? ? iceCream=float(raw_input("liters of ice cream consumed per year?"))? ? datingDataMat, datingLabels=file2matrix('datingTestSet2.txt')? ? normMat, ranges, minVals=autoNorm(datingDataMat)? ? inArr=array([ffMils, percentTats, iceCream])? ? classifierResult=classify0((inArr-minVals)/ranges,normMat,datingLabels,3)print"You will probably like this person:", resultList[classifierResult-1]
實際運行效果如下:
>>>kNN.classifyPerson()percentage of time spent playing video games?10frequent flier miles earned per year?10000liters of ice cream consumed per year?0.5You will probably like this person:insmall doses
完整代碼地址:https://github.com/apachecn/MachineLearning/blob/master/src/python/2.KNN/kNN.py
構造一個能識別數(shù)字 0 到 9 的基于 KNN 分類器的手寫數(shù)字識別系統(tǒng)凝化。
需要識別的數(shù)字是存儲在文本文件中的具有相同的色彩和大小：寬高是 32 像素 * 32 像素的黑白圖像酬荞。
收集數(shù)據(jù)：提供文本文件搓劫。
準備數(shù)據(jù)：編寫函數(shù) img2vector(), 將圖像格式轉換為分類器使用的向量格式
分析數(shù)據(jù)：在 Python 命令提示符中檢查數(shù)據(jù)，確保它符合要求
訓練算法：此步驟不適用于 KNN
測試算法：編寫函數(shù)使用提供的部分數(shù)據(jù)集作為測試樣本混巧，測試樣本與非測試樣本的
區(qū)別在于測試樣本是已經(jīng)完成分類的數(shù)據(jù)枪向，如果預測分類與實際類別不同，
則標記為一個錯誤
使用算法：本例沒有完成此步驟咧党，若你感興趣可以構建完整的應用程序秘蛔，從圖像中提取
數(shù)字，并完成數(shù)字識別，美國的郵件分揀系統(tǒng)就是一個實際運行的類似系統(tǒng)
收集數(shù)據(jù): 提供文本文件
目錄trainingDigits中包含了大約 2000 個例子缠犀，每個例子內(nèi)容如下圖所示数苫，每個數(shù)字大約有 200 個樣本聪舒；目錄testDigits中包含了大約 900 個測試數(shù)據(jù)辨液。
準備數(shù)據(jù): 編寫函數(shù) img2vector(), 將圖像文本數(shù)據(jù)轉換為分類器使用的向量
將圖像文本數(shù)據(jù)轉換為向量
defimg2vector(filename):? ? returnVect=zeros((1,1024))? ? fr=open(filename)foriinrange(32):? ? ? ? lineStr=fr.readLine()forjinrange(32):? ? ? ? ? ? returnVect[0,32*i+j]=int(lineStr[j])returnreturnVect
分析數(shù)據(jù)：在 Python 命令提示符中檢查數(shù)據(jù)，確保它符合要求
在 Python 命令行中輸入下列命令測試 img2vector 函數(shù)箱残，然后與文本編輯器打開的文件進行比較:
>>>testVector=kNN.img2vector('testDigits/0_13.txt')>>>testVector[0,0:31]array([0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,1.,1.,1.,1.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.])>>>testVector[0,31:63]array([0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,1.,1.,1.,1.,1.,1.,1.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.])
訓練算法：此步驟不適用于 KNN
因為測試數(shù)據(jù)每一次都要與全量的訓練數(shù)據(jù)進行比較滔迈，所以這個過程是沒有必要的。
測試算法：編寫函數(shù)使用提供的部分數(shù)據(jù)集作為測試樣本被辑，如果預測分類與實際類別不同燎悍，則標記為一個錯誤
defhandwritingClassTest():#1. 導入訓練數(shù)據(jù)hwLabels=[]? ? trainingFileList=listdir('input/2.KNN/trainingDigits')#load the training setm=len(trainingFileList)? ? trainingMat=zeros((m,1024))#hwLabels存儲0～9對應的index位置， trainingMat存放的每個位置對應的圖片向量foriinrange(m):? ? ? ? fileNameStr=trainingFileList[i]? ? ? ? fileStr=fileNameStr.split('.')[0]#take off .txtclassNumStr=int(fileStr.split('_')[0])? ? ? ? hwLabels.append(classNumStr)#將 32*32的矩陣->1*1024的矩陣trainingMat[i, :]=img2vector('input/2.KNN/trainingDigits/%s'%fileNameStr)#2. 導入測試數(shù)據(jù)testFileList=listdir('input/2.KNN/testDigits')#iterate through the test seterrorCount=0.0mTest=len(testFileList)foriinrange(mTest):? ? ? ? fileNameStr=testFileList[i]? ? ? ? fileStr=fileNameStr.split('.')[0]#take off .txtclassNumStr=int(fileStr.split('_')[0])? ? ? ? vectorUnderTest=img2vector('input/2.KNN/testDigits/%s'%fileNameStr)? ? ? ? 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.0print"\nthe total number of errors is:%d"%errorCountprint"\nthe total error rate is:%f"%(errorCount/float(mTest))
使用算法：本例沒有完成此步驟盼理，若你感興趣可以構建完整的應用程序谈山，從圖像中提取數(shù)字，并完成數(shù)字識別宏怔，美國的郵件分揀系統(tǒng)就是一個實際運行的類似系統(tǒng)
完整代碼地址:https://github.com/apachecn/MachineLearning/blob/master/src/python/2.KNN/kNN.py
GitHub地址:https://github.com/apachecn/MachineLearning
版權聲明：歡迎轉載學習 => 請標注信息來源于ApacheCN
