第3章-k-近鄰算法-(《統(tǒng)計學(xué)習(xí)方法》課件)

第三章

k-近鄰算法第三章

k-近鄰算法1分類問題分類問題2分類問題分類問題3愛情片、劇情片、喜劇片、家庭片、倫理片、

文藝片、音樂片、歌舞片、動漫片、

西部片、武俠片、古裝片、動作片、

恐怖片、驚悚片、冒險片、犯罪片、懸疑片、

記錄片、戰(zhàn)爭片、歷史片、傳記片、體育片、

科幻片、魔幻片、奇幻片

愛情片、劇情片、喜劇片、家庭片、倫理片、

文藝片、音樂片、歌4SupervisedlearningSupervisedlearning5提綱KNN算法原理和流程Python程序調(diào)試Python文件類型模塊Idle調(diào)試環(huán)境數(shù)據(jù)載入算法和關(guān)鍵函數(shù)分析算法改進和實驗作業(yè)提綱KNN算法原理和流程6K-NearestNeighbors算法原理?Dependentofthedatadistributions.Canmakemistakesatboundaries.K=7NeighborhoodK=1NeighborhoodK-NearestNeighbors算法原理?Depend7K-NearestNeighbors算法特點優(yōu)點精度高對異常值不敏感無數(shù)據(jù)輸入假定缺點計算復(fù)雜度高空間復(fù)雜度高適用數(shù)據(jù)范圍數(shù)值型和標稱型

K-NearestNeighbors算法特點優(yōu)點8K-NearestNeighborsAlgorithm工作原理存在一個樣本數(shù)據(jù)集合，也稱作訓(xùn)練樣本集，并且樣本集中每個數(shù)據(jù)都存在標簽，即我們知道樣本集中每個數(shù)據(jù)與所屬分類的對應(yīng)關(guān)系。輸入沒有標簽的新數(shù)據(jù)后，將新數(shù)據(jù)的每個特征與樣本集中數(shù)據(jù)對應(yīng)的特征進行比較，然后算法提取樣本集中特征最相似數(shù)據(jù)（最近鄰）的分類標簽。一般來說，只選擇樣本數(shù)據(jù)集中前N個最相似的數(shù)據(jù)。K一般不大于20，最后，選擇k個中出現(xiàn)次數(shù)最多的分類，作為新數(shù)據(jù)的分類K-NearestNeighborsAlgorithm工9K近鄰算法的一般流程

