前言：

針對一個完整的機器學(xué)習框架目前還沒有總結(jié)出來，所以目前只能總結(jié)每一個單獨的算法。由于現(xiàn)在研究的重點是算法，所以對于數(shù)據(jù)的處理，數(shù)據(jù)的分析和可視化呈現(xiàn)，在現(xiàn)階段并不進行展示（這樣容易陷入糾結(jié)和浪費過多時間）。但是，當理解算法的基本原理和實現(xiàn)方法之后，再回過頭來從頭開始，實現(xiàn)一個完整的機器學(xué)習流程。**

1. KNN 原理

KNN是一種即可用于分類又可用于回歸的機器學(xué)習算法。對于給定測試樣本，基于距離度量找出訓(xùn)練集中與其最靠近的K個訓(xùn)練樣本，然后基于這K個“鄰居”的信息來進行預(yù)測。
在分類任務(wù)中可使用投票法，選擇這K個樣本中出現(xiàn)最多的類別標記作為預(yù)測結(jié)果；在回歸任務(wù)中可使用平均法，將這K個樣本的實值輸出標記的平均值作為預(yù)測結(jié)果。當然還可以基于距離遠近程度進行加權(quán)平均等方法。

2. KNN 優(yōu)缺點

KNN 優(yōu)點

理論成熟，思想簡單，既可以用來做分類也可以用來做回歸
可用于非線性分類
訓(xùn)練時間復(fù)雜度比支持向量機之類的算法低，僅為O(n)
和樸素貝葉斯之類的算法比，對數(shù)據(jù)沒有假設(shè)，準確度高，對異常點不敏感
由于KNN方法主要靠周圍有限的鄰近的樣本，而不是靠判別類域的方法來確定所屬類別的，因此對于類域的交叉或重疊較多的待分樣本集來說，KNN方法較其他方法更為適合
該算法比較適用于樣本容量比較大的類域的自動分類，而那些樣本容量較小的類域采用這種算法比較容易產(chǎn)生誤分

KNN 缺點

計算量大，尤其是特征數(shù)非常多的時候
樣本不平衡的時候，對稀有類別的預(yù)測準確率低
KD樹，球樹之類的模型建立需要大量的內(nèi)存
使用懶散學(xué)習方法，基本上不學(xué)習，導(dǎo)致預(yù)測時速度比起邏輯回歸之類的算法慢
相比決策樹模型，KNN模型可解釋性不強
3. KNN 算法三要素
距離度量

K 值的選擇

下面分析k值過大和過小造成的影響：

k值較小，就相當于用較小的領(lǐng)域中的訓(xùn)練實例進行預(yù)測，訓(xùn)練誤差近似誤差小（偏差小），泛化誤差會增大（方差大），換句話說，K值較小就意味著整體模型變得復(fù)雜，容易發(fā)生過擬合；

k值較大，就相當于用較大領(lǐng)域中的訓(xùn)練實例進行預(yù)測，泛化誤差小（方差小），但缺點是近似誤差大（偏差大），換句話說，K值較大就意味著整體模型變得簡單，容易發(fā)生欠擬合；一個極端是k等于樣本數(shù)m，則完全沒有分類，此時無論輸入實例是什么，都只是簡單的預(yù)測它屬于在訓(xùn)練實例中最多的類，模型過于簡單。

對于k值的選擇，沒有一個固定的經(jīng)驗（sklearn默認為5），一般根據(jù)樣本的分布，選擇一個較小的值，可以通過交叉驗證選擇一個合適的k值。

分類決策規(guī)則

KNN 算法一般是用多數(shù)表決方法，即由輸入實例的K個鄰近的多數(shù)類決定輸入實例的類。這也是經(jīng)驗風險最小化的結(jié)果。

我們定義訓(xùn)練誤差率是K近鄰訓(xùn)練樣本標記與輸入標記不一致的比例，誤差率表示為：

目的是K近鄰的標記值盡可能的與輸入標記一致，

