鑽石舞台

由於公眾號改版不再按照作者的發布時間進行推送，為防止各位朋友錯過月來客棧推送的最新文章，大家可以手動將公眾號設置為「星標⭐」以第一時間獲得推送內容，感謝各位~

各位朋友大家好，我是掌柜空字符，歡迎來到月來客棧。

在前3章中，筆者分別介紹了線性回歸、邏輯回歸以及模型的改善與泛化。從這章開始，我們將繼續學習下一個新的算法模型——K近鄰（K-Nearest Neighbor, KNN），也稱為K近鄰。那麼什麼又是K近鄰呢?

以下為內容目錄，大家可以根據需要進行定位。

某一天，你和幾位朋友準備去外面聚餐，但是就晚上吃什麼菜一直各持己見。最後，無奈的你提出用多數服從少數的原則來進行選擇。於是你們每個人都將自己想要吃的東西寫在了紙條上，最後的統計情況是：3個人贊成吃火鍋、2個人贊成吃炒菜、1個人贊成吃自助。當然，最後你們一致同意按照多數人的意見去吃了火鍋。那這個吃火鍋和K近鄰有什麼關係呢？吃火鍋確實跟K近鄰沒關係，但是整個決策的過程卻完全體現了K近鄰算法的決策過程。

公眾號回復」跟我一起機器學習「即可獲得本文高清PDF內容與教學PPT！

點擊進入討論區「NO. 0005」

如圖5-1所示，黑色樣本點為原始的訓練數據，並且包含了0,1,2這3個類別（分別為圖中不同形狀的樣本點）。現在拿到一個新的樣本點（圖中黑色倒三角），需要對其所屬類別進行分類。那K近鄰是如何對其進行分類的呢？

首先KNN會確定一個K值；然後選擇離自己（黑色倒三角樣本點）最近的K個樣本點；最後，根據投票的規則（Majority Voting Rule）確定新樣本應該所屬的類別。如圖5-1所示，示例中選擇了離三角形樣本點最近的14個樣本點（方形4個、圓形7個、星形3個）。並且在圖中，離三角形樣本點最近的14個樣本中 最多的為圓形樣本，所以KNN算法將把新樣本歸類為類別1。

因此，對於K近鄰算法的原理可以總結為如下三個步驟：

1) 首先確定一個K值;

用於選擇離自己（三角形樣本點）最近的樣本數。

2) 然後選擇一種度量距離;

用來計算得到離自己最近的K個樣本，示例中採用了應用最為廣泛的歐氏距離。

3) 最後確定一種決策規則；

用來判定新樣本所屬類別，示例中採用了基於投票的分類規則。

可以看出，KNN分類的3個步驟其實也就對應了3個超參數的選擇。但是，通常來說對於決策規則的選擇基本上都是採用了基於投票的分類規則，因此下面對於這個問題也就不再進行額外的討論。

K值的選擇會極大程度上影響KNN的分類結果。如圖5-2所示，可以想象如果在分類過程中選擇較小的K值，將會使得模型的訓練誤差減小而使得模型的泛化誤差增大，也就是模型過於複雜而產生了過擬合現象。當選擇較大的K值時，將使得模型趨於簡單，容易發生欠擬合的情況。極端情況下，如果直接將K值設置為樣本總數，那麼無論新輸入的樣本點位於什麼地方，模型都將會簡單地預測它為訓練樣本最多的類別，且會恆定不變。因此，對於K值的選擇，依然建議使用第4章介紹的交叉驗證方法進行選擇。

在樣本空間中，任意兩個樣本點之間的距離都可以看作是兩個樣本點之間相似性的度量。兩個樣本點之間的距離越近，也就也就意味着這兩個樣本點越相似。在第10章介紹聚類算法時，同樣也會用到樣本點間相似性的度量。同時，不同的距離度量方式將會產生不同的距離，進而最後產生不同的分類結果。雖然一般情況下KNN使用的都是歐式距離，但也可以是其它距離，例如更一般的距離或者Minkowski距離[1]。

設訓練樣本其中，即每個樣本包含個特徵維度，則距離定義為

當然，同樣能取其它任意的正整數，然後按照式進行計算即可。

例如現有二維空間的3個樣本點，，則其在不同取值下，距離樣本點最近鄰的點為

由式可知，當時，離樣本點最近的樣本點分別是。

