Kd-Tree点楼，即K-dimensional tree辙培，是一種高維索引樹形數(shù)據(jù)結(jié)構(gòu)，常用于在大規(guī)模的高維數(shù)據(jù)空間進(jìn)行最近鄰查找(Nearest Neighbor)和近似最近鄰查找(Approximate Nearest Neighbor)薯演，例如圖像檢索和識別中的高維圖像特征向量的K近鄰查找與匹配翠勉。本文首先介紹Kd-Tree的基本原理朦蕴，然后對基于BBF的近似查找方法進(jìn)行介紹疏尿，最后給出一些參考文獻(xiàn)和開源實(shí)現(xiàn)代碼榆鼠。

1. Kd-tree

Kd-Tree震鹉，即K-dimensional tree俱笛，是一棵二叉樹，樹中存儲的是一些K維數(shù)據(jù)传趾。在一個K維數(shù)據(jù)集合上構(gòu)建一棵Kd-Tree代表了對該K維數(shù)據(jù)集合構(gòu)成的K維空間的一個劃分迎膜，即樹中的每個結(jié)點(diǎn)就對應(yīng)了一個K維的超矩形區(qū)域（Hyperrectangle）。

在介紹Kd-tree的相關(guān)算法前浆兰，我們先回顧一下二叉查找樹（Binary Search Tree）的相關(guān)概念和算法磕仅。

二叉查找樹（Binary Search Tree珊豹，BST），是具有如下性質(zhì)的二叉樹（來自wiki）：

若它的左子樹不為空榕订，則左子樹上所有結(jié)點(diǎn)的值均小于它的根結(jié)點(diǎn)的值店茶；

若它的右子樹不為空，則右子樹上所有結(jié)點(diǎn)的值均大于它的根結(jié)點(diǎn)的值劫恒；

它的左贩幻、右子樹也分別為二叉排序樹；

例如两嘴，圖1中是一棵二叉查找樹丛楚，其滿足BST的性質(zhì)。

圖1 二叉查找樹（來源：Wiki）

給定一個1維數(shù)據(jù)集合憔辫，怎樣構(gòu)建一棵BST樹呢趣些？根據(jù)BST的性質(zhì)就可以創(chuàng)建，即將數(shù)據(jù)點(diǎn)一個一個插入到BST樹中螺垢，插入后的樹仍然是BST樹喧务，即根結(jié)點(diǎn)的左子樹中所有結(jié)點(diǎn)的值均小于根結(jié)點(diǎn)的值，而根結(jié)點(diǎn)的右子樹中所有結(jié)點(diǎn)的值均大于根結(jié)點(diǎn)的值枉圃。

將一個1維數(shù)據(jù)集用一棵BST樹存儲后功茴，當(dāng)我們想要查詢某個數(shù)據(jù)是否位于該數(shù)據(jù)集合中時，只需要將查詢數(shù)據(jù)與結(jié)點(diǎn)值進(jìn)行比較然后選擇對應(yīng)的子樹繼續(xù)往下查找即可孽亲，查找的平均時間復(fù)雜度為：O(logN)坎穿，最壞的情況下是O(N)。

如果我們要處理的對象集合是一個K維空間中的數(shù)據(jù)集返劲，那么是否也可以構(gòu)建一棵類似于1維空間中的二叉查找樹呢玲昧？答案是肯定的，只不過推廣到K維空間后篮绿，創(chuàng)建二叉樹和查詢二叉樹的算法會有一些相應(yīng)的變化（后面會介紹到兩者的區(qū)別）孵延，這就是下面我們要介紹的Kd-tree算法。

怎樣構(gòu)造一棵Kd-tree亲配？

對于Kd-tree這樣一棵二叉樹尘应，我們首先需要確定怎樣劃分左子樹和右子樹，即一個K維數(shù)據(jù)是依據(jù)什么被劃分到左子樹或右子樹的吼虎。

