完結篇|一文搞懂k近鄰（k-NN）演算法（二）

上篇文章重點講解了最基本的k近鄰演算法一文搞懂k近鄰（k-NN）演算法（一） - 知乎專欄

這篇文章重點講解一下k近鄰演算法的最經典演算法kd樹的相關知識點以及最終的總結！希望看完這篇文章，大家對kd樹能夠有一個直觀的感覺~

本文目錄如下：

1.k近鄰演算法的回顧

2.k近鄰演算法中的分類決策規則講解

3.k近鄰法的實現：kd樹原理的講解以及kd樹詳細例子講解

4.kd樹的不足以及最差情況舉例

5.k近鄰方法的一些優缺點總結

一、k近鄰演算法的回顧

1.我們提出了k近鄰演算法，演算法的核心思想是，即是給定一個訓練數據集，對新的輸入實例，在訓練數據集中找到與該實例最鄰近的K個實例，這K個實例的多數屬於某個類，就把該輸入實例分類到這個類中。更通俗說一遍演算法的過程，來了一個新的輸入實例，我們算出該實例與每一個訓練點的距離（這裡的複雜度為0(n)比較大，所以引出了下文的kd樹等結構），然後找到前k個，這k個哪個類別數最多，我們就判斷新的輸入實例就是哪類！

2.與該實例最近鄰的k個實例，那麼最近鄰的衡量標準是是什麼。這個最近鄰的定義是通過不同距離函數來定義，我們最常用的是歐式距離。

3.為了保證每個特徵同等重要性，我們這裡對每個特徵進行歸一化。

4.k值的選取，既不能太大，也不能太小，何值為最好，需要實驗調整參數確定！

二、k近鄰演算法中的分類決策規則講解

k近鄰演算法的分類決策規則通俗來說就是k 近鄰法中的分類決策規則往往是多數表決決定，背後的數學思維是什麼？

k 近鄰法中的分類決策規則往往是多數表決，即由輸入實例的 k 個近鄰的訓練實例中的多數類決定輸入實例的類。

多數表決規則（majority voting rule）有如下解釋：如果分類的損失函數為 0-1 損失函數，分類函數為：

那麼誤分類的概率是：

換句話說，目前候選種類為c1,c2....cj，我選擇哪一個，使得我們的經驗風險最小（經驗風險通俗講就是訓練數據的錯誤值）。

那麼由上式經驗風險最小，也就是說，要我們預測出的種類屬於cj類的最多（那麼預測出來的種類結果和真實結果一致的越多，我們認為正確可能性就越大，也就是經驗風險越小），也就是我們所說的多數表決規則。而它也等價於我們的經驗風險最小。這也是我們在k近鄰演算法中採用多數表決規則的正確性說明！

三、k近鄰法的實現：kd樹原理的講解以及kd樹詳細例子講解

• kd樹原理的講解

kd 樹的結構

kd樹是一個二叉樹結構，它的每一個節點記載了【特徵坐標，切分軸，指向左枝的指針，指向右枝的指針】。

其中，特徵坐標是線性空間 Rn 中的一個點 (x1,x2,…,xn)切分軸由一個整數 r 表示，這裡 1≤r≤n，是我們在 n 維空間中沿第 rr維進行一次分割。節點的左枝和右枝分別都是 kd 樹，並且滿足：如果 y 是左枝的一個特徵坐標，那麼 yr≤xr（左分支結點）；並且如果 z 是右枝的一個特徵坐標，那麼 zr≥xr（右分支結點）。

給定一個數據樣本集 S?Rn 和切分軸 r，以下遞歸演算法將構建一個基於該數據集的 kd 樹，每一次循環製作一個節點：

?? 如果 |S|=1，記錄 S 中唯一的一個點為當前節點的特徵數據，並且不設左枝和右枝。（|S| 指集合 S 中元素的數量）

?? 如果 |S|>1

• 將 S 內所有點按照第 r 個坐標的大小進行排序；
• 選出該排列後的中位元素（如果一共有偶數個元素，則選擇中位左邊或右邊的元素，左隨便哪一個都無所謂），作為當前節點的特徵坐標，並且記錄切分軸 r；

• 將 SL設為在 S 中所有排列在中位元素之前的元素； SR 設為在 S 中所有排列在中位元素後的元素；

• 當前節點的左枝設為以 SL 為數據集並且 r 為切分軸製作出的 kd 樹；當前節點的右枝設為以 SR 為數據集並且 r為切分軸製作出的 kd 樹。再設 r←(r+1)modn。（這裡，我們想輪流沿著每一個維度進行分割；modn 是因為一共有 n 個維度，在沿著最後一個維度進行分割之後再重新回到第一個維度。）

哎呀，到這裡有沒有一點暈了，這麼多文字，好羅，下面通過例子一步一步給出kd樹的構建，以便容易理解！舉出李航博士例子3.2！

kd樹的構建！例題3.2

給定一個二維空間的數據集：

T = {（2,3），（5,4），（9,6）,（4,7），（8,1），（7,2）}， 構造一個平衡kd樹。

