KNN算法實驗報告

KNN

算法實驗報告

K

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

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

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

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

KNN

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

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

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

k

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

K

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

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

那么根據(jù)以上的描述，我把結(jié)合使用反余弦匹配和

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

個與其距離最小的樣本．統(tǒng)計出

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

維空間

R—〉一維空間

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

的

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

最近鄰子集得目標值，經(jīng)過加權(quán)平均：

作為

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

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

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

回歸算法，則公式

則修改為：一般地距離權(quán)值

和距離成反比關(guān)系，例如，

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

值過低，預測目標容易產(chǎn)生變動性，同時高

值時，

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

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

p

的增長以p

的增多而急p

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

算法的實現(xiàn)要注意：．用

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

，才能避免同名不同內(nèi)容的文件出現(xiàn)。．注意設置

參數(shù)，否則會出現(xiàn)

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

//KNN.java

//KNNNode.java

訓練數(shù)據(jù)：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實驗數(shù)據(jù)：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程序運行結(jié)果：測試元組:

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