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

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

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

3、能影響運(yùn)行結(jié)果?？梢圆捎脵?quán)值的方法（和該樣本距離小的鄰居權(quán)值大）來改進(jìn)。該方法的另一個(gè)不足之處是計(jì)算量較大，因?yàn)閷?duì)每一個(gè)待分類的文本都要計(jì)算它到全體已知樣本的距離，才能求得它的K個(gè)最近鄰點(diǎn)。目前常用的解決方法是事先對(duì)已知樣本點(diǎn)進(jìn)行剪輯，事先去除對(duì)分類作用不大的樣本。該算法比較適用于樣本容量比較大的類域的自動(dòng)分類，而那些樣本容量較小的類域采用這種算法比較容易產(chǎn)生誤分。 二 試驗(yàn)步驟 那么根據(jù)以上的描述，我把結(jié)合使用反余弦匹配和kNN結(jié)合的過程分成以下幾個(gè)步驟： 1計(jì)算出樣本數(shù)據(jù)和待分類數(shù)據(jù)的距離 2為待分類數(shù)據(jù)選擇k個(gè)與其距離最小的樣本 3統(tǒng)計(jì)出k個(gè)樣本中大多數(shù)樣本所屬的分類 4這個(gè)分類就是待分

4、類數(shù)據(jù)所屬的分類 數(shù)學(xué)表達(dá)：目標(biāo)函數(shù)值可以是離散值(分類問題)，也可以是連續(xù)值(回歸問題).函數(shù)形勢(shì)為f:n維空間R一維空間R。 第一步：將數(shù)據(jù)集分為訓(xùn)練集（DTrn）和測(cè)試集（DTES）。 第二步：在測(cè)試集給定一個(gè)實(shí)例Xq;在訓(xùn)練集（DTrn）中找到與這個(gè)實(shí)例Xq的K-最近鄰子集X1、XK，即：DKNN。 第三步：計(jì)算這K-最近鄰子集得目標(biāo)值，經(jīng)過加權(quán)平均：f(Xq)=(f(X1)+.+f(XK)/k作為f(Xq）的近似估計(jì)。改進(jìn)的地方：對(duì)kNN算法的一個(gè)明顯的改進(jìn)是對(duì)k個(gè)最近鄰的貢獻(xiàn)加權(quán)，將較大的權(quán)值賦給較近的近鄰，相應(yīng)的算法稱為距離加權(quán)kNN回歸算法，則公式1則修改為：f(Xq)=(w1

5、*f(X1)+.+wk*f(XK)/(w1+.wk)一般地距離權(quán)值wi和距離成反比關(guān)系，例如，wi近似=1/d(xq;xi).K值的選擇：需要消除K值過低，預(yù)測(cè)目標(biāo)容易產(chǎn)生變動(dòng)性，同時(shí)高k值時(shí)，預(yù)測(cè)目標(biāo)有過平滑現(xiàn)象。推定k值的有益途徑是通過有效參數(shù)的數(shù)目這個(gè)概念。有效參數(shù)的數(shù)目是和k值相關(guān)的，大致等于n/k，其中，n是這個(gè)訓(xùn)練數(shù)據(jù)集中實(shí)例的數(shù)目。 缺點(diǎn)： （1）在大訓(xùn)練集尋找最近鄰的時(shí)間是難以忍受的。 （2）在訓(xùn)練數(shù)據(jù)集中要求的觀測(cè)值的數(shù)目，隨著維數(shù)p的增長(zhǎng)以指數(shù)方式增長(zhǎng)。這是因?yàn)楹妥罱彽钠谕嚯x隨著維數(shù)p的增多而急劇上升，除非訓(xùn)練數(shù)據(jù)集的大小隨著p以指數(shù)方式增長(zhǎng)。這種現(xiàn)象被稱為“維數(shù)災(zāi)難”

6、。 解決辦法有下面幾個(gè)： （1）通過降維技術(shù)來減少維數(shù)，如主成分分析，因子分析，變量選擇（因子選擇）從而減少計(jì)算距離的時(shí)間； （2）用復(fù)雜的數(shù)據(jù)結(jié)構(gòu)，如搜索樹去加速最近鄰的確定。這個(gè)方法經(jīng)常通過公式2公式1設(shè)定“幾乎是最近鄰”的目標(biāo)去提高搜索速度； （3）編輯訓(xùn)練數(shù)據(jù)去減少在訓(xùn)練集中的冗余和幾乎是冗余的點(diǎn)，從而加速搜索最近鄰。在個(gè)別例子中去掉在訓(xùn)練數(shù)據(jù)集中的一些觀察點(diǎn)，對(duì)分類效果沒有影響，原因是這些點(diǎn)被包圍屬于同類的觀測(cè)點(diǎn)中。 三 注意事項(xiàng) KNN算法的實(shí)現(xiàn)要注意： 1用TreeMapString，TreeMap保存測(cè)試集和訓(xùn)練集。 2注意要以類目_文件名作為每個(gè)文件的key，才能避免同名不同

7、內(nèi)容的文件出現(xiàn)。 3注意設(shè)置JM參數(shù)，否則會(huì)出現(xiàn)JAVAheap溢出錯(cuò)誤。 4本程序用向量夾角余弦計(jì)算相似度。 四 代碼 /KNN.java package cqu.KNN; 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)先級(jí)隊(duì)列的比較函數(shù)，距離越大，優(yōu)先

8、級(jí)越高 */ private Comparator comparator = new Comparator() public int compare(KNNNode o1, KNNNode o2) if (o1.getDistance() = o2.getDistance() return -1; else return 1; ; /* * 獲取K個(gè)不同的隨機(jī)數(shù) * param k 隨機(jī)數(shù)的個(gè)數(shù) * param max 隨機(jī)數(shù)最大的范圍 * return 生成的隨機(jī)數(shù)數(shù)組 */ public List getRandKNum(int k, int max) List rand = new Ar

9、rayList(k); for (int i = 0; i k; i+) int temp = (int) (Math.random() * max); if (!rand.contains(temp) rand.add(temp); else i-; return rand; /* * 計(jì)算測(cè)試元組與訓(xùn)練元組之前的距離 * param d1 測(cè)試元組* param d2 訓(xùn)練元組 * return 距離值 */ public double calDistance(List d1, List d2) double distance = 0.00; for (int i = 0; i d1.si

10、ze(); i+) distance += (d1.get(i) - d2.get(i) * (d1.get(i) - d2.get(i); return distance; /* * 執(zhí)行KNN算法，獲取測(cè)試元組的類別 * param datas 訓(xùn)練數(shù)據(jù)集 * param testData 測(cè)試元組 * param k 設(shè)定的K值 * return 測(cè)試元組的類別 */ public String knn(ListList datas, List testData, int k) PriorityQueue pq = new PriorityQueue(k,comparator); Lis

11、t randNum = getRandKNum(k, datas.size(); for (int i = 0; i k; i+) int index = randNum.get(i); List currData = datas.get(index); String c = currData.get(currData.size()-1).toString(); KNNNode node = new KNNNode(index, calDistance(testData, currData), c); pq.add(node); for (int i = 0; i datas.size();

12、i+) List t = datas.get(i); double distance = calDistance(testData, t); KNNNode top = pq.peek(); if (top.getDistance() distance) pq.remove(); pq.add(new KNNNode(i, distance, t.get(t.size()-1).toString(); return getMostClass(pq); /* * 獲取所得到的k個(gè)最近鄰元組的多數(shù)類 * param pq 存儲(chǔ)k個(gè)最近近鄰元組的優(yōu)先級(jí)隊(duì)列* return 多數(shù)類的名稱 */ pri

13、vate String getMostClass(PriorityQueue pq) Map classCount = 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; i

14、nt maxCount = 0; Object classes = classCount.keySet().toArray(); for (int i = 0; i maxCount) maxIndex = i; maxCount = classCount.get(classesi); return classesmaxIndex.toString(); /KNNNode.java package cqu.KNN; public class KNNNode private int index; / 元組標(biāo)號(hào) private double distance; / 與測(cè)試元組的距離 private

15、 String c; / 所屬類別 public KNNNode(int index, double distance, String 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(doubl

16、e distance) this.distance = distance; public String getC() return c; public void setC(String c) this.c = c; /TestKNN.java package cqu.KNN; import java.io.BufferedReader; import java.io.File; import java.io.FileReader; import java.util.ArrayList; import java.util.List; / KNN算法測(cè)試類 public class TestKNN

17、 /* * 從數(shù)據(jù)文件中讀取數(shù)據(jù) * param datas 存儲(chǔ)數(shù)據(jù)的集合對(duì)象 * param path 數(shù)據(jù)文件的路徑 */ public void 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();

18、 for (int i = 0; i t.length; i+) list.add(Double.parseDouble(ti); datas.add(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.separa

19、tor + cqudatadatafile.txt; String testfile = new File().getAbsolutePath() + File.separator + cqudatatestfile.txt; try ListList datas = new ArrayListList(); ListList testDatas = new ArrayListList(); t.read(datas, datafile); t.read(testDatas, testfile); KNN knn = new KNN(); for (int i = 0; i testDatas

20、.size(); i+) List test = testDatas.get(i); System.out.print(測(cè)試元組: ); 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(); 五 運(yùn)行測(cè)試 訓(xùn)練數(shù)據(jù)： 1.0 1.1 1.2 2