knn演算法復雜度

① KNN演算法-4-演算法優化-KD樹

KNN演算法的重要步驟是對所有的實例點進行快速k近鄰搜索。如果採用線性掃描（linear scan），要計算輸入點與每一個點的距離，時間復雜度非常高。因此在查詢操作時，可以使用kd樹對查詢操作進行優化。

Kd-樹是K-dimension tree的縮寫，是對數據點在k維空間（如二維(x，y)，三維(x，y，z)，k維(x1，y，z..)）中劃分的一種數據結構，主要應用於多維空間關鍵數據的搜索（如：范圍搜索和最近鄰搜索）。本質上說，Kd-樹就是一種平衡二叉樹。

k-d tree是每個節點均為k維樣本點的二叉樹，其上的每個樣本點代表一個超平面，該超平面垂直於當前劃分維度的坐標軸，並在該維度上將空間劃分為兩部分，一部分在其左子樹，另一部分在其右子樹。即若當前節點的劃分維度為d，其左子樹上所有點在d維的坐標值均小於當前值，右子樹上所有點在d維的坐標值均大於等於當前值，本定義對其任意子節點均成立。

必須搞清楚的是，k-d樹是一種空間劃分樹，說白了，就是把整個空間劃分為特定的幾個部分，然後在特定空間的部分內進行相關搜索操作。想像一個三維(多維有點為難你的想像力了)空間，kd樹按照一定的劃分規則把這個三維空間劃分了多個空間，如下圖所示：

首先，邊框為紅色的豎直平面將整個空間劃分為兩部分，此兩部分又分別被邊框為綠色的水平平面劃分為上下兩部分。最後此4個子空間又分別被邊框為藍色的豎直平面分割為兩部分，變為8個子空間，此8個子空間即為葉子節點。

常規的k-d tree的構建過程為：

對於構建過程，有兩個優化點：

例子：採用常規的構建方式，以二維平面點(x,y)的集合(2,3)，(5,4)，(9,6)，(4,7)，(8,1)，(7,2) 為例結合下圖來說明k-d tree的構建過程：

如上演算法所述，kd樹的構建是一個遞歸過程，我們對左子空間和右子空間內的數據重復根節點的過程就可以得到一級子節點（5,4）和（9,6），同時將空間和數據集進一步細分，如此往復直到空間中只包含一個數據點。

如之前所述，kd樹中，kd代表k-dimension，每個節點即為一個k維的點。每個非葉節點可以想像為一個分割超平面，用垂直於坐標軸的超平面將空間分為兩個部分，這樣遞歸的從根節點不停的劃分，直到沒有實例為止。經典的構造k-d tree的規則如下：

kd樹的檢索是KNN演算法至關重要的一步，給定點p，查詢數據集中與其距離最近點的過程即為最近鄰搜索。

如在構建好的k-d tree上搜索(3,5)的最近鄰時，對二維空間的最近鄰搜索過程作分析。

首先從根節點(7,2)出發，將當前最近鄰設為(7,2)，對該k-d tree作深度優先遍歷。

以(3,5)為圓心，其到(7,2)的距離為半徑畫圓（多維空間為超球面），可以看出(8,1)右側的區域與該圓不相交，所以(8,1)的右子樹全部忽略。

接著走到(7,2)左子樹根節點(5,4)，與原最近鄰對比距離後，更新當前最近鄰為(5,4)。

以(3,5)為圓心，其到(5,4)的距離為半徑畫圓，發現(7,2)右側的區域與該圓不相交，忽略該側所有節點，這樣(7,2)的整個右子樹被標記為已忽略。

遍歷完(5,4)的左右葉子節點，發現與當前最優距離相等，不更新最近鄰。所以(3,5)的最近鄰為(5,4)。

舉例：查詢點（2.1,3.1）

星號表示要查詢的點（2.1,3.1）。通過二叉搜索，順著搜索路徑很快就能找到最鄰近的近似點，也就是葉子節點（2,3）。而找到的葉子節點並不一定就是最鄰近的，最鄰近肯定距離查詢點更近，應該位於以查詢點為圓心且通過葉子節點的圓域內。為了找到真正的最近鄰，還需要進行相關的『回溯'操作。也就是說，演算法首先沿搜索路徑反向查找是否有距離查詢點更近的數據點。