收集數(shù)據(jù)：可以使用任何方法準備數(shù)據(jù)：距離計算所需要的數(shù)值，最后是結(jié)構(gòu)化的數(shù)據(jù)格式。分析數(shù)據(jù)：可以使用任何方法訓(xùn)練算法：（此步驟kNN）中不適用測試算法：計算錯誤率使用算法：首先需要輸入樣本數(shù)據(jù)和結(jié)構(gòu)化的輸出結(jié)果，然后運行k-近鄰算法判定輸入數(shù)據(jù)分別屬于哪個分類，最后應(yīng)用對計算出的分類執(zhí)行后續(xù)的處理。K近鄰算法的一般流程 收集數(shù)據(jù)：可以使用任何方法10距離度量Lp距離：歐式距離：曼哈頓距離L∞距離距離度量11距離度量距離度量12K值的選擇如果選擇較小的K值“學(xué)習(xí)”的近似誤差（approximationerror)會減小，但“學(xué)習(xí)”的估計誤差（estimationerror)會增大，噪聲敏感K值的減小就意味著整體模型變得復(fù)雜，容易發(fā)生過擬合.如果選擇較大的K值，減少學(xué)習(xí)的估計誤差，但缺點是學(xué)習(xí)的近似誤差會增大.K值的增大就意味著整體的模型變得簡單.K值的選擇如果選擇較小的K值13Python程序調(diào)試Python傳統(tǒng)運行模式：Python解釋器：運行Python程序的程序；Python字節(jié)碼：Python將程序編譯后所得到的底層形式；Python自動將字節(jié)碼保存為名為.pyc的文件中；錄入的源碼轉(zhuǎn)換為字節(jié)碼->字節(jié)碼在PVM（Python虛擬機）中運行->代碼自動被編譯，之后再解釋m.pym.pycPVM源代碼字節(jié)碼運行時Python程序調(diào)試Python傳統(tǒng)運行模式：m.pym.p14Python程序調(diào)試Python無“build”和“make”的步驟，代碼寫好后立即運行Python字節(jié)碼不是機器的二進制代碼（so不能像C++運行速度那么快，其速度介于傳統(tǒng)編譯語言和傳統(tǒng)解釋語言之間）raw_input（）的使用Python程序調(diào)試Python無“build”和“make15Python模塊每一個.py文件都是一個模塊，其他文件可以通過導(dǎo)入一個模塊讀取這個模塊的內(nèi)容，相當(dāng)于C中的include……一個大型程序往往呈現(xiàn)出多模塊的形式。其中一個模塊文件被設(shè)計為主文件（or頂層文件）。模塊是Python程序最大的程序結(jié)構(gòu)每個模塊文件是一個獨立完備的變量包裝，即一個命名空間Python模塊每一個.py文件都是一個模塊，其他文件可以通16模塊的導(dǎo)入import，from和reloadimport語句將模塊作為一個整體引用，相當(dāng)于引入一個類的object。From增加了對變量名的額外賦值，也就是拷貝模塊的屬性，因此能夠以主模塊導(dǎo)入，而不是原來的對象例子：A=“this”B=“is”C=“test”PrintA，B，CImporttest1Test1.AFromtestimport*A模塊的導(dǎo)入import，from和reload17Reload和重編譯修改文件如kNN注意Reload（）或者：重新編譯importpy_compilepy_pile('D:\python\machinelearninginaction\Ch02\kNN.py')最好不要用中文，如果需要，用編碼轉(zhuǎn)換工具codecReload和重編譯修改文件如kNN注意18Idle調(diào)試環(huán)境Idle的使用：Copy的結(jié)果是什么？For語句Reload的好處修改程序，顯示修改時間Import和fromAimport*的關(guān)系空間，如numpyIdle調(diào)試環(huán)境19Python導(dǎo)入數(shù)據(jù)>>>importos>>>os.getcwd()'D:\\python'>>>os.chdir('D:\\python\\machinelearninginaction\\Ch02')>>>os.getcwd()'D:\\python\\machinelearninginaction\\Ch02'>>>open('.\\testDigits\\0_0.txt')<openfile'.\\testDigits\\0_0.txt',mode'r'at0x00D1FCD8>Python導(dǎo)入數(shù)據(jù)>>>importos20Python導(dǎo)入數(shù)據(jù)fromnumpyimport*>>>importoperator>>>defcreateDataSet(): group=array([[1.0,1.1],[1.0,1.0],[0,0],[0,0.1]]) labels=['A','A','B','B'] returngroup,lables>>>group,labels=kNN.createDataSet()Python導(dǎo)入數(shù)據(jù)21算法和關(guān)鍵函數(shù)分析分類算法流程和關(guān)鍵函數(shù)ShapeTileArgsort字典的使用文本中解析數(shù)據(jù)文件讀取相關(guān)函數(shù)用matplotlib繪制散點圖數(shù)據(jù)歸一化使用k-近鄰算法的手寫識別系統(tǒng)算法和關(guān)鍵函數(shù)分析分類算法流程和關(guān)鍵函數(shù)22分類算法流程對未知類別的數(shù)據(jù)集中的每個點依次執(zhí)行以下操作計算已知類別數(shù)據(jù)集眾多點與當(dāng)前點之間的距離按照距離遞增次序排序選取與當(dāng)前點距離最小的k個點群定前k個點所在類別的出現(xiàn)頻率返回前k個點出現(xiàn)頻率最高的類別作為當(dāng)前點的預(yù)測分類分類算法流程對未知類別的數(shù)據(jù)集中的每個點依次執(zhí)行以下操作23分類算法kNN中的分類算法：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={}foriteminrange(k):voteIlabel=labels[sortedDistIndicies[item]]classCount[voteIlabel]=classCount.get(voteIlabel,0)+1sortedClassCount=sorted(classCount.iteritems(),key=operator.itemgetter(1),reverse=True)returnsortedClassCount[0][0]分類算法kNN中的分類算法：24Shape函數(shù)group,labels=kNN.createDataSet()group.shapegroup.shape[0]Shape函數(shù)group,labels=kNN.create25Tile函數(shù)tile([1.0,1.2],(4,1))array([[1.,1.2],[1.,1.2],[1.,1.2],[1.,1.2]])tile([1.0,1.2],(4,1))-grouparray([[0.,0.1],[0.,0.2],[1.,1.2],[1.,1.1]])a=(tile([1.0,1.2],(4,1))-group)**2array([[0.,0.01],[0.,0.04],[1.,1.44],[1.,1.21]])Tile函數(shù)tile([1.0,1.2],(4,1))26Argsort（）b=a.sum(axis=1)c=b**0.5d=c.argsort()>>>darray([0,1,3,2])Argsort（）b=a.sum(axis=1)27字典的使用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]kNN.classify0([0,0.2],group,labels,3)'B'字典的使用classCount={}#字28從文本文件中解析數(shù)據(jù)-打開文件deffile2matrix(filename):fr=open(filename)numberOfLines=len(fr.readlines())#getthenumberoflinesinthefilereturnMat=zeros((numberOfLines,3))#preparematrixtoreturnclassLabelVector=[]#preparelabelsreturnfr=open(filename)index=0