在正式介紹如何用sklearn庫來完成KNN的建模任務前，筆者先來總結一下sklearn的使用方法，這樣更加有利於後續內容的學習。

根據第2、3、4章中的示例代碼可以發現，sklearn在實現各類算法模型時基本上都遵循了統一的接口風格，這使得我們在剛開始學習的時候很容易就能入門上手。總結起來，在sklearn中對於各類模型的使用，基本上都遵循以下3個步驟：

1) 建立模型

這一步通常來說都是通過在對應的路徑下導入我們需要用到的模型類，例如可以通過如下一行代碼來導入一個基於梯度下降算法優化的分類器。

在導入模型類後，需要通過傳入模型對應的參數來實例化這個模型，例如可以通過如下一行代碼來實例化一個邏輯回歸模型。

同時，由於sklearn在迭代更新中可能會更改一些接口的名稱或者位置，具體的路徑信息可以查看官方的API說明文檔[2]。

2) 訓練模型

在sklearn中，所有模型的訓練（或者計算）過程都是通過model.fit()這個方法來完成。並且一般情況下需要按實際情況在調用model.fit()時傳入相應參數。如果是有監督模型則一般是model.fit(x,y)，無監督則是mode.fit(x)。同時，還可可以調用model.score(x,y)來對模型的結果進行評估。

3) 模型預測

在訓練好一個模型後，通常都要對測試集或者新輸入的數據進行預測。在sklearn中一般都是通過模型類對應的model.predict(x)方法來實現的。但這也不是絕對，例如對數據進行預處理時，在調用model.fit()方法在訓練集上計算得到相應的參數後，往往是通過model.transform()方法來對測試集（或新數據）進行的變換。

總體上來講，在sklearn中基本上所有的算法模型都可以通過上面這3個步走來完成對模型的建立、訓練與預測。

從5.2節的分析可知，其實KNN在分類過程中並沒有同之前算法模型一樣，有一個訓練求解參數的過程。這是因為KNN算法根本就沒有可訓練的參數，僅僅只有3個超參數。而KNN算法的核心在於如何快速的找到距離任意一個樣本最近的K個樣本點。當然，最直接的辦法就是挨個遍歷樣本點計算距離，但是當樣本點達到一定數量級後這種做法顯然是行不通。所以此時可以通過建立KD樹（KDTree）或者是Ball樹（BallTree）來解決這一問題。不過這裡暫時不做介紹，先直接通過開源庫sklearn來實現。

本次示例的數據集仍舊採用第4章中介紹的手寫體分類數據集。同時，在下面示例中筆者將介紹如何通過網格搜索（Grid Search）來快速完成模型的選擇，完整代碼見Chapter05/01_knn_train.py文件。

1) 模型選擇

由於在4.6.1節中已經詳細介紹過了該數據集的載入和預處理方法，所以這裡就不再贅述。從上面的分析可以，KNN算法一共有兩個（另外一個暫不考慮）超參數，即K值和度量方式P值。假設兩者的取值分別為n_neighbors = [5, 6, 7, 8, 9, 10],p=[1, 2]，則此時一共就有12個備選模型。同時，如果採用5折交叉驗證，則一共要進行60次的模型擬合，並且需要3個循環來實現。不過好在sklearn中提供了網格所搜的功能可以幫助我們通過4行代碼就實現上述功能，代碼如下：

在上述代碼中，第4行以字典的形式定義了超參數的取值情況，並且需要注意的是，

字典的key必須是類KNeighborsClassifier中參數的名字。其中，類KNeighborsClassifier就是sklearn中所實現的KNN算法模型。因此，該類也包含了KNN中最基本的兩個參數K值和P值。第5行定義了一個KNN模型，但值得注意的是此時並沒有在定義模型的時候就傳入相應的參數，即以KNeighborsClassifier(n_neighbors = 2, p = 2)這樣的形式（其中n_neighbors就是K值）來實例化這個類。因為在使用網格搜索時，需要將模型作為一個參數傳入到GridSearchCV這個類中，同時也需要將模型對應的超參數以字典的形式傳入。第6行在實例化GridSearchCV這個類時便傳入了定義的KNN模型以及參數字典，其中verbose用來控制訓練過程中輸出提示信息的詳細程度，cv=5表示在訓練過程中使用5折交叉驗證。最後，根據傳入的訓練集，便可以對模型進行訓練。