舉例：查詢點（2，4.5）

一個復雜點了例子如查找點為（2，4.5），具體步驟依次如下：

上述兩次實例表明，當查詢點的鄰域與分割超平面兩側空間交割時，需要查找另一側子空間，導致檢索過程復雜，效率下降。

一般來講，最臨近搜索只需要檢測幾個葉子結點即可，如下圖所示：

但是，如果當實例點的分布比較糟糕時，幾乎要遍歷所有的結點，如下所示：

研究表明N個節點的K維k-d樹搜索過程時間復雜度為： 。

同時，以上為了介紹方便，討論的是二維或三維情形。但在實際的應用中，如SIFT特徵矢量128維，SURF特徵矢量64維，維度都比較大，直接利用k-d樹快速檢索（維數不超過20）的性能急劇下降，幾乎接近貪婪線性掃描。假設數據集的維數為D，一般來說要求數據的規模N滿足N»2D，才能達到高效的搜索。

Sklearn中有KDTree的實現，僅構建了一個二維空間的k-d tree，然後對其作k近鄰搜索及指定半徑的范圍搜索。多維空間的檢索，調用方式與此例相差無多。

② kNN（k-NearestNeighbor）演算法

參考《數據挖掘10大演算法》對kNN演算法進行基本總結，附有一個Python3的簡例。

基本思想
從訓練集中找出 k 個最接近測試對象的訓練對象，再從這 k 個對象中找出居於主導的類別，將其賦給測試對象。

定位
由於這種總體占優的決策模式，對於類域的交叉、重疊較多的或者多模型、多標簽的待分樣本集來說，kNN方法較其他方法更為適合。kNN演算法屬於有監督學習的分類演算法。

避開了兩個問題
（1）分類時對象之間不可能完全匹配（kNN方法計算的是對象之間的距離）；
（2）具有相同屬性的對象有不同的類別（kNN方法依據總體占優的類別進行決策，而不是單一對象的類別進行決策）。

需要考慮幾個關鍵要素
（1）訓練集；
（2）用於計算對象之間臨近的程度或者其他相似的指標；
（3）最近鄰的個數 k；
（4）基於 k 個最近鄰及其類別對目標對象類別進行判定的方法。

kNN方法很容易理解和實現，在一定條件下，其分類錯誤率不會超過最優貝葉斯錯誤率的兩倍。一般情況下，kNN方法的錯誤率會逐漸收斂到最優貝葉斯錯誤率，可以用作後者的近似。

基本演算法

演算法的存儲復雜度為O(n)，時間復雜度為O(n)，其中 n 為訓練對象的數量。

影響kNN演算法性能的幾個關鍵因素
（1）k 值的選擇；
如果 k 值選得過小，結果就會對雜訊點特別敏感；k 值選得過大就會使得近鄰中包含太多別的類的點。最佳 k 值的估計可以使用交叉驗證的方法。通常，使用 k=1會有一個比較好的結果（特別是對於小數據集的情況）。但是，在樣本很充足的情況下，選擇較大的 k 值可以提高抗噪能力。

（2）類別決策時的綜合方法；
對目標對象的類別進行決策，最簡單的就是使用總體占優方法（簡單投票，票數最多的一類勝出）。稍微復雜一點，考慮近鄰中每個點與目標對象的距離不同，對決策的份量進行加權考慮。

（3）距離測量標準的選擇。
距離測量的標准一般選擇 歐幾里得距離 或者 曼哈頓距離 。

簡單例子

③ 01 KNN演算法 - 概述

KNN演算法 全稱是K近鄰演算法 （K-nearst neighbors，KNN）

KNN是一種基本的機器學習演算法，所謂K近鄰，就是k個最近的鄰居。即每個樣本都可以用和它 最接近的k個鄰近位置的樣本 來代替。