在構(gòu)造1維BST樹時犬钢，一個1維數(shù)據(jù)根據(jù)其與樹的根結(jié)點(diǎn)和中間結(jié)點(diǎn)進(jìn)行大小比較的結(jié)果來決定是劃分到左子樹還是右子樹，同理思灰，我們也可以按照這樣的方式玷犹，將一個K維數(shù)據(jù)與Kd-tree的根結(jié)點(diǎn)和中間結(jié)點(diǎn)進(jìn)行比較，只不過不是對K維數(shù)據(jù)進(jìn)行整體的比較洒疚，而是選擇某一個維度Di歹颓，然后比較兩個K維數(shù)在該維度Di上的大小關(guān)系坯屿，即每次選擇一個維度Di來對K維數(shù)據(jù)進(jìn)行劃分，相當(dāng)于用一個垂直于該維度Di的超平面將K維數(shù)據(jù)空間一分為二晴股，平面一邊的所有K維數(shù)據(jù)在Di維度上的值小于平面另一邊的所有K維數(shù)據(jù)對應(yīng)維度上的值愿伴。也就是說，我們每選擇一個維度進(jìn)行如上的劃分电湘，就會將K維數(shù)據(jù)空間劃分為兩個部分，如果我們繼續(xù)分別對這兩個子K維空間進(jìn)行如上的劃分鹅经，又會得到新的子空間寂呛，對新的子空間又繼續(xù)劃分，重復(fù)以上過程直到每個子空間都不能再劃分為止瘾晃。以上就是構(gòu)造Kd-Tree的過程贷痪，上述過程中涉及到兩個重要的問題：

每次對子空間的劃分時，怎樣確定在哪個維度上進(jìn)行劃分蹦误。

在某個維度上進(jìn)行劃分時劫拢，怎樣確保在這一維度上的劃分得到的兩個子集合的數(shù)量盡量相等，即左子樹和右子樹中的結(jié)點(diǎn)個數(shù)盡量相等强胰。

問題1： 每次對子空間的劃分時舱沧，怎樣確定在哪個維度上進(jìn)行劃分？

最簡單的方法就是輪著來偶洋，即如果這次選擇了在第i維上進(jìn)行數(shù)據(jù)劃分熟吏，那下一次就在第j(j≠i)維上進(jìn)行劃分，例如：j = (i mod k) + 1玄窝。

想象一下我們切豆腐時牵寺，先是豎著切一刀，切成兩半后恩脂，再橫著來一刀帽氓，就得到了很小的方塊豆腐。

可是“輪著來”的方法是否可以很好地解決問題呢俩块？

再次想象一下黎休，我們現(xiàn)在要切的是一根木條，按照“輪著來”的方法先是豎著切一刀典阵，木條一分為二奋渔，干凈利落，接下來就是再橫著切一刀壮啊，這個時候就有點(diǎn)考驗(yàn)刀法了嫉鲸，如果木條的直徑（橫截面）較大，還可以下手歹啼，如果直徑較小玄渗，就沒法往下切了座菠。

因此，如果K維數(shù)據(jù)的分布像上面的豆腐一樣藤树，“輪著來”的切分方法是可以奏效浴滴，但是如果K維度上數(shù)據(jù)的分布像木條一樣，“輪著來”就不好用了岁钓。因此升略，還需要想想其他的切法。

如果一個K維數(shù)據(jù)集合的分布像木條一樣屡限，那就是說明這K維數(shù)據(jù)在木條較長方向代表的維度上品嚣，這些數(shù)據(jù)的分布散得比較開，數(shù)學(xué)上來說钧大，就是這些數(shù)據(jù)在該維度上的方差（invariance）比較大翰撑，換句話說，正因?yàn)檫@些數(shù)據(jù)在該維度上分散的比較開啊央，我們就更容易在這個維度上將它們劃分開眶诈，因此，這就引出了我們選擇維度的另一種方法：最大方差法（max invarince）瓜饥，即每次我們選擇維度進(jìn)行劃分時逝撬，都選擇具有最大方差維度。

問題2：在某個維度上進(jìn)行劃分時压固，怎樣確保在這一維度上的劃分得到的兩個子集合的數(shù)量盡量相等球拦，即左子樹和右子樹中的結(jié)點(diǎn)個數(shù)盡量相等？

