什么是KD樹_數據分析師

       之前曾經介紹過SIFT特征匹配算法，特征點匹配和數據庫查、圖像檢索本質上是同一個問題，都可以歸結為一個通過距離函數在高維矢量之間進行相似性檢索的問題，如何快速而準確地找到查詢點的近鄰，不少人提出了很多高維空間索引結構和近似查詢的算法。

    一般說來，索引結構中相似性查詢有兩種基本的方式：

1. 一種是范圍查詢，范圍查詢時給定查詢點和查詢距離閾值，從數據集中查找所有與查詢點距離小于閾值的數據
2. 另一種是K近鄰查詢，就是給定查詢點及正整數K，從數據集中找到距離查詢點最近的K個數據，當K=1時，它就是最近鄰查詢。

    同樣，針對特征點匹配也有兩種方法：

• 最容易的辦法就是線性掃描，也就是我們常說的窮舉搜索，依次計算樣本集E中每個樣本到輸入實例點的距離，然后抽取出計算出來的最小距離的點即為最近鄰點。此種辦法簡單直白，但當樣本集或訓練集很大時，它的缺點就立馬暴露出來了，舉個例子，在物體識別的問題中，可能有數千個甚至數萬個SIFT特征點，而去一一計算這成千上萬的特征點與輸入實例點的距離，明顯是不足取的。
• 另外一種，就是構建數據索引，因為實際數據一般都會呈現簇狀的聚類形態，因此我們想到建立數據索引，然后再進行快速匹配。索引樹是一種樹結構索引方法，其基本思想是對搜索空間進行層次劃分。根據劃分的空間是否有混疊可以分為Clipping和Overlapping兩種。前者劃分空間沒有重疊，其代表就是k-d樹；后者劃分空間相互有交疊，其代表為R樹。

 1975年，來自斯坦福大學的Jon Louis Bentley在ACM雜志上發表的一篇論文：Multidimensional Binary Search Trees Used for Associative Searching 中正式提出和闡述的了如下圖形式的把空間劃分為多個部分的k-d樹。

2.1、什么是KD樹

    Kd-樹是K-dimension tree的縮寫，是對數據點在k維空間（如二維(x，y)，三維(x，y，z)，k維(x1，y，z..)）中劃分的一種數據結構，主要應用于多維空間關鍵數據的搜索（如：范圍搜索和最近鄰搜索）。本質上說，Kd-樹就是一種平衡二叉樹。

    首先必須搞清楚的是，k-d樹是一種空間劃分樹，說白了，就是把整個空間劃分為特定的幾個部分，然后在特定空間的部分內進行相關搜索操作。想像一個三維(多維有點為難你的想象力了)空間，kd樹按照一定的劃分規則把這個三維空間劃分了多個空間，如下圖所示：