1.KNN算法流程步驟

(1)收集數據：可以使用任何方法。包括爬蟲，或者第三方提供的免費或收費數據

(2)準備數據：距離計算所需要的數值，最好是結構化的數據格式(計算測試數據與各個訓練數據之間的距離)

(3)分析數據：可以使用任何方法。此處使用Python解析，預處理數據

(4)訓練算法：此步驟不適用于k-近鄰算法

(5)測試算法：計算錯誤率

(6)使用算法：首先需要輸入樣本數據和結構化的輸出結果，然后運行k-近鄰算法判斷輸入數據分別屬于哪個類別，最后應用對計算出的分類執行后續的處理

比如我這里取k值為3，那么在電影例子中，按照距離依次排序的三個點分別是動作片(108,5)、動作片(115,8)、愛情片(5,89)。在這三個點中，動作片出現的頻率為三分之二，愛情片出現的頻率為三分之一，所以該紅色圓點標記的電影為動作片。這個判別過程就是k-近鄰算法

2.KNN算法——蠻力實現原理

既然我們要找到K個最近的鄰居來做預測，那么我們只需要計算預測樣本和所有訓練集中的樣本的距離，然后計算出最小的k個距離即可，接著多數表決，很容易做出預測。這個方法的確簡單直接，在樣本量少，樣本特征少的時候有效。但是在實際運用中很多時候用不上，為什么呢?因為我們經常碰到樣本的特征數有上千以上，樣本量有幾十萬以上，如果我們這要去預測少量的測試集樣本，算法的時間效率很成問題。因此，這個方法我們一般稱為蠻力實現。比較適合于少量樣本的簡單模型的時候用。

既然蠻力實現的特征多，樣本多的時候很有局限性，那么我們有沒有其他的好辦法呢?有!下面說兩種，一個是KD樹實現，一個是球樹實現。

3.KNN算法——KD樹實現原理

KD樹算法沒有一開始就嘗試對測試樣本分類，而是先對訓練集建模，建立的模型就是KD樹，建好了模型再對測試集做預測。所謂的KD樹就是K個特征維度的樹，注意這里的K和KNN中的K意思不同。KNN中的K代表最近的K個樣本，KD樹中的K代表樣本特征的維數。為了防止混淆，后面我們稱特征維數為n。

KD樹算法包括三步，第一步是建樹，第二步是搜索最近鄰，最后一步是預測。

KD樹的建立

我們首先來看建樹的方法。KD樹建樹采用的是從m個樣本的n維特征中，分別計算n個特征的取值的方法，用方差最大的第k維特征nk來作為根節點。對于這個特征，我們選擇特征nk的取值的中位數nkv對應的樣本作為劃分點，對于所有第k維特征的取值小于nkv的樣本，我們劃入左子樹，對于第k維特征的取值大于等于nkv的樣本，我們劃入右子樹，對于左子樹和右子樹，我們采用和剛才同樣的方法來找方差最大的特征來做根節點，遞歸的生成KD樹。

以上內容為大家介紹了Pythonk-近鄰算法的實現原理，希望對大家有所幫助，如果想要了解更多Python相關知識，請關注IT培訓機構:千鋒教育。