kd樹近鄰算法_數據分析師

kd樹近鄰搜索算法的改進：BBF算法

    咱們順著上一節的思路，參考統計學習方法一書上的內容，再來總結下kd樹的最近鄰搜索算法：

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

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

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

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

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

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

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

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

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

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

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

2.7.1、球樹

    咱們來針對上文內容總結回顧下，針對下面這樣一棵kd樹：

    現要找它的最近鄰。

    通過上文2.5節，總結來說，我們已經知道：

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

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

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

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

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

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

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

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

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

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

2.7.2、VP樹與MVP樹簡介

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

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

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

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

     讀者點評：

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