第2章k近鄰算法

K-近鄰算法（KNN）kNN特點(diǎn)kNN是一種基于向量空間的分類方法該方法非常簡(jiǎn)單，也容易實(shí)現(xiàn)在大多數(shù)情況下，kNN的效果比樸素貝葉斯和中心向量法要好如果你急切需要一種精度很高分類器并很快投入運(yùn)行.....如果你不是特別關(guān)注效率......那么就使用kNN工作原理測(cè)量不同特征值之間的距離方法進(jìn)行分類優(yōu)點(diǎn)：精度高、對(duì)異常值不敏感、無(wú)數(shù)據(jù)輸入假定缺點(diǎn)：計(jì)算復(fù)雜度高、空間復(fù)雜度高適用數(shù)據(jù)范圍：數(shù)值型和標(biāo)稱型計(jì)算新數(shù)據(jù)與樣本數(shù)據(jù)的相似度樣本集（有標(biāo)簽的數(shù)據(jù)集）新數(shù)據(jù)集選擇樣本數(shù)據(jù)集中前k個(gè)最相似的數(shù)據(jù)出現(xiàn)最多的分類作為新數(shù)據(jù)的分類創(chuàng)建數(shù)據(jù)集和標(biāo)簽defcreateDataSet():group=array([[1.0,1.1],[1.0,1.0],[0,0],[0,0.1]])labels=['A','A','B','B']returngroup,labelsK-近鄰算法：帶有4個(gè)數(shù)據(jù)點(diǎn)的數(shù)據(jù)集importkNNgroup,labels=kNN.createDataSet()importmatplotlibimportmatplotlib.pyplotaspltfig=plt.figure()ax=fig.add_subplot(111)ax.scatter(group[:,0],group[:,1])plt.show()kNN算法計(jì)算已知類別數(shù)據(jù)集中的每個(gè)點(diǎn)依次執(zhí)行以下操作：計(jì)算已知類別數(shù)據(jù)集中的點(diǎn)與當(dāng)前點(diǎn)之間的距離按照距離遞增次序排序選取與當(dāng)前點(diǎn)距離最小的k個(gè)點(diǎn)確定前k個(gè)點(diǎn)所在類別的出現(xiàn)頻率返回前k個(gè)點(diǎn)出現(xiàn)頻率最高的類別作為當(dāng)前點(diǎn)的預(yù)測(cè)分類K-近鄰算法defclassify0(inX,dataSet,labels,k):dataSetSize=dataSet.shape[0]diffMat=tile(inX,(dataSetSize,1))-dataSetsqDiffMat=diffMat**2sqDistances=sqDiffMat.sum(axis=1)distances=sqDistances**0.5sortedDistIndicies=distances.argsort()classCount={}foriinrange(k):voteIlabel=labels[sortedDistIndicies[i]]classCount[voteIlabel]=classCount.get(voteIlabel,0)+1sortedClassCount=sorted(classCount.iteritems(),key=operator.itemgetter(1),reverse=True)returnsortedClassCount[0][0]axis=1是將一個(gè)矩陣的每一行向量相加

importnumpyasnpnp.sum([[0,1,2],[2,1,3],axis=1)的結(jié)果就是：array（[3,6]）Classify0()中的參數(shù)輸入?yún)?shù)：inX待分類的輸入向量dataSet輸入的訓(xùn)練樣本集Labels標(biāo)簽向量K用于選擇最近鄰居的數(shù)目計(jì)算兩個(gè)向量點(diǎn)xA和xB之間的歐氏距離一些函數(shù)介紹：Tile(A,n)將數(shù)組A重復(fù)n次，構(gòu)成一個(gè)新的數(shù)組如：A=[0,1,2]B=tile(a,2)Barray([0,1,2,0,1,2])Operator.itemgetter函數(shù)用于獲取對(duì)象的哪些維的數(shù)據(jù)，參數(shù)為一些序號(hào)，如：a=[1,2,3]B=operator.itemgetter(1)B(a)2B=operator.itemgetter(1,0)B(a)(2,1)Python中sorted（）的用法iterable，中文意思是迭代器iteralbe指的是能夠一次返回它的一個(gè)成員的對(duì)象。iterable主要包括3類：第一類是所有的序列類型，比如list(列表)、str(字符串)、tuple(元組)。第二類是一些非序列類型，比如dict(字典)、file(文件)。第三類是你定義的任何包含__iter__()或__getitem__()方法的類的對(duì)象。Sorted用法sorted(iterable[,cmp,[,key[,reverse=True]]])作用：Returnanewsortedlistfromtheitemsiniterable.

