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

KNN算法試驗(yàn)匯報(bào)一試驗(yàn)原理K近來(lái)鄰(k-NearestNeighbor，KNN)分類算法，是一種理論上比較成熟的措施，也是最簡(jiǎn)樸的機(jī)器學(xué)習(xí)算法之一。該措施的思緒是：假如一種樣本在特性空間中的k個(gè)最相似(即特性空間中最鄰近)的樣本中的大多數(shù)屬于某一種類別，則該樣本也屬于這個(gè)類別。KNN算法中，所選擇的鄰居都是已經(jīng)對(duì)的分類的對(duì)象。該措施在定類決策上只根據(jù)最鄰近的一種或者幾種樣本的類別來(lái)決定待分樣本所屬的類別。KNN措施雖然從原理上也依賴于極限定理，但在類別決策時(shí)，只與很少許的相鄰樣本有關(guān)。由于KNN措施重要靠周圍有限的鄰近的樣本，而不是靠鑒別類域的措施來(lái)確定所屬類別的，因此對(duì)于類域的交叉或重疊較多的待分樣本集來(lái)說(shuō)，KNN措施較其他措施更為適合。KNN算法不僅可以用于分類，還可以用于回歸。通過(guò)找出一種樣本的k個(gè)近來(lái)鄰居，將這些鄰居的屬性的平均值賦給該樣本，就可以得到該樣本的屬性。更有用的措施是將不一樣距離的鄰居對(duì)該樣本產(chǎn)生的影響予以不一樣的權(quán)值(weight)，如權(quán)值與距離成正比。該算法在分類時(shí)有個(gè)重要的局限性是，當(dāng)樣本不平衡時(shí)，如一種類的樣本容量很大，而其他類樣本容量很小時(shí)，有也許導(dǎo)致當(dāng)輸入一種新樣本時(shí)，該樣本的K個(gè)鄰居中大容量類的樣本占多數(shù)。該算法只計(jì)算“近來(lái)的”鄰居樣本，某一類的樣本數(shù)量很大，那么或者此類樣本并不靠近目的樣本，或者此類樣本很靠近目的樣本。無(wú)論怎樣，數(shù)量并不能影響運(yùn)行成果?？梢圆捎脵?quán)值的措施（和該樣本距離小的鄰居權(quán)值大）來(lái)改善。該措施的另一種局限性之處是計(jì)算量較大，由于對(duì)每一種待分類的文本都要計(jì)算它到全體已知樣本的距離，才能求得它的K個(gè)近來(lái)鄰點(diǎn)。目前常用的處理措施是事先對(duì)已知樣本點(diǎn)進(jìn)行剪輯，事先清除對(duì)分類作用不大的樣本。該算法比較合用于樣本容量比較大的類域的自動(dòng)分類，而那些樣本容量較小的類域采用這種算法比較輕易產(chǎn)生誤分。二試驗(yàn)環(huán)節(jié)那么根據(jù)以上的描述，我把結(jié)合使用反余弦匹配和kNN結(jié)合的過(guò)程提成如下幾種環(huán)節(jié)：1．計(jì)算出樣本數(shù)據(jù)和待分類數(shù)據(jù)的距離2．為待分類數(shù)據(jù)選擇k個(gè)與其距離最小的樣本3．記錄出k個(gè)樣本中大多數(shù)樣本所屬的分類4．這個(gè)分類就是待分類數(shù)據(jù)所屬的分類數(shù)學(xué)體現(xiàn)：目的函數(shù)值可以是離散值(分類問(wèn)題)，也可以是持續(xù)值(回歸問(wèn)題).函數(shù)形勢(shì)為f:n維空間R—〉一維空間R。第一步：將數(shù)據(jù)集分為訓(xùn)練集（DTrn）和測(cè)試集（DTES）。第二步：在測(cè)試集給定一種實(shí)例Xq;在訓(xùn)練集（DTrn）中找到與這個(gè)實(shí)例Xq的K-近來(lái)鄰子集{X1、、、、XK}，即：DKNN。第三步：計(jì)算這K-近來(lái)鄰子集得目的值，通過(guò)加權(quán)平均：^f(Xq)=(f(X1)+...+f(XK))/k作為f(Xq）的近似估計(jì)。改善的地方：對(duì)kNN算法的一種明顯的改善是對(duì)k個(gè)近來(lái)鄰的奉獻(xiàn)加權(quán)，將較大的權(quán)值賦給較近的近鄰，對(duì)應(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值過(guò)低，預(yù)測(cè)目的輕易產(chǎn)生變動(dòng)性，同步高k值時(shí)，預(yù)測(cè)目的有過(guò)平滑現(xiàn)象。推定k值的有益途徑是通過(guò)有效參數(shù)的數(shù)目這個(gè)概念。有效參數(shù)的數(shù)目是和k值有關(guān)的，大體等于n/k，其中，n是這個(gè)訓(xùn)練數(shù)據(jù)集中實(shí)例的數(shù)目。缺陷：（1）在大訓(xùn)練集尋找近來(lái)鄰的時(shí)間是難以忍受的。（2）在訓(xùn)練數(shù)據(jù)集中規(guī)定的觀測(cè)值的數(shù)目，伴隨維數(shù)p的增長(zhǎng)以指數(shù)方式增長(zhǎng)。這是由于和近來(lái)鄰的期望距離伴隨維數(shù)p的增多而急劇上升，除非訓(xùn)練數(shù)據(jù)集的大小伴隨p以指數(shù)方式增長(zhǎng)。這種現(xiàn)象被稱為“維數(shù)劫難”。處理措施有下面幾種：（1）通過(guò)降維技術(shù)來(lái)減少維數(shù)，如主成分分析，因子分析，變量選擇（因子選擇）從而減少計(jì)算距離的時(shí)間；（2）用復(fù)雜的數(shù)據(jù)構(gòu)造，如搜索樹(shù)去加速近來(lái)鄰確實(shí)定。這個(gè)措施常常通過(guò)公式2公式1設(shè)定“幾乎是近來(lái)鄰”的目的去提高搜索速度；（3）編輯訓(xùn)練數(shù)據(jù)去減少在訓(xùn)練集中的冗余和幾乎是冗余的點(diǎn)，從而加速搜索近來(lái)鄰。在個(gè)別例子中去掉在訓(xùn)練數(shù)據(jù)集中的某些觀測(cè)點(diǎn)，對(duì)分類效果沒(méi)有影響，原因是這些點(diǎn)被包圍屬于同類的觀測(cè)點(diǎn)中。三注意事項(xiàng)KNN算法的實(shí)現(xiàn)要注意：1．用TreeMap<String，TreeMap<String，Double>>保留測(cè)試集和訓(xùn)練集。2．注意要以"類目_文獻(xiàn)名"作為每個(gè)文獻(xiàn)的key，才能防止同名不一樣內(nèi)容的文獻(xiàn)出現(xiàn)。3．注意設(shè)置JM參數(shù)，否則會(huì)出現(xiàn)JAVAheap溢出錯(cuò)誤。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)先級(jí)隊(duì)列的比較函數(shù)，距離越大，優(yōu)先級(jí)越高*/privateComparator<KNNNode>comparator=newComparator<KNNNode>(){publicintcompare(KNNNodeo1,KNNNodeo2){if(o1.getDistance()>=o2.getDistance()){ return-1;}else{ return1;}}};/***獲取K個(gè)不一樣的隨機(jī)數(shù)*@paramk隨機(jī)數(shù)的個(gè)數(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ì)算測(cè)試元組與訓(xùn)練元組之前的距離*@paramd1測(cè)試元組*@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算法，獲取測(cè)試元組的類別*@paramdatas訓(xùn)練數(shù)據(jù)集*@paramtestData測(cè)試元組*@paramk設(shè)定的K值*@return測(cè)試元組的類別*/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個(gè)近來(lái)鄰元組的多數(shù)類*@parampq存儲(chǔ)k個(gè)近來(lái)近鄰元組的優(yōu)先級(jí)隊(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)號(hào)privatedoubledistance;//與測(cè)試元組的距離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算法測(cè)試類publicclassTestKNN{/***從數(shù)據(jù)文獻(xiàn)中讀取數(shù)據(jù)*@paramdatas存儲(chǔ)數(shù)據(jù)的集合對(duì)象*@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("測(cè)試元組:");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,