KNN

算法實驗報告

K

最近鄰(k-NearestNeighbor，KNN)分類算法，是一個理論上比較成熟的方法，也是最簡單的機器學習算法之一。該方法的思路是：如果一個樣本在特征空間中的k

特征空間中最鄰近)的樣本中的大多數屬于某一個類別，則該樣本也

該方法在定類決策上只依據最鄰近的一個或者幾個樣本的類別來決定待分樣本所屬的類別。KNN

方法雖然從原理上也依賴于極限定理，

KNN

方法主要靠周圍有限的鄰近的樣本，而不是靠判別類域的方法來確定所屬類別

方法較其他方法更為適合。KNN

算法不僅可以用于分類，還可以用于回歸。通過找出一個樣本的

k

的影響給予不同的權值(weight)，如權值與距離成正比。

K

并不接近目標樣本，或者這類樣本很靠近目標樣本。無論怎樣，數量K

個最近鄰點。目前常用的解決方法是事先對已知樣本點進行剪輯，易產生誤分。

那么根據以上的描述，我把結合使用反余弦匹配和

結合的過程分成以下幾個步驟：．計算出樣本數據和待分類數據的距離．為待分類數據選擇

個與其距離最小的樣本．統計出

個樣本中大多數樣本所屬的分類．這個分類就是待分類數據所屬的分類數學表達：目標函數值可以是離散值分類問題，也可以是連續值回歸問題).函數形勢為

維空間

R—〉一維空間

R。第一步：將數據集分為訓練集（）和測試集（DTES）。第二步：在測試集給定一個實例在訓練集（）中找到與這個實例

的

最近鄰子集{X1、、、、XK}，即：。第三步：計算這

最近鄰子集得目標值，經過加權平均：

作為

）的近似估計。改進的地方：對

算法的一個明顯的改進是對

個最近鄰的貢獻加權，將較大的權值賦給較近的近鄰，相應的算法稱為距離加權

回歸算法，則公式

則修改為：一般地距離權值

和距離成反比關系，例如，

近似值的選擇：需要消除K

值過低，預測目標容易產生變動性，同時高

值時，

值的有益途徑是通過有效參數的數目這個概念。有效參數的數目是和

值相關的，大致等于，其中，是這個訓練數據集中實例的數目。缺點：（）在大訓練集尋找最近鄰的時間是難以忍受的。（

p

的增長以p

的增多而急p

稱為“維數災難”。解決辦法有下面幾個：（）通過降維技術來減少維數，如主成分分析，因子分析，變量選擇（因子選擇）從而減少計算距離的時間；（）用復雜的數據結構，如搜索樹去加速最近鄰的確定。這個方法經常通過公式公式設定“幾乎是最近鄰”的目標去提高搜索速度；（）編輯訓練數據去減少在訓練集中的冗余和幾乎是冗余的點，

算法的實現要注意：．用

，，保存測試集和訓練集。．注意要以類目_文件名作為每個文件的

，才能避免同名不同內容的文件出現。．注意設置

參數，否則會出現

溢出錯誤。．本程序用向量夾角余弦計算相似度。

//KNN.java

//KNNNode.java

訓練數據：1.0

1.1

1.2

2.1

0.3

2.3

1.4

0.5

11.7

1.2

1.4

2.0

0.2

2.5

1.2

0.8

11.2

1.8

1.6

2.5

0.1

2.2

1.8

0.2

11.9

2.1

6.2

1.1

0.9

3.3

2.4

5.5

01.0

0.8

1.6

2.1

0.2

2.3

1.6

0.5

11.6

2.1

5.2

1.1

0.8

3.6

2.4

4.5

0實驗數據：1.0

1.1

1.2

2.1

0.3

2.3

1.4

0.51.7

1.2

1.4

2.0

0.2

2.5

1.2

0.81.2

1.8

1.6

2.5

0.1

2.2

1.8

0.21.9

2.1

6.2

1.1

0.9

3.3

2.4

5.51.0

0.8

1.6

2.1

0.2

2.3

1.6

0.51.6

2.1

5.2

1.1

0.8

3.6

2.4

4.5程序運行結果：測試元組:

1.0

1.1

1.2

2.1

0.3

2.3

1.4

0.5

類別為:

1測試元組:

1.7

1.2

1.4

2.0

0.2

2.5

1.2

0.8

類別為:

1測試元組:

1.2

1.8

1.6

2.5

0.1

2.2

1.8

0.2

類別為:

1測試元組:

1.9

2.1

6.2

1