第一個(gè)參數(shù)是一個(gè)iterable，返回值是一個(gè)對(duì)iterable中元素進(jìn)行排序后的列表(list)?？蛇x的參數(shù)有三個(gè)，cmp、key和reverse。1)cmp指定一個(gè)定制的比較函數(shù)，這個(gè)函數(shù)接收兩個(gè)參數(shù)（iterable的元素），如果第一個(gè)參數(shù)小于第二個(gè)參數(shù)，返回一個(gè)負(fù)數(shù)；如果第一個(gè)參數(shù)等于第二個(gè)參數(shù)，返回零；如果第一個(gè)參數(shù)大于第二個(gè)參數(shù)，返回一個(gè)正數(shù)。默認(rèn)值為None。2)key指定一個(gè)接收一個(gè)參數(shù)的函數(shù)，這個(gè)函數(shù)用于從每個(gè)元素中提取一個(gè)用于比較的關(guān)鍵字。默認(rèn)值為None。3)reverse是一個(gè)布爾值。如果設(shè)置為T(mén)rue，列表元素將被倒序排列。通常來(lái)說(shuō)，key和reverse比一個(gè)等價(jià)的cmp函數(shù)處理速度要快。這是因?yàn)閷?duì)于每個(gè)列表元素，cmp都會(huì)被調(diào)用多次，而key和reverse只被調(diào)用一次。具體的用法如下：>>>sorted([5,2,3,1,4])[1,2,3,4,5]你也可以使用list的list.sort()方法。這個(gè)方法會(huì)修改原始的list（返回值為None）。通常這個(gè)方法不如sorted()方便-如果你不需要原始的list，list.sort()方法效率會(huì)稍微高一些。>>>a=[5,2,3,1,4]>>>a.sort()>>>a[1,2,3,4,5]另一個(gè)區(qū)別在于list.sort()方法只為list定義。而sorted()函數(shù)可以接收任何的iterable。KeyFunctions(關(guān)鍵字函數(shù))>>>sorted("ThisisateststringfromAndrew".split(),key=str.lower)['a','Andrew','from','is','string','test','This']key的值應(yīng)該是一個(gè)函數(shù)，這個(gè)函數(shù)接收一個(gè)參數(shù)并且返回一個(gè)用于比較的關(guān)鍵字。這種技術(shù)比較快，原因在于對(duì)每個(gè)輸入記錄，這個(gè)函數(shù)只會(huì)被調(diào)用一次。對(duì)復(fù)雜對(duì)象的比較通常是使用對(duì)象的切片作為關(guān)鍵字。例如：>>>student_tuples=[('john','A',15),('jane','B',12),('dave','B',10),]

