kd樹近鄰算法_數(shù)據(jù)分析師

kd樹近鄰搜索算法的改進(jìn)：BBF算法

    咱們順著上一節(jié)的思路，參考統(tǒng)計學(xué)習(xí)方法一書上的內(nèi)容，再來總結(jié)下kd樹的最近鄰搜索算法：

1. 在kd樹種找出包含目標(biāo)點x的葉結(jié)點：從根結(jié)點出發(fā)，遞歸地向下搜索kd樹。若目標(biāo)點x當(dāng)前維的坐標(biāo)小于切分點的坐標(biāo)，則移動到左子結(jié)點，否則移動到右子結(jié)點，直到子結(jié)點為葉結(jié)點為止。
2. 以此葉結(jié)點為“當(dāng)前最近點”。
3. 遞歸的向上回溯，在每個結(jié)點進(jìn)行以下操作：
   （a）如果該結(jié)點保存的實例點比當(dāng)前最近點距離目標(biāo)點更近，則更新“當(dāng)前最近點”，也就是說以該實例點為“當(dāng)前最近點”。
   （b）當(dāng)前最近點一定存在于該結(jié)點一個子結(jié)點對應(yīng)的區(qū)域，檢查子結(jié)點的父結(jié)點的另一子結(jié)點對應(yīng)的區(qū)域是否有更近的點。具體做法是，檢查另一子結(jié)點對應(yīng)的區(qū)域是否以目標(biāo)點位球心，以目標(biāo)點與“當(dāng)前最近點”間的距離為半徑的圓或超球體相交：
   如果相交，可能在另一個子結(jié)點對應(yīng)的區(qū)域內(nèi)存在距目標(biāo)點更近的點，移動到另一個子結(jié)點，接著，繼續(xù)遞歸地進(jìn)行最近鄰搜索；
   如果不相交，向上回溯。
4. 當(dāng)回退到根結(jié)點時，搜索結(jié)束，最后的“當(dāng)前最近點”即為x 的最近鄰點。

    如果實例點是隨機分布的，那么kd樹搜索的平均計算復(fù)雜度是O（NlogN），這里的N是訓(xùn)練實例樹。所以說，kd樹更適用于訓(xùn)練實例數(shù)遠(yuǎn)大于空間維數(shù)時的k近鄰搜索，當(dāng)空間維數(shù)接近訓(xùn)練實例數(shù)時，它的效率會迅速下降，一降降到“解放前”：線性掃描的速度。

    也正因為上述k最近鄰搜索算法的第4個步驟中的所述：“回退到根結(jié)點時，搜索結(jié)束”，每個最近鄰點的查詢比較完成過程最終都要回退到根結(jié)點而結(jié)束，而導(dǎo)致了許多不必要回溯訪問和比較到的結(jié)點，這些多余的損耗在高維度數(shù)據(jù)查找的時候，搜索效率將變得相當(dāng)之地下，那有什么辦法可以改進(jìn)這個原始的kd樹最近鄰搜索算法呢？

    從上述標(biāo)準(zhǔn)的kd樹查詢過程可以看出其搜索過程中的“回溯”是由“查詢路徑”決定的，并沒有考慮查詢路徑上一些數(shù)據(jù)點本身的一些性質(zhì)。一個簡單的改進(jìn)思路就是將“查詢路徑”上的結(jié)點進(jìn)行排序，如按各自分割超平面（也稱bin）與查詢點的距離排序，也就是說，回溯檢查總是從優(yōu)先級最高（Best Bin）的樹結(jié)點開始。

    針對此BBF機制，讀者Feng&書童點評道：

1. 在某一層，分割面是第ki維，分割值是kv，那么 abs(q[ki]-kv) 就是沒有選擇的那個分支的優(yōu)先級，也就是計算的是那一維上的距離；
2. 同時，從優(yōu)先隊列里面取節(jié)點只在某次搜索到葉節(jié)點后才發(fā)生，計算過距離的節(jié)點不會出現(xiàn)在隊列的，比如1~10這10個節(jié)點，你第一次搜索到葉節(jié)點的路徑是1-5-7，那么1，5，7是不會出現(xiàn)在優(yōu)先隊列的。換句話說，優(yōu)先隊列里面存的都是查詢路徑上節(jié)點對應(yīng)的相反子節(jié)點，比如：搜索左子樹，就把對應(yīng)這一層的右節(jié)點存進(jìn)隊列。

    如此，就引出了本節(jié)要討論的kd樹最近鄰搜索算法的改進(jìn)：BBF（Best-Bin-First）查詢算法，它是由發(fā)明sift算法的David Lowe在1997的一篇文章中針對高維數(shù)據(jù)提出的一種近似算法，此算法能確保優(yōu)先檢索包含最近鄰點可能性較高的空間，此外，BBF機制還設(shè)置了一個運行超時限定。采用了BBF查詢機制后，kd樹便可以有效的擴展到高維數(shù)據(jù)集上。

    偽代碼如下圖所示（圖取自圖像局部不變特性特征與描述一書）：

    還是以上面的查詢（2,4.5）為例，搜索的算法流程為：

