《Machine Learning：Clustering & Retrieval》課程第2章之手算KD-tree

本文來源於Machine Learning: Clustering & Retrieval | Coursera課程中的kdtree一節，做了一些重新組織和翻譯。

數據集：

kd-tree構建過程：

第一步：進行第一次split

從上圖可以看出，X軸的方差更大一些，所以先從X軸進行split。split value取point 1和point 2的平均值，即(0.89+0.04) / 2 = 0.465

分成如下兩個結點：

在每個結點，我們記錄下它的tight coordinate bound，這個是為了在查詢的時候剪枝用的。

這個時候，這棵樹的樣子：

第二步：遞歸進行split

我們先來確定我們用的啟發式方法：

a.選擇哪個軸進行split？方差大的，或者還沒有使用過的軸

b.如何確定split value：(smallest value + biggest value) / 2

c.什麼時候stop？在本例子中選擇node只含有<=2個point的時候

因為第一次是用的x軸split，為了充分利用信息，第二次使用y軸split

現在就樹是這個樣子了：

同樣對node 1進行split：

樹變成這個樣子：

因為node 5的point有3個，所以需要繼續split，因為上次用Y軸split，所以這次用x軸。

最終的樹：

kd-tree查詢過程：

比如我們的query point是紅色點：

從kdtree里可以找到屬於node 6：

它到data point 0的距離是0.256，所以最近鄰居一定出現在以0.256為半徑的圓里。

我們來tranverse back：

但是node7的tight bounding box並不在圓里，所以prune掉。

繼續向上找：

node4隻有一個點，而這個點不在圓里，prune掉。

繼續tranverse：

node0包含兩個結點，node0本身在圓里，所以就想看node2和node3

計算node2和node3到query point的距離：

這個時候data point3到query point的距離最小，而已縮小搜索圓了，搜索圓的半徑減小到0.18439。

這個時候繼續搜索，但是所有結點都搜索完了，所以data point3是最近鄰。

推薦閱讀：