KNN是個相對比較簡單的演算法，比起之前提過的回歸演算法和分類演算法更容易。如果一個人從來沒有接觸過機器學習的演算法，拿到數據後最容易想到的分類方式就是K近鄰。打個比方：你們想了解我是個怎樣的人，然後你們發現我的身邊關系最密切的朋友是一群逗逼，所以你們可以默認我也是一個逗逼。

KNN演算法即可以應用於 分類演算法 中，也可以應用於 回歸演算法 中。

KNN在做回歸和分類的主要區別，在於最後做預測時候的決策不同。在分類預測時，一般採用 多數表決法 。在做回歸預測時，一般使用 平均值法 。

多數表決法： 分類時，哪些樣本離我的目標樣本比較近，即目標樣本離哪個分類的樣本更接近。

平均值法： 預測一個樣本的平均身高，觀察目標樣本周圍的其他樣本的平均身高，我們認為平均身高是目標樣本的身高。

再舉個例子：
分別根據甜度和脆度兩個特徵來判斷食物的種類。
根據樣本我們普遍發現：
比較甜，比較脆的食物都是水果。
不甜，不太脆的食物是蛋白質。
不甜，比較脆的食物是蔬菜。
於是根據目標的樣本甜度和脆度兩個特徵，我們可以對其進行分類了。

k值的選擇:
先選一個較小的值，然後通過交叉驗證選擇一個合適的最終值。
k越小，即使用較小的領域中的樣本進行預測，訓練誤差會減小，但模型會很復雜，以至於過擬合。
k越大，即使用交大的領域中的樣本進行預測，訓練誤差會增大，模型會變得簡單，容易導致欠擬合。

距離的度量:
使用歐幾里得距離：歐幾里得度量（euclidean metric）（也稱歐氏距離）是一個通常採用的距離定義，指在m維空間中兩個點之間的真實距離，或者向量的自然長度（即該點到原點的距離）。在二維和三維空間中的歐氏距離就是兩點之間的實際距離。

決策規劃:
分類：多數表決法、加權多數表決法。
回歸：平均值法、加權平均值法。

加權多數表決法：

平均值法和加權平均值法：
同樣看上面的圖，上方的三個樣本值為3，下面兩個樣本值為2，預測？的值。
如果不考慮加權，直接計算平均值：
(3 * 3 + 2 * 2) / 5 = 2.6

加權平均值：權重分別為1/7和2/7。計算加權平均值：
(3 * 3* 1/7 + 2 * 2 * 2/7) / 5 = 2.43

1、蠻力實現(brute)：
計算預測樣本到所有訓練集樣本的距離，然後選擇最小的k個距離，即可得到k個最鄰近點。
缺點：當特徵數多、樣本數多時，演算法的效率比較低。

2、KD樹 (kd_tree)：
首先對訓練數據進行建模，構建KD樹，然後根據建好的模型來獲取鄰近樣本數據。
後續內容會介紹KD樹搜索最小值的方式，讓大家直觀感受到KD樹比蠻力實現要少檢索多少數據。

④ k近鄰演算法的案例介紹

