kd-tree構(gòu)建算法

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

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

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

表2 構(gòu)建k-d樹的偽碼

以上述舉的實(shí)例來看，過程如下:

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

(1)確定split域的首先該取的值。分別計(jì)算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é)點(diǎn)的分割超平面就是通過(7,2)并垂直于split = 0(x軸)的直線x = 7;

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

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

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

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

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

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

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

一個(gè)復(fù)雜點(diǎn)了例子如查找點(diǎn)為(2，4.5)。同樣先進(jìn)行二叉查找，先從(7,2)查找到(5,4)節(jié)點(diǎn)，在進(jìn)行查找時(shí)是由y = 4為分割超平面的，由于查找點(diǎn)為y值為4.5，因此進(jìn)入右子空間查找到(4,7)，形成搜索路徑<(7,2)，(5,4)，(4,7)>，取(4,7)為當(dāng)前最近鄰點(diǎn)，計(jì)算其與目標(biāo)查找點(diǎn)的距離為3.202。然后回溯到(5,4)，計(jì)算其與查找點(diǎn)之間的距離為3.041。以(2，4.5)為圓心，以3.041為半徑作圓，如圖5所示?？梢娫搱A和y = 4超平面交割，所以需要進(jìn)入(5,4)左子空間進(jìn)行查找。此時(shí)需將(2,3)節(jié)點(diǎn)加入搜索路徑中得<(7,2)，(2,3)>。回溯至(2,3)葉子節(jié)點(diǎn)，(2,3)距離(2,4.5)比(5,4)要近，所以最近鄰點(diǎn)更新為(2，3)，最近距離更新為1.5。回溯至(7,2)，以(2,4.5)為圓心1.5為半徑作圓，并不和x = 7分割超平面交割，如圖6所示。至此，搜索路徑回溯完。返回最近鄰點(diǎn)(2,3)，最近距離1.5。k-d樹查詢算法的偽代碼如下所示。