從文本文件中解析數(shù)據(jù)-打開文件deffile2matrix29從文本文件中解析數(shù)據(jù)-獲得數(shù)據(jù)forlineinfr.readlines():line=line.strip()listFromLine=line.split(‘\t’)截取掉所有回車符號，\t分割成列表returnMat[index,:]=listFromLine[0:3]classLabelVector.append(int(listFromLine[-1]))index+=1returnreturnMat,classLabelVector從文本文件中解析數(shù)據(jù)-獲得數(shù)據(jù)forlineinfr.30文件讀取相關(guān)函數(shù)Open()的使用Readlines的使用Zeros()的使用文件讀取相關(guān)函數(shù)Open()的使用31文件讀取相關(guān)函數(shù)Open()的使用工作路徑和絕對路徑Readlines的使用Zeros()的使用fr=open('test1.txt')>>>forlineinfr.readlines(): printline執(zhí)行a=fr.readlines()>>>a結(jié)果是什么呢？>>>fr.seek(0)>>>a=fr.readlines()文件讀取相關(guān)函數(shù)Open()的使用32文件讀取相關(guān)函數(shù)>>>a=fr.readlines()>>>a['13412\n','57813\n','9101114']>>>b=a[0]>>>b'13412\n'>>>c=b.strip()>>>c'13412'>>>d=c.split('\t')>>>d['13412']>>>d[0]'13412'>>>文件讀取相關(guān)函數(shù)>>>a=fr.readlines()33文件讀取相關(guān)函數(shù)forlineina: line=line.strip() line=line.split() printline

['1','3','4','12']['5','7','8','13']['9','10','11','14']文件讀取相關(guān)函數(shù)forlineina:34文件讀取相關(guān)函數(shù)forlineina: line=line.strip() line=line.split() printline

['1','3','4','12']['5','7','8','13']['9','10','11','14']文件讀取相關(guān)函數(shù)forlineina:35文件讀取相關(guān)函數(shù)forlineina: line=line.strip() line=line.split() line=[int(x)forxinline] printline