如 上圖所示，有兩類不同的樣本數據，分別用藍色的小正方形和紅色的小三角形表示，而圖正中間的那個綠色的圓所標示的數據則是待分類的數據。也就是說，現在， 我們不知道中間那個綠色的數據是從屬於哪一類（藍色小正方形or紅色小三角形），下面，我們就要解決這個問題：給這個綠色的圓分類。我們常說，物以類聚，人以群分，判別一個人是一個什麼樣品質特徵的人，常常可以從他/她身邊的朋友入手，所謂觀其友，而識其人。我們不是要判別上圖中那個綠色的圓是屬於哪一類數據么，好說，從它的鄰居下手。但一次性看多少個鄰居呢？從上圖中，你還能看到：
如果K=3，綠色圓點的最近的3個鄰居是2個紅色小三角形和1個藍色小正方形，少數從屬於多數，基於統計的方法，判定綠色的這個待分類點屬於紅色的三角形一類。 如果K=5，綠色圓點的最近的5個鄰居是2個紅色三角形和3個藍色的正方形，還是少數從屬於多數，基於統計的方法，判定綠色的這個待分類點屬於藍色的正方形一類。 於此我們看到，當無法判定當前待分類點是從屬於已知分類中的哪一類時，我們可以依據統計學的理論看它所處的位置特徵，衡量它周圍鄰居的權重，而把它歸為(或分配)到權重更大的那一類。這就是K近鄰演算法的核心思想。
KNN演算法中，所選擇的鄰居都是已經正確分類的對象。該方法在定類決策上只依據最鄰近的一個或者幾個樣本的類別來決定待分樣本所屬的類別。
KNN 演算法本身簡單有效，它是一種 lazy-learning 演算法，分類器不需要使用訓練集進行訓練，訓練時間復雜度為0。KNN 分類的計算復雜度和訓練集中的文檔數目成正比，也就是說，如果訓練集中文檔總數為 n，那麼 KNN 的分類時間復雜度為O(n)。
KNN方法雖然從原理上也依賴於極限定理，但在類別決策時，只與極少量的相鄰樣本有關。由於KNN方法主要靠周圍有限的鄰近的樣本，而不是靠判別類域的方法來確定所屬類別的，因此對於類域的交叉或重疊較多的待分樣本集來說，KNN方法較其他方法更為適合。
K 近鄰演算法使用的模型實際上對應於對特徵空間的劃分。K 值的選擇，距離度量和分類決策規則是該演算法的三個基本要素： K 值的選擇會對演算法的結果產生重大影響。K值較小意味著只有與輸入實例較近的訓練實例才會對預測結果起作用，但容易發生過擬合；如果 K 值較大，優點是可以減少學習的估計誤差，但缺點是學習的近似誤差增大，這時與輸入實例較遠的訓練實例也會對預測起作用，是預測發生錯誤。在實際應用中，K 值一般選擇一個較小的數值，通常採用交叉驗證的方法來選擇最優的 K 值。隨著訓練實例數目趨向於無窮和 K=1 時，誤差率不會超過貝葉斯誤差率的2倍，如果K也趨向於無窮，則誤差率趨向於貝葉斯誤差率。 該演算法中的分類決策規則往往是多數表決，即由輸入實例的 K 個最臨近的訓練實例中的多數類決定輸入實例的類別 距離度量一般採用 Lp 距離，當p=2時，即為歐氏距離，在度量之前，應該將每個屬性的值規范化，這樣有助於防止具有較大初始值域的屬性比具有較小初始值域的屬性的權重過大。 KNN演算法不僅可以用於分類，還可以用於回歸。通過找出一個樣本的k個最近鄰居，將這些鄰居的屬性的平均值賦給該樣本，就可以得到該樣本的屬性。更有用的方法是將不同距離的鄰居對該樣本產生的影響給予不同的權值(weight)，如權值與距離成反比。該演算法在分類時有個主要的不足是，當樣本不平衡時，如一個類的樣本容量很大，而其他類樣本容量很小時，有可能導致當輸入一個新樣本時，該樣本的K個鄰居中大容量類的樣本佔多數。 該演算法只計算「最近的」鄰居樣本，某一類的樣本數量很大，那麼或者這類樣本並不接近目標樣本，或者這類樣本很靠近目標樣本。無論怎樣，數量並不能影響運行結果。可以採用權值的方法（和該樣本距離小的鄰居權值大）來改進。
該方法的另一個不足之處是計算量較大，因為對每一個待分類的文本都要計算它到全體已知樣本的距離，才能求得它的K個最近鄰點。目前常用的解決方法是事先對已知樣本點進行剪輯，事先去除對分類作用不大的樣本。該演算法比較適用於樣本容量比較大的類域的自動分類，而那些樣本容量較小的類域採用這種演算法比較容易產生誤分。
實現 K 近鄰演算法時，主要考慮的問題是如何對訓練數據進行快速 K 近鄰搜索，這在特徵空間維數大及訓練數據容量大時非常必要。

⑤ KNN演算法常見問題總結

給定測試實例，基於某種距離度量找出訓練集中與其最靠近的k個實例點，然後基於這k個最近鄰的信息來進行預測。

通常，在分類任務中可使用「投票法」，即選擇這k個實例中出現最多的標記類別作為預測結果；在回歸任務中可使用「平均法」，即將這k個實例的實值輸出標記的平均值作為預測結果；還可基於距離遠近進行加權平均或加權投票，距離越近的實例權重越大。

