KD樹最近鄰搜索如何工作？

Question

我正在查看KD樹木的維基百科頁面。作爲一個例子，我在python中實現了構建kd樹的算法。

但是，使用KD樹進行KNN搜索的算法會切換語言，但並不完全清楚。英文解釋開始有意義，但其中的部分內容（例如，「解開遞歸」來檢查其他葉節點的區域）對我來說並沒有任何意義。

這是如何工作，以及如何使用python中的KD樹進行KNN搜索？這不意味着是一個"send me the code!"類型的問題，我不期望。只是簡單的解釋，請:)

Answer 1

這book introduction，第3頁：

鑑於d維空間中一組的n個點，KD樹構造 遞歸如下。首先，找到點的座標值（最初，i = 1）的中值。也就是說，計算M值，使得至少50％的點的第i個座標大於或等於 到M，而至少50％的點的第i個座標小於或等於 M.存儲x的值，並且集合P被分割成PL和PR，其中PL僅包含其第i個座標 小於或等於M的點，並且| PR | = | PL |±1。這個過程然後在PL和PR上遞歸地重複 ，我用i + 1（或1，如果i = d）替換。 當節點上的一組點的大小爲1時，遞歸停止。

以下段落討論了它在求解最近鄰中的用法。或者，這裏是original 1975 paper by Jon Bentley。

編輯：我要補充一點，SciPy的有kdtree實現：

• scipy.spatial
• another Stack Overflow question

Answer 2

我剛剛花了一些時間令人費解了算法的Wikipedia描述自己，並提出了以下可能有所幫助的Python實現：https://gist.github.com/863301

closest_point的第一階段是一個簡單的深度優先搜索，以找到最匹配的葉節點。

而不是簡單地返回發現備份調用堆棧的最佳節點，第二階段檢查，看是否有可能是「離開」側上的更接近節點：（ASCII藝術圖）

  n  current node 
b   |  best match so far 
|  p |  point we're looking for 
|< >| |  error 
     |< >|  distance to "away" side 
     |< | >| error "sphere" extends to "away" side 
      | x possible better match on the "away" side 

當前節點n沿着一條線分割空間，所以如果點p與最佳匹配b之間的「誤差」大於從點p和線n之間的距離，我們只需要看「離開」側。如果是，那麼我們檢查一下，看看「離開」方面是否有任何點更接近。

因爲我們最好的匹配節點被傳遞到了第二個測試中，所以它不必完全遍歷分支，並且如果它位於錯誤的軌道上，它會很快停下來（只能沿着「near」子節點直到它碰到一片葉子。）

要計算點p和通過節點n分割空間的線之間的距離，我們可以簡單地將點「投影」到軸上，方法是將相應座標複製爲軸都是正交的（水平或垂直）。