[1,3,4,12][5,7,8,13][9,10,11,14]文件讀取相關(guān)函數(shù)forlineina:36數(shù)組和矩陣Python數(shù)組和numpy矩陣的關(guān)系>>>a=[[1,2,3,4],[5,6,7,8],[9,10,11,12]]>>>c=zeros((3,4))>>>carray([[0.,0.,0.,0.],[0.,0.,0.,0.],[0.,0.,0.,0.]])>>>c[0,:]=a[0]>>>carray([[1.,2.,3.,4.],[0.,0.,0.,0.],[0.,0.,0.,0.]])數(shù)組和矩陣Python數(shù)組和numpy矩陣的關(guān)系37解析數(shù)據(jù)fr=open('datingTestSet.txt')>>>a=fr.readlines()b=len(a)line=a[0]line=line.strip()list=line.split('\t')>>>r[0,:]=list[0:3]rList[-1]ClassLat=[]classLab.append(list[-1])>>>classLab解析數(shù)據(jù)fr=open('datingTestSet.txt38使用Matplotlib創(chuàng)建散點圖importmatplotlib>>>importmatplotlib.pyplotasplt>>>fig=plt.figure()>>>ax=fig.add_subplot(111)>>>ax.scatter(datingDataMat[:,1],datingDataMat[:,2])<matplotlib.collections.PathCollectionobjectat0x01D8F590>>>>plt.show()使用Matplotlib創(chuàng)建散點圖importmatplo39

使用Matplotlib創(chuàng)建散點圖>>>fig=plt.figure()>>>ax=fig.add_subplot(111)>>>ax.scatter(datingDataMat[:,1],datingDataMat[:,2],15.0*array(datingLabels),15.0*array(datingLabels))>>>plt.show()

使用Matplotlib創(chuàng)建散點圖>>>fig=plt.40數(shù)據(jù)歸一化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ù)歸一化defautoNorm(dataSet):41數(shù)據(jù)歸一化>>>n,r,m=kNN.autoNorm(datingDataMat)>>>narray([[0.44832535,0.39805139,0.56233353],[0.15873259,0.34195467,0.98724416],[0.28542943,0.06892523,0.47449629],...,[0.29115949,0.50910294,0.51079493],[0.52711097,0.43665451,0.4290048],[0.47940793,0.3768091,0.78571804]])>>>rarray([9.12730000e+04,2.09193490e+01,1.69436100e+00])>>>marray([0.,0.,0.001156])數(shù)據(jù)歸一化>>>n,r,m=kNN.autoNorm(da42測試算法：驗證分類器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))printerrorCount測試算法：驗證分類器defdatingClassTest(43使用k-近鄰算法的手寫識別系統(tǒng)準備數(shù)據(jù)，將圖像轉(zhuǎn)換為測試向量32x32defimg2vector(filename):returnVect=zeros((1,1024))fr=open(filename)foriinrange(32):lineStr=fr.readline()forjinrange(32):returnVect[0,32*i+j]=int(lineStr[j])returnreturnVect使用k-近鄰算法的手寫識別系統(tǒng)準備數(shù)據(jù)，將圖像轉(zhuǎn)換為測試向量44測試算法>>>testVector=kNN.img2vector('testDigits/0_13.txt')>>>tesVector[0,0:31]測試算法>>>testVector=kNN.img2vec45KNN算法改進和實驗作業(yè)KNN面臨的挑戰(zhàn)算法改進距離度量馬氏距離KD樹實驗要求KNN算法改進和實驗作業(yè)KNN面臨的挑戰(zhàn)46KNN面臨的挑戰(zhàn)Instance-BasedLearningNoexplicitdescriptionofthetargetfunctionCanhandlecomplicatedsituations.KNN面臨的挑戰(zhàn)Instance-BasedLearnin47KNN面臨挑戰(zhàn)K值確定Non-monotonousimpactonaccuracyTooBigvs.TooSmallRuleofthumbs特征的選擇Differentfeaturesmayhavedifferentimpact…距離函數(shù)確定Therearemanydifferentwaystomeasurethedistance.Euclidean,Manhattan…復(fù)雜度NeedtocalculatethedistancebetweenX′andalltrainingdata.Inproportiontothesizeofthetrainingdata.KAccuracyKNN面臨挑戰(zhàn)K值確定KAccuracy48DistanceMetricsDistanceMetrics49MahalanobisDistance馬氏距離DistancefromapointtoapointsetMahalanobisDistance馬氏距離Distan50馬氏距離(MahalanobisDistance)由P.C.Mahalanobis提出基于樣本分布的一種距離測量考慮到各種特性之間的聯(lián)系（例如身高和體重），可以消除樣本間的相關(guān)性廣泛用于分類和聚類分析馬氏距離(MahalanobisDistance)由P.C51一維數(shù)據(jù)馬氏距離(MahalanobisDistance)例：[0,8,12,20]8.3

[8,9,11,12]

1.8均值：

標準差：

方差：

多維向量一維數(shù)據(jù)馬氏距離(MahalanobisDistance)52協(xié)方差矩陣協(xié)方差矩陣53協(xié)方差矩陣協(xié)方差矩陣54馬氏距離

定義馬氏距離定義55馬氏距離

定義續(xù)馬氏距離定義續(xù)56馬氏距離

計算示例馬氏距離計算示例57馬氏距離

NUMPY示例importnumpyx=numpy.array([[3,4],[5,6],[2,2],[8,4]])xT=x.TD=numpy.cov(xT)invD=numpy.linalg.inv(D)tp=x[0]–x[1]printnumpy.sqrt(dot(dot(tp,invD),tp.T))馬氏距離NUMPY示例importnumpy58MahalanobisDistanceForidentitymatrixS:FordiagonalmatrixS:MahalanobisDistanceForident59KD樹kd樹是一種對K維空間中的實例點進行存儲以便對其進行快速檢索的樹形數(shù)據(jù)結(jié)構(gòu).Kd樹是二叉樹，表示對K維空間的一個劃分（partition).構(gòu)造Kd樹相當(dāng)于不斷地用垂直于坐標軸的超平面將k維空間切分，構(gòu)成一系列的k維超矩形區(qū)域.Kd樹的每個結(jié)點對應(yīng)于一個k維超矩形區(qū)域.KD樹kd樹是一種對K維空間中的實例點進行存儲以便對其進行快60KD樹構(gòu)造kd樹：對深度為j的節(jié)點，選擇xl為切分的坐標軸例：KD樹構(gòu)造kd樹：61KD樹{(2,3),(5,4),(9,6),(4,7),(8,1),(7,2)}，建立索引KD樹{(2,3),(5,4),(9,6),(4,7),(62KD樹搜索KD樹搜索63第3章--k-近鄰算法--(《統(tǒng)計學(xué)習(xí)方法》課件)64作業(yè)要求作業(yè)里包含如下文件：源代碼（改進部分要有注釋），實驗報告：包含對改進算法的描述以及實驗結(jié)果對比情況。給分依據(jù)：代碼質(zhì)量（包含可讀性），改進算法難度實驗報告的詳細性。若有疑惑，可聯(lián)系助教邱鑫。作業(yè)要求作業(yè)里包含如下文件：65

Q&A？Q&A？66第三章

k-近鄰算法第三章

k-近鄰算法67分類問題分類問題68分類問題分類問題69愛情片、劇情片、喜劇片、家庭片、倫理片、

文藝片、音樂片、歌舞片、動漫片、

西部片、武俠片、古裝片、動作片、

恐怖片、驚悚片、冒險片、犯罪片、懸疑片、

記錄片、戰(zhàn)爭片、歷史片、傳記片、體育片、

科幻片、魔幻片、奇幻片

愛情片、劇情片、喜劇片、家庭片、倫理片、

文藝片、音樂片、歌70SupervisedlearningSupervisedlearning71提綱KNN算法原理和流程Python程序調(diào)試Python文件類型模塊Idle調(diào)試環(huán)境數(shù)據(jù)載入算法和關(guān)鍵函數(shù)分析算法改進和實驗作業(yè)提綱KNN算法原理和流程72K-NearestNeighbors算法原理?Dependentofthedatadistributions.Canmakemistakesatboundaries.K=7NeighborhoodK=1NeighborhoodK-NearestNeighbors算法原理?Depend73K-NearestNeighbors算法特點優(yōu)點精度高對異常值不敏感無數(shù)據(jù)輸入假定缺點計算復(fù)雜度高空間復(fù)雜度高適用數(shù)據(jù)范圍數(shù)值型和標稱型

K-NearestNeighbors算法特點優(yōu)點74K-NearestNeighborsAlgorithm工作原理存在一個樣本數(shù)據(jù)集合，也稱作訓(xùn)練樣本集，并且樣本集中每個數(shù)據(jù)都存在標簽，即我們知道樣本集中每個數(shù)據(jù)與所屬分類的對應(yīng)關(guān)系。輸入沒有標簽的新數(shù)據(jù)后，將新數(shù)據(jù)的每個特征與樣本集中數(shù)據(jù)對應(yīng)的特征進行比較，然后算法提取樣本集中特征最相似數(shù)據(jù)（最近鄰）的分類標簽。一般來說，只選擇樣本數(shù)據(jù)集中前N個最相似的數(shù)據(jù)。K一般不大于20，最后，選擇k個中出現(xiàn)次數(shù)最多的分類，作為新數(shù)據(jù)的分類K-NearestNeighborsAlgorithm工75K近鄰算法的一般流程

收集數(shù)據(jù)：可以使用任何方法準備數(shù)據(jù)：距離計算所需要的數(shù)值，最后是結(jié)構(gòu)化的數(shù)據(jù)格式。分析數(shù)據(jù)：可以使用任何方法訓(xùn)練算法：（此步驟kNN）中不適用測試算法：計算錯誤率使用算法：首先需要輸入樣本數(shù)據(jù)和結(jié)構(gòu)化的輸出結(jié)果，然后運行k-近鄰算法判定輸入數(shù)據(jù)分別屬于哪個分類，最后應(yīng)用對計算出的分類執(zhí)行后續(xù)的處理。K近鄰算法的一般流程 收集數(shù)據(jù)：可以使用任何方法76距離度量Lp距離：歐式距離：曼哈頓距離L∞距離距離度量77距離度量距離度量78K值的選擇如果選擇較小的K值“學(xué)習(xí)”的近似誤差（approximationerror)會減小，但“學(xué)習(xí)”的估計誤差（estimationerror)會增大，噪聲敏感K值的減小就意味著整體模型變得復(fù)雜，容易發(fā)生過擬合.如果選擇較大的K值，減少學(xué)習(xí)的估計誤差，但缺點是學(xué)習(xí)的近似誤差會增大.K值的增大就意味著整體的模型變得簡單.K值的選擇如果選擇較小的K值79Python程序調(diào)試Python傳統(tǒng)運行模式：Python解釋器：運行Python程序的程序；Python字節(jié)碼：Python將程序編譯后所得到的底層形式；Python自動將字節(jié)碼保存為名為.pyc的文件中；錄入的源碼轉(zhuǎn)換為字節(jié)碼->字節(jié)碼在PVM（Python虛擬機）中運行->代碼自動被編譯，之后再解釋m.pym.pycPVM源代碼字節(jié)碼運行時Python程序調(diào)試Python傳統(tǒng)運行模式：m.pym.p80Python程序調(diào)試Python無“build”和“make”的步驟，代碼寫好后立即運行Python字節(jié)碼不是機器的二進制代碼（so不能像C++運行速度那么快，其速度介于傳統(tǒng)編譯語言和傳統(tǒng)解釋語言之間）raw_input（）的使用Python程序調(diào)試Python無“build”和“make81Python模塊每一個.py文件都是一個模塊，其他文件可以通過導(dǎo)入一個模塊讀取這個模塊的內(nèi)容，相當(dāng)于C中的include……一個大型程序往往呈現(xiàn)出多模塊的形式。其中一個模塊文件被設(shè)計為主文件（or頂層文件）。模塊是Python程序最大的程序結(jié)構(gòu)每個模塊文件是一個獨立完備的變量包裝，即一個命名空間Python模塊每一個.py文件都是一個模塊，其他文件可以通82模塊的導(dǎo)入import，from和reloadimport語句將模塊作為一個整體引用，相當(dāng)于引入一個類的object。From增加了對變量名的額外賦值，也就是拷貝模塊的屬性，因此能夠以主模塊導(dǎo)入，而不是原來的對象例子：A=“this”B=“is”C=“test”PrintA，B，CImporttest1Test1.AFromtestimport*A模塊的導(dǎo)入import，from和reload83Reload和重編譯修改文件如kNN注意Reload（）或者：重新編譯importpy_compilepy_pile('D:\python\machinelearninginaction\Ch02\kNN.py')最好不要用中文，如果需要，用編碼轉(zhuǎn)換工具codecReload和重編譯修改文件如kNN注意84Idle調(diào)試環(huán)境Idle的使用：Copy的結(jié)果是什么？For語句Reload的好處修改程序，顯示修改時間Import和fromAimport*的關(guān)系空間，如numpyIdle調(diào)試環(huán)境85Python導(dǎo)入數(shù)據(jù)>>>importos>>>os.getcwd()'D:\\python'>>>os.chdir('D:\\python\\machinelearninginaction\\Ch02')>>>os.getcwd()'D:\\python\\machinelearninginaction\\Ch02'>>>open('.\\testDigits\\0_0.txt')<openfile'.\\testDigits\\0_0.txt',mode'r'at0x00D1FCD8>Python導(dǎo)入數(shù)據(jù)>>>importos86Python導(dǎo)入數(shù)據(jù)fromnumpyimport*>>>importoperator>>>defcreateDataSet(): group=array([[1.0,1.1],[1.0,1.0],[0,0],[0,0.1]]) labels=['A','A','B','B'] returngroup,lables>>>group,labels=kNN.createDataSet()Python導(dǎo)入數(shù)據(jù)87算法和關(guān)鍵函數(shù)分析分類算法流程和關(guān)鍵函數(shù)ShapeTileArgsort字典的使用文本中解析數(shù)據(jù)文件讀取相關(guān)函數(shù)用matplotlib繪制散點圖數(shù)據(jù)歸一化使用k-近鄰算法的手寫識別系統(tǒng)算法和關(guān)鍵函數(shù)分析分類算法流程和關(guān)鍵函數(shù)88分類算法流程對未知類別的數(shù)據(jù)集中的每個點依次執(zhí)行以下操作計算已知類別數(shù)據(jù)集眾多點與當(dāng)前點之間的距離按照距離遞增次序排序選取與當(dāng)前點距離最小的k個點群定前k個點所在類別的出現(xiàn)頻率返回前k個點出現(xiàn)頻率最高的類別作為當(dāng)前點的預(yù)測分類分類算法流程對未知類別的數(shù)據(jù)集中的每個點依次執(zhí)行以下操作89分類算法kNN中的分類算法：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={}foriteminrange(k):voteIlabel=labels[sortedDistIndicies[item]]classCount[voteIlabel]=classCount.get(voteIlabel,0)+1sortedClassCount=sorted(classCount.iteritems(),key=operator.itemgetter(1),reverse=True)returnsortedClassCount[0][0]分類算法kNN中的分類算法：90Shape函數(shù)group,labels=kNN.createDataSet()group.shapegroup.shape[0]Shape函數(shù)group,labels=kNN.create91Tile函數(shù)tile([1.0,1.2],(4,1))array([[1.,1.2],[1.,1.2],[1.,1.2],[1.,1.2]])tile([1.0,1.2],(4,1))-grouparray([[0.,0.1],[0.,0.2],[1.,1.2],[1.,1.1]])a=(tile([1.0,1.2],(4,1))-group)**2array([[0.,0.01],[0.,0.04],[1.,1.44],[1.,1.21]])Tile函數(shù)tile([1.0,1.2],(4,1))92Argsort（）b=a.sum(axis=1)c=b**0.5d=c.argsort()>>>darray([0,1,3,2])Argsort（）b=a.sum(axis=1)93字典的使用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]kNN.classify0([0,0.2],group,labels,3)'B'字典的使用classCount={}#字94從文本文件中解析數(shù)據(jù)-打開文件deffile2matrix(filename):fr=open(filename)numberOfLines=len(fr.readlines())#getthenumberoflinesinthefilereturnMat=zeros((numberOfLines,3))#preparematrixtoreturnclassLabelVector=[]#preparelabelsreturnfr=open(filename)index=0

