我有 2 个集合:A 和 B。两个集合都包含相同数量的高维点。如何为集合 B 中的每个点找到集合 A 中的最近邻居？
我考虑过使用 Voronoi 图，但似乎(根据维基百科)它不适合高于 2 的维度。
有人可以给我建议一个方法吗？
最佳答案
弗兰恩
如果您的数据确实位于高维空间中，那么您可以使用 FLANN .
它实际上构建了许多旋转的 kd 树并查询(一点)每棵树，保留找到的最佳结果。它还会轮换数据集以避免出现令人讨厌的情况。
在出版物部分，您可以阅读有关其工作原理的更多信息。
在获取 FLANN 部分，您还可以阅读手册。
但是，由于您希望在高维空间中执行最近邻搜索(NNS)，因此您需要接受时间和精度之间的权衡(时间越长，精度越高)。这就是 FLANN 执行近似 NNS 的原因(查看 this 答案以了解更多信息)。
LSH
作为替代方案，我建议使用 LSH 算法。这是E²LSH ，它实际上实现了LSH算法。手册可以找到here .
该算法背后的想法是，我们希望将彼此靠近的点(很有可能)放置在同一个桶中。而LSH致力于解决R近邻问题。
通过R-近邻数据结构，作者可能的意思是给定一个查询点q，我们可以回答这个问题:“数据集中的哪些点位于q的半径R内？”。
但是，手册解释了如何使用 LSH 来执行 NN 搜索。
请注意，此类问题不适用于本网站。我回答你是因为你是新用户。下次一定不要忘记这一点。 :)
关于algorithm - 两组高维点: Find the nearest neighbour in the other set，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/26641937/