2024年KNN算法實(shí)驗(yàn)報告

KNN算法試驗(yàn)匯報一試驗(yàn)原理K近來鄰(k-NearestNeighbor，KNN)分類算法，是一種理論上比較成熟的措施，也是最簡樸的機(jī)器學(xué)習(xí)算法之一。該措施的思緒是：假如一種樣本在特性空間中的k個最相似(即特性空間中最鄰近)的樣本中的大多數(shù)屬于某一種類別，則該樣本也屬于這個類別。KNN算法中，所選擇的鄰居都是已經(jīng)對的分類的對象。該措施在定類決策上只根據(jù)最鄰近的一種或者幾種樣本的類別來決定待分樣本所屬的類別。KNN措施雖然從原理上也依賴于極限定理，但在類別決策時，只與很少許的相鄰樣本有關(guān)。由于KNN措施重要靠周圍有限的鄰近的樣本，而不是靠鑒別類域的措施來確定所屬類別的，因此對于類域的交叉或重疊較多的待分樣本集來說，KNN措施較其他措施更為適合。KNN算法不僅可以用于分類，還可以用于回歸。通過找出一種樣本的k個近來鄰居，將這些鄰居的屬性的平均值賦給該樣本，就可以得到該樣本的屬性。更有用的措施是將不一樣距離的鄰居對該樣本產(chǎn)生的影響予以不一樣的權(quán)值(weight)，如權(quán)值與距離成正比。該算法在分類時有個重要的局限性是，當(dāng)樣本不平衡時，如一種類的樣本容量很大，而其他類樣本容量很小時，有也許導(dǎo)致當(dāng)輸入一種新樣本時，該樣本的K個鄰居中大容量類的樣本占多數(shù)。該算法只計(jì)算“近來的”鄰居樣本，某一類的樣本數(shù)量很大，那么或者此類樣本并不靠近目的樣本，或者此類樣本很靠近目的樣本。無論怎樣，數(shù)量并不能影響運(yùn)行成果?？梢圆捎脵?quán)值的措施（和該樣本距離小的鄰居權(quán)值大）來改善。該措施的另一種局限性之處是計(jì)算量較大，由于對每一種待分類的文本都要計(jì)算它到全體已知樣本的距離，才能求得它的K個近來鄰點(diǎn)。目前常用的處理措施是事先對已知樣本點(diǎn)進(jìn)行剪輯，事先清除對分類作用不大的樣本。該算法比較合用于樣本容量比較大的類域的自動分類，而那些樣本容量較小的類域采用這種算法比較輕易產(chǎn)生誤分。二試驗(yàn)環(huán)節(jié)那么根據(jù)以上的描述，我把結(jié)合使用反余弦匹配和kNN結(jié)合的過程提成如下幾種環(huán)節(jié)：1．計(jì)算出樣本數(shù)據(jù)和待分類數(shù)據(jù)的距離2．為待分類數(shù)據(jù)選擇k個與其距離最小的樣本3．記錄出k個樣本中大多數(shù)樣本所屬的分類4．這個分類就是待分類數(shù)據(jù)所屬的分類數(shù)學(xué)體現(xiàn)：目的函數(shù)值可以是離散值(分類問題)，也可以是持續(xù)值(回歸問題).函數(shù)形勢為f:n維空間R—〉一維空間R。第一步：將數(shù)據(jù)集分為訓(xùn)練集（DTrn）和測試集（DTES）。第二步：在測試集給定一種實(shí)例Xq;在訓(xùn)練集（DTrn）中找到與這個實(shí)例Xq的K-近來鄰子集{X1、、、、XK}，即：DKNN。第三步：計(jì)算這K-近來鄰子集得目的值，通過加權(quán)平均：^f(Xq)=(f(X1)+...+f(XK))/k作為f(Xq）的近似估計(jì)。改善的地方：對kNN算法的一種明顯的改善是對k個近來鄰的奉獻(xiàn)加權(quán)，將較大的權(quán)值賦給較近的近鄰，對應(yīng)的算法稱為距離加權(quán)kNN回歸算法，則公式1則修改為：^f(Xq)=(w1*f(X1)+...+wk*f(XK))/(w1+...wk)一般地距離權(quán)值wi和距離成反比關(guān)系，例如，wi近似=1/d(xq;xi).K值的選擇：需要消除K值過低，預(yù)測目的輕易產(chǎn)生變動性，同步高k值時，預(yù)測目的有過平滑現(xiàn)象。推定k值的有益途徑是通過有效參數(shù)的數(shù)目這個概念。有效參數(shù)的數(shù)目是和k值有關(guān)的，大體等于n/k，其中，n是這個訓(xùn)練數(shù)據(jù)集中實(shí)例的數(shù)目。缺陷：（1）在大訓(xùn)練集尋找近來鄰的時間是難以忍受的。（2）在訓(xùn)練數(shù)據(jù)集中規(guī)定的觀測值的數(shù)目，伴隨維數(shù)p的增長以指數(shù)方式增長。這是由于和近來鄰的期望距離伴隨維數(shù)p的增多而急劇上升，除非訓(xùn)練數(shù)據(jù)集的大小伴隨p以指數(shù)方式增長。這種現(xiàn)象被稱為“維數(shù)劫難”。處理措施有下面幾種：（1）通過降維技術(shù)來減少維數(shù)，如主成分分析，因子分析，變量選擇（因子選擇）從而減少計(jì)算距離的時間；（2）用復(fù)雜的數(shù)據(jù)構(gòu)造，如搜索樹去加速近來鄰確實(shí)定。這個措施常常通過公式2公式1設(shè)定“幾乎是近來鄰”的目的去提高搜索速度；（3）編輯訓(xùn)練數(shù)據(jù)去減少在訓(xùn)練集中的冗余和幾乎是冗余的點(diǎn)，從而加速搜索近來鄰。在個別例子中去掉在訓(xùn)練數(shù)據(jù)集中的某些觀測點(diǎn)，對分類效果沒有影響，原因是這些點(diǎn)被包圍屬于同類的觀測點(diǎn)中。三注意事項(xiàng)KNN算法的實(shí)現(xiàn)要注意：1．用TreeMap<String，TreeMap<String，Double>>保留測試集和訓(xùn)練集。2．注意要以"類目_文獻(xiàn)名"作為每個文獻(xiàn)的key，才能防止同名不一樣內(nèi)容的文獻(xiàn)出現(xiàn)。3．注意設(shè)置JM參數(shù)，否則會出現(xiàn)JAVAheap溢出錯誤。4．本程序用向量夾角余弦計(jì)算相似度。四代碼//KNN.javapackagecqu.KNN;importjava.util.ArrayList;importjava.util.Comparator;importjava.util.HashMap;importjava.util.List;importjava.util.Map;importjava.util.PriorityQueue;//KNN算法主體類publicclassKNN{/***設(shè)置優(yōu)先級隊(duì)列的比較函數(shù)，距離越大，優(yōu)先級越高*/privateComparator<KNNNode>comparator=newComparator<KNNNode>(){publicintcompare(KNNNodeo1,KNNNodeo2){if(o1.getDistance()>=o2.getDistance()){ return-1;}else{ return1;}}};/***獲取K個不一樣的隨機(jī)數(shù)*@paramk隨機(jī)數(shù)的個數(shù)*@parammax隨機(jī)數(shù)最大的范圍*@return生成的隨機(jī)數(shù)數(shù)組*/publicList<Integer>getRandKNum(intk,intmax){List<Integer>rand=newArrayList<Integer>(k);for(inti=0;i<k;i++){inttemp=(int)(Math.random()*max);if(!rand.contains(temp)){rand.add(temp);}else{i--;}}returnrand;}/***計(jì)算測試元組與訓(xùn)練元組之前的距離*@paramd1測試元組*@paramd2訓(xùn)練元組*@return距離值*/publicdoublecalDistance(List<Double>d1,List<Double>d2){doubledistance=0.00;for(inti=0;i<d1.size();i++){distance+=(d1.get(i)-d2.get(i))*(d1.get(i)-d2.get(i));}returndistance;}/***執(zhí)行KNN算法，獲取測試元組的類別*@paramdatas訓(xùn)練數(shù)據(jù)集*@paramtestData測試元組*@paramk設(shè)定的K值*@return測試元組的類別*/publicStringknn(List<List<Double>>datas,List<Double>testData,intk){PriorityQueue<KNNNode>pq=newPriorityQueue<KNNNode>(k,comparator);List<Integer>randNum=getRandKNum(k,datas.size());for(inti=0;i<k;i++){intindex=randNum.get(i);List<Double>currData=datas.get(index);Stringc=currData.get(currData.size()-1).toString();KNNNodenode=newKNNNode(index,calDistance(testData,currData),c);pq.add(node);}for(inti=0;i<datas.size();i++){List<Double>t=datas.get(i);doubledistance=calDistance(testData,t);KNNNodetop=pq.peek();if(top.getDistance()>distance){pq.remove();pq.add(newKNNNode(i,distance,t.get(t.size()-1).toString()));}}returngetMostClass(pq);}/***獲取所得到的k個近來鄰元組的多數(shù)類*@parampq存儲k個近來近鄰元組的優(yōu)先級隊(duì)列*@return多數(shù)類的名稱*/privateStringgetMostClass(PriorityQueue<KNNNode>pq){Map<String,Integer>classCount=newHashMap<String,Integer>();intpqsize=pq.size();for(inti=0;i<pqsize;i++){KNNNodenode=pq.remove();Stringc=node.getC();if(classCount.containsKey(c)){classCount.put(c,classCount.get(c)+1);}else{classCount.put(c,1);}}intmaxIndex=-1;intmaxCount=0;Object[]classes=classCount.keySet().toArray();for(inti=0;i<classes.length;i++){if(classCount.get(classes[i])>maxCount){maxIndex=i;maxCount=classCount.get(classes[i]);}}returnclasses[maxIndex].toString();}}//KNNNode.javapackagecqu.KNN;publicclassKNNNode{privateintindex;//元組標(biāo)號privatedoubledistance;//與測試元組的距離privateStringc;//所屬類別publicKNNNode(intindex,doubledistance,Stringc){super();this.index=index;this.distance=distance;this.c=c;}publicintgetIndex(){returnindex;}publicvoidsetIndex(intindex){this.index=index;}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.util.List;//KNN算法測試類publicclassTestKNN{/***從數(shù)據(jù)文獻(xiàn)中讀取數(shù)據(jù)*@paramdatas存儲數(shù)據(jù)的集合對象*@parampath數(shù)據(jù)文獻(xiàn)的途徑*/publicvoidread(List<List<Double>>datas,Stringpath){try{BufferedReaderbr=newBufferedReader(newFileReader(newFile(path)));Stringreader=br.readLine();while(reader!=null){Stringt[]=reader.split("");ArrayList<Double>list=newArrayList<Double>();for(inti=0;i<t.length;i++){list.add(Double.parseDouble(t[i]));}datas.add(list);reader=br.readLine();}}catch(Exceptione){e.printStackTrace();}}/***程序執(zhí)行入口*@paramargs*/publicstaticvoidmain(String[]args){TestKNNt=newTestKNN();Stringdatafile=newFile("").getAbsolutePath()+File.separator+"cqudata\\datafile.txt";Stringtestfile=newFile("").getAbsolutePath()+File.separator+"cqudata\\testfile.txt";try{List<List<Double>>datas=newArrayList<List<Double>>();List<List<Double>>testDatas=newArrayList<List<Double>>();t.read(datas,datafile);t.read(testDatas,testfile);KNNknn=newKNN();for(inti=0;i<testDatas.size();i++){List<Double>test=testDatas.get(i);System.out.print("測試元組:");for(intj=0;j<test.size();j++){System.out.print(test.get(j)+"");}System.out.print("類別為:");System.out.println(Math.round(Float.parseFloat((knn.knn(datas,