一、KNN 簡介

KNN 算法，或者稱 k-最近鄰算法，是 有監(jiān)督學(xué)習(xí) 中的 分類算法 。它可以用于分類或回歸問題，但它通常用作分類算法。

二、KNN 核心思想

KNN 的全稱是 K Nearest Neighbors，意思是 K 個最近的鄰居。該算法用 K 個最近鄰來干什么呢？其實，KNN 的原理就是：當(dāng)預(yù)測一個新樣本的類別時，根據(jù)它距離最近的 K 個樣本點(diǎn)是什么類別來判斷該新樣本屬于哪個類別（多數(shù)投票）。

實例

圖中綠色的點(diǎn)是待預(yù)測點(diǎn)，假設(shè) K=3。那么 KNN 算法就會找到與它距離最近的三個點(diǎn)（這里用圓圈把它圈起來了），然后看這三個點(diǎn)中哪種類別多一些，比如這個例子中是藍(lán)色三角形多一些，新來的綠色點(diǎn)就被歸類到藍(lán)三角了。

但是，當(dāng) K=5 的時候，判定就變得不一樣了。這次變成紅圓多一些，所以新來的綠點(diǎn)被歸類成紅圓。從這個例子中，我們就能看得出 k 值的確定對KNN算法的預(yù)測結(jié)果有著至關(guān)重要的影響。

分析：K 值的影響

如果k值比較小，相當(dāng)于我們用較小的領(lǐng)域內(nèi)的訓(xùn)練樣本對實例進(jìn)行預(yù)測。這時，算法的近似誤差（Approximate Error）會比較小，因為只有與輸入實例相近的訓(xùn)練樣本才會對預(yù)測結(jié)果起作用。但是，它也有明顯的缺點(diǎn)：算法的估計誤差比較大，預(yù)測結(jié)果會對近鄰點(diǎn)十分敏感，也就是說，如果近鄰點(diǎn)是噪聲點(diǎn)的話，預(yù)測就會出錯。因此，k值過小容易導(dǎo)致KNN算法的過擬合。

同理，如果k值選擇較大的話，距離較遠(yuǎn)的訓(xùn)練樣本也能夠?qū)嵗A(yù)測結(jié)果產(chǎn)生影響。這時候，模型相對比較魯棒，不會因為個別噪聲點(diǎn)對最終預(yù)測結(jié)果產(chǎn)生影響。但是缺點(diǎn)也十分明顯：算法的近鄰誤差會偏大，距離較遠(yuǎn)的點(diǎn)（與預(yù)測實例不相似）也會同樣對預(yù)測結(jié)果產(chǎn)生影響，使得預(yù)測結(jié)果產(chǎn)生較大偏差，此時模型容易發(fā)生 欠擬合。

因此，在實際工程實踐中，我們一般采用交叉驗證的方式選取 k 值（以下第三節(jié)會介紹）。通過以上分析可知，一般 k 值選得比較小，我們會在較小范圍內(nèi)選取 k 值，同時把測試集上準(zhǔn)確率最高的那個確定為最終的算法超參數(shù) k 。

三、KNN 的關(guān)鍵

實際上，KNN 算法有兩個關(guān)鍵點(diǎn)：1. 點(diǎn)之間距離的計算；2. K 值的選取。

1. 距離計算

樣本空間內(nèi)的兩個點(diǎn)之間的距離量度表示兩個樣本點(diǎn)之間的相似程度：距離越短，表示相似程度越高；反之，相似程度越低。

常用的距離量度方式包括：

1. 閔可夫斯基距離
2. 曼哈頓距離
3. 歐氏距離
4. 切比雪夫距離
5. 余弦距離

1. 閔可夫斯基距離

閔可夫斯基距離本身不是一種距離，而是一類距離的定義。對于n維空間中的兩個點(diǎn)x(x1,x2,…,xn)和y(y1,y2,…,yn)，x和y之間的閔可夫斯基距離可以表示為：

其中，p是一個可變參數(shù)：

• 當(dāng)p=1時，被稱為曼哈頓距離；
• 當(dāng)p=2時，被稱為歐氏距離；
• 當(dāng)p=∞時，被稱為切比雪夫距離。

2. 曼哈頓距離

根據(jù)閔可夫斯基距離定義，曼哈頓距離的計算公式可以寫為：

