1.KNN算法流程步驟

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

(2)準(zhǔn)備數(shù)據(jù)：距離計算所需要的數(shù)值，最好是結(jié)構(gòu)化的數(shù)據(jù)格式(計算測試數(shù)據(jù)與各個訓(xùn)練數(shù)據(jù)之間的距離)

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

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

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

(6)使用算法：首先需要輸入樣本數(shù)據(jù)和結(jié)構(gòu)化的輸出結(jié)果，然后運(yùn)行k-近鄰算法判斷輸入數(shù)據(jù)分別屬于哪個類別，最后應(yīng)用對計算出的分類執(zhí)行后續(xù)的處理

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

2.KNN算法——蠻力實(shí)現(xiàn)原理

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

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

3.KNN算法——KD樹實(shí)現(xiàn)原理

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

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

KD樹的建立

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

以上內(nèi)容為大家介紹了Pythonk-近鄰算法的實(shí)現(xiàn)原理，希望對大家有所幫助，如果想要了解更多Python相關(guān)知識，請關(guān)注IT培訓(xùn)機(jī)構(gòu):千鋒教育。