1. 將（7,2）壓人優(yōu)先隊列中；
2. 提取優(yōu)先隊列中的（7,2），由于（2,4.5）位于（7,2）分割超平面的左側(cè)，所以檢索其左子結(jié)點（5,4）。同時，根據(jù)BBF機制”搜索左/右子樹，就把對應(yīng)這一層的兄弟結(jié)點即右/左結(jié)點存進(jìn)隊列”，將其（5,4）對應(yīng)的兄弟結(jié)點即右子結(jié)點（9,6）壓人優(yōu)先隊列中，此時優(yōu)先隊列為{（9,6）}，最佳點為（7,2）；然后一直檢索到葉子結(jié)點（4,7），此時優(yōu)先隊列為{（2,3），（9,6）}，“最佳點”則為（5,4）；
3. 提取優(yōu)先級最高的結(jié)點（2,3），重復(fù)步驟2，直到優(yōu)先隊列為空。

2.7、球樹、M樹、VP樹、MVP樹

2.7.1、球樹

    咱們來針對上文內(nèi)容總結(jié)回顧下，針對下面這樣一棵kd樹：

    現(xiàn)要找它的最近鄰。

    通過上文2.5節(jié)，總結(jié)來說，我們已經(jīng)知道：

1、為了找到一個給定目標(biāo)點的最近鄰，需要從樹的根結(jié)點開始向下沿樹找出目標(biāo)點所在的區(qū)域，如下圖所示，給定目標(biāo)點，用星號標(biāo)示，我們似乎一眼看出，有一個點離目標(biāo)點最近，因為它落在以目標(biāo)點為圓心以較小長度為半徑的虛線圓內(nèi)，但為了確定是否可能還村莊一個最近的近鄰，我們會先檢查葉節(jié)點的同胞結(jié)點，然葉節(jié)點的同胞結(jié)點在圖中所示的陰影部分，虛線圓并不與之相交，所以確定同胞葉結(jié)點不可能包含更近的近鄰。

2、于是我們回溯到父節(jié)點，并檢查父節(jié)點的同胞結(jié)點，父節(jié)點的同胞結(jié)點覆蓋了圖中所有橫線X軸上的區(qū)域。因為虛線圓與右上方的矩形(KD樹把二維平面劃分成一個一個矩形)相交...

    如上，我們看到，KD樹是可用于有效尋找最近鄰的一個樹結(jié)構(gòu)，但這個樹結(jié)構(gòu)其實并不完美，當(dāng)處理不均勻分布的數(shù)據(jù)集時便會呈現(xiàn)出一個基本沖突：既邀請樹有完美的平衡結(jié)構(gòu)，又要求待查找的區(qū)域近似方形，但不管是近似方形，還是矩形，甚至正方形，都不是最好的使用形狀，因為他們都有角。

    什么意思呢？就是說，在上圖中，如果黑色的實例點離目標(biāo)點星點再遠(yuǎn)一點，那么勢必那個虛線圓會如紅線所示那樣擴大，以致與左上方矩形的右下角相交，既然相交了，那么勢必又必須檢查這個左上方矩形，而實際上，最近的點離星點的距離很近，檢查左上方矩形區(qū)域已是多余。于此我們看見，KD樹把二維平面劃分成一個一個矩形，但矩形區(qū)域的角卻是個難以處理的問題。

    解決的方案就是使用如下圖所示的球樹：