假設(shè)當(dāng)前我們按照最大方差法選擇了在維度i上進(jìn)行K維數(shù)據(jù)集S的劃分帐我，此時我們需要在維度i上將K維數(shù)據(jù)集合S劃分為兩個子集合A和B坎炼，子集合A中的數(shù)據(jù)在維度i上的值都小于子集合B中。首先考慮最簡單的劃分法拦键，即選擇第一個數(shù)作為比較對象（即劃分軸谣光，pivot），S中剩余的其他所有K維數(shù)據(jù)都跟該pivot在維度i上進(jìn)行比較芬为，如果小于pivot則劃A集合萄金，大于則劃入B集合。把A集合和B集合分別看做是左子樹和右子樹媚朦，那么我們在構(gòu)造一個二叉樹的時候氧敢，當(dāng)然是希望它是一棵盡量平衡的樹，即左右子樹中的結(jié)點(diǎn)個數(shù)相差不大询张。而A集合和B集合中數(shù)據(jù)的個數(shù)顯然跟pivot值有關(guān)孙乖，因?yàn)樗鼈兪歉鷓ivot比較后才被劃分到相應(yīng)的集合中去的。好了，現(xiàn)在的問題就是確定pivot了唯袄。給定一個數(shù)組弯屈，怎樣才能得到兩個子數(shù)組，這兩個數(shù)組包含的元素個數(shù)差不多且其中一個子數(shù)組中的元素值都小于另一個子數(shù)組呢恋拷？方法很簡單资厉，找到數(shù)組中的中值（即中位數(shù)，median）蔬顾，然后將數(shù)組中所有元素與中值進(jìn)行比較宴偿，就可以得到上述兩個子數(shù)組。同樣阎抒，在維度i上進(jìn)行劃分時酪我，pivot就選擇該維度i上所有數(shù)據(jù)的中值，這樣得到的兩個子集合數(shù)據(jù)個數(shù)就基本相同了且叁。

解決了上面兩個重要的問題后，就得到了Kd-Tree的構(gòu)造算法了秩伞。

Kd-Tree的構(gòu)建算法：

（1） 在K維數(shù)據(jù)集合中選擇具有最大方差的維度k逞带，然后在該維度上選擇中值m為pivot對該數(shù)據(jù)集合進(jìn)行劃分，得到兩個子集合纱新；同時創(chuàng)建一個樹結(jié)點(diǎn)node展氓，用于存儲；

（2）對兩個子集合重復(fù)（1）步驟的過程脸爱，直至所有子集合都不能再劃分為止遇汞；如果某個子集合不能再劃分時，則將該子集合中的數(shù)據(jù)保存到葉子結(jié)點(diǎn)（leaf node）簿废。

以上就是創(chuàng)建Kd-Tree的算法空入。下面給出一個簡單例子。

給定二維數(shù)據(jù)集合：(2,3), (5,4), (9,6), (4,7), (8,1), (7,2)族檬，利用上述算法構(gòu)建一棵Kd-tree歪赢。左圖是Kd-tree對應(yīng)二維數(shù)據(jù)集合的一個空間劃分，右圖是構(gòu)建的一棵Kd-tree单料。

圖2 構(gòu)建的kd-tree

其中圓圈代表了中間結(jié)點(diǎn)(k, m)埋凯，而紅色矩形代表了葉子結(jié)點(diǎn)。

Kd-Tree與一維二叉查找樹之間的區(qū)別：

二叉查找樹：數(shù)據(jù)存放在樹中的每個結(jié)點(diǎn)（根結(jié)點(diǎn)扫尖、中間結(jié)點(diǎn)白对、葉子結(jié)點(diǎn)）中；

Kd-Tree：數(shù)據(jù)只存放在葉子結(jié)點(diǎn)换怖，而根結(jié)點(diǎn)和中間結(jié)點(diǎn)存放一些空間劃分信息（例如劃分維度甩恼、劃分值）；

構(gòu)建好一棵Kd-Tree后，下面給出利用Kd-Tree進(jìn)行最近鄰查找的算法：

（1）將查詢數(shù)據(jù)Q從根結(jié)點(diǎn)開始媳拴，按照Q與各個結(jié)點(diǎn)的比較結(jié)果向下訪問Kd-Tree黄橘，直至達(dá)到葉子結(jié)點(diǎn)。

