algorithm - 两组高维点 : Find the nearest neighbour in the other set

Question

我有 2 个集合:A 和 B。两个集合包含相同数量的高维点。如何为集合 B 中的每个点找到集合 A 中的最近邻居？

我考虑过使用 Voronoi 图，但似乎(根据维基百科)它不适合大于 2 的维度。

有人可以向我推荐一种方法吗？

Answer 1

法兰

如果您的数据确实位于高维空间中，那么您可以使用 FLANN .

它实际上构建了许多旋转的 kd 树并查询(一点点)每一棵树，以保持找到的最佳结果。它还会轮换数据集以避免不良情况。

在出版物部分，您可以阅读有关其工作原理的更多信息。

在获取 FLANN 部分，您还可以阅读手册。

但是，由于您希望在高维空间中执行最近邻搜索 (NNS)，您需要接受时间和准确性之间的权衡(时间越长，准确性越高)。这就是 FLANN 执行近似 NNS 的原因(查看 this 答案了解更多信息)。

---

左旋甲状腺激素

作为替代方案，我建议使用 LSH 算法。这是 E²LSH ，它实际上实现了 LSH 算法。手册可以找到here .

该算法背后的想法是，我们希望将彼此靠近的点(以高概率)放置在同一个桶中。而LSH致力于解决R近邻问题。

R-near neighbor数据结构，作者大概的意思是给定一个查询点q，我们可以回答这个问题:“数据集的哪些点位于q的半径R内？”。

但是，手册解释了如何使用 LSH 执行 NN 搜索。

---

请注意，此类问题不适用于本网站。我回答你是因为你是新用户。下次一定不要忘记这一点。 :)