k近鄰法不具有顯式的學習過程，事實上，它是懶惰學習（lazy learning）的著名代表，此類學習技術在訓練階段僅僅是把樣本保存起來，訓練時間開銷為零，待收到測試樣本後再進行處理。

KNN一般採用歐氏距離，也可採用其他距離度量，一般的Lp距離：

KNN中的K值選取對K近鄰演算法的結果會產生重大影響。如果選擇較小的K值，就相當於用較小的領域中的訓練實例進行預測，「學習」近似誤差（近似誤差：可以理解為對現有訓練集的訓練誤差）會減小，只有與輸入實例較近或相似的訓練實例才會對預測結果起作用，與此同時帶來的問題是「學習」的估計誤差會增大，換句話說，K值的減小就意味著整體模型變得復雜，容易發生過擬合；

如果選擇較大的K值，就相當於用較大領域中的訓練實例進行預測，其優點是可以減少學習的估計誤差，但缺點是學習的近似誤差會增大。這時候，與輸入實例較遠（不相似的）訓練實例也會對預測器作用，使預測發生錯誤，且K值的增大就意味著整體的模型變得簡單。

在實際應用中，K值一般取一個比較小的數值，例如採用交叉驗證法來選擇最優的K值。經驗規則：k一般低於訓練樣本數的平方根

1、計算測試對象到訓練集中每個對象的距離

2、按照距離的遠近排序

3、選取與當前測試對象最近的k的訓練對象，作為該測試對象的鄰居

4、統計這k個鄰居的類別頻率

5、k個鄰居里頻率最高的類別，即為測試對象的類別

輸入X可以採用BallTree或KDTree兩種數據結構，優化計算效率，可以在實例化KNeighborsClassifier的時候指定。

KDTree

基本思想是，若A點距離B點非常遠，B點距離C點非常近， 可知A點與C點很遙遠，不需要明確計算它們的距離。 通過這樣的方式，近鄰搜索的計算成本可以降低為O[DNlog(N)]或更低。 這是對於暴力搜索在大樣本數N中表現的顯著改善。KD 樹的構造非常快，對於低維度 (D<20) 近鄰搜索也非常快, 當D增長到很大時，效率變低： 這就是所謂的 「維度災難」 的一種體現。

KD 樹是一個二叉樹結構，它沿著數據軸遞歸地劃分參數空間，將其劃分為嵌入數據點的嵌套的各向異性區域。 KD 樹的構造非常快：因為只需沿數據軸執行分區, 無需計算D-dimensional 距離。 一旦構建完成, 查詢點的最近鄰距離計算復雜度僅為O[log(N)]。 雖然 KD 樹的方法對於低維度 (D<20) 近鄰搜索非常快, 當D增長到很大時, 效率變低。

KD樹的特性適合使用歐氏距離。

BallTree

BallTree解決了KDTree在高維上效率低下的問題，這種方法構建的樹要比 KD 樹消耗更多的時間，但是這種數據結構對於高結構化的數據是非常有效的， 即使在高維度上也是一樣。

KD樹是依次對K維坐標軸，以中值切分構造的樹；ball tree 是以質心C和半徑r分割樣本空間，每一個節點是一個超球體。換句簡單的話來說，對於目標空間(q, r)，所有被該超球體截斷的子超球體內的所有子空間都將被遍歷搜索。

BallTree通過使用三角不等式減少近鄰搜索的候選點數:|x+y|<=|x|+|y|通過這種設置, 測試點和質心之間的單一距離計算足以確定距節點內所有點的距離的下限和上限. 由於 ball 樹節點的球形幾何, 它在高維度上的性能超出 KD-tree, 盡管實際的性能高度依賴於訓練數據的結構。

BallTree適用於更一般的距離。

1、優點

非常簡單的分類演算法沒有之一，人性化，易於理解，易於實現

適合處理多分類問題，比如推薦用戶

可用於數值型數據和離散型數據，既可以用來做分類也可以用來做回歸

對異常值不敏感

2、缺點