其中Q與結(jié)點(diǎn)的比較指的是將Q對應(yīng)于結(jié)點(diǎn)中的k維度上的值與m進(jìn)行比較屈溉，若Q(k) < m塞关，則訪問左子樹，否則訪問右子樹子巾。達(dá)到葉子結(jié)點(diǎn)時帆赢，計(jì)算Q與葉子結(jié)點(diǎn)上保存的數(shù)據(jù)之間的距離，記錄下最小距離對應(yīng)的數(shù)據(jù)點(diǎn)线梗，記為當(dāng)前“最近鄰點(diǎn)”Pcur和最小距離Dcur椰于。

（2）進(jìn)行回溯（Backtracking）操作，該操作是為了找到離Q更近的“最近鄰點(diǎn)”仪搔。即判斷未被訪問過的分支里是否還有離Q更近的點(diǎn)瘾婿，它們之間的距離小于Dcur。

如果Q與其父結(jié)點(diǎn)下的未被訪問過的分支之間的距離小于Dcur烤咧，則認(rèn)為該分支中存在離P更近的數(shù)據(jù)偏陪，進(jìn)入該結(jié)點(diǎn)，進(jìn)行（1）步驟一樣的查找過程煮嫌，如果找到更近的數(shù)據(jù)點(diǎn)笛谦，則更新為當(dāng)前的“最近鄰點(diǎn)”Pcur，并更新Dcur昌阿。

如果Q與其父結(jié)點(diǎn)下的未被訪問過的分支之間的距離大于Dcur饥脑，則說明該分支內(nèi)不存在與Q更近的點(diǎn)。

回溯的判斷過程是從下往上進(jìn)行的懦冰，直到回溯到根結(jié)點(diǎn)時已經(jīng)不存在與P更近的分支為止灶轰。

怎樣判斷未被訪問過的樹分支Branch里是否還有離Q更近的點(diǎn)？

從幾何空間上來看儿奶，就是判斷以Q為中心center和以Dcur為半徑Radius的超球面（Hypersphere）與樹分支Branch代表的超矩形（Hyperrectangle）之間是否相交框往。

在實(shí)現(xiàn)中，我們可以有兩種方式來求Q與樹分支Branch之間的距離闯捎。第一種是在構(gòu)造樹的過程中椰弊，就記錄下每個子樹中包含的所有數(shù)據(jù)在該子樹對應(yīng)的維度k上的邊界參數(shù)[min, max]；第二種是在構(gòu)造樹的過程中瓤鼻，記錄下每個子樹所在的分割維度k和分割值m秉版，（k, m），Q與子樹的距離則為|Q(k) - m|茬祷。

以上就是Kd-tree的構(gòu)造過程和基于Kd-Tree的最近鄰查找過程清焕。

下面用一個簡單的例子來演示基于Kd-Tree的最近鄰查找的過程。

數(shù)據(jù)點(diǎn)集合：(2,3), (4,7), (5,4), (9,6), (8,1), (7,2) 。

已建好的Kd-Tree：

圖3 構(gòu)建的kd-tree

其中秸妥，左圖中紅色點(diǎn)表示數(shù)據(jù)集合中的所有點(diǎn)滚停。

查詢點(diǎn)： (8, 3) （在左圖中用茶色菱形點(diǎn)表示）

第一次查詢：

圖4 第一次查詢的kd-tree

當(dāng)前最近鄰點(diǎn)： (9, 6) ， 最近鄰距離： sqrt(10)粥惧，

且在未被選擇的樹分支中存在于Q更近的點(diǎn)（如茶色圈圈內(nèi)的兩個紅色點(diǎn)）

回溯：

圖5 回溯kd-tree

當(dāng)前最近鄰點(diǎn)： (8, 1)和(7, 2) 键畴， 最近鄰距離： sqrt(2)

最后，查詢點(diǎn)(8, 3)的近似最近鄰點(diǎn)為(8, 1)和(7, 2) 突雪。

2. Kd-tree with BBF