從文本文件中解析數(shù)據(jù)-打開文件deffile2matrix95從文本文件中解析數(shù)據(jù)-獲得數(shù)據(jù)forlineinfr.readlines():line=line.strip()listFromLine=line.split(‘\t’)截取掉所有回車符號，\t分割成列表returnMat[index,:]=listFromLine[0:3]classLabelVector.append(int(listFromLine[-1]))index+=1returnreturnMat,classLabelVector從文本文件中解析數(shù)據(jù)-獲得數(shù)據(jù)forlineinfr.96文件讀取相關(guān)函數(shù)Open()的使用Readlines的使用Zeros()的使用文件讀取相關(guān)函數(shù)Open()的使用97文件讀取相關(guān)函數(shù)Open()的使用工作路徑和絕對路徑Readlines的使用Zeros()的使用fr=open('test1.txt')>>>forlineinfr.readlines(): printline執(zhí)行a=fr.readlines()>>>a結(jié)果是什么呢？>>>fr.seek(0)>>>a=fr.readlines()文件讀取相關(guān)函數(shù)Open()的使用98文件讀取相關(guān)函數(shù)>>>a=fr.readlines()>>>a['13412\n','57813\n','9101114']>>>b=a[0]>>>b'13412\n'>>>c=b.strip()>>>c'13412'>>>d=c.split('\t')>>>d['13412']>>>d[0]'13412'>>>文件讀取相關(guān)函數(shù)>>>a=fr.readlines()99文件讀取相關(guān)函數(shù)forlineina: line=line.strip() line=line.split() printline