>>>sorted(student_tuples,key=lambdastudent:student[2])#sortbyage[('dave','B',10),('jane','B',12),('john','A',15)]調(diào)用kNN.createDataSet(),創(chuàng)建數(shù)據(jù)集作為樣本數(shù)據(jù),調(diào)用kNN.classify0(),對(duì)向量[0,0]分類例：使用k-近鄰算法改進(jìn)約會(huì)網(wǎng)站的配對(duì)效果步驟收集數(shù)據(jù)：提供文本文件準(zhǔn)備數(shù)據(jù)：使用python解析文本文件分析數(shù)據(jù)：使用matplotlib畫(huà)二維散點(diǎn)圖訓(xùn)練算法測(cè)試算法：使用提供的部分?jǐn)?shù)據(jù)作為測(cè)試樣本使用算法：產(chǎn)生簡(jiǎn)單的命令行程序，用戶輸入一些特征數(shù)據(jù)以作判斷樣本數(shù)據(jù)（datingTestSet2.txt）1000條數(shù)據(jù)，每條數(shù)據(jù)一行，前三列為特征數(shù)據(jù)，第四列為標(biāo)簽。前三列的含義為：每年獲得的飛行里程數(shù)玩視頻游戲所耗時(shí)間百分比每周消費(fèi)的冰激凌公升數(shù)將文本記錄轉(zhuǎn)換為矩陣file2matrix()deffile2matrix(filename):fr=open(filename)numberOfLines=len(fr.readlines())#getthenumberoflinesinthefilereturnMat=zeros((numberOfLines,3))#preparematrixtoreturnclassLabelVector=[]#preparelabelsreturnfr=open(filename)index=0forlineinfr.readlines():line=line.strip()#截掉\nlistFromLine=line.split(‘\t’)#根據(jù)\t獲得數(shù)組returnMat[index,:]=listFromLine[0:3]classLabelVector.append(int(listFromLine[-1]))#將倒數(shù)第一列字符轉(zhuǎn)換為整數(shù)并添加到標(biāo)簽向量中index+=1returnreturnMat,classLabelVector將導(dǎo)出的樣本文件數(shù)據(jù)畫(huà)出散點(diǎn)圖importkNNdatingDataMat,datingLabels=kNN.file2matrix('datingTestSet2.txt')importmatplotlib.pyplotaspltfig=plt.figure()ax=fig.add_subplot(111)ax.scatter(datingDataMat[:,1],datingDataMat[:,2])plt.show()fig.savefig('ex2_02.png')只取第2和第3個(gè)特征的數(shù)據(jù)集加上顏色和不同大小的散點(diǎn)圖fromnumpyimport*ImportkNNdatingDataMat,datingLabels=kNN.file2matrix(‘datingTestSet2.txt’)importmatplotlibimportmatplotlib.pyplotaspltfig=plt.figure()ax=fig.add_subplot(111)ax.scatter(datingDataMat[:,1],datingDataMat[:,2],15.0*array(datingLabels),15.0*array(datingLabels))繪制不同顏色的點(diǎn)說(shuō)明：Fromnumpyimport*#為了使用arrayax.scatter(datingDataMat[:,1],datingDataMat[:,2],15.0*array(datingLabels),15.0*array(datingLabels))#第三個(gè)參數(shù)表示點(diǎn)的大小#第四個(gè)參數(shù)表示顏色特征數(shù)據(jù)的影響（ex2_05.py)使用前兩列數(shù)據(jù)進(jìn)行繪圖，飛行里程數(shù)對(duì)于計(jì)算結(jié)果的影響遠(yuǎn)大于其它兩個(gè)特征：MatplotlibMatplotlib功能強(qiáng)大：Matlab的語(yǔ)法、python語(yǔ)言、latex的畫(huà)圖質(zhì)量,（還可以使用內(nèi)嵌的latex引擎繪制的數(shù)學(xué)公式）Matplotlib繪圖庫(kù)matplotlib實(shí)際上是一套面向?qū)ο蟮睦L圖庫(kù)，它所繪制的圖表中的每個(gè)繪圖元素，例如線條Line2D、文字Text、刻度等在內(nèi)存中都有一個(gè)對(duì)象與之對(duì)應(yīng)。為了方便快速繪圖matplotlib通過(guò)pyplot模塊提供了一套和MATLAB類似的繪圖API，將眾多繪圖對(duì)象所構(gòu)成的復(fù)雜結(jié)構(gòu)隱藏在這套API內(nèi)部。我們只需要調(diào)用pyplot模塊所提供的函數(shù)就可以實(shí)現(xiàn)快速繪圖以及設(shè)置圖表的各種細(xì)節(jié)。Pyplot模塊雖然用法簡(jiǎn)單，但不適合在較大的應(yīng)用程序中使用。

為了將面向?qū)ο蟮睦L圖庫(kù)包裝成只使用函數(shù)的調(diào)用接口，pyplot模塊的內(nèi)部保存了當(dāng)前圖表以及當(dāng)前子圖等信息。當(dāng)前的圖表和子圖可以使用plt.gcf()和plt.gca()獲得，分別表示“Get

Current

Figure“和"Get

Current

Axes"。在pyplot模塊中，許多函數(shù)都是對(duì)當(dāng)前的Figure或Axes對(duì)象進(jìn)行處理，比如說(shuō)：

plt.plot()實(shí)際上會(huì)通過(guò)plt.gca()獲得當(dāng)前的Axes對(duì)象ax，然后再調(diào)用ax.plot()方法實(shí)現(xiàn)真正的繪圖。

