kd-tree

k-d樹是一個二叉樹，每個節(jié)點表示一個空間范圍。表1給出的是k-d樹每個節(jié)點中主要包含的數(shù)據(jù)結構。

表1 k-d樹中每個節(jié)點的數(shù)據(jù)類型

從上面對k-d樹節(jié)點的數(shù)據(jù)類型的描述可以看出構建k-d樹是一個逐級展開的遞歸過程。表2給出的是構建k-d樹的偽碼。

表2 構建k-d樹的偽碼

以上述舉的實例來看，過程如下:

由于此例簡單，數(shù)據(jù)維度只有2維，所以可以簡單地給x，y兩個方向軸編號為0,1，也即split={0,1}。

(1)確定split域的首先該取的值。分別計算x，y方向上數(shù)據(jù)的方差得知x方向上的方差最大，所以split域值首先取0，也就是x軸方向;

(2)確定Node-data的域值。根據(jù)x軸方向的值2,5,9,4,8,7排序選出中值為7，所以Node-data = (7,2)。這樣，該節(jié)點的分割超平面就是通過(7,2)并垂直于split = 0(x軸)的直線x = 7;

(3)確定左子空間和右子空間。分割超平面x = 7將整個空間分為兩部分，如圖2所示。x < = 7的部分為左子空間，包含3個節(jié)點{(2,3)，(5,4)，(4,7)};另一部分為右子空間，包含2個節(jié)點{(9,6)，(8,1)}。

如算法所述，k-d樹的構建是一個遞歸的過程。然后對左子空間和右子空間內(nèi)的數(shù)據(jù)重復根節(jié)點的過程就可以得到下一級子節(jié)點(5,4)和(9,6)(也就是左右子空間的'根'節(jié)點)，同時將空間和數(shù)據(jù)集進一步細分。如此反復直到空間中只包含一個數(shù)據(jù)點，如圖1所示。最后生成的k-d樹如圖3所示。

在k-d樹中進行數(shù)據(jù)的查找也是特征匹配的重要環(huán)節(jié)，其目的是檢索在k-d樹中與查詢點距離最近的數(shù)據(jù)點。這里先以一個簡單的實例來描述最鄰近查找的基本思路。

星號表示要查詢的點(2.1,3.1)。通過二叉搜索，順著搜索路徑很快就能找到最鄰近的近似點，也就是葉子節(jié)點(2,3)。而找到的葉子節(jié)點并不一定就是最鄰近的，最鄰近肯定距離查詢點更近，應該位于以查詢點為圓心且通過葉子節(jié)點的圓域內(nèi)。為了找到真正的最近鄰，還需要進行'回溯'操作:算法沿搜索路徑反向查找是否有距離查詢點更近的數(shù)據(jù)點。此例中先從(7,2)點開始進行二叉查找，然后到達(5,4)，最后到達(2,3)，此時搜索路徑中的節(jié)點為<(7,2)，(5,4)，(2,3)>，首先以(2,3)作為當前最近鄰點，計算其到查詢點(2.1,3.1)的距離為0.1414，然后回溯到其父節(jié)點(5,4)，并判斷在該父節(jié)點的其他子節(jié)點空間中是否有距離查詢點更近的數(shù)據(jù)點。以(2.1,3.1)為圓心，以0.1414為半徑畫圓，如圖4所示。發(fā)現(xiàn)該圓并不和超平面y = 4交割，因此不用進入(5,4)節(jié)點右子空間中去搜索。

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

一個復雜點了例子如查找點為(2，4.5)。同樣先進行二叉查找，先從(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。以(2，4.5)為圓心，以3.041為半徑作圓，如圖5所示?？梢娫搱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?；厮葜?7,2)，以(2,4.5)為圓心1.5為半徑作圓，并不和x = 7分割超平面交割，如圖6所示。至此，搜索路徑回溯完。返回最近鄰點(2,3)，最近距離1.5。k-d樹查詢算法的偽代碼如下所示。

先以一個簡單直觀的實例來介紹k-d樹算法。假設有6個二維數(shù)據(jù)點{(2,3)，(5,4)，(9,6)，(4,7)，(8,1)，(7,2)}，數(shù)據(jù)點位于二維空間內(nèi)(如圖1中黑點所示)。k-d樹算法就是要確定圖1中這些分割空間的分割線(多維空間即為分割平面，一般為超平面)。下面就要通過一步步展示k-d樹是如何確定這些分割線的。

k-d樹算法可以分為兩大部分，一部分是有關k-d樹本身這種數(shù)據(jù)結構建立的算法，另一部分是在建立的k-d樹上如何進行最鄰近查找的算法。