文章目錄

• KNN 簡介
• KNN 三要素
• • 距離度量
  • k值的選擇
  • 分類決策規則
• KNN 實現
• • 1，構造kd樹
  • 2，搜索最近鄰
  • 3，預測
• 用kd樹完成最近鄰搜索

K近鄰算法(KNN)算法，是一種基本的分類與回歸算法，本文只討論解決分類問題的KNN算法。

KNN 簡介

思想：給定一個訓練數據集，對于新輸入的樣本，在訓練集中找到與該樣本最鄰近的k個已知樣本，這k個已知樣本的多數屬于某個類別，那么新輸入的樣本就屬于這個類別。

如下圖所示，假定使用歐氏距離作為度量方式，采樣投票法決定類別，并且？表示待預測的樣本，當ｋ取１時，則變成了最近鄰算法，對應的類別為★；當ｋ取７時，類別為▲；可見k的取值對分類效果有比較大的影響。在實際應用中，k的取值一般不超過20。

該算法的優點是：

精度高

對異常值不敏感

無數據輸入假定

缺點是：

計算復雜度高

空間復雜度高

KNN 三要素

KNN算法不具有顯式的訓練過程。距離度量(如歐氏距離)、k值以及分類決策規則(如投票表決)是KNN算法的三要素。在給定訓練集合于三要素后，對于任何新輸入的樣本，它所屬的類別是唯一確定的。下面對這三個要素展開討論。

距離度量

在n維的特征空間中，距離反映的是兩個點的相似程度。KNN 算法常用的距離度量為歐式距離，但也可以采用其他距離，比如更一般的 $L_p$距離，其中p為正整數：
$$L_p(x_i,x_j)={\left(\sum _{l=1}^n{\left|x_i^{(l)}?x_j^{(l)}\right|}^p\right)}^{\frac{1}{p}}$$
當p=1時，即為曼哈頓距離，也叫出租車距離，用以標明兩個點在標準坐標系上的絕對軸距總和，如下圖中的紅色線條所示，藍色和黃色為等價曼哈頓距離。

當p=2時，即為常見的歐氏距離，也就是直線距離，如上圖的綠色線條所示。

不同距離度量確定的最近點是不同的，例如對于:
$$x_1=(1,1),x_2=(5,1),x_3=(4,4)$$
由于$x_1,x_2$只有一個坐標軸不同，所以無論p取多少，距離都為4。但是：
$$\begin{gathered} L_1(x_1,x_3)=6,L_2(x_1,x_3)=4.24 \\ {L}_3(x_1,x_3)=3.78,L_4(x_1,x_3)=3.57 \end{gathered}$$
也就是說當p大于等于3時，$x_1,x_3$ 之間距離最近。

k值的選擇

k 值的選擇對結果會產生重大影響。

如果選擇較小的k值，那么相當于只用少數的訓練樣本完成預測。這樣的預測結果對鄰近的樣本點非常敏感，一方面容易造成過擬合，另一方面容易受到恰巧是噪聲的臨近點的干擾。

如果選擇較大的k值，那么距離較遠的(不相似)的點也會對預測結果產生影響，容易使得預測結果發生錯誤。極端情況下，當k取樣本的個數時，預測結果就是眾數，完全忽略了訓練樣本中真正有效的信息。

實際應用中，k一般取較小的值，采用交叉驗證的方法確定最優的k值。

分類決策規則

一般是以多數表決為決策規則，即通過投票決定最終的類別。

假設分類函數為：
$$f:R^n\to \{c_1,c_2,...,c_K\}$$
對一個預測結果$f(X)$而言，誤分類的概率為：
$$P(Y=f(X))=1?P(Y=f(X))$$
假定KNN取最近鄰的k個樣本組成的集合$N_k(x)$用于表決，設表決結果為$c_j$，那么誤分類的概率為：
$$\frac{1}{k}\sum _{x_i\in N_k(x)}I(y_i=c_i)=1?\frac{1}{k}\sum _{x_i\in N_k(x)}I(y_i=c_i)$$
要使得誤分類概率最小，則需要$\frac{1}{k}{\sum }_{x_i\in N_k(x)}I(y_i=c_i)$最大，也就是$c_j$ 應該是$N_k(x)$中出現次數最多的類別。

KNN 實現

實現KNN算法時，主要問題是如何快速在訓練樣本中找到k個最近鄰的點。

一種最簡單的實現是線性掃描，每輸入一個新的樣本，就需要計算這個樣本和所有訓練樣本的距離，進而找到最近的k個樣本。這樣計算過于耗時，在特征空間維數很高以及訓練樣本特別多時尤為明顯。

為了提高搜索效率，可以考慮使用樹來存儲訓練數據，例如使用kd樹算法。kd樹中的k表示存儲k維空間數據的樹結構，與KNN中的k意義不同。

kd樹算法包括三個步驟：1，構造kd樹。2，搜索最近鄰。3，預測。

1，構造kd樹

kd樹是二叉樹，表示對k維空間的一個劃分。構造kd樹的過程就是不斷的用垂直于坐標軸的超平面來切分k維空間，構成一些列的k維超矩形區域。最終kd樹的每一個節點對應于一個k維超矩形區域。

