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

KNN

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

K

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

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

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

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

KNN

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

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

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

k

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

K

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

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

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

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

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

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

維空間

R—〉一維空間

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

的

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

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

作為

）的近似估計(jì)。改進(jìn)的地方：對

算法的一個明顯的改進(jìn)是對

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

回歸算法，則公式

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

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

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

值過低，預(yù)測目標(biāo)容易產(chǎn)生變動性，同時(shí)高

值時(shí)，

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

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

p

的增長以p

的增多而急p

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

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

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

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

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

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

//KNN.java

//KNNNode.java

訓(xùn)練數(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í)驗(yàn)數(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程序運(yùn)行結(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