它測量兩點(diǎn)之間的絕對值。

3. 歐氏距離

根據(jù)以上定義，歐氏距離可以寫為：

歐氏距離（L2范數(shù)）是最易于理解的一種距離計算方法，源自歐氏空間中兩點(diǎn)間的距離公式，也是最常用的距離量度。它測量兩點(diǎn)之間的直線距離。

通常 KNN 算法中使用的是歐式距離。

4. 切比雪夫距離

切比雪夫距離是將2個點(diǎn)之間的距離定義為其各坐標(biāo)數(shù)值差的最大值。對應(yīng)L∞范數(shù)：

5. 余弦距離

余弦相似度的取值范圍是[-1,1]，相同兩個向量的之間的相似度為1。

余弦相似度的定義公式為 ：

余弦距離的取值范圍是[0,2]：

總結(jié)

這樣我們就明白了如何計算距離。KNN 算法最簡單粗暴的就是將預(yù)測點(diǎn)與所有點(diǎn)距離進(jìn)行計算，然后保存并排序，選出前面 K 個值看看哪些類別比較多。但其實也可以通過一些數(shù)據(jù)結(jié)構(gòu)來輔助，比如最大堆、KDTree，能夠減小計算量，從而快速找到 K 個最近鄰。

2. K值選擇

通過上面那張圖我們知道 K 的取值比較重要，那么該如何確定 K 取多少值好呢？答案是通過交叉驗證（將樣本數(shù)據(jù)按照一定比例，拆分出訓(xùn)練用的數(shù)據(jù)和驗證用的數(shù)據(jù)，比如6：4拆分出部分訓(xùn)練數(shù)據(jù)和驗證數(shù)據(jù)），從選取一個較小的 K 值開始，不斷增加 K 的值，然后計算驗證集合的方差，最終找到一個比較合適的 K 值。

通過交叉驗證計算方差后你大致會得到下面這樣的圖：

這個圖其實很好理解，當(dāng)你增大 K 的時候，一般錯誤率會先降低，因為有周圍更多的樣本可以借鑒了，分類效果會變好。但是，K值太大的時候就會失去意義：這也很好理解，比如說你一共就35個樣本，當(dāng)你 K 增大到30的時候，KNN 基本上就沒意義了。

所以選擇 K 點(diǎn)的時候可以選擇一個較大的臨界 K 點(diǎn)，當(dāng)它繼續(xù)增大或減小的時候，錯誤率都會上升，比如圖中的 K=10。

四、KNN 的改進(jìn)：KDTree

KNN 算法最簡單粗暴的就是將預(yù)測點(diǎn)與所有點(diǎn)距離進(jìn)行計算，然后保存并排序，選出前面 K 個值看看哪些類別比較多。這樣的直接暴力尋找的方法，在特征空間維度不高且訓(xùn)練樣本容量小時，是可行的，但是當(dāng)特征空間維度特別高或者樣本容量較大時，計算過程就會非常耗時，這種方法就不可行了。

因此，為了快速查找到 k 個近鄰，我們可以考慮使用特殊的數(shù)據(jù)結(jié)構(gòu)存儲訓(xùn)練數(shù)據(jù)，用來減少搜索次數(shù)。其中，KDTree就是最著名的一種。

KDTree（K-dimension Tree）是一種對k維空間中的實例點(diǎn)進(jìn)行存儲以便對其進(jìn)行快速檢索的樹形數(shù)據(jù)結(jié)構(gòu)。KDTree是一種二叉樹，表示對k維空間的一種劃分構(gòu)造KDTree相當(dāng)于不斷地利用垂直于坐標(biāo)軸的超平面將k維空間進(jìn)行切分，構(gòu)成一系列的k維超矩形區(qū)域。KDTree的每個節(jié)點(diǎn)對應(yīng)于一個k維超矩形區(qū)域。利用KDTree可以省去對大部分?jǐn)?shù)據(jù)點(diǎn)的搜索，從而減少搜索的計算量。

關(guān)于 KDTree 的詳細(xì)介紹，請參考我的另一篇文章：【KNN分類】kd-tree

五、KNN 回歸算法

上文所述的 KNN 算法主要用于分類，實際上，KNN算法也可以用于回歸預(yù)測。接下來，我們討論一下KNN算法如何用于回歸。

