(完整版)KNN算法實驗報告

1、KNNKNN 算法實驗報告算法實驗報告一試驗原理一試驗原理K 最近鄰(k-NearestNeighbor,KNN)分類算法，是一個理論上比較成熟的方法，也是最簡單的機器學習算法之一。該方法的思路是：如果一個樣本在特征空間中的 k 個最相似(即特征空間中最鄰近)的樣本中的大多數(shù)屬于某一個類別，則該樣本也屬于這個類別。KNN 算法中，所選擇的鄰居都是已經(jīng)正確分類的對象。該方法在定類決策上只依據(jù)最鄰近的一個或者幾個樣本的類別來決定待分樣本所屬的類別。KNN 方法雖然從原理上也依賴于極限定理，但在類別決策時， 只與極少量的相鄰樣本有關。 由于 KNN 方法主要靠周圍有限的鄰近的樣本， 而不是靠判別類域

2、的方法來確定所屬類別的， 因此對于類域的交叉或重疊較多的待分樣本集來說， KNN 方法較其他方法更為適合。KNN 算法不僅可以用于分類，還可以用于回歸。通過找出一個樣本的 k 個最近鄰居， 將這些鄰居的屬性的平均值賦給該樣本， 就可以得到該樣本的屬性。 更有用的方法是將不同距離的鄰居對該樣本產(chǎn)生的影響給予不同的權值(weight)，如權值與距離成正比。該算法在分類時有個主要的不足是，當樣本不平衡時，如一個類的樣本容量很大， 而其他類樣本容量很小時， 有可能導致當輸入一個新樣本時，該樣本的 K 個鄰居中大容量類的樣本占多數(shù)。該算法只計算“最近的”鄰居樣本， 某一類的樣本數(shù)量很大， 那么或者這類樣

3、本并不接近目標樣本，或者這類樣本很靠近目標樣本。無論怎樣，數(shù)量并不能影響運行結果?？梢圆捎脵嘀档姆椒ǎê驮摌颖揪嚯x小的鄰居權值大）來改進。 該方法的另一個不足之處是計算量較大， 因為對每一個待分類的文本都要計算它到全體已知樣本的距離， 才能求得它的 K 個最近鄰點。目前常用的解決方法是事先對已知樣本點進行剪輯， 事先去除對分類作用不大的樣本。該算法比較適用于樣本容量比較大的類域的自動分類，而那些樣本容量較小的類域采用這種算法比較容易產(chǎn)生誤分。二試驗步驟二試驗步驟那么根據(jù)以上的描述，我把結合使用反余弦匹配和 kNN結合的過程分成以下幾個步驟：1計算出樣本數(shù)據(jù)和待分類數(shù)據(jù)的距離2.為待分類數(shù)據(jù)選擇

4、 k個與其距離最小的樣本3統(tǒng)計出 k個樣本中大多數(shù)樣本所屬的分類4這個分類就是待分類數(shù)據(jù)所屬的分類數(shù)學表達：目標函數(shù)值可以是離散值（分類問題），也可以是連續(xù)值（回歸問題）.函數(shù)形勢為 f:n維空間 R一維空間 R。第一步：將數(shù)據(jù)集分為訓練集（DTrn）和測試集（DTES）。第二步：在測試集給定一個實例 Xq;在訓練集（DTrn）中找到與這個實例 Xq的 K-最近鄰子集XI、XK,即：DKNNo第三步：計算這 K-最近鄰子集得目標值，經(jīng)過加權平均：Af（Xq）=（f（Xl）+.+f（XK）/k作為 f（Xq）的近似估計。改進的地方：對 kNN算法的一個明顯的改進是對 k 個最近鄰的貢獻加權，將較

