1.KNN算法流程步驟

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

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

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

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

(5)測試算法：計(jì)算錯(cuò)誤率

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

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

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

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

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

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

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

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

KD樹的建立

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

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