在模型訓練完成後，便可以輸出最佳模型（超參數組合），以及此時對應的模型得分，如下所示

從最終的輸出結果可知，當數K取值為5且P取值為1時所對應的模型最佳。同時，由於模型在進行交叉驗證時各個擬合過程之間相互獨立的，為了提高整個過程的訓練速度，GridSearchCV還支持以並行的方式進行參數搜索。當在實例化類GridSearchCV時，只需要同時指定n_jobs=2即可實現參數的並行搜索，它表示同時使用CPU的兩個核來進行計算。當然也可以指定為-1，即使用所有的核同時進行計算。

2) 模型測試

在經過網格搜索得到最優參數組合後，便可以再拿完整的訓練集重新再訓練一次模型，然後再來評估其在測試集上的泛化誤差。當然，在這裡也可以直接使用GridSearchCV中的predict()和score()方法來得到測試集的預測結果以及對應的準確率，即gs.predict(x_test)和gs.score(x_test,y_test)。

這樣，便能夠得到模型在測試集上的泛化誤差。

在這節內容中，文章筆者首先通過一個引例介紹了KNN分類器的主要思想；接着介紹了K值對算法結果的影響，以及介紹了衡量樣本間距離的不同度量方式；最後筆者通過開源的sklearn框架介紹了如何建模使用KNN分類器，並同時還總結了sklearn中模型使用的3個步驟以及如何使用GridSearch來實現超參數的並行搜索。

在前面幾節內容在，筆者分別介紹了KNN分類器的基本原理以及其如何通過開源的sklearn框架來實現KNN的建模。不過到目前為止，還有一個問題沒有解決的就是如何快速的找到當前樣本點周圍最近的K個樣本點。通常來說，這一問題可以通過樹來解決，下面開始介紹其具體原理。

到此對於整個KNN算法的基本內容就介紹完了，如果客官覺得內容對自己有所幫助，還望給掌柜點個讚。

樹（-Dimensional Tree）是一種空間劃分數據結構，用於組織維空間中的點，其本質上也就等同於二叉搜索樹。不同的是，在樹中每個節點存儲的並不是一個值，而是一個維的樣本點[3]。在二叉搜索樹中，任意節點中的值都大於其左子樹中的所有值，小於或等於其右子樹中的所有值，如圖5-3所示。

在樹，所有的節點也都滿足類似二叉搜索樹的特性，即左子樹中所有的樣本點均「小於」其父節點中的樣本點，而右子樹中所有的樣本點均「大於」或「等於」其父節點中的樣本點。因此可以看出，構造樹的關鍵就在於如何定義任意兩個維樣本點之間的大小關係。

具體的，在構造樹時，每一層的節點在劃分左右子樹時只會循環的選擇維中的其中一個維度進行比較。例如樣本點中一共有兩個維度，那麼在對根節點進行劃分時可以以維度對左右子樹進行劃分；接着再以維度對根節點的孩子進行左右子樹劃分；進一步，根節點的孩子的孩子再以維度進行左右子樹劃分，以此循環[4]。同時，為了使得最後得到的是一棵平衡的樹，所以在的構建過程中每次都會選擇當前子樹中對應維度的中位數作為切分點。

例如現在有樣本點[5,7], [3,8], [6,2], [8,5], [15,6], [10,4], [12,13], [9,10],[11,14]，那麼根據上述規則便可以構造得到如圖5-4所示的樹。

從圖5-4可以看出，對於根節點來說其左子樹中所有樣本點的維度均小於9，其右子樹的維度均大於等於9；對於根節點的左孩子來說其左子樹中所有樣本點的維度均小於7，其右子樹中所有樣本點的維度均大於等於7。當然，對於其它節點也都滿足類似的特性。同時，根據樹交替選擇特徵維度對樣本空間進行劃分的特性，以圖5-4中的劃分方式還能得到如圖5-5所示的特徵空間。

圖5-5 樹特徵空間

從圖5-5中可以看出，整個二維平面首先被樣本點[9,10]劃分成了左右兩個部分（對應圖5-4中的左右子樹），接着左右兩個部分又各自分別被[5,7]和[15,6]劃分成了上下兩個部分，直到劃分結束。到此，對於樹的構造就介紹完了，接下來看如何通過樹來完成搜索任務。

