簡介

kd樹（k-dimensional樹的簡稱），是一種分割k維數據空間的數據結構。主要應用于多維空間關鍵數據的搜索（如：范圍搜索和最近鄰搜索）。

一個KDTree的例子

上圖的樹就是一棵KDTree，形似二叉搜索樹，其實KDTree就是二叉搜索樹的變種。這里的K = 3.

首先來看下樹的組織原則。將每一個元組按0排序（第一項序號為0，第二項序號為1，第三項序號為2），在樹的第n層，第 n%3 項被用粗體顯示，而這些被粗體顯示的樹就是作為二叉搜索樹的key值，比如，根節點的左子樹中的每一個節點的第一個項均小于根節點的的第一項，右子樹的節點中第一項均大于根節點的第一項，子樹依次類推。

對于這樣的一棵樹，對其進行搜索節點會非常容易，給定一個元組，首先和根節點比較第一項，小于往左，大于往右，第二層比較第二項，依次類推。

分割的概念

看了上面的例子，確實比較簡單，但不知道為何要這樣做，這里從幾何意義出發，引出分割的概念。

先看一個標準的BSTree，每個節點只有一個key值。

將key值對應到一維的坐標軸上。

根節點對應的就是2，左子樹都在2的左邊，右子樹都在2的右邊，整個一維空間就被根節點分割成了兩個部分，當要查找結點0的時候，由于是在2的左邊，所以可以放心的只搜索左子樹的部分。整個搜索的過程可以看成不斷分割搜索區間的過程，直到找到目標節點。

這樣的分割可以擴展到二維甚至更多維的情況。

但是問題來了，二維的節點怎么比較大小？

在BSTree中，節點分割的是一維數軸，那么在二維中，就應當是分割平面了，就像這樣：

黃色的點作為根節點，上面的點歸左子樹，下面的點歸右子樹，接下來再不斷地劃分，最后得到一棵樹就是赫赫有名的BSPTree（binary?space partitioning tree）. 分割的那條線叫做分割超平面（splitting hyperplane），在一維中是一個點，二維中是線，三維的是面。

KDTree就是超平面都垂直于軸的BSPTree。同樣的數據集，用KDTree劃分之后就是這樣：

黃色節點就是Root節點，下一層是紅色，再下一層是綠色，再下一層是藍色。為了更好的理解KDTree的分割，我們在圖形中來形象地看一下搜索的過程，假設現在需要搜尋右下角的一個點，首先要做的就是比較這個點的x坐標和root點的x坐標值，由于x坐標值大于root節點的x坐標，所以只需要在右邊搜尋，接下來，要比較該節點和右邊紅色節點y值得大小...后面依此類推。整個過程如下圖：

? ?->??->

理解完KDTree之后，下面要說的就是關于KDTree的兩個最重要的問題：

1.樹的建立；

2.最近鄰域搜索（Nearest-Neighbor Lookup）。

?

樹的建立

先定義一下節點的數據結構。每個節點應當有下面幾個域：

Node-data - ?數據矢量， 數據集中某個數據點，是n維矢量（這里也就是k維）
Range ?- 空間矢量， 該節點所代表的空間范圍
split??-?整數， 垂直于分割超平面的方向軸序號
Left??-?k-d樹， 由位于該節點分割超平面左子空間內所有數據點所構成的k-d樹
Right??-?k-d樹， 由位于該節點分割超平面右子空間內所有數據點所構成的k-d樹
parent??-?k-d樹， 父節點

建立樹最大的問題在于軸點（pivot）的選擇，選擇好軸點之后，樹的建立就和BSTree差不多了。

建樹必須遵循兩個準則：

1.建立的樹應當盡量平衡，樹越平衡代表著分割得越平均，搜索的時間也就是越少。

2.最大化鄰域搜索的剪枝機會。

第一種選取軸點的策略是median of the most?spread dimension pivoting?strategy，對于所有描述子數據（特征矢量），統計他們在每個維度上的數據方差，挑選出方差中最大值，對應的維就是split域的值。數據方差大說明沿該坐標軸方向上數據點分散的比較開。這個方向上，進行數據分割可以獲得最好的平衡。數據點集Data-Set按照第split維的值排序，位于正中間的那個數據點 被選為軸點（軸點就是概率論中的中位數）。

?

