我有 2 组：A 和 B。两组都包含相同数量的高维点。如何为 Set B 中的每个点找到 Set A 中的最近邻居？
我考虑过使用 Voronoi 图，但似乎（根据维基百科）它不适合高于 2 的尺寸。
有人可以向我建议一种方法吗？
问问题
863 次
1 回答
3
法兰
如果您的数据确实位于高维空间中，那么您可以使用FLANN。
它实际上构建了许多旋转的 kd 树并查询（一点）每棵树，以保持找到的最佳结果。它还轮换数据集以避免令人讨厌的情况。
在出版物部分，您可以阅读有关其工作原理的更多信息。
在获取 FLANN 部分，您还可以阅读手册。
但是，由于您希望在高维空间中执行最近邻搜索（NNS），您需要接受时间和准确性之间的权衡（更多的时间带来更高的准确性）。这就是 FLANN 执行近似 NNS 的原因（更多信息请查看此答案）。
LSH
作为替代方案，我建议使用 LSH 算法。这是E²LSH，它实际上实现了 LSH 算法。该手册可以在这里找到。
该算法背后的想法是，我们希望将彼此靠近的点（以高概率）放置在同一个桶中。然而，LSH 致力于解决 R 最近邻问题。
通过R-近邻数据结构，作者可能的意思是给定一个查询点q，我们可以回答这个问题：“数据集的哪些点位于q的半径R内？”。
但是，该手册解释了如何使用 LSH 执行 NN 搜索。
请注意，此类问题不适用于本网站。我回答你是因为你是新用户。下次确保你不要忘记这一点。:)
于 2014-10-30T22:37:55.233 回答