Python中怎么實現(xiàn)一個KNN最近鄰算法

這篇文章給大家介紹Python中怎么實現(xiàn)一個KNN最近鄰算法，內(nèi)容非常詳細，感興趣的小伙伴們可以參考借鑒，希望對大家能有所幫助。

    k-NN是一種基本的分類和回歸方法，用于分類時，算法思路較簡單：通過計算不同特征之間的距離方法來得到最近的k個訓(xùn)練實例，根據(jù)k個實例的類別采用多數(shù)表決等方式進行預(yù)測。而做回歸分析時，則通過對k個實例取均值來做預(yù)測。因此我們可以看到k-NN的三個基本要素：k值選擇、距離度量及分類決策規(guī)則。

一、算法分析

輸入:訓(xùn)練集和類別的數(shù)據(jù)集表示為如下：

T={(x₁,y₁),(x₂,y₂),…,(x_N,y_N)}

其中，輸出：實例x所屬的類y是實例的類別。

(1)    根據(jù)給定的距離度量，在訓(xùn)練集T中找出與x最鄰近的k個點。

(2)    對k個點根據(jù)分類決策規(guī)則（如多數(shù)表決）決定x的類別y：

二、基本要素

距離度量：特征空間中的兩個實例的距離是兩個實例點相似程度的反映，k-NN模型通常使用的是歐氏距離，但也可以選用其它距離，如曼哈頓距離、切比雪夫距離和閔可夫斯基距離等。

k值的選擇：k值的選擇對于k-NN的結(jié)果有重大影響，如果選擇較小的k值，相當于用較小的領(lǐng)域中的訓(xùn)練實例進行預(yù)測，此時預(yù)測結(jié)果對近鄰的實例點非常敏感，如果實例點恰巧是噪聲，預(yù)測就會出錯，也就是說，k值越小，整體的模型越復(fù)雜，模型容易出現(xiàn)過擬合現(xiàn)象。k=1的情況被稱為最近鄰算法。如果選擇較大k值，相當于用較大領(lǐng)域中的訓(xùn)練實例進行預(yù)測，此時容易出現(xiàn)一些較遠的訓(xùn)練實例（不相似的）也會對預(yù)測起作用，k值得增大就意味著整體模型變簡單了。k=N時會出現(xiàn)模型將輸入實例簡單的預(yù)測屬于訓(xùn)練實例中最多的類。因此在應(yīng)用中，k一般取較小的數(shù)值，通常采取交叉驗證法選取最優(yōu)的k值。

分類決策規(guī)則：k-NN中的分類決策規(guī)則一般選擇多數(shù)表決，即輸入實例的k個鄰近的訓(xùn)練實例中多數(shù)類決定輸入實例的類。

三、算法實現(xiàn)

算法步驟：

step.1---初始化距離為最大值

step.2---計算未知樣本和每個訓(xùn)練樣本的距離dist

step.3---得到目前K個最臨近樣本中的最大距離maxdist

step.4---如果dist小于maxdist，則將該訓(xùn)練樣本作為K-最近鄰樣本

step.5---重復(fù)步驟2、3、4，直到未知樣本和所有訓(xùn)練樣本的距離都算完

step.6---統(tǒng)計K-最近鄰樣本中每個類標號出現(xiàn)的次數(shù)

step.7---選擇出現(xiàn)頻率最大的類標號作為未知樣本的類標號

四、算法優(yōu)化

實現(xiàn)k-NN近鄰時，主要考慮的問題是如何對訓(xùn)練數(shù)據(jù)進行快速搜索，這點對于維數(shù)大及訓(xùn)練數(shù)據(jù)容量大的特征空間尤為重要，k-NN最簡單的實現(xiàn)方法是線性掃描，即計算每個輸入實例和訓(xùn)練實例的距離，訓(xùn)練集很大時，非常耗時，也失去了本身的意義。為了提高k近鄰的搜索效率，可以采用kd樹，由于篇幅先不討論kd樹，以后再寫，另外一點，我們在使用k-NN時可能會選擇距離太遠的近鄰，這些與輸入實例的相似性較低，因此一種補償方法是根據(jù)距離的遠近為其賦予相應(yīng)的權(quán)重，有三種常用獲取權(quán)重的方法。

1．  反函數(shù)

取距離的反函數(shù)作為權(quán)重，最簡單的方式是取距離的倒數(shù)，但是存在一個問題，當出現(xiàn)完全一樣或非常近的實例時，會使得權(quán)重非常的大，甚至無窮，基于此，對距離取導(dǎo)數(shù)前加上一個較小的常數(shù)。

2．  減法函數(shù)

用一個常數(shù)值減去距離，如果相減的結(jié)果大于0，則權(quán)重為相減的結(jié)果，否則，結(jié)果取0，該方法很好的克服了權(quán)重分配過大的問題，但也存在一些局限，由于權(quán)重限定一定距離的實例，因此可能我們找不到足夠近的項視為近鄰，即對于一些實例，無法做預(yù)測。

3．高斯函數(shù)

      該方法是根據(jù)高斯函數(shù)取權(quán)重，在距離為0的時候權(quán)重為1，并且權(quán)重隨著距離的增加而減小，和減法函數(shù)不同的是，權(quán)重不會出現(xiàn)跌至到0，很好的克服了前兩個函數(shù)的局限，不過相對復(fù)雜一些，使得執(zhí)行速度沒有前兩個函數(shù)快。

五、算法的優(yōu)缺點

k-NN能夠利用復(fù)雜函數(shù)進行數(shù)值預(yù)測，同時又保持簡單易懂的特點，它是一種在線（online）技術(shù)，也就是說，新的數(shù)據(jù)可以在任何時候不需要進行任何計算，直接將數(shù)據(jù)添加到集合即可。

k-NN主要的缺點是為了完成預(yù)測，所有的訓(xùn)練集數(shù)據(jù)都必須缺一不可，當面對百萬樣本的數(shù)據(jù)集，在空間上和時間上都存在著問題。

關(guān)于Python中怎么實現(xiàn)一個KNN最近鄰算法就分享到這里了，希望以上內(nèi)容可以對大家有一定的幫助，可以學(xué)到更多知識。如果覺得文章不錯，可以把它分享出去讓更多的人看到。