Python中怎么實現一個KNN最近鄰算法

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

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

一、算法分析

輸入:訓練集和類別的數據集表示為如下：

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

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

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

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

二、基本要素

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

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

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

三、算法實現

算法步驟：

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

step.2---計算未知樣本和每個訓練樣本的距離dist

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

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

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

step.6---統計K-最近鄰樣本中每個類標號出現的次數

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

四、算法優化

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

1．  反函數

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

2．  減法函數

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

3．高斯函數

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

五、算法的優缺點

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

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

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