['1','3','4','12']['5','7','8','13']['9','10','11','14']文件讀取相關(guān)函數(shù)forlineina:100文件讀取相關(guān)函數(shù)forlineina: line=line.strip() line=line.split() printline

['1','3','4','12']['5','7','8','13']['9','10','11','14']文件讀取相關(guān)函數(shù)forlineina:101文件讀取相關(guān)函數(shù)forlineina: line=line.strip() line=line.split() line=[int(x)forxinline] printline

[1,3,4,12][5,7,8,13][9,10,11,14]文件讀取相關(guān)函數(shù)forlineina:102數(shù)組和矩陣Python數(shù)組和numpy矩陣的關(guān)系>>>a=[[1,2,3,4],[5,6,7,8],[9,10,11,12]]>>>c=zeros((3,4))>>>carray([[0.,0.,0.,0.],[0.,0.,0.,0.],[0.,0.,0.,0.]])>>>c[0,:]=a[0]>>>carray([[1.,2.,3.,4.],[0.,0.,0.,0.],[0.,0.,0.,0.]])數(shù)組和矩陣Python數(shù)組和numpy矩陣的關(guān)系103解析數(shù)據(jù)fr=open('datingTestSet.txt')>>>a=fr.readlines()b=len(a)line=a[0]line=line.strip()list=line.split('\t')>>>r[0,:]=list[0:3]rList[-1]ClassLat=[]classLab.append(list[-1])>>>classLab解析數(shù)據(jù)fr=open('datingTestSet.txt104使用Matplotlib創(chuàng)建散點圖importmatplotlib>>>importmatplotlib.pyplotasplt>>>fig=plt.figure()>>>ax=fig.add_subplot(111)>>>ax.scatter(datingDataMat[:,1],datingDataMat[:,2])<matplotlib.collections.PathCollectionobjectat0x01D8F590>>>>plt.show()使用Matplotlib創(chuàng)建散點圖importmatplo105

使用Matplotlib創(chuàng)建散點圖>>>fig=plt.figure()>>>ax=fig.add_subplot(111)>>>ax.scatter(datingDataMat[:,1],datingDataMat[:,2],15.0*array(datingLabels),15.0*array(datingLabels))>>>plt.show()

使用Matplotlib創(chuàng)建散點圖>>>fig=plt.106數(shù)據(jù)歸一化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ù)歸一化defautoNorm(dataSet):107數(shù)據(jù)歸一化>>>n,r,m=kNN.autoNorm(datingDataMat)>>>narray([[0.44832535,0.39805139,0.56233353],[0.15873259,0.34195467,0.98724416],[0.28542943,0.06892523,0.47449629],...,[0.29115949,0.50910294,0.51079493],[0.52711097,0.43665451,0.4290048],[0.47940793,0.3768091,0.78571804]])>>>rarray([9.12730000e+04,2.09193490e+01,1.69436100e+00])>>>marray([0.,0.,0.001156])數(shù)據(jù)歸一化>>>n,r,m=kNN.autoNorm(da108測試算法：驗證分類器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))printerrorCount測試算法：驗證分類器defdatingClassTest(109使用k-近鄰算法的手寫識別系統(tǒng)準備數(shù)據(jù)，將圖像轉(zhuǎn)換為測試向量32x32defimg2vector(filename):