是否可以找到KIN樹中的* IN *節點的KNN？

嘗試使用KD樹創建KNN搜索。我可以組建KD樹（或者至少我相信我可以！）。我的問題是，我正在尋找最近的2個鄰居到點列表中的每個點。是否可以找到KIN樹中的* IN *節點的KNN？

那麼，有沒有一種方法可以找到使用KD樹的點的K個最近鄰點，即使這個點實際上是在樹中，還是我需要爲每個點構造一個單獨的KD樹，而忽略了我希望搜索的點？

我的實現語言是C++，但我更期待算法或一般幫助，謝謝！

感謝，斯蒂芬

2010-03-26 Stephen

作爲一個起點，http://en.wikipedia.org/wiki/Kd-tree#Nearest_neighbor_search描述瞭如何執行KNN算法。它看起來基本上是重複NN阿爾格，而跟蹤以前的命中。我知道這是非常普遍的幫助，但我希望它能指出你的方向。 – 2010-03-26 17:02:37

如果你想ķ確切您的樹中近鄰，只是查詢樹K + 1鄰居（顯然因爲第一近鄰將是你的查詢）。

來源

2010-03-26 17:57:03 Jacob

+1和附註：如果搜索點位於樹中，搜索無關緊要。所以這種方法可以正常工作，你只需要從結果中篩選出搜索點，這應該很容易（因爲它是最接近的）。 – PeterK 2010-06-24 08:37:45

這是不是真的太多的答案，但我不適合我要粘貼到什麼評論。總之，這裏的維基百科中的有關內容：

該算法可以在幾個簡單的修改方式進行擴展。它可以提供k-最近鄰居通過保持k目前 bests而不是一個。分支僅當它們不能具有比當前最好的任何一個更接近的點時才被消除。

它也可以轉換爲近似算法運行得更快。例如，近似最近鄰近搜索可以通過可以實現簡單地設置在點數的上限在樹中檢查，或通過中斷基於實時時鐘（其可以更搜索過程適用於硬件實現）。對於那些樹已經點近鄰可以通過不更新爲給零距離爲結果節點的細化來實現，這具有不唯一丟棄點的缺點，但合作 - 位於原始搜索點。

近似最近的鄰居是有用實時應用，如機器人由於沒有搜索的最佳點獲得詳盡的顯著速度增加。其中一個是，其實現是Best Bin First。

來源

2010-03-26 17:04:42

我建議考慮看看ANN的實施細則http://www.cs.umd.edu/~mount/ANN/

它被設計爲近似最近鄰搜索，但還可以做精確的近鄰查詢。這也是我找到的最清晰，最好的代碼，即使你想自己實現，也應該給你一些洞見。

來源

2010-06-24 08:35:29 Meekohi

是否可以找到KIN樹中的* IN *節點的KNN？

回答

相關問題