屬於懶惰演算法，時間復雜度較高，因為需要計算未知樣本到所有已知樣本的距離

樣本平衡度依賴高，當出現極端情況樣本不平衡時，分類絕對會出現偏差，可以調整樣本權值改善

可解釋性差，無法給出類似決策樹那樣的規則

向量的維度越高，歐式距離的區分能力就越弱

樣本空間太大不適合，因為計算量太大，預測緩慢

文本分類

用戶推薦

回歸問題

1）所有的觀測實例中隨機抽取出k個觀測點，作為聚類中心點，然後遍歷其餘的觀測點找到距離各自最近的聚類中心點，將其加入到該聚類中。這樣，我們就有了一個初始的聚類結果，這是一次迭代的過程。

2）我們每個聚類中心都至少有一個觀測實例，這樣，我們可以求出每個聚類的中心點（means），作為新的聚類中心，然後再遍歷所有的觀測點，找到距離其最近的中心點，加入到該聚類中。然後繼續運行2）。

3）如此往復2），直到前後兩次迭代得到的聚類中心點一模一樣。

本演算法的時間復雜度：O(tkmn)，其中，t為迭代次數，k為簇的數目，m為記錄數，n為維數；

空間復雜度：O((m+k)n)，其中，k為簇的數目，m為記錄數，n為維數。

適用范圍：

K-menas演算法試圖找到使平凡誤差准則函數最小的簇。當潛在的簇形狀是凸面的，簇與簇之間區別較明顯，且簇大小相近時，其聚類結果較理想。前面提到，該演算法時間復雜度為O(tkmn)，與樣本數量線性相關，所以，對於處理大數據集合，該演算法非常高效，且伸縮性較好。但該演算法除了要事先確定簇數K和對初始聚類中心敏感外，經常以局部最優結束，同時對「雜訊」和孤立點敏感，並且該方法不適於發現非凸面形狀的簇或大小差別很大的簇。

1）首先，演算法只能找到局部最優的聚類，而不是全局最優的聚類。而且演算法的結果非常依賴於初始隨機選擇的聚類中心的位置。我們通過多次運行演算法，使用不同的隨機生成的聚類中心點運行演算法，然後對各自結果C通過evaluate(C)函數進行評估，選擇多次結果中evaluate(C)值最小的那一個。k-means++演算法選擇初始seeds的基本思想就是：初始的聚類中心之間的相互距離要盡可能的遠

2）關於初始k值選擇的問題。首先的想法是，從一個起始值開始，到一個最大值，每一個值運行k-means演算法聚類，通過一個評價函數計算出最好的一次聚類結果，這個k就是最優的k。我們首先想到了上面用到的evaluate(C)。然而，k越大，聚類中心越多，顯然每個觀測點距離其中心的距離的平方和會越小，這在實踐中也得到了驗證。第四節中的實驗結果分析中將詳細討論這個問題。

3）關於性能問題。原始的演算法，每一次迭代都要計算每一個觀測點與所有聚類中心的距離。有沒有方法能夠提高效率呢？是有的，可以使用k-d tree或者ball tree這種數據結構來提高演算法的效率。特定條件下，對於一定區域內的觀測點，無需遍歷每一個觀測點，就可以把這個區域內所有的點放到距離最近的一個聚類中去。這將在第三節中詳細地介紹。

相似點：都包含這樣的過程，給定一個點，在數據集中找離它最近的點。即二者都用到了NN(Nears Neighbor)演算法，一般用KD樹來實現NN。

k-d tree 與 ball tree

1）k-d tree[5]

把n維特徵的觀測實例放到n維空間中，k-d tree每次通過某種演算法選擇一個特徵(坐標軸)，以它的某一個值作為分界做超平面，把當前所有觀測點分為兩部分，然後對每一個部分使用同樣的方法，直到達到某個條件為止。

上面的表述中，有幾個地方下面將會詳細說明：（1）選擇特徵（坐標軸）的方法 （2）以該特徵的哪一個為界 （3）達到什麼條件演算法結束。

(1)選擇特徵的方法

計算當前觀測點集合中每個特徵的方差，選擇方差最大的一個特徵，然後畫一個垂直於這個特徵的超平面將所有觀測點分為兩個集合。

