基本介紹
- 中文名：k-d樹
- 外文名：k-dimensional樹
- 簡稱：kd-tree
- 屬於：分割k維數據空間的數據結構
- 用於：多維空間關鍵數據的搜尋
- 科目：計算機科學
簡介,k-d樹的運算,創建k-d樹,最鄰近搜尋,處理高維數據,套用舉例,實例,構建算法,查找算法,編程實現,基於sklearn,基於純python實現,
簡介
k-d樹是每個節點都為k維點的二叉樹。所有非葉子節點可以視作用一個超平面把空間分割成兩個半空間。節點左邊的子樹代表在超平面左邊的點，節點右邊的子樹代表在超平面右邊的點。選擇超平面的方法如下：每個節點都與k維中垂直於超平面的那一維有關。因此，如果選擇按照x軸劃分，所有x值小於指定值的節點都會出現在左子樹，所有x值大於指定值的節點都會出現在右子樹。這樣，超平面可以用該x值來確定，其法線為x軸的單位向量。
k-d樹的運算
創建k-d樹
有很多種方法可以選擇軸垂直分割面（ axis-aligned splitting planes ），所以有很多種創建k-d樹的方法。 最典型的方法如下：
- 隨著樹的深度輪流選擇軸當作分割面。（例如：在三維空間中根節點是 x 軸垂直分割面，其子節點皆為 y 軸垂直分割面，其孫節點皆為 z 軸垂直分割面，其曾孫節點則皆為 x 軸垂直分割面，依此類推。）
- 點由垂直分割面之軸座標的中位數區分並放入子樹
這個方法產生一個平衡的k-d樹。每個葉節點的高度都十分接近。然而，平衡的樹不一定對每個套用都是最佳的。
最鄰近搜尋
最鄰近搜尋用來找出在樹中與輸入點最接近的點。
k-d樹最鄰近搜尋的過程如下：
- 從根節點開始，遞歸的往下移。往左還是往右的決定方法與插入元素的方法一樣(如果輸入點在分區面的左邊則進入左子節點，在右邊則進入右子節點)。
- 一旦移動到葉節點，將該節點當作"當前最佳點"。
- 解開遞歸，並對每個經過的節點運行下列步驟：
- 如果當前所在點比當前最佳點更靠近輸入點，則將其變為當前最佳點。
- 檢查另一邊子樹有沒有更近的點，如果有則從該節點往下找。
當根節點搜尋完畢後完成最鄰近搜尋。
處理高維數據
維數災難讓大部分的搜尋算法在高維情況下都顯得花哨且不實用。 同樣的，在高維空間中，k-d樹葉並不能做很高效的最鄰近搜尋。一般的準則是：在k維情況下，數據點數目N應當遠遠大於
時，k-d樹的最鄰近搜尋才可以很好的發揮其作用。不然的話，大部分的點都會被查詢，最終算法效率也不會比全體查詢一遍要好到哪裡去。另外，如果只是需要一個足夠快，且不必最優的結果，那么可以考慮使用近似鄰近查詢的方法。
套用舉例
索引結構中相似性查詢有兩種基本的方式：一種是範圍查詢（range searches），另一種是K近鄰查詢（K-neighbor searches）。範圍查詢就是給定查詢點和查詢距離的閾值，從數據集中找出所有與查詢點距離小於閾值的數據；K近鄰查詢是給定查詢點及正整數K，從數據集中找到距離查詢點最近的K個數據，當K=1時，就是最近鄰查詢（nearest neighbor searches）。
特徵匹配運算元大致可以分為兩類。
一類是線性掃描法，即將數據集中的點與查詢點逐一進行距離比較，也就是窮舉，缺點很明顯，就是沒有利用數據集本身蘊含的任何結構信息，搜尋效率較低。
第二類是建立數據索引，然後再進行快速匹配。因為實際數據一般都會呈現出簇狀的聚類形態，通過設計有效的索引結構可以大大加快檢索的速度。索引樹屬於第二類，其基本思想就是對搜尋空間進行層次劃分。根據劃分的空間是否有混疊可以分為Clipping和Overlapping兩種。前者劃分空間沒有重疊，其代表就是k-d樹；後者劃分空間相互有交疊，其代表為R樹。
實例
先以一個簡單直觀的實例來介紹k-d樹算法。假設有6個二維數據點{（2,3），（5,4），（9,6），（4,7），（8,1），（7,2）}，數據點位於二維空間內（如圖1中黑點所示）。k-d樹算法就是要確定圖1中這些分割空間的分割線（多維空間即為分割平面，一般為超平面）。下面就要通過一步步展示k-d樹是如何確定這些分割線的。
k-d樹算法可以分為兩大部分，一部分是有關k-d樹本身這種數據結構建立的算法，另一部分是在建立的k-d樹上如何進行最鄰近查找的算法。
構建算法
k-d樹是一個二叉樹，每個節點表示一個空間範圍。表1給出的是k-d樹每個節點中主要包含的數據結構。
域名 | 數據類型 | 描述 |
Node-data | 數據矢量 | 數據集中某個數據點，是n維矢量（這裡也就是k維） |
Range | 空間矢量 | 該節點所代表的空間範圍 |
split | 整數 | 垂直於分割超平面的方向軸序號 |
Left | k-d樹 | 由位於該節點分割超平面左子空間內所有數據點所構成的k-d樹 |
Right | k-d樹 | 由位於該節點分割超平面右子空間內所有數據點所構成的k-d樹 |
parent | k-d樹 | 父節點 |
從上面對k-d樹節點的數據類型的描述可以看出構建k-d樹是一個逐級展開的遞歸過程。表2給出的是構建k-d樹的偽碼。
算法：構建k-d樹（createKDTree） |
輸入：數據點集Data-set和其所在的空間Range |
輸出：Kd，類型為k-d tree |
1.If Data-set為空，則返回空的k-d tree |
2.調用節點生成程式： （1）確定split域：對於所有描述子數據（特徵矢量），統計它們在每個維上的數據方差。以SURF特徵為例，描述子為64維，可計算64個方差。挑選出最大值，對應的維就是split域的值。數據方差大表明沿該坐標軸方向上的數據分散得比較開，在這個方向上進行數據分割有較好的解析度； （2）確定Node-data域：數據點集Data-set按其第split域的值排序。位於正中間的那個數據點被選為Node-data。此時新的Data-set' = Data-set\Node-data（除去其中Node-data這一點）。 |
3. dataleft = {d屬於Data-set' && d[split] ≤ Node-data[split]} Left_Range = {Range && dataleft} dataright = {d屬於Data-set' && d[split] > Node-data[split]} Right_Range = {Range && dataright} |
4. left = 由（dataleft，Left_Range）建立的k-d tree，即遞歸調用createKDTree（dataleft，Left_ Range）。並設定left的parent域為Kd； right = 由（dataright，Right_Range）建立的k-d tree，即調用createKDTree（dataright，Right_ Range）。並設定right的parent域為Kd。 |
以上述舉的實例來看，過程如下：
由於此例簡單，數據維度只有2維，所以可以簡單地給x，y兩個方向軸編號為0,1，也即split={0,1}。
（1）確定split域的首先該取的值。分別計算x，y方向上數據的方差得知x方向上的方差最大，所以split域值首先取0，也就是x軸方向；
（2）確定Node-data的域值。根據x軸方向的值2,5,9,4,8,7排序選出中值為7，所以Node-data = （7,2）。這樣，該節點的分割超平面就是通過（7,2）並垂直於split = 0（x軸）的直線x = 7；
（3）確定左子空間和右子空間。分割超平面x = 7將整個空間分為兩部分，如圖2所示。x < = 7的部分為左子空間，包含3個節點{（2,3），（5,4），（4,7）}；另一部分為右子空間，包含2個節點{（9,6），（8,1）}。
如算法所述，k-d樹的構建是一個遞歸的過程。然後對左子空間和右子空間內的數據重複根節點的過程就可以得到下一級子節點（5,4）和（9,6）（也就是左右子空間的'根'節點），同時將空間和數據集進一步細分。如此反覆直到空間中只包含一個數據點，如圖1所示。最後生成的k-d樹如圖3所示。
查找算法
星號表示要查詢的點（2.1,3.1）。通過二叉搜尋，順著搜尋路徑很快就能找到最鄰近的近似點，也就是葉子節點（2,3）。而找到的葉子節點並不一定就是最鄰近的，最鄰近肯定距離查詢點更近，應該位於以查詢點為圓心且通過葉子節點的圓域內。
為了找到真正的最近鄰，還需要進行'回溯'操作：算法沿搜尋路徑反向查找是否有距離查詢點更近的數據點。此例中先從（7,2）點開始進行二叉查找，然後到達（5,4），最後到達（2,3），此時搜尋路徑中的節點為<（7,2），（5,4），（2,3）>，首先以（2,3）作為當前最近鄰點，計算其到查詢點（2.1,3.1）的距離為0.1414，然後回溯到其父節點（5,4），並判斷在該父節點的其他子節點空間中是否有距離查詢點更近的數據點。以（2.1,3.1）為圓心，以0.1414為半徑畫圓，如圖4所示。發現該圓並不和超平面y = 4交割，因此不用進入（5,4）節點右子空間中去搜尋。
再回溯到（7,2），以（2.1,3.1）為圓心，以0.1414為半徑的圓更不會與x = 7超平面交割，因此不用進入（7,2）右子空間進行查找。至此，搜尋路徑中的節點已經全部回溯完，結束整個搜尋，返回最近鄰點（2,3），最近距離為0.1414。
一個複雜點的例子如查找點為（2，4.5）。同樣先進行二叉查找，先從（7,2）查找到（5,4）節點，在進行查找時是由y = 4為分割超平面的，由於查找點為y值為4.5，因此進入右子空間查找到（4,7），形成搜尋路徑<（7,2），（5,4），（4,7）>，取（4,7）為當前最近鄰點，計算其與目標查找點的距離為3.202。然後回溯到（5,4），計算其與查找點之間的距離為3.041。以（2，4.5）為圓心，以3.041為半徑作圓，如圖5所示。可見該圓和y = 4超平面交割，所以需要進入（5,4）左子空間進行查找。此時需將（2,3）節點加入搜尋路徑中得<（7,2），（2,3）>。回溯至（2,3）葉子節點，（2,3）距離（2,4.5）比（5,4）要近，所以最近鄰點更新為（2，3），最近距離更新為1.5。回溯至（7,2），以（2,4.5）為圓心1.5為半徑作圓，並不和x = 7分割超平面交割，如圖6所示。至此，搜尋路徑回溯完。返回最近鄰點（2,3），最近距離1.5。k-d樹查詢算法的偽代碼如下所示。
- 從root節點開始，DFS搜尋直到葉子節點，同時在stack中順序存儲已經訪問的節點。
- 如果搜尋到葉子節點，當前的葉子節點被設為最近鄰節點。
- 然後通過stack回溯:
如果當前點的距離比最近鄰點距離近，更新最近鄰節點.
然後檢查以最近距離為半徑的圓是否和父節點的超平面相交.
如果相交，則必須到父節點的另外一側，用同樣的DFS搜尋法，開始檢查最近鄰節點。
如果不相交，則繼續往上回溯，而父節點的另一側子節點都被淘汰，不再考慮的範圍中. - 當搜尋回到root節點時，搜尋完成，得到最近鄰節點。
編程實現
基於sklearn
基於sklearn庫的實現
from sklearn.neighbors import KDTreeimport numpy as npfrom sklearn.neighbors import KDTree np.random.seed(0)X = np.array([[2, 3], [5, 4], [9, 6], [4, 7], [8, 1], [7, 2]]) tree = KDTree(X, leaf_size=2)dist, ind = tree.query(X[:1], k=3) print(dist) # 3個最近的距離print(ind) # 3個最近的索引print(X[ind]) # 3個最近的點 #[[0. 3.16227766 4.47213595]][[0 1 3]][[[2 3] [5 4] [4 7]]]
基於純python實現
class KDNode(object): def __init__(self, value, split, left, right): # value=[x,y] self.value = value self.split = split self.right = right self.left = left class KDTree(object): def __init__(self, data): # data=[[x1,y1],[x2,y2]...,] # 維度 k = len(data[0]) def CreateNode(split, data_set): if not data_set: return None data_set.sort(key=lambda x: x[split]) # 整除2 split_pos = len(data_set) // 2 median = data_set[split_pos] split_next = (split + 1) % k return KDNode(median, split, CreateNode(split_next, data_set[: split_pos]), CreateNode(split_next, data_set[split_pos + 1:])) self.root = CreateNode(0, data) def search(self, root, x, count=1): nearest = [] for i in range(count): nearest.append([-1, None]) self.nearest = np.array(nearest) def recurve(node): if node is not None: axis = node.split daxis = x[axis] - node.value[axis] if daxis < 0: recurve(node.left) else: recurve(node.right) dist = sqrt(sum((p1 - p2) ** 2 for p1, p2 in zip(x, node.value))) for i, d in enumerate(self.nearest): if d[0] < 0 or dist < d[0]: # 如果當前nearest內i處未標記（-1），或者新點與x距離更近 self.nearest = np.insert(self.nearest, i, [dist, node.value], axis=0) # 插入比i處距離更小的 self.nearest = self.nearest[:-1] break # 找到nearest集合里距離最大值的位置，為-1值的個數 n = list(self.nearest[:, 0]).count(-1) # 切分軸的距離比nearest中最大的小（存在相交） if self.nearest[-n - 1, 0] > abs(daxis): if daxis < 0: # 相交，x[axis]< node.data[axis]時，去右邊（左邊已經遍歷了） recurve(node.right) else: # x[axis]> node.data[axis]時，去左邊，（右邊已經遍歷了） recurve(node.left) recurve(root) return self.nearest # 最近坐標點、最近距離和訪問過的節點數result = namedtuple("Result_tuple", "nearest_point nearest_dist nodes_visited") data = [[2, 3], [5, 4], [9, 6], [4, 7], [8, 1], [7, 2]]kd = KDTree(data) #[3, 4.5]最近的3個點n = kd.search(kd.root, [3, 4.5], 3)print(n) #[[1.8027756377319946 list([2, 3])] [2.0615528128088303 list([5, 4])] [2.692582403567252 list([4, 7])]]