上一節(jié)介紹的Kd-tree在維度較小時（例如：K≤30）起惕，算法的查找效率很高，然而當(dāng)Kd-tree用于對高維數(shù)據(jù)（例如：K≥100）進(jìn)行索引和查找時咏删，就面臨著維數(shù)災(zāi)難（curse of dimension）問題惹想，查找效率會隨著維度的增加而迅速下降。通常督函，實(shí)際應(yīng)用中嘀粱，我們常常處理的數(shù)據(jù)都具有高維的特點(diǎn)，例如在圖像檢索和識別中辰狡，每張圖像通常用一個幾百維的向量來表示草穆，每個特征點(diǎn)的局部特征用一個高維向量來表征（例如：128維的SIFT特征）。因此搓译，為了能夠讓Kd-tree滿足對高維數(shù)據(jù)的索引，Jeffrey S. Beis和David G. Lowe提出了一種改進(jìn)算法——Kd-tree with BBF（Best Bin First）锋喜，該算法能夠?qū)崿F(xiàn)近似K近鄰的快速搜索些己，在保證一定查找精度的前提下使得查找速度較快。

在介紹BBF算法前嘿般，我們先來看一下原始Kd-tree是為什么在低維空間中有效而到了高維空間后查找效率就會下降段标。在原始kd-tree的最近鄰查找算法中（第一節(jié)中介紹的算法），為了能夠找到查詢點(diǎn)Q在數(shù)據(jù)集合中的最近鄰點(diǎn)炉奴，有一個重要的操作步驟：回溯逼庞，該步驟是在未被訪問過的且與Q的超球面相交的子樹分支中查找可能存在的最近鄰點(diǎn)。隨著維度K的增大瞻赶，與Q的超球面相交的超矩形（子樹分支所在的區(qū)域）就會增加赛糟，這就意味著需要回溯判斷的樹分支就會更多，從而算法的查找效率便會下降很大砸逊。

一個很自然的思路是：既然kd-tree算法在高維空間中是由于過多的回溯次數(shù)導(dǎo)致算法查找效率下降的話璧南，我們就可以限制查找時進(jìn)行回溯的次數(shù)上限，從而避免查找效率下降师逸。這樣做有兩個問題需要解決：1）最大回溯次數(shù)怎么確定司倚？2）怎樣保證在最大回溯次數(shù)內(nèi)找到的最近鄰比較接近真實(shí)最近鄰，即查找準(zhǔn)確度不能下降太大。

問題1）：最大回溯次數(shù)怎么確定动知？

最大回溯次數(shù)一般人為設(shè)定皿伺，通常根據(jù)在數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果進(jìn)行調(diào)整。

問題2）：怎樣保證在最大回溯次數(shù)內(nèi)找到的最近鄰比較接近真實(shí)最近鄰盒粮，即查找準(zhǔn)確度不能下降太大鸵鸥？

限制回溯次數(shù)后，如果我們還是按照原來的回溯方法挨個地進(jìn)行訪問的話拆讯，那很顯然最后的查找結(jié)果的精度就很大程度上取決于數(shù)據(jù)的分布和回溯次數(shù)了脂男。挨個訪問的方法的問題在于認(rèn)為每個待回溯的樹分支中存在最近鄰的概率是一樣的，所以它對所有的待回溯樹分支一視同仁种呐。實(shí)際上宰翅，在這些待回溯樹分支中，有些樹分支存在最近鄰的可能性比其他樹分支要高爽室，因?yàn)闃浞种щxQ點(diǎn)之間的距離或相交程度是不一樣的汁讼，離Q更近的樹分支存在Q的最近鄰的可能性更高。因此阔墩，我們需要區(qū)別對待每個待回溯的樹分支嘿架，即采用某種優(yōu)先級順序來訪問這些待回溯樹分支，使得在有限的回溯次數(shù)中找到Q的最近鄰的可能性很高啸箫。我們要介紹的BBF算法正是基于這樣的解決思路耸彪，下面我們介紹BBF查找算法。

基于BBF的Kd-Tree近似最近鄰查找算法

已知：

Q：查詢數(shù)據(jù)忘苛； KT：已建好的Kd-Tree蝉娜；

