K近鄰法（KNN）是一種基本的分類方法，它的輸入為實(shí)例的特征向量，對(duì)應(yīng)于特征空間中的點(diǎn)，輸出為實(shí)例的類別，可以取多類。實(shí)際上是利用訓(xùn)練數(shù)據(jù)集對(duì)特征向量空間進(jìn)行劃分，并作為其分類的模型。

0 k近鄰算法的主要學(xué)習(xí)內(nèi)容

1）k近鄰算法

2）k值的選擇

3）距離度量

4）分類決策規(guī)則

1 k近鄰算法

k=1時(shí),這個(gè)算法稱為最近鄰算法，對(duì)于輸入的實(shí)例點(diǎn)（特征向量）x，最近鄰法將訓(xùn)練數(shù)據(jù)集中與x最近鄰點(diǎn)的類作為x的類。k近鄰法沒有顯式的學(xué)習(xí)過程。

2 k近鄰模型

2.1 距離度量[1]

特征空間中兩個(gè)實(shí)例點(diǎn)的距離是兩個(gè)實(shí)例點(diǎn)相似程度的反映，k近鄰模型的特征空間一般是n維實(shí)數(shù)向量空間Rn，使用的距離是歐式距離，但也可以是其他距離。如更一般的Lp距離

例[1]:

2.2 k值的選擇

k值的選擇會(huì)對(duì)k近鄰法的結(jié)果產(chǎn)生重大影響。

如果選擇較小的k值，就相當(dāng)于用較少的實(shí)例在進(jìn)行預(yù)測(cè)，“學(xué)習(xí)”的近似誤差會(huì)減小，因?yàn)橹挥信c輸入實(shí)例距離較近的訓(xùn)練實(shí)例才會(huì)對(duì)預(yù)測(cè)結(jié)果起作用，不足在于“學(xué)習(xí)”的估計(jì)誤差會(huì)增大，會(huì)對(duì)近鄰的實(shí)例點(diǎn)非常敏感，如果近鄰的實(shí)例點(diǎn)恰巧是噪聲，分類預(yù)測(cè)就會(huì)出錯(cuò)，而且k值較小就意味著整體模型會(huì)比較復(fù)雜，容易發(fā)生過擬合。

如果選擇較大的k值，就相當(dāng)于用較多的訓(xùn)練實(shí)例來進(jìn)行預(yù)測(cè)，雖減少了學(xué)習(xí)的估計(jì)誤差，但學(xué)習(xí)的近似誤差會(huì)增大，與輸入實(shí)例較遠(yuǎn)的不相似的實(shí)例也會(huì)對(duì)預(yù)測(cè)起作用，使預(yù)測(cè)發(fā)生錯(cuò)誤，這時(shí)的整體模型變得簡(jiǎn)單。

如果k=N，那么無論輸入實(shí)例是什么，都將簡(jiǎn)單地預(yù)測(cè)它屬于在訓(xùn)練實(shí)例中最多的類，這時(shí)，模型過于簡(jiǎn)單，完全忽略訓(xùn)練實(shí)例中的大量有用信息，是不可取的。

在應(yīng)用中，k值一般取一個(gè)比較小的數(shù)值，通常采用交叉驗(yàn)證法來選取最優(yōu)的k值。經(jīng)驗(yàn)規(guī)則：k一般低于訓(xùn)練樣本數(shù)的平方根[2]。

2.3 分類決策規(guī)則[1]

k近鄰算法的分類決策規(guī)則往往是多數(shù)表決（少數(shù)服從多數(shù)），即由輸入實(shí)例的k個(gè)近鄰的訓(xùn)練實(shí)例中多數(shù)類決定輸入實(shí)例的類。

表示方法：

3 k近鄰法的實(shí)現(xiàn)

3.1 kd樹