在正式介紹K近鄰（即最近的K個樣本點）搜索前，筆者先來介紹如何利用樹進行最近鄰搜索。總的來說，在已知樹中搜索離給定樣本點最近的樣本點時，首先設定一個當前全局最佳點和一個當前全局最短距離，分別用來保存當前離最近的樣本點以及對應的距離；然後從根節點開始以類似生成樹的規則來遞歸的遍歷樹中的節點，如果當前節點離的距離小於全局最短距離，那麼更新全局最佳點和全局最短距離；如果被搜索點到當前節點劃分維度的距離小於全局最短距離，那麼再遞歸遍歷當前節點另外一個子樹，直至整個遞歸過程結束。具體步驟可以總結為[4]：

(1) 設定一個當前全局最佳點和全局最短距離，分別用來保存當前離搜索點最近的樣本點和最短距離，初始值分別為空和無窮大；

(2) 從根節點開始，並設其為當前節點；

(3) 如果當前節點為空，則結束；

(4) 如果當前節點到被搜索點的距離小於當前全局最短距離，則更新全局最佳點和最短距離；

(5) 如果被搜索點的劃分維度小於當前節點的劃分維度，則設當前節點的左孩子為新的當前節點並執行步驟(3)(4)(5)(6)；反之設當前節點的右孩子為新的當前節點並執行步驟(3)(4)(5)(6)；

(6) 如果被搜索點到當前節點劃分維度的距離小於全局最短距離，則說明全局最佳點可能存在於當前節點的另外一個子樹中，所以設當前節點的另外一個孩子為當前節點並執行步驟(3)(4)(5)(6)；

遞歸完成後，此時的全局最佳點就是在樹中離被搜索點最近的樣本點。

這裡需要明白一點的是，利用步驟(6)中的規則來判斷另外一個子樹中是否可能存在全局最佳點的原理如圖5-6所示。

在圖5-6中，右上角為當前全局最佳點，五角星為被搜索點。可以看到，此時的整個空間被下方的樣本點劃分成了左右兩個部分（子樹）。並且，五角星離左子樹中樣本點的最短距離為五角星到當前劃分維度的距離。顯然，如果被搜索點到當前全局最佳點的距離小於距離，那麼此時左子樹中就不可能存在更優的全局最佳點。

當然，上述步驟還可以通過一個更清晰的偽代碼來進行表達：

在上述代碼中，q_i和curr_node_i分別表示被搜索點和當前節點的劃分維度；curr_node.other表示curr_node.left和curr_node.right中先前未被訪問過的子樹。

在介紹完最近鄰的搜索原理後再來看幾個實際的搜索示例，以便對搜索過程有更加清晰的理解。如圖5-7所示，左右兩邊分別是5.4.1節中所得到的樹和特徵劃分空間，同時右圖中的五角星為給定的被搜索點，接下來開始在左邊的樹中搜索離點最近的樣本點。

在搜索伊始，全局最佳點和全局最短距離分別為空和無窮大。第1次遞歸：此時設根節點[9,10]為當前節點，因滿足步驟(4)當前節點到被搜索點的距離小於當前全局最短距離，所以更新當前最佳點為[9,10]，全局最短距離為7.07。接着，由於被搜索點的劃分維度10大於當前節點的劃分維度9，因此設當前節點的右孩子[15,6]為新的當前節點。第2次遞歸：繼續執行步驟(4)，由於此時當前節點到被搜索點的距離為5.83，小於全最最短距離，所以更新當前最佳點為[15,6]，全局最短距離為5.83。進一步，由於被搜索點的劃分維度3小於當前節點的劃分維度6，因此設當前節點的左孩子[10,4]為新的當前節點。第3次遞歸：繼續執行步驟(4)，由於此時當前節點到被搜索點的距離為1，小於全最最短距離，所以更新當前最佳點為[10,4]，全局最短距離為1。此時，由於被搜索點的劃分維度10大於等於當前節點的劃分維度10，因此設當前節點的右孩子為新的當前節點，並進入第4次遞歸。

