k-d樹 轉至百度百科



kd-tree編輯

轉至： http://baike.baidu.com/view/8668561.htm

k-d樹 [1]  （k-dimensional樹的簡稱），是一種分割k維資料空間的資料結構。主要應用于多元空間關鍵資料的搜尋（如：範圍搜尋和最近鄰搜尋）。K-D樹是二進制空間分割樹的特殊的情況。 外文名 k-dimensional樹 簡    稱 kd-tree 屬    于 分割k維資料空間的資料結構 用    于 多元空間關鍵資料的搜尋

目錄

1應用背景

2執行個體

3建構算法

4查找算法

1應用背景編輯

SIFT算法中做特征點比對的時候就會利用到k-d樹。而特征點比對實際上就是一個通過距離函數在高維矢量之間進行相似性檢索的問題。針對如何快速而準确地找到查詢點的近鄰，現在提出了很多高維空間索引結構和近似查詢的算法，k-d樹就是其中一種。 索引結構中相似性查詢有兩種基本的方式：一種是範圍查詢（range searches），另一種是K近鄰查詢（K-neighbor searches）。範圍查詢就是給定查詢點和查詢距離的門檻值，從資料集中找出所有與查詢點距離小于門檻值的資料；K近鄰查詢是給定查詢點及正整數K，從資料集中找到距離查詢點最近的K個資料，當K=1時，就是最近鄰查詢（nearest neighbor searches）。 特征比對算子大緻可以分為兩類。一類是線性掃描法，即将資料集中的點與查詢點逐一進行距離比較，也就是窮舉，缺點很明顯，就是沒有利用資料集本身蘊含的任何結構資訊，搜尋效率較低，第二類是建立資料索引，然後再進行快速比對。因為實際資料一般都會呈現出簇狀的聚類形态，通過設計有效的索引結構可以大大加快檢索的速度。索引樹屬于第二類，其基本思想就是對搜尋空間進行層次劃分。根據劃分的空間是否有混疊可以分為Clipping和Overlapping兩種。前者劃分空間沒有重疊，其代表就是k-d樹；後者劃分空間互相有交疊，其代表為R樹。（這裡隻介紹k-d樹 [2]  ）

2執行個體編輯

先以一個簡單直覺的執行個體來介紹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樹上如何進行最鄰近查找的算法。

3建構算法編輯

k-d樹是一個二叉樹，每個節點表示一個空間範圍。表1給出的是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樹的僞碼。 表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所示。

4查找算法編輯

在k-d樹中進行資料的查找也是特征比對的重要環節，其目的是檢索在k-d樹中與查詢點距離最近的資料點。這裡先以一個簡單的執行個體來描述最鄰近查找的基本思路。 星号表示要查詢的點（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樹查詢算法的僞代碼如下所示。

1. 從root節點開始，DFS搜尋直到葉子節點，同時在stack中順序存儲已經通路的節點。
2. 如果搜尋到葉子節點，目前的葉子節點被設為最近鄰節點。
3. 然後通過stack回溯: 如果目前點的距離比最近鄰點距離近，更新最近鄰節點. 然後檢查以最近距離為半徑的圓是否和父節點的超平面相交. 如果相交，則必須到父節點的另外一側，用同樣的DFS搜尋法，開始檢查最近鄰節點。 如果不相交，則繼續往上回溯，而父節點的另一側子節點都被淘汰，不再考慮的範圍中.
4. 當搜尋回到root節點時，搜尋完成，得到最近鄰節點。