5、大的權值賦給較近的近鄰，相應的算法稱為距離加權 kNN回歸算法，則公式 1則修改為：Af(Xq)=(wl*f(Xl)+.+wk*f(XK)/(wl+.wk)般地距離權值 wi 和距離成反比關系，例如，wi 近似=1/d(xq;xi).K值的選擇：需要消除 K值過低，預測目標容易產(chǎn)生變動性，同時高 k 值時,預測目標有過平滑現(xiàn)象。 推定 k 值的有益途徑是通過有效參數(shù)的數(shù)目這個概念。有效參數(shù)的數(shù)目是和 k值相關的，大致等于 nk,其中，n 是這個訓練數(shù)據(jù)集中實例的數(shù)目。缺點：(1) 在大訓練集尋找最近鄰的時間是難以忍受的。(2) 在訓練數(shù)據(jù)集中要求的觀測值的數(shù)目， 隨著維數(shù) p 的增長以指數(shù)方式

6、增長。 這是因為和最近鄰的期望距離隨著維數(shù) p 的增多而急劇上升， 除非訓練數(shù)據(jù)集的大小隨著 p以指數(shù)方式增長。 這種現(xiàn)象被稱為“維數(shù)災難”。解決辦法有下面幾個：(1) 通過降維技術來減少維數(shù)，如主成分分析，因子分析，變量選擇(因子選擇)從而減少計算距離的時間；(2) 用復雜的數(shù)據(jù)結構，如搜索樹去加速最近鄰的確定。這個方法經(jīng)常通過公式 2公式 1設定“幾乎是最近鄰”的目標去提高搜索速度；(3) 編輯訓練數(shù)據(jù)去減少在訓練集中的冗余和幾乎是冗余的點， 從而加速搜索最近鄰。在個別例子中去掉在訓練數(shù)據(jù)集中的一些觀察點，對分類效果沒有影響，原因是這些點被包圍屬于同類的觀測點中。三注意事項三注意事項KNN

7、 算法的實現(xiàn)要注意：1. 用 TreeMapvString,TreeMapvString,Double保存測試集和訓練集。2. 注意要以類目_文件名作為每個文件的 key,才能避免同名不同內(nèi)容的文件出現(xiàn)。3. 注意設置 JM 參數(shù)，否則會出現(xiàn) JAVAheap溢出錯誤。4. 本程序用向量夾角余弦計算相似度。四代碼四代碼/KNN.java/KNN.javapackagecqu.KNN;importjava.util.ArrayList;importjava.util.Comparator;importjava.util.HashMap;importjava.util.List;importjav

8、a.util.Map;importjava.util.PriorityQueue;/KNN 算法主體類publicclassKNN/*設置優(yōu)先級隊列的比較函數(shù)，距離越大，優(yōu)先級越高*/privateComparatorcomparator=newComparator()publicintcompare(KNNNodeo1,KNNNodeo2)if(o1.getDistance()=o2.getDistance()return-1;elsereturn1;/*獲取 K 個不同的隨機數(shù)*paramk 隨機數(shù)的個數(shù)*parammax 隨機數(shù)最大的范圍*return 生成的隨機數(shù)數(shù)組*/publicL

9、istgetRandKNum(intk,intmax)Listrand=newArrayList(k);for(inti=0;ik;i+)inttemp=(int)(Math.random()*max);if(!rand.contains(temp)rand.add(temp);elsei-;returnrand;/*計算測試元組與訓練元組之前的距離*paramdl 測試元組*paramd2 訓練元組*return 距離值*/publicdoublecalDistance(Listdl,Listd2)doubledistance=0.00;for(inti=0;idl.size();i+)di

10、stance+=(dl.get(i)-d2.get(i)*(dl.get(i)-d2.get(i);returndistance;/*執(zhí)行 KNN 算法，獲取測試元組的類別*paramdatas 訓練數(shù)據(jù)集*paramtestData 測試元組*paramk 設定的 K 值*return 測試元組的類別*/publicStringknn(ListListdatas,ListtestData,intk)PriorityQueuepq=newPriorityQueue(k,comparator);ListrandNum=getRandKNum(k,datas.size();for(inti=0;i

11、k;i+)intindex=randNum.get(i);ListcurrData=datas.get(index);Stringc=currData.get(currData.size()-1).toString();KNNNodenode=newKNNNode(index,calDistance(testData,currData),c);pq.add(node);for(inti=0;idatas.size();i+)Listt=datas.get(i);doubledistance=calDistance(testData,t);KNNNodetop=pq.peek();if(top.

12、getDistance()distance)pq.remove();pq.add(newKNNNode(i,distance,t.get(t.size()-1).toString();returngetMostClass(pq);/*獲取所得到的 k 個最近鄰元組的多數(shù)類*parampq 存儲 k 個最近近鄰元組的優(yōu)先級隊列*return 多數(shù)類的名稱*/privateStringgetMostClass(PriorityQueuepq)MapclassCount=newHashMap();intpqsize=pq.size();for(inti=0;ipqsize;i+)KNNNodenod

13、e=pq.remove();Stringc=node.getC();if(classCount.containsKey(c)classCount.put(c,classCount.get(c)+1);elseclassCount.put(c,1);intmaxIndex=-1;intmaxCount=0;Objectclasses=classCount.keySet().toArray();for(inti=0;imaxCount)maxIndex=i;maxCount=classCount.get(classesi);returnclassesmaxIndex.toString();/KNN

14、Node/KNNNode.javajavapackagecqu.KNN;publicclassKNNNodeprivateintindex;/元組標號privatedoubledistance;/與測試元組的距離privateStringc;/所屬類別publicKNNNode(intindex,doubledistance,Stringc)super();this.index=index;this.distance=distance;this.c=c;publicintgetIndex()returnindex;publicvoidsetIndex(intindex)this.index=i

15、ndex;publicdoublegetDistance()returndistance;publicvoidsetDistance(doubledistance)this.distance=distance;publicStringgetC()returnc;publicvoidsetC(Stringc)this.c=c;/TestKNN.javapackagecqu.KNN;importjava.io.BufferedReader;importjava.io.File;importjava.io.FileReader;importjava.util.ArrayList;importjava

16、.util.List;/KNN 算法測試類publicclassTestKNN/*從數(shù)據(jù)文件中讀取數(shù)據(jù)*paramdatas 存儲數(shù)據(jù)的集合對象*parampath 數(shù)據(jù)文件的路徑*/publicvoidread(ListListdatas,Stringpath)tryBufferedReaderbr=newBufferedReader(newFileReader(newFile(path);Stringreader=br.readLine();while(reader!=null)Stringt=reader.split();ArrayListlist=newArrayList();for(

17、inti=0;it.length;i+)list.add(Double.parseDouble(ti);datas.add(list);reader=br.readLine();catch(Exceptione)e.printStackTrace();/*程序執(zhí)行入口*paramargs*/publicstaticvoidmain(Stringargs)TestKNNt=newTestKNN();Stringdatafile=newFile().getAbsolutePath()+File.separator+cqudatadatafile.txt;Stringtestfile=newFile

18、().getAbsolutePath()+File.separator+cqudatatestfile.txt;tryListListdatas=newArrayListList();ListListtestDatas=newArrayListList();t.read(datas,datafile);t.read(testDatas,testfile);KNNknn=newKNN();for(inti=0;itestDatas.size();i+)Listtest=testDatas.get(i);System.out.print(測試元組：)；for(intj=0;jtest.size();j+)System.out.print(test.get(j)+);System.out.print(類別為：)；System.out.println(Math.round(Float.parseFloat(knn.knn(data