第4次遞歸：由於此時當前節點為空，所以第4次遞歸結束返回第3次遞歸，即此時的當前節點為[10,4]，並繼續執行步驟(6)。由於被搜索點[10,3]到當前劃分維度的距離為0，小於全局最短距離1，說明全局最佳點可能存在於當前節點的左子樹中（此時可以想象假如樹中存在點[9.9,3]）,所以設當前節點的左孩子為新的當前節點。第5次遞歸：由於當前節點為空，所以第5次遞歸結束回到第3次遞歸中。返回第3次遞歸後，此時的當前節點為[10,4]，且已執行完步驟(6)，返回到第2次遞歸中。返回第2次遞歸後，此時的當前節點為[15,6]，並繼續執行步驟(6)。由於被搜索點[10,3]到當前劃分維度的距離為3，大於全局最短距離，則說明節點[15,6]的右子樹中不可能存在全局最佳點，此時返回到第1次遞歸中。返回第1次遞歸後，此時的當前節點為根節點[9,10]，並繼續執行步驟(6)。由於被搜索點[10,3]到當前劃分維度的距離為1，大於等於全局最短距離1，所以當前節點的左子樹中不可能存在全局最佳點。到此步驟(6)執行結束，即所有的遞歸過程都執行完畢。此時的全局最佳點中保存的點[10,4]便是樹中離被搜索點[10,3]最近的樣本點。

經過上述步驟後，相信讀者朋友們對於樹的搜索過程已經有了清晰的認識。同時，各位讀者也可以自己來試着從上述樹中來搜索離[8.9,4]最近的樣本點。在搜索過程中會發現，一開始會從根節點進入左子樹，並找到[8,5]為當前全局最佳點。但是當一步步回溯後會發現，原來右子樹中的[10,4]才是真正離[8.9,4]最近的樣本點。

在介紹完最近鄰的樹搜索原理後便可以輕鬆的理解K近鄰的樹搜索過程。需要注意的是，這裡的兩個「K」分別表示兩種不同的含義，前者表示要搜索得到離給定點最近的K個樣本點，而後者表示的是樣本點的維度。

總的來說K近鄰的搜索過程和最近鄰的搜索過程類似，只是需要額外的維護一個大小為K的有序列表。在整個列表中，當前距離被搜索點最近的樣本點放在首位，而距離被搜索點最遠的樣本點放在末尾。具體的搜索過程可以總結為：

(1) 設定大小為K的有序列表用來保存當前離搜索點最近的K個樣本點；

(2) 從根節點開始，並設其為當前節點；

(3) 如果當前節點為空，則結束；

(4) 如果列表不滿，則直接將當前樣本插入到列表中；如果列表已滿，則判斷當前樣本到被搜索點的距離是否小於列表最後一個元素到被搜索點的距離，成立則將列表中最後一個元素刪除，並插入當前樣本；（每次插入後仍有序）

(5) 如果被搜索點的劃分維度小於當前節點的劃分維度，則設當前節點的左孩子為新的當前節點並執行步驟(3)(4)(5)(6)；反之設當前節點的右孩子為新的當前節點並執行步驟(3)(4)(5)(6)；

(6) 如果列表不滿，或者如果被搜索點到當前節點劃分維度的距離小於列表中最後一個元素到被搜索點的距離，則設當前節點的另外一個孩子為當前節點並執行步驟(3)(4)(5)(6)；

遞歸完成後，此時離被搜索點最近的K個樣本點就是有序列表中的K個元素。

上述步驟同樣可以通過一個更清晰的偽代碼來進行表達：

在上述代碼中，KNearestNodes[-1]表示取有序列表中的最後一個元素；q_i和curr_node_i分別表示被搜索點和當前節點的劃分維度；curr_node.other表示curr_node.left和curr_node.right中先前未被訪問過的子樹。

下面，以圖5-7中的樹為例，來搜索離[10,3]最近的3個樣本點。

在搜索伊始，有序列表為空，K為3。第一次遞歸：此時設根節點[9,10]為當前節點，因滿足步驟(4)中的列表為空的條件，所以直接將根節點加入列表中，即此時KNearestNodes=([9,10])。接着，由於被搜索點的劃分維度10大於當前節點的劃分維度9，因此設當前節點的右孩子[15,6]為新的當前節點。第2次遞歸：繼續執行步驟(4)，由於此時列表未滿，所以直接將當前節點插入列表中，即此時KNearestNodes=([15,6], [9,10])。進一步，由於被搜索點的劃分維度3小於當前節點的劃分維度6，因此設當前節點的左孩子[10,4]為新的當前節點。第3次遞歸：繼續執行步驟(4)，由於此時列表未滿，所以直接將當前節點插入列表中，且由於[10,4]當前離被搜索點最近，所以應該放在列表最前面，即此時KNearestNodes=([10,4], [15,6], [9,10])。進一步，由於被搜索點的劃分維度10大於等於當前節點的劃分維度10，所以設當前節點的右孩子為新的當前節點，並進入第4次遞歸。

