算法實(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è)樣本的類別來(lái)決定待分樣本所屬的類別。KNN方法雖然從原理上也依賴于極限定理，但在類別決策時(shí)，只與極少量的相鄰樣本有關(guān)。由于KNN方法主要靠周圍有限的鄰近的樣本，而不是靠判別類域的方法來(lái)確定所屬類別的，因此對(duì)于類域的交叉或重

2、疊較多的待分樣本集來(lái)說(shuō)，KNN方法較其他方法更為適合。KNN算法不僅可以用于分類，還可以用于回歸。通過(guò)找出一個(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)樣本。無(wú)論怎樣，數(shù)量并不能影響運(yùn)行

3、結(jié)果?？梢圆捎脵?quán)值的方法（和該樣本距離小的鄰居權(quán)值大）來(lái)改進(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é)合的過(guò)程分成以下幾個(gè)步驟：1計(jì)算出樣本數(shù)據(jù)和待分類數(shù)據(jù)的距離2為待分類數(shù)據(jù)選擇k個(gè)與其距離最小的樣本3統(tǒng)計(jì)出k個(gè)樣本中大多數(shù)樣本所屬的分類4這個(gè)分類就是待分類數(shù)據(jù)所屬的分類數(shù)學(xué)表

4、達(dá)：目標(biāo)函數(shù)值可以是離散值(分類問(wèn)題)，也可以是連續(xù)值(回歸問(wèn)題).函數(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)過(guò)加權(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*f(X1)+.+wk*f(X

5、K)/(w1+.wk)一般地距離權(quán)值wi和距離成反比關(guān)系，例如，wi近似=1/d(xq;xi).K值的選擇：需要消除K值過(guò)低，預(yù)測(cè)目標(biāo)容易產(chǎn)生變動(dòng)性，同時(shí)高k值時(shí)，預(yù)測(cè)目標(biāo)有過(guò)平滑現(xiàn)象。推定k值的有益途徑是通過(guò)有效參數(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)難”。解決辦法有下面幾個(gè)：（1）通過(guò)降維

6、技術(shù)來(lái)減少維數(shù)，如主成分分析，因子分析，變量選擇（因子選擇）從而減少計(jì)算距離的時(shí)間；（2）用復(fù)雜的數(shù)據(jù)結(jié)構(gòu)，如搜索樹去加速最近鄰的確定。這個(gè)方法經(jīng)常通過(guò)公式2公式1設(shè)定“幾乎是最近鄰”的目標(biāo)去提高搜索速度；（3）編輯訓(xùn)練數(shù)據(jù)去減少在訓(xùn)練集中的冗余和幾乎是冗余的點(diǎn)，從而加速搜索最近鄰。在個(gè)別例子中去掉在訓(xùn)練數(shù)據(jù)集中的一些觀察點(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注意要以"類目_文件名"作為每個(gè)

7、文件的key，才能避免同名不同內(nèi)容的文件出現(xiàn)。3注意設(shè)置JM參數(shù)，否則會(huì)出現(xiàn)JAVAheap溢出錯(cuò)誤。4本程序用向量夾角余弦計(jì)算相似度。四 代碼/KNN.javapackage 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ù)

8、，距離越大，優(yōu)先級(jí)越高 */ private Comparator<KNNNode> comparator = new Comparator<KNNNode>() 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<I

9、nteger> getRandKNum(int k, int max) List<Integer> rand = new ArrayList<Integer>(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 距離值 */

10、 public double calDistance(List<Double> d1, List<Double> d2) double distance = 0.00; for (int i = 0; i < d1.size(); 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值 * retu

11、rn 測(cè)試元組的類別 */ public String knn(List<List<Double>> datas, List<Double> testData, int k) PriorityQueue<KNNNode> pq = new PriorityQueue<KNNNode>(k,comparator); List<Integer> randNum = getRandKNum(k, datas.size(); for (int i = 0; i < k; i+) int index = randNum.get

12、(i); List<Double> 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(); i+) List<Double> t = datas.get(i); double distance = calDistance

13、(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ù)類的名稱 */ private String getMostClass(PriorityQueue<KNNNode&g

14、t; pq) Map<String, Integer> classCount = new HashMap<String, Integer>(); 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 m

15、axIndex = -1; int maxCount = 0; Object classes = classCount.keySet().toArray(); for (int i = 0; i < classes.length; i+) if (classCount.get(classesi) > maxCount) maxIndex = i; maxCount = classCount.get(classesi); return classesmaxIndex.toString(); /KNNNode.javapackage cqu.KNN;public class KNNNo

16、de private int index; / 元組標(biāo)號(hào) private double distance; / 與測(cè)試元組的距離 private 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; pu

17、blic double getDistance() return distance; public void setDistance(double distance) this.distance = distance; public String getC() return 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.uti

18、l.ArrayList;import java.util.List; / KNN算法測(cè)試類 public class TestKNN /* * 從數(shù)據(jù)文件中讀取數(shù)據(jù) * param datas 存儲(chǔ)數(shù)據(jù)的集合對(duì)象 * param path 數(shù)據(jù)文件的路徑 */ public void read(List<List<Double>> datas, String path) try BufferedReader br = new BufferedReader(new FileReader(new File(path); String reader = br.readLine

19、(); while (reader != null) String t = reader.split(" "); ArrayList<Double> list = new ArrayList<Double>(); 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

20、 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() + File.separator + "cqudatatestfile.txt" try Lis

21、t<List<Double>> datas = new ArrayList<List<Double>>(); List<List<Double>> testDatas = new ArrayList<List<Double>>(); t.read(datas, datafile); t.read(testDatas, testfile); KNN knn = new KNN(); for (int i = 0; i < testDatas.size(); i+) List<Double> 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);