所以最小化

最大化：

?

4 KNN 算法實現(xiàn)

線性掃描

線性掃描也叫“暴力搜索”，是計算輸入實例與每一個訓(xùn)練實例的距離，并選擇前k個最近鄰的樣本來多數(shù)表決。這種實現(xiàn)方法簡單，但是當訓(xùn)練集或特征維度很大時（我們經(jīng)常碰到樣本的特征數(shù)有上千以上，樣本量有幾十萬以上），如果我們這要去預(yù)測少量的測試集樣本，算法的時間效率很成問題，計算非常耗時，故這種暴力實現(xiàn)原理是不可行的 。

kd 樹實現(xiàn)

kd 樹是一種對k維空間中的實例點進行存儲以便對其進行快速檢索的樹形數(shù)據(jù)結(jié)構(gòu)，構(gòu)造kd樹相當于不斷用垂直于坐標軸的超平面將k維空間進行劃分，構(gòu)成一系列的k維超矩形區(qū)域，kd樹省去了對大部分數(shù)據(jù)的搜索，大大的較少了計算量。

注意這里的k和KNN中的k的意思不同。KNN中的k代表最近的k個樣本，kd樹中的k代表樣本特征的維數(shù)。

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

kd 樹的建立。kd樹實質(zhì)是二叉樹，其劃分思想與CART樹一致，切分使樣本復(fù)雜度降低最多的特征。kd樹分別計算k個特征的方差，認為特征方差越大，則該特征的復(fù)雜度亦越大，優(yōu)先對該特征進行切分 ，切分點是所有實例在該特征的中位數(shù)。重復(fù)該切分步驟，直到切分后無樣本則終止切分，終止時的樣本為葉節(jié)點，形成kd樹。

kd樹搜索最近鄰。生成kd樹以后，對于一個目標點以目標點為圓心，以目標點到葉子節(jié)點樣本實例的距離為半徑，得到一個超球體，最近鄰的點一定在這個超球體內(nèi)部。然后返回葉子節(jié)點的父節(jié)點，檢查另一個子節(jié)點包含的超矩形體是否和超球體相交，如果相交就到這個子節(jié)點尋找是否有更加近的近鄰,有的話就更新最近鄰。如果不相交直接返回父節(jié)點的父節(jié)點，在另一個子樹繼續(xù)搜索最近鄰。依次下去，當回溯到根節(jié)點時，算法結(jié)束，此時保存的最近鄰節(jié)點就是最終的最近鄰。

對于kd樹來說，劃分后可以大大減少無效的最近鄰搜索，很多樣本點由于所在的超矩形體和超球體不相交，根本不需要計算距離。大大節(jié)省了計算時間。

kd樹預(yù)測。

分類：每一次搜尋與輸入樣本最近的樣本節(jié)點，然后忽略該節(jié)點，重復(fù)同樣步驟K次，找到與輸入樣本最近鄰的K個樣本 ，投票法確定輸出結(jié)果。

回歸：用K個最近樣本的輸出的平均值作為回歸預(yù)測值。

球樹實現(xiàn)

kd樹算法雖然提高了KNN搜索的效率，但是在某些時候效率并不高，比如當處理不均勻分布的數(shù)據(jù)集時,不管是近似方形，還是矩形，甚至正方形，都不是最好的使用形狀，因為他們都有角。為了優(yōu)化超矩形體導(dǎo)致的搜索效率的問題，從而提出了球樹實現(xiàn)的方法。其基本思想和kd樹類似，就是每個分割塊都是超球體，而不是KD樹里面的超矩形體。

5 sklearn實現(xiàn)KNN算法

在scikit-learn 中，與近鄰法這一大類相關(guān)的類庫都在sklearn.neighbors包之中。KNN分類樹的類是KNeighborsClassifier，KNN回歸樹的類KNeighborsRegressor。除此之外，還有KNN的擴展，即限定半徑最近鄰分類樹的類RadiusNeighborsClassifier和限定半徑最近鄰回歸樹的類RadiusNeighborsRegressor， 以及最近質(zhì)心分類算法NearestCentroid。