可以在Ipython中輸入類似“plt.plot??“的命令查看pyplot模塊的函數(shù)是如何對(duì)各種繪圖對(duì)象進(jìn)行包裝的Matplotlib舉例importnumpyasnpimportmatplotlib.pyplotaspltplt.figure(1)plt.figure(2)ax1=plt.subplot(211)ax2=plt.subplot(212)x=np.linspace(0,3,100)foriinxrange(5):plt.figure(1)plt.plot(x,np.exp(i*x/3))plt.sca(ax1)plt.plot(x,np.sin(i*x))plt.sca(ax2)plt.plot(x,np.cos(i*x))plt.show()畫(huà)出的圖將畫(huà)出的圖保存下來(lái)fig.savefig(‘temp.png’)數(shù)據(jù)的歸一化處理為了避免特征數(shù)據(jù)由于數(shù)值范圍不一樣而造成對(duì)結(jié)果影響的不同，需要將特征數(shù)據(jù)進(jìn)行歸一化處理newValue=(oldValue-min)/(max-min)歸一化特征值autoNorm(dataSet)defautoNorm(dataSet):minVals=dataSet.min(0)maxVals=dataSet.max(0)ranges=maxVals-minValsnormDataSet=zeros(shape(dataSet))m=dataSet.shape[0]normDataSet=dataSet-tile(minVals,(m,1))normDataSet=normDataSet/tile(ranges,(m,1))#elementwisedividereturnnormDataSet,ranges,minVals歸一化樣本數(shù)據(jù)importkNNdatingDataMat,datingLabels=kNN.file2matrix('datingTestSet2.txt')normMat,ranges,minVals=kNN.autoNorm(datingDataMat)normMatrangesminVals歸一化后的樣本數(shù)據(jù)2.2.4驗(yàn)證分類器defdatingClassTest():hoRatio=0.50#holdout10%datingDataMat,datingLabels=file2matrix('datingTestSet2.txt')#loaddatasetfromfilenormMat,ranges,minVals=autoNorm(datingDataMat)m=normMat.shape[0]numTestVecs=int(m*hoRatio)errorCount=0.0foriinrange(numTestVecs):classifierResult=classify0(normMat[i,:],normMat[numTestVecs:m,:],datingLabels[numTestVecs:m],3)print"theclassifiercamebackwith:%d,therealansweris:%d"%(classifierResult,datingLabels[i])if(classifierResult!=datingLabels[i]):errorCount+=1.0print"thetotalerrorrateis:%f"%(errorCount/float(numTestVecs))printerrorCountimportkNNkNN.datingClassTest()thetotalerrorrateis:0.064000構(gòu)建完整可用的分類系統(tǒng)ClassifyPerson()defclassifyPerson():resultList=['notatall','insmalldoses','inlargedoses']percentTats=float(raw_input("percentageoftimespentplayingvideogames?"))ffMiles=float(raw_input("frequentfliermilesearnedperyear?"))iceCream=float(raw_input("litersoficecreamconsumedperyear?"))datingDataMat,datingLabels=file2matrix('datingTestSet2.txt')normMat,ranges,minVals=autoNorm(datingDataMat)inArr=array([ffMiles,percentTats,iceCream])classifierResult=classify0((inArr-minVals)/ranges,normMat,datingLabels,3)print"Youwillprobablylikethisperson:",resultList[classifierResult-1]運(yùn)行結(jié)果:2.3手寫(xiě)識(shí)別系統(tǒng)收集數(shù)據(jù)：提供文本文件準(zhǔn)備數(shù)據(jù)：編寫(xiě)函數(shù)classify0()，將圖像格式轉(zhuǎn)換為分類器使用的list格式分析數(shù)據(jù)：在python命令提示符中檢查數(shù)據(jù)，確保它符合要求訓(xùn)練算法測(cè)試算法：編寫(xiě)函數(shù)使用提供的部分?jǐn)?shù)據(jù)集作為測(cè)試樣本；使用算法一、準(zhǔn)備數(shù)據(jù)，將圖像轉(zhuǎn)換為測(cè)試向量（ch02/digits/trainingDigits,來(lái)源：/ml)將圖像格式化處理為一個(gè)向量將32*32的二進(jìn)制圖像矩陣轉(zhuǎn)換為1*1024的向量Img2vector()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測(cè)試將圖像轉(zhuǎn)變?yōu)橄蛄縤mportkNNtestVector=kNN.img2vector('digits/testDigits/0_13.txt')testVector[0,0:31]測(cè)試：使用k-近鄰算法識(shí)別手寫(xiě)數(shù)字defhandwritingClassTest():hwLabels=[]trainingFileList=listdir('digits/trainingDigits')#loadthetrainingsetm=len(trainingFileList)trainingMat=zeros((m,1024))foriinrange(m):fileNameStr=trainingFileList[i]fileStr=fileNameStr.split('.')[0]#takeoff.txtclassNumStr=int(fileStr.split('_')[0])