但是問題來了，理論上空間均勻分布的點，在一個方向上分割只有，通過計算方差，下一次分割就不會出現在這個方向上了，但是一些特殊的情況中，還是會出現問題，比如

這樣就會出現很多長條的分割，對于KDTree來說是很不利的。

為了避免這種情況，需要修改一下算法（其實在實際應用中也不會有那個時間去修改的，直接就換算法了），維度的選擇的依據為數據范圍最大的那一維作為分割維度，之后也是選中這個維度的中間節點作為軸點（這個意思就是不再輪流比較各個維度了，而是總是比較同一個維度），然后進行分割，分割出來的結果是：

（觀察這個圖的右上方，可以看到，y維度分布范圍更大，那就橫切y維度，取中位點，

同理左下方x維度分布范圍更大，那就取x維的中位點，然后縱向切）

這樣的結果對于最鄰近搜索是非常友好的。

但是這樣做還是有一些不好，就是在樹上很可能有一些空的節點，當要限制樹的高度的時候，這種方法就不合適了。

自己總結：以上這個例子的意思就是，我們是通過方差來決定下一維度到底是x維還是y維度，但是可能存在一種情況，就是每次計算都是某一維的方差大，這個時候，就要換一種判定“分割維”的方式，采用“數據分散得最開”的那一維度作為下一個“分割維度”，用來對于當前根節點所在的子樹的大小判斷（根節點與左右子節點的大小判斷）

之所以要選擇方差最大、或者數據范圍遍及最廣的維度，是因為從這種特性入手，可以最快縮短測試點和最近點的距離，試想一個例子，如果下面三個點：

(2.1,9),(2.2,18),(2,3,36)這么三個點，切割維必須是y，如果是x的話，對于計算距離是沒有幫助的，y維度他可以幫助迅速縮短與最近點的距離

鄰近搜索

給定一個KDTree和一個節點，求KDTree中離這個節點最近的節點.(這個節點就是最臨近點)

這里距離的求法用的是歐式距離。

?

基本的思路很簡單：首先通過二叉樹搜索（比較待查詢節點和分裂節點的分裂維（所謂的分裂維，就是某個坐標的一個軸的值）的值，小于等于就進入左子樹分支，等于就進入右子樹分支直到葉子結點），順著“搜索路徑”很快能找到最近鄰的近似點，也就是與待查詢點處于同一個子空間的葉子結點；然后再回溯搜索路徑，并判斷搜索路徑上的結點的其他子結點空間中是否可能有距離查詢點更近的數據點，如果有可能，則需要跳到其他子結點空間中去搜索（將其他子結點加入到搜索路徑）。重復這個過程直到搜索路徑為空。（這個需要找具體例子來理解）

這里還有幾個細節需要注意一下，如下圖，假設標記為星星的點是 test point， 綠色的點是找到的近似點，在回溯過程中，需要用到一個隊列，存儲需要回溯的點，在判斷其他子節點空間中是否有可能有距離查詢點更近的數據點時，做法是以查詢點為圓心，以當前的最近距離為半徑畫圓，這個圓稱為候選超球（candidate hypersphere），如果圓與回溯點的軸相交，則需要將軸另一邊的節點都放到回溯隊列里面來。

判斷軸是否與候選超球相交的方法可以參考下圖：

?

下面再用一個例子來具體說一下查詢的過程。

假設我們的k-d tree就是上面通過樣本集{(2,3), (5,4), (9,6), (4,7), (8,1), (7,2)}創建的。
我們來查找點(2.1,3.1)，

在(7,2)點測試到達(5,4)，

在(5,4)點測試到達(2,3)，

然后search_path中的結點為<(7,2), (5,4), (2,3)>，

從search_path中取出(2,3)作為當前最佳結點nearest, dist為0.141；

然后回溯至(5,4)，以(2.1,3.1)為圓心，以dist=0.141為半徑畫一個圓，

并不和超平面y=4相交，如下圖，所以不必跳到結點(5,4)的右子空間去搜索，因為右子空間中不可能有更近樣本點了。
于是在回溯至(7,2)，同理，以(2.1,3.1)為圓心，以dist=0.141為半徑畫一個圓并不和超平面x=7相交，所以也不用跳到結點(7,2)的右子空間去搜索。
至此，search_path為空，結束整個搜索，返回nearest(2,3)作為(2.1,3.1)的最近鄰點，最近距離為0.141。