第4次遞歸：由於此時當前節點為空，所以第4次遞歸結束並返回到第3次遞歸中，即此時的當前節點為[10,4]，並繼續執行步驟(6)。此時列表已滿，但由於被搜索點[10,3]到當前劃分維度的距離為0，小於被搜索點到有序列表中最後一個樣本點距離，說明可能存在一個比有序列表中最後一個元素更佳的樣本點。所以設當前節點的左孩子為新的當前節點。第5次遞歸：由於當前節點為空，所以第5次遞歸結束回到第3次遞歸中。返回到第3次遞歸後，此時的當前節點為[10,4]，且已執行完步驟(6)，返回到第2次遞歸中。返回到第2次遞歸後，此時的當前節點為[15,6]，並繼續執行步驟(6)。此時列表已滿，但由於被搜索點[10,3]到當前劃分維度的距離為3，小於被搜索點到[9,10]的距離7.07，說明在當前節點[15,6]的右子樹中可能存在一個比[9,10]更佳的樣本點。所以設[15,6]的右孩子[12,13]為新的當前節點。第6次遞歸：此時列表已滿，且由於當前節點到被搜索點的距離10.19，大於被搜索點到[9,10]的距離，所以繼續執行步驟(5)。由於被搜索點的劃分維度10小於當前節點的劃分維度12，所以設[11,14]為新的當前節點，並進入第7次遞歸。

第7次遞歸：此時列表已滿，且由於當前節點到被搜索點的距離11.04，大於被搜索點到[9,10]的距離，所以繼續執行步驟(5)。由於被搜索點的劃分維度3小於當前節點的劃分維度14，所以設[11,14]的左孩子為新的當前節點。第8次遞歸：由於此時當前節點為空，所以第8次遞歸結束並返回到第7次遞歸中，即此時的當前節點為[11,14]，並繼續執行步驟(6)。此時列表已滿，且由於被搜索點[10,3]到當前劃分維度的距離為11，大於被搜索點到有序列表中最後一個樣本點距離，所以第7次遞歸結束並回到第6次遞歸。

返回第6次遞歸後，此時的當前節點為[12,13]，繼續執行步驟(6)。此時列表已滿，且由於被搜索點[10,3]到當前劃分維度的距離為2，小於被搜索點到有序列表中最後一個樣本點的距離，說明當前節點[12,13]的右子樹中存在比[9,10]更近的點（可以想象假設存在點[12.1,6.1]），所以設[12,13]的右孩子為新的當前節點。第9次遞歸：由於此時當前節點為空，所以第9次遞歸結束並返回到第6次遞歸中，即此時的當前節點為[12,13]，且已經執行完步驟(6)，進而返回到第2次遞歸。返回到第2次遞歸後，此時的當前節點為[15,6]，且已執行完步驟(6)，進而返回到第1次遞歸中。

返回第1次遞歸後，此時的當前節點為[9,10]，繼續執行步驟(6)。此時列表已滿，但由於被搜索點[10,3]到當前劃分維度的距離為1，小於被搜索點到有序列表中最後一個樣本點的距離，說明當前節點[9,10]的左子樹中存在比[9,10]更近的點（從圖5-7中一眼便能看出，例如點[8,5]），所以設[5,7]為新的當前節點。第10次遞歸：此時列表已滿，但由於當前節點到被搜索點的距離6.4，小於被搜索點到有序列表中最後一個樣本點[9,10]的距離7.07，因此更新KNearestNodes=([10,4], [15,6], [5,7])，並繼續執行步驟(5)。由於被搜索點的劃分維度3小於當前節點的劃分維度7，所以設[8,5]為新的當前節點，並進入第11次遞歸。