（2)以該特徵的哪一個值為界 即垂直選擇坐標軸的超平面的具體位置。

第一種是以各個點的方差的中值（median）為界。這樣會使建好的樹非常地平衡，會均勻地分開一個集合。這樣做的問題是，如果點的分布非常不好地偏斜的，選擇中值會造成連續相同方向的分割，形成細長的超矩形(hyperrectangles)。

替代的方法是計算這些點該坐標軸的平均值，選擇距離這個平均值最近的點作為超平面與這個坐標軸的交點。這樣這個樹不會完美地平衡，但區域會傾向於正方地被劃分，連續的分割更有可能在不同方向上發生。

（3）達到什麼條件演算法結束

實際中，不用指導葉子結點只包含兩個點時才結束演算法。你可以設定一個預先設定的最小值，當這個最小值達到時結束演算法。

圖6中，星號標注的是目標點，我們在k-d tree中找到這個點所處的區域後，依次計算此區域包含的點的距離，找出最近的一個點（黑色點），如果在其他region中還包含更近的點則一定在以這兩個點為半徑的圓中。假設這個圓如圖中所示包含其他區域。先看這個區域兄弟結點對應區域，與圓不重疊；再看其雙親結點的兄弟結點對應區域。從它的子結點對應區域中尋找（圖中確實與這個雙親結點的兄弟結點的子結點對應區域重疊了）。在其中找是否有更近的結點。

k-d tree的優勢是可以遞增更新。新的觀測點可以不斷地加入進來。找到新觀測點應該在的區域，如果它是空的，就把它添加進去，否則，沿著最長的邊分割這個區域來保持接近正方形的性質。這樣會破壞樹的平衡性，同時讓區域不利於找最近鄰。我們可以當樹的深度到達一定值時重建這棵樹。

然而，k-d tree也有問題。矩形並不是用到這里最好的方式。偏斜的數據集會造成我們想要保持樹的平衡與保持區域的正方形特性的沖突。另外，矩形甚至是正方形並不是用在這里最完美的形狀，由於它的角。如果圖6中的圓再大一些，即黑點距離目標點點再遠一些，圓就會與左上角的矩形相交，需要多檢查一個區域的點，而且那個區域是當前區域雙親結點的兄弟結點的子結點。

為了解決上面的問題，我們引入了ball tree。

2）ball tree[4]

解決上面問題的方案就是使用超球面而不是超矩形劃分區域。使用球面可能會造成球面間的重疊，但卻沒有關系。ball tree就是一個k維超球面來覆蓋這些觀測點，把它們放到樹裡面。圖7（a)顯示了一個2維平麵包含16個觀測實例的圖,圖7（b）是其對應的ball tree，其中結點中的數字表示包含的觀測點數。

不同層次的圓被用不同的風格畫出。樹中的每個結點對應一個圓，結點的數字表示該區域保含的觀測點數，但不一定就是圖中該區域囊括的點數，因為有重疊的情況，並且一個觀測點只能屬於一個區域。實際的ball tree的結點保存圓心和半徑。葉子結點保存它包含的觀測點。

使用ball tree時，先自上而下找到包含target的葉子結點，從此結點中找到離它最近的觀測點。這個距離就是最近鄰的距離的上界。檢查它的兄弟結點中是否包含比這個上界更小的觀測點。方法是：如果目標點距離兄弟結點的圓心的距離大於這個圓的圓心加上前面的上界的值，則這個兄弟結點不可能包含所要的觀測點。（如圖8）否則，檢查這個兄弟結點是否包含符合條件的觀測點。

那麼，ball tree的分割演算法是什麼呢？

選擇一個距離當前圓心最遠的觀測點i1，和距離i1最遠的觀測點 i2，將圓中所有離這兩個點最近的觀測點都賦給這兩個簇的中心，然後計算每一個簇的中心點和包含所有其所屬觀測點的最小半徑。對包含n個觀測點的超圓進行分割，只需要線性的時間。

與k-d tree一樣，如果結點包含的觀測點到達了預先設定的最小值，這個頂點就可以不再分割了。