KD樹的構建_數據分析師

KD樹的構建

    kd樹構建的偽代碼如下圖所示：

    再舉一個簡單直觀的實例來介紹k-d樹構建算法。假設有6個二維數據點{(2,3)，(5,4)，(9,6)，(4,7)，(8,1)，(7,2)}，數據點位于二維空間內，如下圖所示。為了能有效的找到最近鄰，k-d樹采用分而治之的思想，即將整個空間劃分為幾個小部分，首先，粗黑線將空間一分為二，然后在兩個子空間中，細黑直線又將整個空間劃分為四部分，最后虛黑直線將這四部分進一步劃分。

    6個二維數據點{(2,3)，(5,4)，(9,6)，(4,7)，(8,1)，(7,2)}構建kd樹的具體步驟為：

1. 確定：split域=x。具體是：6個數據點在x，y維度上的數據方差分別為39，28.63，所以在x軸上方差更大，故split域值為x；
2. 確定：Node-data = （7,2）。具體是：根據x維上的值將數據排序，6個數據的中值(所謂中值，即中間大小的值)為7，所以Node-data域位數據點（7,2）。這樣，該節點的分割超平面就是通過（7,2）并垂直于：split=x軸的直線x=7；
3. 確定：左子空間和右子空間。具體是：分割超平面x=7將整個空間分為兩部分：x<=7的部分為左子空間，包含3個節點={(2,3),(5,4),(4,7)}；另一部分為右子空間，包含2個節點={(9,6)，(8,1)}；

    與此同時，經過對上面所示的空間劃分之后，我們可以看出，點(7,2)可以為根結點，從根結點出發的兩條紅粗斜線指向的(5,4)和(9,6)則為根結點的左右子結點，而(2,3)，(4,7)則為(5,4)的左右孩子(通過兩條細紅斜線相連)，最后，(8,1)為(9,6)的左孩子(通過細紅斜線相連)。如此，便形成了下面這樣一棵k-d樹：

    k-d樹的數據結構

    針對上表給出的kd樹的數據結構，轉化成具體代碼如下所示(注，本文以下代碼分析基于Rob Hess維護的sift庫)：

    也就是說，如之前所述，kd樹中，kd代表k-dimension，每個節點即為一個k維的點。每個非葉節點可以想象為一個分割超平面，用垂直于坐標軸的超平面將空間分為兩個部分，這樣遞歸的從根節點不停的劃分，直到沒有實例為止。經典的構造k-d tree的規則如下：

1. 隨著樹的深度增加，循環的選取坐標軸，作為分割超平面的法向量。對于3-d tree來說，根節點選取x軸，根節點的孩子選取y軸，根節點的孫子選取z軸，根節點的曾孫子選取x軸，這樣循環下去。
2. 每次均為所有對應實例的中位數的實例作為切分點，切分點作為父節點，左右兩側為劃分的作為左右兩子樹。

    對于n個實例的k維數據來說，建立kd-tree的時間復雜度為O(k*n*logn)。

    以下是構建k-d樹的代碼：

    上面的涉及初始化操作的兩個函數kd_node_init，及expand_kd_node_subtree代碼分別如下所示：

    構建完kd樹之后，如今進行最近鄰搜索呢？從下面的動態gif圖中，你是否能看出些許端倪呢？

    k-d樹算法可以分為兩大部分，除了上部分有關k-d樹本身這種數據結構建立的算法，另一部分是在建立的k-d樹上各種諸如插入，刪除，查找(最鄰近查找)等操作涉及的算法。