KNN算法實驗報告

1、knn算法實驗報告knn算法實驗報告 編輯整理：尊敬的讀者朋友們：這里是精品文檔編輯中心，本文檔內(nèi)容是由我和我的同事精心編輯整理后發(fā)布的，發(fā)布之前我們對文中內(nèi)容進行仔細校對，但是難免會有疏漏的地方，但是任然希望（knn算法實驗報告）的內(nèi)容能夠給您的工作和學(xué)習(xí)帶來便利。同時也真誠的希望收到您的建議和反饋，這將是我們進步的源泉，前進的動力。本文可編輯可修改，如果覺得對您有幫助請收藏以便隨時查閱，最后祝您生活愉快 業(yè)績進步，以下為knn算法實驗報告的全部內(nèi)容。 knn算法實驗報告一 試驗原理k最近鄰（knearestneighbor,knn)分類算法，是一個理論上比較成熟的方法，也是最簡單的機器學(xué)習(xí)

2、算法之一。該方法的思路是：如果一個樣本在特征空間中的k個最相似(即特征空間中最鄰近)的樣本中的大多數(shù)屬于某一個類別，則該樣本也屬于這個類別。knn算法中，所選擇的鄰居都是已經(jīng)正確分類的對象。該方法在定類決策上只依據(jù)最鄰近的一個或者幾個樣本的類別來決定待分樣本所屬的類別.knn方法雖然從原理上也依賴于極限定理，但在類別決策時，只與極少量的相鄰樣本有關(guān)。由于knn方法主要靠周圍有限的鄰近的樣本，而不是靠判別類域的方法來確定所屬類別的,因此對于類域的交叉或重疊較多的待分樣本集來說，knn方法較其他方法更為適合。knn算法不僅可以用于分類,還可以用于回歸。通過找出一個樣本的k個最近鄰居,將這些鄰居的屬

3、性的平均值賦給該樣本，就可以得到該樣本的屬性。更有用的方法是將不同距離的鄰居對該樣本產(chǎn)生的影響給予不同的權(quán)值(weight)，如權(quán)值與距離成正比。該算法在分類時有個主要的不足是，當(dāng)樣本不平衡時，如一個類的樣本容量很大,而其他類樣本容量很小時,有可能導(dǎo)致當(dāng)輸入一個新樣本時，該樣本的k個鄰居中大容量類的樣本占多數(shù).該算法只計算“最近的”鄰居樣本，某一類的樣本數(shù)量很大,那么或者這類樣本并不接近目標(biāo)樣本,或者這類樣本很靠近目標(biāo)樣本。無論怎樣，數(shù)量并不能影響運行結(jié)果.可以采用權(quán)值的方法（和該樣本距離小的鄰居權(quán)值大)來改進。該方法的另一個不足之處是計算量較大，因為對每一個待分類的文本都要計算它到全體已知樣

4、本的距離，才能求得它的k個最近鄰點。目前常用的解決方法是事先對已知樣本點進行剪輯,事先去除對分類作用不大的樣本。該算法比較適用于樣本容量比較大的類域的自動分類，而那些樣本容量較小的類域采用這種算法比較容易產(chǎn)生誤分。二 試驗步驟那么根據(jù)以上的描述，我把結(jié)合使用反余弦匹配和knn結(jié)合的過程分成以下幾個步驟:1計算出樣本數(shù)據(jù)和待分類數(shù)據(jù)的距離2為待分類數(shù)據(jù)選擇k個與其距離最小的樣本3統(tǒng)計出k個樣本中大多數(shù)樣本所屬的分類4這個分類就是待分類數(shù)據(jù)所屬的分類數(shù)學(xué)表達：目標(biāo)函數(shù)值可以是離散值(分類問題），也可以是連續(xù)值(回歸問題）.函數(shù)形勢為f:n維空間r一維空間r。第一步：將數(shù)據(jù)集分為訓(xùn)練集（dtrn）和

5、測試集（dtes）.第二步：在測試集給定一個實例xq;在訓(xùn)練集（dtrn）中找到與這個實例xq的k最近鄰子集x1、xk,即：dknn。第三步:計算這k最近鄰子集得目標(biāo)值，經(jīng)過加權(quán)平均:f（xq)=（f（x1)+。+f(xk)）/k作為f(xq）的近似估計。改進的地方：對knn算法的一個明顯的改進是對k個最近鄰的貢獻加權(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ù)測目標(biāo)容易產(chǎn)

6、生變動性,同時高k值時，預(yù)測目標(biāo)有過平滑現(xiàn)象。推定k值的有益途徑是通過有效參數(shù)的數(shù)目這個概念。有效參數(shù)的數(shù)目是和k值相關(guān)的，大致等于n/k,其中，n是這個訓(xùn)練數(shù)據(jù)集中實例的數(shù)目。缺點:（1）在大訓(xùn)練集尋找最近鄰的時間是難以忍受的。(2）在訓(xùn)練數(shù)據(jù)集中要求的觀測值的數(shù)目，隨著維數(shù)p的增長以指數(shù)方式增長。這是因為和最近鄰的期望距離隨著維數(shù)p的增多而急劇上升，除非訓(xùn)練數(shù)據(jù)集的大小隨著p以指數(shù)方式增長。這種現(xiàn)象被稱為“維數(shù)災(zāi)難”。解決辦法有下面幾個：（1）通過降維技術(shù)來減少維數(shù)，如主成分分析，因子分析，變量選擇（因子選擇)從而減少計算距離的時間；（2）用復(fù)雜的數(shù)據(jù)結(jié)構(gòu)，如搜索樹去加速最近鄰的確定.這個

7、方法經(jīng)常通過公式2公式1設(shè)定“幾乎是最近鄰”的目標(biāo)去提高搜索速度；（3)編輯訓(xùn)練數(shù)據(jù)去減少在訓(xùn)練集中的冗余和幾乎是冗余的點,從而加速搜索最近鄰。在個別例子中去掉在訓(xùn)練數(shù)據(jù)集中的一些觀察點，對分類效果沒有影響，原因是這些點被包圍屬于同類的觀測點中。三 注意事項knn算法的實現(xiàn)要注意：1用treemapstring，treemapstring,double保存測試集和訓(xùn)練集。2注意要以”類目_文件名作為每個文件的key，才能避免同名不同內(nèi)容的文件出現(xiàn)。3注意設(shè)置jm參數(shù)，否則會出現(xiàn)javaheap溢出錯誤。4本程序用向量夾角余弦計算相似度。四 代碼/knn.javapackage cqu。knn;

