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

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

1）k近鄰算法

2）k值的選擇

3）距離度量

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

1 k近鄰算法

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

2 k近鄰模型

2.1 距離度量[1]

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

例[1]:

2.2 k值的選擇

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

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

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

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

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

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

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

表示方法：

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

3.1 kd樹

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

例：

3.2 搜索kd樹

如圖：

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

例：

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

解:

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

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

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

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

2.對異常值不敏感

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

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

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

4.2 k近鄰法的缺點

1.懶惰算法，對測試樣本分類時的計算量大，內(nèi)存開銷大，評分慢。

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

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

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

1.KNN約會配對

2.K近鄰房價評估

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

4.網(wǎng)頁分類

參考文獻(xiàn)

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

[2] 常用數(shù)據(jù)挖掘算法總結(jié)及python實現(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)，請及時與我們聯(lián)系，我們會在第一時間刪除或處理侵權(quán)內(nèi)容。電話：4006770986    負(fù)責(zé)人：張明）