為了方便，我這裡進行編號A(2，3)、B（5,4）、C（9,6）、D（4,7）、E（8,1）、F（7,2）

初始值r=0，對應x軸。

可視化數據點如下：

首先先沿 x 坐標進行切分，我們選出 x 坐標的中位點，獲取最根部節點的坐標，對數據點x坐標進行排序得：

A(2，3)、D（4,7）、B（5,4）、F（7,2）、E（8,1）、C（9,6）

則我們得到中位點為B或者F，我這裡選擇F作為我們的根結點，並作出切分（並得到左右子樹），如圖：

對應的樹結構如下：

根據演算法，此時r=r+1=1，對應y軸，此時對應演算法|S|>1，則我們分別遞歸的在F對應的左子樹與右子樹按y軸進行分類，得到中位節點分別為B，C點，如圖所示：

對應樹結構為：

而到此時，B的左孩子為A，右孩子為D，C的左孩子為E,均滿足|S|==1，此時r = (r+1)mod2 = 0,又滿足x軸排序，對x軸劃分！則如圖所示：

對應樹結構如下：

恩恩，到這裡為止，給定的kd樹構造完成啦，所有的數據點都能在樹上的每個結點找到！而我們根據上面構造樹的過程，也能很容易的知道，來了一個新的數據點的時候，對應該層的指定維數，通過比較大小，我就能知道往左（預測點對應維度數據小於該結點對對應維度數據）走還是往右（預測點對應維度數據大於該結點對應維度數據）走，那麼好的情況下，我們就能省掉一半的數據點啦~（不好的情況，哈哈，沒有節省，後面會說到，這也是kd樹的致命缺點~）

恩，好啦，到這裡為止，我們一步一步給出了kd樹的構造過程。這也是李航博士書籍上例子中kd樹構造的詳細過程！他的圖片如下：

對應kd樹為:

• kd樹搜索

我這裡和統計學習方法例子一樣，以最近鄰為例加以敘述，同樣的方法可以應用到k近鄰。

為了讓大家更好的理解，我這裡直接用上面例子給大家一步一步給出過程！

首先我們來看用kd樹的最近鄰搜索演算法流程：

輸入：已構造的kd樹；目標點x；

輸出：x的最近鄰.

（1）在kd樹中找出包含目標點x的葉結點：從根結點出發，遞歸地向下訪問kd樹，若目標點x當前維的坐標小於切分點的坐標,則移動到左子節點，否則移動到右子結點.直到子結點為葉結點位置.

（2）以此葉結點為「當前最近點」

（3）遞歸地向上回退，在每個結點進行以下操作：

（a）如果該結點保存的實例點比當前最近點距離目標點更近，則以該實例點為「當前最近點」.

（b）當前最近點一定存在於該結點一個子結點對應的區域.檢查該子結點的父結點的另一個子結點對應的區域是否有更近的點.具體地，檢查另一子結點對應的區域是否以目標點為球心、以目標點與「當前最近點」間為半徑的超球體相交。

如果不相交，向上回退.

（4）當回退到根結點時，搜索結束。最後的「當前最近點」即為最近鄰點.

看到這裡是不是有點暈了，哈哈，不要怕，下面通過例子，一步一步走一遍上面所描述的演算法過程，化抽象為具體！

kd樹最近鄰搜索例題：

給定一個二維空間的數據集：

T = {（2,3），（5,4），（9,6）,（4,7），（8,1），（7,2）}，輸入目標實例為K(8.5,1),求K的最近鄰。

首先我們由上面可以給出，T的kd樹對應如下：

我們此時的K（8.5,1），根據演算法第一步得：第一層的x軸K點為8大於F點的7，所以進入F（7,2）的右子樹，進入下面紅色線條區域：

到了第二層，分割平面坐標為y軸，K點y軸坐標為1，小於C點y軸坐標6，則繼續向右走，在下圖紅色線條區域內：

則此時演算法對應第（1）部分完成，我們找到了葉子節點E（8,1）。

我們進行演算法第（2）步，把E（8,1）作為最近鄰點。此時我們算一下KE之間的距離為0.5（便於後面步驟用到）.

然後進行演算法第（3）步，遞歸的往上回退，每個結點進行相同步驟，好，我現在從E點回退到C點，對應圖片如下；

此時對C點進行第（3）步的（a）操作，判斷一下KC距離與保存的最近鄰距離（這時是KE）比較，KC距離為點K（8.5,1）與點C（9,6）之間的距離>最近鄰0.5，於是不更新最近鄰點。

然後對C點進行第（3）步的（b）操作，判斷一下當前最近鄰的距離畫一個圓是否與C點切割面相交，如圖所示：

我們很容易看到與C點切割面並沒有相交，於是執行由C點回退到它的父結點F點。如圖：

對F點進行（a），（b）操作！

進行（a）步驟，判斷FK的距離是否小於當前保存的最小值，FK=>0.5，所以不改變最小距離

下面我們進行（b）步驟，為了判斷F點的另一半區域是否有更小的點，判斷一下當前最近鄰的距離畫一個圓是否與F點切割面相交，如圖所示：

