KD樹

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

1、kd樹的原理

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

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

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

KD樹劃分后的三維空間

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

2、kd樹的構建

常規(guī)的k-d tree的構建過程為：

1、循環(huán)依序取數(shù)據(jù)點的各維度來作為切分維度

2、取數(shù)據(jù)點在該維度的中值作為切分超平面

3、將中值左側的數(shù)據(jù)點掛在其左子樹，將中值右側的數(shù)據(jù)點掛在其右子樹

4、遞歸處理其子樹，直至所有數(shù)據(jù)點掛載完畢

對于構建過程，有兩個優(yōu)化點：

• 選擇切分維度：根據(jù)數(shù)據(jù)點在各維度上的分布情況，方差越大，分布越分散，從方差大的維度開始切分，有較好的切分效果和平衡性。

• 確定中值點：預先對原始數(shù)據(jù)點在所有維度進行一次排序，存儲下來，然后在后續(xù)的中值選擇中，無須每次都對其子集進行排序，提升了性能。也可以從原始數(shù)據(jù)點中隨機選擇固定數(shù)目的點，然后對其進行排序，每次從這些樣本點中取中值，來作為分割超平面。該方式在實踐中被證明可以取得很好性能及很好的平衡性。

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

1、構建根節(jié)點時，此時的切分維度為x，如上點集合在x維從小到大排序為(2,3)，(4,7)，(5,4)，(7,2)，(8,1)，(9,6)；其中值為(7,2)。（注：2,4,5,7,8,9在數(shù)學中的中值為(5 + 7)/2=6，但因該算法的中值需在點集合之內，所以本文中值計算用的是len(points)//2=3, points[3]=(7,2)）

2、(2,3)，(4,7)，(5,4)掛在(7,2)節(jié)點的左子樹，(8,1)，(9,6)掛在(7,2)節(jié)點的右子樹。

3、構建(7,2)節(jié)點的左子樹時，點集合(2,3)，(4,7)，(5,4)此時的切分維度為y，中值為(5,4)作為分割平面，(2,3)掛在其左子樹，(4,7)掛在其右子樹。

4、構建(7,2)節(jié)點的右子樹時，點集合(8,1)，(9,6)此時的切分維度也為y，中值為(9,6)作為分割平面，(8,1)掛在其左子樹。至此k-d tree構建完成。

kd樹的構建過程.jpg

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

kd樹的構建流程.jpg

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

1、隨著樹的深度增加，循環(huán)的選取坐標軸，作為分割超平面的法向量。對于3-d tree來說，根節(jié)點選取x軸，根節(jié)點的孩子選取y軸，根節(jié)點的孫子選取z軸，根節(jié)點的曾孫子選取x軸，這樣循環(huán)下去。

2、每次均為所有對應實例的中位數(shù)的實例作為切分點，切分點作為父節(jié)點，左右兩側為劃分的作為左右兩子樹。

# points為實例點集合，depth深度，為用來確定取維度的參數(shù)
def kd_tree(points, depth):    
    if 0 == len(points):
        return None
    # 指定切分維度，len(points[0])是數(shù)據(jù)的實際維度，這樣計算可以保證循環(huán)
    cutting_dim = depth % len(points[0])
    # 切分點初始化
    medium_index = len(points)
    # 對所有的實例點按照指定維度進行排序，itemgetter用于獲取對象哪些維度上的數(shù)據(jù)，參數(shù)為需要獲取的數(shù)據(jù)在對象中的序號
    points.sort(key=itemgetter(cutting_dim))  
    # 將該維度的中值點作為根節(jié)點
    node = Node(points[medium_index]) 
    # 對于左子樹，重復構建（depth+1）
    node.left = kd_tree(points[:medium_index], depth + 1)    
    # 對于右子樹，重復構建（depth+1）
    node.right = kd_tree(points[medium_index + 1:], depth + 1)    
    return node

3、kd樹的檢索

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

查找方式.gif

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

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

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

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

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

遍歷完(5,4)的左右葉子節(jié)點，發(fā)現(xiàn)與當前最優(yōu)距離相等，不更新最近鄰。所以(3,5)的最近鄰為(5,4)。

舉例：查詢點（2.1,3.1）

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

1、二叉樹搜索：先從（7,2）點開始進行二叉查找，然后到達（5,4），最后到達（2,3），此時搜索路徑中的節(jié)點為<(7,2)，(5,4)，(2,3)>，首先以（2,3）作為當前最近鄰點，計算其到查詢點（2.1,3.1）的距離為0.1414，

2、回溯查找：在得到（2,3）為查詢點的最近點之后，回溯到其父節(jié)點（5,4），并判斷在該父節(jié)點的其他子節(jié)點空間中是否有距離查詢點更近的數(shù)據(jù)點。以（2.1,3.1）為圓心，以0.1414為半徑畫圓，如下圖所示。發(fā)現(xiàn)該圓并不和超平面y = 4交割，因此不用進入（5,4）節(jié)點右子空間中(圖中灰色區(qū)域)去搜索；

3、最后，再回溯到（7,2），以（2.1,3.1）為圓心，以0.1414為半徑的圓更不會與x = 7超平面交割，因此不用進入（7,2）右子空間進行查找。至此，搜索路徑中的節(jié)點已經全部回溯完，結束整個搜索，返回最近鄰點（2,3），最近距離為0.1414。

example1.jpg

舉例：查詢點（2，4.5）

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

1、同樣先進行二叉查找，先從（7,2）查找到（5,4）節(jié)點，在進行查找時是由y = 4為分割超平面的，由于查找點為y值為4.5，因此進入右子空間查找到（4,7），形成搜索路徑<(7,2)，(5,4)，(4,7)>，但（4,7）與目標查找點的距離為3.202，而（5,4）與查找點之間的距離為3.041，所以（5,4）為查詢點的最近點；

2、以（2，4.5）為圓心，以3.041為半徑作圓，如下圖所示?？梢娫搱A和y = 4超平面交割，所以需要進入（5,4）左子空間進行查找，也就是將（2,3）節(jié)點加入搜索路徑中得<(7,2)，(2,3)>；于是接著搜索至（2,3）葉子節(jié)點，（2,3）距離（2,4.5）比（5,4）要近，所以最近鄰點更新為（2，3），最近距離更新為1.5；

3、回溯查找至（5,4），直到最后回溯到根結點（7,2）的時候，以（2,4.5）為圓心1.5為半徑作圓，并不和x = 7分割超平面交割，如下圖所示。至此，搜索路徑回溯完，返回最近鄰點（2,3），最近距離1.5。

example2.jpg

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

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

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

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

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

4、sklearn中的KDTree

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

import numpy as np
from matplotlib import pyplot as plt
from matplotlib.patches import Circle
from sklearn.neighbors import KDTree
%matplotlib inline
np.random.seed(0)
points = np.random.random((100, 2))
# print(points)
tree = KDTree(points)
point = points[0]
# kNN
dists, indices = tree.query([point], k=3)
print(dists, indices)
# query radius
indices = tree.query_radius([point], r=0.2)
print(indices)
fig = plt.figure()
ax = fig.add_subplot(111, aspect='equal')
ax.add_patch(Circle(point, 0.2, color='r', fill=False))
X, Y = [p[0] for p in points], [p[1] for p in points]
plt.scatter(X, Y)
plt.scatter([point[0]], [point[1]], c='r')
plt.show()

[[0.         0.06703304 0.10907128]] [[ 0 68 11]]
[array([62,  1, 67, 68,  2, 53, 16, 18, 93, 22, 55,  0, 11], dtype=int64)]