尝试使用 KD 树创建 KNN 搜索。我可以很好地形成 KD 树（或者至少，我相信我可以！）。我的问题是我正在寻找与点列表中每个点最近的 2 个邻居。
那么，有没有一种方法可以使用 KD 树找到一个点的 K 最近邻居，即使该点实际上在树中，还是我需要为每个点构建一个单独的 KD 树，而忽略我希望的点寻找？
我的实现语言是 C++，但我更多的是寻找算法或一般帮助，谢谢！
谢谢，斯蒂芬
问问题
940 次
3 回答
3
如果您想要树中的K个 确切最近邻居，只需查询树中的K+1个邻居（显然，因为第一个最近邻居将是您的查询）。
于 2010-03-26T17:57:03.840 回答
1
这不是一个真正的答案，但我不适合我想要粘贴到评论中的内容。无论如何，这是来自维基百科的相关文本：
该算法可以通过简单的修改以多种方式扩展。它可以通过保持 k 个当前最佳值而不是仅仅一个来为一个点提供 k 个最近邻。只有当它们的点不能比任何 k 当前最佳值更接近时，分支才会被消除。
它也可以转换为近似算法以更快地运行。例如，近似最近邻搜索可以通过简单地设置树中要检查的点数的上限来实现，或者通过基于实时时钟中断搜索过程（这在硬件实现中可能更合适）来实现。树中点的最近邻居可以通过不更新结果为零距离的节点的细化来实现，这具有丢弃不唯一但与原始搜索点位于同一位置的点的缺点.
近似最近邻在机器人等实时应用中很有用，因为通过不穷举搜索最佳点可以显着提高速度。它的一个实现是 Best Bin First。
于 2010-03-26T17:04:42.193 回答
0
我建议查看 ANN 以了解实施细节http://www.cs.umd.edu/~mount/ANN/
它专为近似最近邻搜索而设计，但也可以进行精确最近邻搜索。它也是我发现的一些最清晰和最好的编写代码，即使你想要自己的实现，也应该给你一些洞察力。
于 2010-06-24T08:35:29.887 回答