先從球中選擇一個離球的中心最遠(yuǎn)的點，然后選擇第二個點離第一個點最遠(yuǎn)，將球中所有的點分配到離這兩個聚類中心最近的一個上，然后計算每個聚類的中心，以及聚類能夠包含它所有數(shù)據(jù)點所需的最小半徑。這種方法的優(yōu)點是分裂一個包含n個殊絕點的球的成本只是隨n呈線性增加。

    使用球樹找出給定目標(biāo)點的最近鄰方法是，首先自上而下貫穿整棵樹找出包含目標(biāo)點所在的葉子，并在這個球里找出與目標(biāo)點最靠近的點，這將確定出目標(biāo)點距離它的最近鄰點的一個上限值，然后跟KD樹查找一樣，檢查同胞結(jié)點，如果目標(biāo)點到同胞結(jié)點中心的距離超過同胞結(jié)點的半徑與當(dāng)前的上限值之和，那么同胞結(jié)點里不可能存在一個更近的點；否則的話，必須進(jìn)一步檢查位于同胞結(jié)點以下的子樹。

    如下圖，目標(biāo)點還是用一個星表示，黑色點是當(dāng)前已知的的目標(biāo)點的最近鄰，灰色球里的所有內(nèi)容將被排除，因為灰色球的中心點離的太遠(yuǎn)，所以它不可能包含一個更近的點，像這樣，遞歸的向樹的根結(jié)點進(jìn)行回溯處理，檢查所有可能包含一個更近于當(dāng)前上限值的點的球。

    球樹是自上而下的建立，和KD樹一樣，根本問題就是要找到一個好的方法將包含數(shù)據(jù)點集的球分裂成兩個，在實踐中，不必等到葉子結(jié)點只有兩個胡數(shù)據(jù)點時才停止，可以采用和KD樹一樣的方法，一旦結(jié)點上的數(shù)據(jù)點打到預(yù)先設(shè)置的最小數(shù)量時，便可提前停止建樹過程。

    也就是上面所述，先從球中選擇一個離球的中心最遠(yuǎn)的點，然后選擇第二個點離第一個點最遠(yuǎn)，將球中所有的點分配到離這兩個聚類中心最近的一個上，然后計算每個聚類的中心，以及聚類能夠包含它所有數(shù)據(jù)點所需的最小半徑。這種方法的優(yōu)點是分裂一個包含n個殊絕點的球的成本只是隨n呈線性增加(注：本小節(jié)內(nèi)容主要來自參考條目19：數(shù)據(jù)挖掘實用機器學(xué)習(xí)技術(shù)，[新西蘭]Ian H.Witten 著，第4章4.7節(jié))。

2.7.2、VP樹與MVP樹簡介

    高維特征向量的距離索引問題是基于內(nèi)容的圖像檢索的一項關(guān)鍵技術(shù)，目前經(jīng)常采用的解決辦法是首先對高維特征空間做降維處理，然后采用包括四叉樹、kd樹、R樹族等在內(nèi)的主流多維索引結(jié)構(gòu)，這種方法的出發(fā)點是：目前的主流多維索引結(jié)構(gòu)在處理維數(shù)較低的情況時具有比較好的效率，但對于維數(shù)很高的情況則顯得力不從心(即所謂的維數(shù)危機) 。

    實驗結(jié)果表明當(dāng)特征空間的維數(shù)超過20 的時候，效率明顯降低，而可視化特征往往采用高維向量描述，一般情況下可以達(dá)到10^2的量級，甚至更高。在表示圖像可視化特征的高維向量中各維信息的重要程度是不同的，通過降維技術(shù)去除屬于次要信息的特征向量以及相關(guān)性較強的特征向量，從而降低特征空間的維數(shù)，這種方法已經(jīng)得到了一些實際應(yīng)用。

    然而這種方法存在不足之處采用降維技術(shù)可能會導(dǎo)致有效信息的損失，尤其不適合于處理特征空間中的特征向量相關(guān)性很小的情況。另外主流的多維索引結(jié)構(gòu)大都針對歐氏空間，設(shè)計需要利用到歐氏空間的幾何性質(zhì)，而圖像的相似性計算很可能不限于基于歐氏距離。這種情況下人們越來越關(guān)注基于距離的度量空間高維索引結(jié)構(gòu)可以直接應(yīng)用于高維向量相似性查詢問題。

    度量空間中對象之間的距離度量只能利用三角不等式性質(zhì)，而不能利用其他幾何性質(zhì)。向量空間可以看作由實數(shù)坐標(biāo)串組成的特殊度量空間，目前針對度量空間的高維索引問題提出的索引結(jié)構(gòu)有很多種大致可以作如下分類，如下圖所示：

     讀者點評：

1. UESTC_HN_AY_GUOBO：現(xiàn)在主要是在kdtree的基礎(chǔ)上有了mtree或者mvptree，其實關(guān)鍵還是pivot的選擇，以及度量空間中算法怎么減少距離計算；
2. mandycool：mvp-tree，是利用三角形不等式來縮小搜索區(qū)域的，不過mvp-tree的目標(biāo)稍有不同，查詢的是到query點的距離小于某個值r的點；另外作者test的數(shù)據(jù)集只有20維，不知道上百維以后效果如何，而減少距離計算的一個思路是做embedding，通過不等式排除掉一部分點。