發現與任何分割線都沒有交點，那麼執行演算法最後一步，此時F點已經是根結點，無法進行回退，那麼我們可以得到我們保留的當前最短距離點E點就是我們要找的最近鄰點！任務完成，

並且根據演算法流程，我們並沒有遍歷所有數據點，而是F點的左孩子根本沒有遍歷，節省了時間，但是並不是所有的kd樹都能到達這樣的效果。

四、kd樹的不足以及最差情況舉例

講解這個知識點，我還是通過一個例子來直觀說明!

給定一個二維空間的數據集：

T = {（2,3），（5,4），（9,6）,（4,7），（8,1），（7,2）}，輸入目標實例為K(8,3),求K的最近鄰。

首先我們由上面可以給出，T的kd樹對應如下：

我們此時的K（8,3），根據演算法第一步得：第一層的x軸K點為8大於F點的7，所以進入F（7,2）的右子樹，進入下面紅色線條區域：

（注意：這裡葉子節點畫不畫分割線都沒有關係！）

到了第二層，分割平面坐標為y軸，K點y軸坐標為3，小於C點y軸坐標6，則繼續向右走，在下圖紅色線條區域內：

則此時演算法對應第（1）部分完成，我們找到了葉子節點E（8,1）。

我們進行演算法第（2）步，把E（8,1）作為最近鄰點。此時我們算一下KE之間的距離為2（便於後面步驟用到）.

然後進行演算法第（3）步，遞歸的往上回退，每個結點進行相同步驟，好，我現在從E點回退到C點，對應圖片如下；

此時對C點進行第（3）步的（a）操作，判斷一下KC距離與保存的最近鄰距離（這時是KE）比較，KC距離為點K（8,3）與點C（9,6）之間的距離>最近鄰2，於是不更新最近鄰點。

然後對C點進行第（3）步的（b）操作，判斷一下當前最近鄰的距離畫一個圓是否與C點切割面相交，如圖所示：

我們很容易看到與C點切割面並沒有相交，於是執行由C點回退到它的父結點F點。如圖：

對F點進行（a），（b）操作！

進行（a）步驟，判斷FK的距離是否小於當前保存的最小值，FK=

<2,所以將最小距離替換為FK的距離！

下面我們進行（b）步驟，為了判斷F點的另一半區域是否有更小的點，判斷一下當前最近鄰的距離畫一個圓是否與F點切割面相交，如圖所示：

我們可以看出，此時圓與F點有交點，那麼說明F點左側是有可能存在與K點距離更小的點（注:這裡我們人為看起來好像沒有，但是計算機不知道，必須搜索下去，只要以當前最小值畫圓發現與節點切割面有交點，那麼一定要進行搜索，不然數據如果是下圖：）

如果不進行搜索，我們就可能會漏掉Z數據點，因為KZ比當前最小值KF小！

此時相交，我們就需要再F點的左孩子進行搜索，一直搜索到葉子節點A，然後進行（a），（b）步驟，繼續回溯到它的父親結點B，以及最後到達F點，完成最後的最近鄰是F點，這裡幾乎遍歷了所有數據點，幾乎退化了為線性時間0（n）了。這也是kd樹的最差的情況。

當給定的數據分布很差的時候，我們每一次計算畫圓過程中，都會與每一個分割面相交的時候，都會遞歸搜索到該結點的另一個子空間中遍歷，那麼這樣最壞的情況是進行線性時間搜索！比如構建的kd樹和數據分布如下：

如圖所示，我們可以看到幾乎所有的數據離給定預測的點距離很遠，每次進行演算法第三步判斷是否與分割面有交點的時候，幾乎每個面都有交點，只要有交點，就必須將該點的另一半結點遍歷到葉子結點，重複的進行演算法步驟，導致了搜索的低效！

五、k近鄰方法的一些優缺點總結

優點：

1.KNN分類方法是一種非參數的分類技術，簡單直觀，易於實現！只要讓預測點分別和訓練數據求距離，挑選前k個即可，非常簡單直觀。

2.KNN是一種在線技術，新數據可以直接加入數據集而不必進行重新訓練

缺點及改進：

1.當樣本不平衡時，比如一個類的樣本容量很大，其他類的樣本容量很小，輸入一個樣本的時候，K個鄰近值大多數都是大樣本容量的那個類，這時可能會導致分類錯誤。

改進方法：對K鄰近點進行加權，也就是距離近的權值大，距離遠的點權值小。

2.計算量較大，每個待分類的樣本都要計算它到全部點的距離，根據距離排序才能求得K個臨近點。

改進方法：先對已知樣本帶你進行裁剪，事先去除分類作用不大的樣本，採取kd樹以及其它高級搜索方法BBF等演算法減少搜索時間。

參考：

李航老師《統計學習方法》

【量化課堂】一隻兔子幫你理解 kNN

【量化課堂】kd 樹演算法之詳細篇

從K近鄰演算法、距離度量談到KD樹、SIFT+BBF演算法 - 結構之法 演算法之道 - 博客頻道 - CSDN.NET

致謝：德川，皓宇，繼豪，施琦

推薦閱讀：