總結這里的圓是在查詢到最后一個節點的時候，半徑=（被查詢點-樹的最下面的葉子節點的差值）2，然后再在回溯的時候，看看被回溯的樣本點會不會落在這個圓里面，如果落在里面，那么修改圓半徑，否則就認為當前最短

再舉一個稍微復雜的例子，

我們來查找點(2,4.5)，

在(7,2)處測試到達(5,4)，

在(5,4)處測試到達(4,7)，

然后search_path中的結點為<(7,2), (5,4), (4,7)>，

從search_path中取出(4,7)作為當前最佳結點nearest,

dist（半徑距離）為3.202；
然后回溯至(5,4)，以(2,4.5)為圓心，以dist=3.202為半徑畫一個圓與超平面y=4相交，如下圖，所以需要跳到(5,4)的左子空間去搜索。所以要將(2,3)加入到search_path中，現在search_path中的結點為<(7,2), (2, 3)>；另外，(5,4)與(2,4.5)的距離為3.04 < dist = 3.202，所以將(5,4)賦給nearest，并且dist=3.04。（可以看到這里最近點進行了更替，由(4,7)改成了(5,4)）
回溯至(2,3)，(2,3)是葉子節點，直接平判斷(2,3)是否離(2,4.5)更近，計算得到距離為1.5，所以nearest更新為(2,3)，dist更新為(1.5)
回溯至(7,2)，同理，以(2,4.5)為圓心，以dist=1.5為半徑畫一個圓并不和超平面x=7相交, 所以不用跳到結點(7,2)的右子空間去搜索。

至此，search_path為空，結束整個搜索，返回nearest(2,3)作為(2,4.5)的最近鄰點，最近距離為1.5。

所以在搜索中可能會出現不同的情況，比如下面的兩張圖就是比較極端的兩個例子。

?

代碼清單

以下是k-d樹的c++代碼實現，包括建樹過程和搜索過程。算法main函數輸入k-d樹訓練實例點，算法會完成建樹操作，隨后可以輸入待查詢的目標點，程序將會搜索K-d樹找出與輸入目標點最近鄰的訓練實例點。本程序只實現了1近鄰搜索(所以下面的代碼就不值得看了)，如果要實現k近鄰搜索，只需對程序稍作修改。比如可以對每個結點添加一個標記，如果已經輸出該結點為最近鄰結點，那么就繼續查找次近鄰的結點，直到輸出k個結點后算法結束。