在這些算法中，KNN分類和回歸的類參數(shù)完全一樣。具體參數(shù)如下：

sklearn.neighbors.KNeighborsClassifier(n_neighbors=5, weights=’uniform’,? algorithm=’auto’, leaf_size=30, p=2, metric=’minkowski’, metric_params=None,? n_jobs=None, **kwargs)

n_neighbors：KNN中的k值，默認為5（對于k值的選擇，前面已經(jīng)給出解釋）；

weights：用于標識每個樣本的近鄰樣本的權(quán)重，可選擇"uniform",“distance” 或自定義權(quán)重。默認"uniform"，所有最近鄰樣本權(quán)重都一樣。如果是"distance"，則權(quán)重和距離成反比例；如果樣本的分布是比較成簇的，即各類樣本都在相對分開的簇中時，我們用默認的"uniform"就可以了，如果樣本的分布比較亂，規(guī)律不好尋找，選擇"distance"是一個比較好的選擇；

algorithm：限定半徑最近鄰法使用的算法，可選‘a(chǎn)uto’, ‘ball_tree’, ‘kd_tree’, ‘brute’。
‘brute’對應(yīng)第一種線性掃描；
‘kd_tree’對應(yīng)第二種kd樹實現(xiàn)；
‘ball_tree’對應(yīng)第三種的球樹實現(xiàn)；
‘a(chǎn)uto’則會在上面三種算法中做權(quán)衡，選擇一個擬合最好的最優(yōu)算法。

leaf_size：這個值控制了使用kd樹或者球樹時， 停止建子樹的葉子節(jié)點數(shù)量的閾值。這個值越小，則生成的kc樹或者球樹就越大，層數(shù)越深，建樹時間越長，反之，則生成的kd樹或者球樹會小，層數(shù)較淺，建樹時間較短。默認是30。

這個值一般依賴于樣本的數(shù)量，隨著樣本數(shù)量的增加，這個值必須要增加，否則不光建樹預(yù)測的時間長，還容易過擬合?？梢酝ㄟ^交叉驗證來選擇一個適中的值。當然，如果使用的算法是蠻力實現(xiàn)，則這個參數(shù)可以忽略；

metric，p：距離度量（前面介紹過），默認閔可夫斯基距離 “minkowski”（p=1為曼哈頓距離， p=2為歐式距離）；

metric_params：距離度量其他附屬參數(shù)（具體我也不知道，一般用得少）；

n_jobs：并行處理任務(wù)數(shù)，主要用于多核CPU時的并行處理，加快建立KNN樹和預(yù)測搜索的速度。n_jobs= -1，即所有的CPU核都參與計算。

限定半徑最近鄰法分類和回歸的類的主要參數(shù)也和KNN基本一樣。具體參數(shù)如下：

sklearn.neighbors.RadiusNeighborsClassifier(radius=1.0, weights=’uniform’,? algorithm=’auto’, leaf_size=30, p=2, metric=’minkowski’, outlier_label=None,? metric_params=None, n_jobs=None, **kwargs)

radius：限定半徑，默認為1。半徑的選擇與樣本分布有關(guān)，可以通過交叉驗證來選擇一個較小的半徑，盡量保證每類訓(xùn)練樣本其他類別樣本的距離較遠；
outlier_labe：int類型，主要用于預(yù)測時，如果目標點半徑內(nèi)沒有任何訓(xùn)練集的樣本點時，應(yīng)該標記的類別，不建議選擇默認值 None,因為這樣遇到異常點會報錯。一般設(shè)置為訓(xùn)練集里最多樣本的類別。

?

參考鏈接：https://blog.csdn.net/qq_40195360/article/details/86714337

總結(jié)

以上是生活随笔為你收集整理的【Python学习】 - sklearn学习 - KNN的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。