與分類預(yù)測類似，KNN算法用于回歸預(yù)測時，同樣是尋找新來的預(yù)測實例的 k 近鄰，然后對這 k 個樣本的目標(biāo)值取 均值 即可作為新樣本的預(yù)測值：

六、用 sklearn 實現(xiàn) KNN

sklearn 中實現(xiàn) KNN 的算法是：sklearn.neighbors.KNeighborsClassifier

函數(shù)原型

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

可選參數(shù)

• n_neighbors: 表示選幾個鄰居，KNN 算法中的 k 值， int，默認(rèn)值為5，

• weight: str or callable，默認(rèn)值為uniform，還可以是distance和自定義函數(shù)
  ‘uniform’：表示所有點(diǎn)的權(quán)重相等
  ‘distance’：表示權(quán)重是距離的倒數(shù)，意味著k個點(diǎn)中距離近的點(diǎn)對分類結(jié)果的影響大于距離遠(yuǎn)的點(diǎn)
  [callable]：用戶自定義函數(shù)，接受一個距離數(shù)組，返回一個同維度的權(quán)重數(shù)

• algorithm：{‘ball_tree’，‘kd_tree’，‘brute’，‘a(chǎn)uto’}，找出 k 近鄰點(diǎn)的計算方法
  ‘ball_tree’：使用BallTree維數(shù)大于20時建議使用
  ‘kd_tree’：使用KDTree，原理是數(shù)據(jù)結(jié)構(gòu)的二叉樹，以中值為劃分，每個節(jié)點(diǎn)是一個超矩形，在維數(shù)小于20是效率高
  ‘brute’：暴力算法，線性掃描
  ‘a(chǎn)uto’：自動選取最合適的算法
  注意：在稀疏的輸入數(shù)據(jù)上擬合，將使用’brute’覆蓋此參數(shù)

• leaf_size：int，默認(rèn)值為30，用于構(gòu)造BallTree和KDTree。leaf_size參數(shù)設(shè)置會影響樹構(gòu)造的樹構(gòu)造和詢問的速度，同樣也會影響樹存儲需要的內(nèi)存，這個值的設(shè)定取決于問題本身

• p：int，默認(rèn)值為2
  1：使用曼哈頓距離進(jìn)行度量
  2：使用歐式距離進(jìn)行度量

• metric : string or callable, 默認(rèn)使用’minkowski’(閔可夫斯基距離)，度量函數(shù)
  其中p是一個變參數(shù)，也就是上一個介紹的參數(shù)p
  當(dāng)p=1時，就是曼哈頓距離
  當(dāng)p=2時，就是歐氏距離
  當(dāng)p→∞時，就是切比學(xué)夫距離

• metric_params : dict，默認(rèn)為None。度量函數(shù)的其他關(guān)鍵參數(shù)，一般不用設(shè)置

• n_jobs : int or None, 默認(rèn)None。用于搜索k近鄰點(diǎn)并行任務(wù)數(shù)量，-1表示任務(wù)數(shù)量設(shè)置為CPU的核心數(shù)，即CPU的所有core都并行工作，不會影響fit(擬合)函數(shù)文章來源地址http://www.zghlxwxcb.cn/news/detail-423770.html

方法

1. fit(X, y)：使用X作為訓(xùn)練集作為便簽集，來擬合模型
2. get_params([deep])：獲得估計器的參數(shù)
3. kneighbors([X, n_neighbors, return_distance]) ：查找X數(shù)組中所有點(diǎn)的K鄰居點(diǎn)
4. kneighbors_graph([X, n_neighbors, mode])：計算X中每個點(diǎn)的K鄰居權(quán)重圖
5. predict(X)：預(yù)測X數(shù)據(jù)集中每個點(diǎn)對應(yīng)的標(biāo)簽
6. predict_proba(X)：返回X數(shù)據(jù)集中對應(yīng)每個標(biāo)簽的概率估計值
7. score(X, y[, sample_weight])：返回給定數(shù)據(jù)集和標(biāo)簽的平均準(zhǔn)確率
8. set_params(params)：設(shè)置估計器的參數(shù)

參考鏈接

1. Python—KNN分類算法（詳解）
2. 什么是KNN算法？
3. sklearn.neighbors.KNeighborsClassifier的k-近鄰算法使用介紹

到了這里，關(guān)于【機(jī)器學(xué)習(xí)】KNN 算法介紹的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！