1. 查找Q的當(dāng)前最近鄰點(diǎn)P

1）從KT的根結(jié)點(diǎn)開始，將Q與中間結(jié)點(diǎn)node(k,m)進(jìn)行比較扎唾，根據(jù)比較結(jié)果選擇某個樹分支Branch（或稱為Bin）召川；并將未被選擇的另一個樹分支（Unexplored Branch）所在的樹中位置和它跟Q之間的距離一起保存到一個優(yōu)先級隊(duì)列中Queue；

2）按照步驟1）的過程胸遇，對樹分支Branch進(jìn)行如上比較和選擇荧呐，直至訪問到葉子結(jié)點(diǎn)，然后計(jì)算Q與葉子結(jié)點(diǎn)中保存的數(shù)據(jù)之間的距離纸镊，并記錄下最小距離D以及對應(yīng)的數(shù)據(jù)P倍阐。

注：

A、Q與中間結(jié)點(diǎn)node(k,m)的比較過程：如果Q(k) > m則選擇右子樹薄腻，否則選擇左子樹收捣。

B、優(yōu)先級隊(duì)列：按照距離從小到大的順序排列庵楷。

C罢艾、葉子結(jié)點(diǎn)：每個葉子結(jié)點(diǎn)中保存的數(shù)據(jù)的個數(shù)可能是一個或多個楣颠。

2. 基于BBF的回溯

已知：最大回溯次數(shù)BTmax

1）如果當(dāng)前回溯的次數(shù)小于BTmax，且Queue不為空咐蚯，則進(jìn)行如下操作：

從Queue中取出最小距離對應(yīng)的Branch童漩，然后按照1.1步驟訪問該Branch直至達(dá)到葉子結(jié)點(diǎn)；計(jì)算Q與葉子結(jié)點(diǎn)中各個數(shù)據(jù)間距離春锋，如果有比D更小的值矫膨，則將該值賦給D，該數(shù)據(jù)則被認(rèn)為是Q的當(dāng)前近似最近鄰點(diǎn)期奔；

2）重復(fù)1）步驟侧馅，直到回溯次數(shù)大于BTmax或Queue為空時，查找結(jié)束呐萌，此時得到的數(shù)據(jù)P和距離D就是Q的近似最近鄰點(diǎn)和它們之間的距離馁痴。

下面用一個簡單的例子來演示基于Kd-Tree+BBF的近似最近鄰查找的過程。

數(shù)據(jù)點(diǎn)集合：(2,3), (4,7), (5,4), (9,6), (8,1), (7,2) 肺孤。

已建好的Kd-Tree：

圖6 構(gòu)建的kd-tree

基于BBF的查找的過程：

查詢點(diǎn)Q： (5.5, 5)

第一遍查詢：

圖7 第一次查詢的kd-tree

當(dāng)前最近鄰點(diǎn)： (9, 6) 罗晕， 最近鄰距離： sqrt(13.25)，

同時將未被選擇的樹分支的位置和與Q的距離記錄到優(yōu)先級隊(duì)列中赠堵。

BBF回溯：

從優(yōu)先級隊(duì)列里選擇距離Q最近的未被選擇樹分支進(jìn)行回溯小渊。

圖8 利用BBF方法回溯kd-tree

當(dāng)前最近鄰點(diǎn)： (4, 7) ， 最近鄰距離： sqrt(6.25)

繼續(xù)從優(yōu)先級隊(duì)列里選擇距離Q最近的未被選擇樹分支進(jìn)行回溯茫叭。

圖9 利用BBF方法回溯kd-tree

當(dāng)前最近鄰點(diǎn)： (5, 4) 酬屉， 最近鄰距離： sqrt(1.25)

最后，查詢點(diǎn)(5.5, 5)的近似最近鄰點(diǎn)為(5, 4) 揍愁。

作者：婉妃

鏈接：http://www.reibang.com/p/abcaaf754f92

來源：簡書

著作權(quán)歸作者所有梆惯。商業(yè)轉(zhuǎn)載請聯(lián)系作者獲得授權(quán)，非商業(yè)轉(zhuǎn)載請注明出處吗垮。