如何遍歷KDTree找到最近的k個鄰居？

-1

這個問題涉及KNN搜索KDTrees的實現。遍歷KDTree以找到單個最佳匹配（最近鄰居）很簡單，類似於修改後的二進制搜索。如何遍歷KDTree找到最近的k個鄰居？

遍歷如何修改爲徹底和有效地找到k-最佳匹配（KNN）？

編輯澄清：在找到輸入查詢I的最近節點M之後，遍歷算法如何繼續找到與查詢最接近的其餘K-1匹配？是否存在遍歷模式，以保證按照最佳匹配查詢的順序訪問節點？

2016-01-09 user2647513

的可能的複製[如何使用KDTrees實現最近鄰搜索？]（http://stackoverflow.com/questions/4093392/how-to-implement-nearest-neighbor -search-using-kdtrees） –

這不是[link]的副本（http://stackoverflow.com/questions/4093392/how-to-implement-nearest-neighbor-search-using-kdtrees）;我明確指出，我理解遍歷找到一個最近的鄰居。該問題詢問如何修改遍歷以徹底查找單個查詢的k個最近鄰居。我懷疑從最初的最佳匹配中可以找到一條有效的路徑，它可以依次找到更遠的鄰居。 – user2647513

只要繼續搜索同樣的方式。 –

目前，我已經決定執行一系列逐漸增大範圍搜索的次優解決方案，直到找到K個節點。

來源

2016-01-11 19:00:05 user2647513

您可以維護大小爲k的最大堆（k是我們想要查找的最近鄰居的數量）。

從根節點開始，並將距離值插入到最大堆節點中。繼續使用維分裂，標準在k-d樹中搜索並不斷更新Max Heap樹。

https://gopalcdas.wordpress.com/2017/05/24/construction-of-k-d-tree-and-using-it-for-nearest-neighbour-search/

〜阿希什

來源

2017-10-20 08:09:12

如何遍歷KDTree找到最近的k個鄰居？

回答

相關問題