第11次遞歸：此時列表已滿，但由於當前節點到被搜索點的距離2.83，小於被搜索點到有序列表中最後一個樣本點[5,7]的距離6.4，因此更新KNearestNodes=([10,4], [8,5], [15,6])，並繼續執行步驟(5)。由於被搜索點的劃分維度10大於當前節點的劃分維度8，所以設[8,5]的右孩子為新的當前節點。第12次遞歸：由於此時當前節點為空，所以第12次遞歸結束並返回到第11次遞歸中，即此時的當前節點為[8,5]，並繼續執行步驟(6)。此時列表已滿，但由於被搜索點[10,3]到當前劃分維度的距離為2，小於被搜索點到有序列表中最後一個樣本點的距離，所以設[6,3]為新的當前節點，並進入第13次遞歸。

第13次遞歸：此時列表已滿，但由於當前節點到被搜索點的距離4.0，小於被搜索點到有序列表中最後一個樣本點[15,6]的距離5.83，因此更新KNearestNodes=([10,4], [8,5], [6,3])，並繼續執行步驟(5)。由於被搜索點的劃分維度3大於等於當前節點的劃分維度3，所以設[6,3]的右孩子為新的當前節點。第14次遞歸：由於此時當前節點為空，所以第14次遞歸結束並返回到第13次遞歸中，即此時的當前節點為[6,3]，並繼續執行步驟(6)。此時列表已滿，但由於被搜索點[10,3]到當前劃分維度的距離為0，小於被搜索點到有序列表中最後一個樣本點的距離，說明[6,3]的左子樹中存在比[6,3]更近的點（可以想象假設存在點[7,2.9]），所以設[6,3]的左孩子為新的當前節點，並進入第15次遞歸。

第15次遞歸：由於此時當前節點為空，所以第15次遞歸結束並返回到第13次遞歸中，即此時的當前節點為[6,3]，且已經執行完步驟(6)進一步返回第11次遞歸中。返回第11次遞歸後，此時的當前節點為[8,5]，且已經執行完步驟(6)進一步返回第10次遞歸中。返回第10次遞歸後，當前節點為[5,7]，繼續執行步驟(6)。由於此時列表已滿，且被搜索點[10,3]到當前劃分維度的距離4，大於等於被搜索點到有序列表中最後一個樣本點[6,3]的距離，所以[5,7]的右子樹中不可能存在比[6,3]更近的點，故返回第1次遞歸。

在返回到第1次遞歸後，此時的當前節點為[9,10]，且已執行完步驟(6)，即所有的遞歸過程結束。此時有序列表中的元素便為樹中離被搜索點[10,3]最近的3個樣本點，即KNearestNodes=([10,4], [8,5], [6,3])。整個遞歸過程順序如圖5-8所示。

到此，對於K近鄰算法的原理就介紹完了。

點擊進入討論區「NO. 0005」

在本節中，筆者首先介紹了樹的基本原理，以及如何來構造一棵樹；接着介紹了如何通過樹來搜索離給定點最近的樣本點，並通過一個實際的搜索示例來進行了詳細的介紹；最後介紹了如何在最近鄰的基礎上，在樹中來搜索離給定點最近的K個樣本點，即K近鄰搜索。

總結一下，在本章中筆者首先介紹了K近鄰算法的主要思想及其原理，包括K值選擇和距離的度量方式等；接着簡單的總結了sklearn框架接口的設計風格以及通用的建模步驟；然後介紹了如何通過sklearn來建立完整的KNN分類器，包括模型訓練、模型選擇、並行搜索和交叉驗證等；最後詳細介紹了如何通過樹來實現KNN中K近鄰樣本點的搜索。

本次內容就到此結束，感謝您的閱讀！如果客官覺得上述內容對你有所幫助，可以給掌柜一個贊。青山不改，綠水長流，我們月來客棧見！

[1]《統計機器學習》李航

[2]Scikit-learn: Machine Learning in Python, Pedregosa et al., JMLR 12, pp. 2825-2830, 2011.

[3]https://en.wikipedia.org/wiki/K-d_tree

[4]http://web.stanford.edu/class/cs106l/

[1]第1章 機器學習入門之環境安裝配置（附高清PDF與教學PPT）

[2]第2章 從零認識線性回歸（附高清PDF與教學PPT）

[3]第3章 從零認識邏輯回歸（附高清PDF與教學PPT）

[4]第4章 模型的改善與泛化（附高清PDF與教學PPT）

都滑到這兒了，隨手幫掌柜點個讚👍🏻吧！