具體而言，KD樹建樹首先計算m個樣本的n個特征的取值的方差，用方差最大的第k維特征$n_k$來作為根節點。假設特征$n_k$的中位數為$n_{kv}$，那么對于所有第k維特征的取值小于$n_{kv}$的樣本，我們劃入左子樹，對于第k維特征的取值大于等于$n_{kv}$的樣本，我們劃入右子樹。對于左右兩顆子樹，則對未用于父節點劃分的特征重復上面的操作，直到左右子樹沒有樣本時終止。

舉個例子，假設有二維樣本6個，{(2,3)，(5,4)，(9,6)，(4,7)，(8,1)，(7,2)}，構建kd樹的具體步驟為：

(1) 找到劃分特征。x維度方差6.97 > y維度方差 5.37。所以選擇第一個維度進行劃分。

(2) 確定劃分點。x維度數字為：2，4，5，7，8，9?？梢匀≈形粩禐?#xff1a;5或者7，這里取7。于是劃分超平面會經過(7,2)且垂直于坐標軸X。

(3) 確定左右子空間。由于劃分超平面的確定，所以x<=7的樣本{(2,3),(5,4),(4,7)}屬于左子空間，x>=7的樣本{(9,6)，(8,1)}屬于右子空間。

(3) 對未用于父節點劃分的特征重復上面的操作。

最后得到的KD樹如下：

2，搜索最近鄰

給定目標點(2，4.5)，要搜索其最近鄰，首先要找到包含目標點的葉節點。具體而言，首先從根節點(7，2)出發，首先根據x=2 < x=7向左找到節點(5，4)，繼續跟進y=4.5 > y=4 向右找到(4，7)，即與目標點最近的點為(4，7)。

以目標點(2，4.5)為圓心，以目標點到葉子節點(4，7)樣本實例的距離3.202為半徑，得到一個超球體。最近鄰的點肯定在超球體的內部，如下圖所示：

計算得到圓心到其父節點（5,4）的距離為3.041，所以最近鄰點更新為(5, 4)。

繼續查找在半徑3.041內的點，發現父節點（5,4）的另一邊的子空間和超球面有交集，所以還需要到（5,4）的左子空間內確定其中的點到目標點的距離是否更小。發現(2，3)節點的距離更小，最近鄰點更新為（2，3），最近距離更新為1.5。

此時目標點區域父節點（5,4）的兩個子空間都搜索完畢，需要繼續搜索（5,4）的父節點的另一個子空間是否有更近的點。重復這個過程，直到遇到根節點后結束搜索，得到最近鄰的點為（2，3）。

上面的過程總結如下：

當我們生成KD樹以后，就可以去預測測試集里面的樣本目標點了。對于一個目標點，我們首先在KD樹里面找到包含目標點的葉子節點。以目標點為圓心，以目標點到葉子節點樣本實例的距離為半徑，得到一個超球體，最近鄰的點一定在這個超球體內部。然后返回葉子節點的父節點，檢查另一個子節點包含的超矩形體是否和超球體相交，如果相交就到這個子節點尋找是否有更加近的近鄰，有的話就更新最近鄰。如果不相交那就簡單了，我們直接返回父節點的父節點，在另一個子樹繼續搜索最近鄰。當回溯到根節點時，算法結束，此時保存的最近鄰節點就是最終的最近鄰。

3，預測

理解最近鄰點的搜索方法后，如果我們要查找最近鄰的K個點，只需要在第一輪先找到最近鄰點，然后在第二輪忽略這個最近鄰的點，查找次最近鄰的點。重復這個過程，直到找到了K個近鄰的點。如果是KNN分類，預測為K個最近鄰里面有最多類別數的類別。如果是KNN回歸，用K個最近鄰樣本輸出的平均值作為回歸預測值。

用kd樹完成最近鄰搜索

輸入:已構造的kd樹，目標點x

輸出: x的最近鄰。

(1) 在kd樹中找出包含目標點x的葉結點：從根結點出發，遞歸地向下訪問kd樹。若目標點x當前維的坐標小于切分點的坐標，則移動到左子結點，否則移動到右子結點。直到子結點為葉結點為止。.

(2) 以找到的葉結點為“當前最近點”。

(3) 遞歸地向上回退，在每個父結點進行以下操作:

如果該結點保存的實例點比當前最近點距離目標點更近，則以該實例點為“當前最近點”。

當前最近點一定存在于該父結點的一個子結點對應的區域，即檢查父結點的另一子結點對應的區域是否有更近的點。具體地，檢查另一子結點對應的區域是否與以目標點為球心、以目標點與“當前最近點”間的距離為半徑的超球體相交。

如果相交，可能在另一個子結點對應的區域內存在距目標點更近的點，移動到另一個子結點。接著，遞歸地進行最近鄰搜索。

如果不相交，向上回退。

(4) 當回退到根結點時，搜索結束。最后的“當前最近點”即為x的最近鄰點。

如果實例點是隨機分布的，kd樹搜索的平均計算復雜度是O(logN)，這里N是訓練實例數。kd樹更適用于訓練實例數遠大于空間維數時的k近鄰搜索。當空間維數接近訓練實例數時，它的效率會迅速下降，幾乎接近線性掃描。

參考文章：

《統計學習方法 第二版》

K近鄰法(KNN)原理小結

總結

以上是生活随笔為你收集整理的基于KD树的K近邻算法(KNN)算法的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。