實(shí)現(xiàn)k近鄰算法時(shí)，我們主要考慮的問題是如何對(duì)訓(xùn)練集進(jìn)行k近鄰搜索，這點(diǎn)在特征空間的維數(shù)高，訓(xùn)練數(shù)據(jù)容量大時(shí)尤其必要。為提高k近鄰搜索的效率，可以考慮使用特殊的結(jié)構(gòu)存儲(chǔ)訓(xùn)練數(shù)據(jù)，以減少計(jì)算距離次數(shù)。kd樹就有這一作用，kd樹是一個(gè)二叉樹。

例：

3.2 搜索kd樹

如圖：

kd樹適用于訓(xùn)練實(shí)例數(shù)大于空間維數(shù)時(shí)的k近鄰搜索，當(dāng)空間維數(shù)接近訓(xùn)練實(shí)例數(shù)時(shí)，它的效率會(huì)迅速下降，幾乎接近線性掃描。

例：

給定一個(gè)如圖的kd樹，根結(jié)點(diǎn)為A，其子結(jié)點(diǎn)為B，C等，樹上共存儲(chǔ)7個(gè)實(shí)例點(diǎn)；另一個(gè)輸入目標(biāo)實(shí)例點(diǎn)S，求S的最近鄰。

解:

首先在kd樹中找到包含點(diǎn)S的葉結(jié)點(diǎn)D，以點(diǎn)D作為近似最近鄰，真正最近鄰一定在以點(diǎn)S為中心通過點(diǎn)D的圓的內(nèi)部，然后返回結(jié)點(diǎn)D的父結(jié)點(diǎn)B，在結(jié)點(diǎn)B的另一個(gè)子結(jié)點(diǎn)F的區(qū)域內(nèi)搜索最近鄰，結(jié)果F的區(qū)域與圓不相交，不可能有最近鄰點(diǎn)，繼續(xù)返回上一級(jí)父結(jié)點(diǎn)A，在結(jié)點(diǎn)A的另一個(gè)結(jié)點(diǎn)C的區(qū)域內(nèi)搜索最近鄰，結(jié)點(diǎn)C的區(qū)域與圓相交，該區(qū)域在園內(nèi)的實(shí)例點(diǎn)有點(diǎn)E，點(diǎn)E比點(diǎn)D更近，成為新的最近鄰近似。最后得到點(diǎn)E是點(diǎn)S的最近鄰。

4 k近鄰法的總結(jié)

4.1 k近鄰法的優(yōu)點(diǎn)

1.簡(jiǎn)單，易于理解，易于實(shí)現(xiàn)，無參數(shù)估計(jì)，無需訓(xùn)練

2.對(duì)異常值不敏感

3.適合對(duì)稀有事件進(jìn)行分類

4.適合樣本容量比較大的分類問題

5.適合多分類問題研究，效果有時(shí)比支持向量機(jī)要好

4.2 k近鄰法的缺點(diǎn)

1.懶惰算法，對(duì)測(cè)試樣本分類時(shí)的計(jì)算量大，內(nèi)存開銷大，評(píng)分慢。

2.可解釋性不強(qiáng)，無法給出如決策樹那樣的規(guī)則

3.對(duì)于小樣本的分類問題，會(huì)產(chǎn)生誤分。

5 k近鄰法的應(yīng)用

1.KNN約會(huì)配對(duì)

2.K近鄰房?jī)r(jià)評(píng)估

3.蛋白質(zhì)功能檢測(cè)中的應(yīng)用

4.網(wǎng)頁分類

參考文獻(xiàn)

[1] 李航，《統(tǒng)計(jì)學(xué)習(xí)方法》

[2] 常用數(shù)據(jù)挖掘算法總結(jié)及python實(shí)現(xiàn)

[3] https://blog.csdn.net/hhy518518/article/details/52840152

[4] https://blog.csdn.net/qq_15258623/article/details/80286230

[5]https://www.docin.com/p-1285931544.html

(部分文字、圖片來自網(wǎng)絡(luò)，如涉及侵權(quán)，請(qǐng)及時(shí)與我們聯(lián)系，我們會(huì)在第一時(shí)間刪除或處理侵權(quán)內(nèi)容。電話：4006770986    負(fù)責(zé)人：張明）