#include?<iostream>?????? #include?<algorithm>?????? #include?<stack>?????? #include?<math.h>?????? using?namespace?std;?????? /*function?of?this?program:?build?a?2d?tree?using?the?input?training?data???the?input?is?exm_set?which?contains?a?list?of?tuples?(x,y)???the?output?is?a?2d?tree?pointer*/??????struct?data?????? {??????double?x?=?0;??????double?y?=?0;?????? };??????struct?Tnode?????? {??????struct?data?dom_elt;??????int?split;??????struct?Tnode?*?left;??????struct?Tnode?*?right;?????? };??????bool?cmp1(data?a,?data?b){??????return?a.x?<?b.x;?????? }??????bool?cmp2(data?a,?data?b){??????return?a.y?<?b.y;?????? }??????bool?equal(data?a,?data?b){??????if?(a.x?==?b.x?&&?a.y?==?b.y)??????{??????return?true;??????}??????else{??????return?false;??????}?????? }??????void?ChooseSplit(data?exm_set[],?int?size,?int?&split,?data?&SplitChoice){??????/*compute?the?variance?on?every?dimension.?Set?split?as?the?dismension?that?have?the?biggest???variance.?Then?choose?the?instance?which?is?the?median?on?this?split?dimension.*/??????/*compute?variance?on?the?x,y?dimension.?DX=EX^2-(EX)^2*/??????double?tmp1,tmp2;??????tmp1?=?tmp2?=?0;??????for?(int?i?=?0;?i?<?size;?++i)??????{??????tmp1?+=?1.0?/?(double)size?*?exm_set[i].x?*?exm_set[i].x;??????tmp2?+=?1.0?/?(double)size?*?exm_set[i].x;??????}??????double?v1?=?tmp1?-?tmp2?*?tmp2;??//compute?variance?on?the?x?dimension??????tmp1?=?tmp2?=?0;??????for?(int?i?=?0;?i?<?size;?++i)??????{??????tmp1?+=?1.0?/?(double)size?*?exm_set[i].y?*?exm_set[i].y;??????tmp2?+=?1.0?/?(double)size?*?exm_set[i].y;??????}??????double?v2?=?tmp1?-?tmp2?*?tmp2;??//compute?variance?on?the?y?dimension??????split?=?v1?>?v2???0:1;?//set?the?split?dimension??????if?(split?==?0)??????{??????sort(exm_set,exm_set?+?size,?cmp1);??????}??????else{??????sort(exm_set,exm_set?+?size,?cmp2);??????}??????//set?the?split?point?value??????SplitChoice.x?=?exm_set[size?/?2].x;??????SplitChoice.y?=?exm_set[size?/?2].y;??????}??????Tnode*?build_kdtree(data?exm_set[],?int?size,?Tnode*?T){??????//call?function?ChooseSplit?to?choose?the?split?dimension?and?split?point??????if?(size?==?0){??????return?NULL;??????}??????else{??????int?split;??????data?dom_elt;??????ChooseSplit(exm_set,?size,?split,?dom_elt);??????data?exm_set_right?[100];??????data?exm_set_left?[100];??????int?sizeleft?,sizeright;??????sizeleft?=?sizeright?=?0;??????if?(split?==?0)??????{??????for?(int?i?=?0;?i?<?size;?++i)??????{??????if?(!equal(exm_set[i],dom_elt)?&&?exm_set[i].x?<=?dom_elt.x)??????{??????exm_set_left[sizeleft].x?=?exm_set[i].x;??????exm_set_left[sizeleft].y?=?exm_set[i].y;??????sizeleft++;??????}??????else?if?(!equal(exm_set[i],dom_elt)?&&?exm_set[i].x?>?dom_elt.x)??????{??????exm_set_right[sizeright].x?=?exm_set[i].x;??????exm_set_right[sizeright].y?=?exm_set[i].y;??????sizeright++;??????}??????}??????}??????else{??????for?(int?i?=?0;?i?<?size;?++i)??????{??????if?(!equal(exm_set[i],dom_elt)?&&?exm_set[i].y?<=?dom_elt.y)??????{??????exm_set_left[sizeleft].x?=?exm_set[i].x;??????exm_set_left[sizeleft].y?=?exm_set[i].y;??????sizeleft++;??????}??????else?if?(!equal(exm_set[i],dom_elt)?&&?exm_set[i].y?>?dom_elt.y)??????{??????exm_set_right[sizeright].x?=?exm_set[i].x;??????exm_set_right[sizeright].y?=?exm_set[i].y;??????sizeright++;??????}??????}??????}??????T?=?new?Tnode;??????T->dom_elt.x?=?dom_elt.x;??????T->dom_elt.y?=?dom_elt.y;??????T->split?=?split;??????T->left?=?build_kdtree(exm_set_left,?sizeleft,?T->left);??????T->right?=?build_kdtree(exm_set_right,?sizeright,?T->right);??????return?T;??????}?????? }??????double?Distance(data?a,?data?b){??????double?tmp?=?(a.x?-?b.x)?*?(a.x?-?b.x)?+?(a.y?-?b.y)?*?(a.y?-?b.y);??????return?sqrt(tmp);?????? }??????void?searchNearest(Tnode?*?Kd,?data?target,?data?&nearestpoint,?double?&?distance){??????//1.?如果Kd是空的，則設dist為無窮大返回??????//2.?向下搜索直到葉子結點??????stack<Tnode*>?search_path;??????Tnode*?pSearch?=?Kd;??????data?nearest;??????double?dist;??????while(pSearch?!=?NULL)??????{??????//pSearch加入到search_path中;??????search_path.push(pSearch);??????if?(pSearch->split?==?0)??????{??????if(target.x?<=?pSearch->dom_elt.x)?/*?如果小于就進入左子樹?*/??????{??????pSearch?=?pSearch->left;??????}??????else??????{??????pSearch?=?pSearch->right;??????}??????}??????else{??????if(target.y?<=?pSearch->dom_elt.y)?/*?如果小于就進入左子樹?*/??????{??????pSearch?=?pSearch->left;??????}??????else??????{??????pSearch?=?pSearch->right;??????}??????}??????}??????//取出search_path最后一個賦給nearest??????nearest.x?=?search_path.top()->dom_elt.x;??????nearest.y?=?search_path.top()->dom_elt.y;??????search_path.pop();??????dist?=?Distance(nearest,?target);??????//3.?回溯搜索路徑??????Tnode*?pBack;??????while(search_path.size()?!=?0)??????{??????//取出search_path最后一個結點賦給pBack??????pBack?=?search_path.top();??????search_path.pop();??????if(pBack->left?==?NULL?&&?pBack->right?==?NULL)?/*?如果pBack為葉子結點?*/??????{??????if(?Distance(nearest,?target)?>?Distance(pBack->dom_elt,?target)?)??????{??????nearest?=?pBack->dom_elt;??????dist?=?Distance(pBack->dom_elt,?target);??????}??????}??????else??????{??????int?s?=?pBack->split;??????if?(s?==?0)??????{??????if(?fabs(pBack->dom_elt.x?-?target.x)?<?dist)?/*?如果以target為中心的圓（球或超球），半徑為dist的圓與分割超平面相交，?那么就要跳到另一邊的子空間去搜索?*/??????{??????if(?Distance(nearest,?target)?>?Distance(pBack->dom_elt,?target)?)??????{??????nearest?=?pBack->dom_elt;??????dist?=?Distance(pBack->dom_elt,?target);??????}??????if(target.x?<=?pBack->dom_elt.x)?/*?如果target位于pBack的左子空間，那么就要跳到右子空間去搜索?*/??????pSearch?=?pBack->right;??????else??????pSearch?=?pBack->left;?/*?如果target位于pBack的右子空間，那么就要跳到左子空間去搜索?*/??????if(pSearch?!=?NULL)??????//pSearch加入到search_path中??????search_path.push(pSearch);??????}??????}??????else?{??????if(?fabs(pBack->dom_elt.y?-?target.y)?<?dist)?/*?如果以target為中心的圓（球或超球），半徑為dist的圓與分割超平面相交，?那么就要跳到另一邊的子空間去搜索?*/??????{??????if(?Distance(nearest,?target)?>?Distance(pBack->dom_elt,?target)?)??????{??????nearest?=?pBack->dom_elt;??????dist?=?Distance(pBack->dom_elt,?target);??????}??????if(target.y?<=?pBack->dom_elt.y)?/*?如果target位于pBack的左子空間，那么就要跳到右子空間去搜索?*/??????pSearch?=?pBack->right;??????else??????pSearch?=?pBack->left;?/*?如果target位于pBack的右子空間，那么就要跳到左子空間去搜索?*/??????if(pSearch?!=?NULL)??????//?pSearch加入到search_path中??????search_path.push(pSearch);??????}??????}??????}??????}??????nearestpoint.x?=?nearest.x;??????nearestpoint.y?=?nearest.y;??????distance?=?dist;??????}??????int?main(){??????data?exm_set[100];?//assume?the?max?training?set?size?is?100??????double?x,y;??????int?id?=?0;??????cout<<"Please?input?the?training?data?in?the?form?x?y.?One?instance?per?line.?Enter?-1?-1?to?stop."<<endl;??????while?(cin>>x>>y){??????if?(x?==?-1)??????{??????break;??????}??????else{??????exm_set[id].x?=?x;??????exm_set[id].y?=?y;??????id++;??????}??????}??????struct?Tnode?*?root?=?NULL;??????root?=?build_kdtree(exm_set,?id,?root);??????data?nearestpoint;??????double?distance;??????data?target;??????cout?<<"Enter?search?point"<<endl;??????while?(cin>>target.x>>target.y)??????{??????searchNearest(root,?target,?nearestpoint,?distance);??????cout<<"The?nearest?distance?is?"<<distance<<",and?the?nearest?point?is?"<<nearestpoint.x<<","<<nearestpoint.y<<endl;??????cout?<<"Enter?search?point"<<endl;??????}?????? }????

?

參考

最近鄰算法的實現:k-d tree -?http://blog.csdn.NET/zhl30041839/article/details/9277807

從K近鄰算法、距離度量談到KD樹、SIFT+BBF算法 -?http://blog.csdn.Net/v_july_v/article/details/8203674

Stanford CS106L assignment3 download

CMU?An intoductory tutorial on kd trees ?download

?

?

總結

以上是生活随笔為你收集整理的详解 KDTree（转）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。