8、import java.util.arraylist； import java.util。comparator； import java.util。hashmap; import java.util。list; import java。util.map；import java。util。priorityqueue; /knn算法主體類 public class knn / 設(shè)置優(yōu)先級隊列的比較函數(shù)，距離越大，優(yōu)先級越高 */ private comparator comparator = new comparatorknnnode（) public int compare（knnnode o1

9、, knnnode o2） if (o1。getdistance（) = o2.getdistance（) return -1； else return 1； ； / * 獲取k個不同的隨機數(shù) param k 隨機數(shù)的個數(shù) param max 隨機數(shù)最大的范圍 return 生成的隨機數(shù)數(shù)組 */ public listinteger getrandknum(int k, int max) listinteger rand = new arraylistinteger(k)； for （int i = 0; i k; i+） int temp = (int) (math。random（） *

10、max); if (！rand。contains(temp)） rand.add(temp）; else i-； return rand; / 計算測試元組與訓(xùn)練元組之前的距離 * param d1 測試元組* param d2 訓(xùn)練元組 * return 距離值 */ public double caldistance(listdouble d1， listdouble d2) double distance = 0。00； for (int i = 0； i d1。size(); i+） distance += （d1.get（i) d2.get（i) * (d1。get（i) d2。ge

11、t(i)）; return distance; /* 執(zhí)行knn算法，獲取測試元組的類別 * param datas 訓(xùn)練數(shù)據(jù)集 param testdata 測試元組 param k 設(shè)定的k值 * return 測試元組的類別 */ public string knn(listlist testdata， int k） priorityqueueknnnode pq = new priorityqueueknnnode(k，comparator）； listinteger randnum = getrandknum（k, datas.size(）； for （int i = 0; i k；

12、 i+） int index = randnum。get（i); list distance) pq。remove(）; pq。add（new knnnode(i， distance, t。get(t.size()-1).tostring(); return getmostclass（pq); /* * 獲取所得到的k個最近鄰元組的多數(shù)類 param pq 存儲k個最近近鄰元組的優(yōu)先級隊列* return 多數(shù)類的名稱 */ private string getmostclass(priorityqueueknnnode pq) mapstring, integer classcount =

13、new hashmap(）； int pqsize = pq。size（)； for (int i = 0； i pqsize; i+） knnnode node = pq。remove(）; string c = node.getc（); if (classcount.containskey（c） classcount。put(c, classcount.get（c） + 1）； else classcount。put（c, 1)； int maxindex = 1; int maxcount = 0; object classes = classcount。keyset().toarray

14、(); for (int i = 0； i maxcount) maxindex = i； maxcount = classcount。get(classesi）； return classesmaxindex.tostring(); /knnnode.javapackage cqu.knn;public class knnnode private int index； / 元組標(biāo)號 private double distance; / 與測試元組的距離 private string c; / 所屬類別 public knnnode(int index， double distance， st

15、ring c） super（）； this。index = index； this.distance = distance； this。c = c; public int getindex(） return index; public void setindex(int index) this.index = index; public double getdistance（) return distance; public void setdistance(double distance) this.distance = distance； public string getc（) retu

16、rn c; public void setc(string c) this。c = c； /testknn。javapackage cqu.knn；import java。io。bufferedreader；import java。io。file；import java.io。filereader;import java。util.arraylist;import java.util.list； / knn算法測試類 public class testknn /* 從數(shù)據(jù)文件中讀取數(shù)據(jù) param datas 存儲數(shù)據(jù)的集合對象 param path 數(shù)據(jù)文件的路徑 / public void

17、 read（listlist datas, string path) try bufferedreader br = new bufferedreader（new filereader（new file(path）); string reader = br.readline(); while (reader ！= null) string t = reader。split（” ”)； arraylist list = new arraylist(）； for （int i = 0； i t.length； i+） list.add(double.parsedouble(ti）; datas。a

18、dd(list）； reader = br.readline(）； catch （exception e) e.printstacktrace（）; /* 程序執(zhí)行入口 * param args */ public static void main（string args) testknn t = new testknn(); string datafile = new file(”).getabsolutepath（） + file。separator + cqudatadatafile。txt”; string testfile = new file(”)。getabsolutepath(

19、) + file。separator + ”cqudatatestfile.txt”； try list datas = new arraylistlistdouble()； listlistdouble testdatas = new arraylist(); t.read(datas， datafile）； t。read（testdatas， testfile）； knn knn = new knn(）; for (int i = 0; i testdatas.size（); i+） list test = testdatas。get（i）; system.out。print（測試元組： ）； for （int j = 0； j test.size（); j+) system。out.print（test.get（j) + ）； system。out.print（”類別為： ); system.out.println（math.round(float.parsefloat(（knn.knn（datas, test, 3）)）); catch （exception e) e。printstacktrace（)； 五 運行測試訓(xùn)練數(shù)據(jù)： 1。0 1.1 1.2 2.1