如何遍历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个邻居？

回答

相关问题