logo标签列表

在N维空间中比较两组点的更快方法是什么？

algorithmmathgeometrycomputational-geometryeuclidean-distance
4
List1包含高数量（约7^10）的N维点（N<=10），List2包含相同或更少数量的N维点（N<=10）。
我的任务是：我想要检查List1中每个点最接近（欧几里得距离）List2中的哪个点，然后对其执行一些操作。当List1中的点不超过50个时，我一直在使用简单的嵌套循环方式完成此任务，但是对于7^10个点，这显然需要很长时间。
有什么快速的方法可以做到这一点吗？计算几何中的任何概念可能会有所帮助？
编辑：我已经建立了一个kd-tree，其中包含List2的所有点，现在我正在为List1中的每个点进行最近邻搜索。正如我最初指出的那样，List1有7^10个点，因此尽管我避免了暴力欧几里得距离方法，但是List1中的点数太多了，导致消耗了很多时间。有什么方法可以改善这种情况吗？
你能对你的代码进行性能剖析，看看时间主要花费在哪里吗？也就是说，如果80%的时间在拆分操作上，可以尝试简化拆分代码；如果80%的时间用于距离比较，可以尝试改进比较方法（例如：如果一个轴上的距离大于当前最小总和，则不必检查其他维度），等等。我们来看看哪些地方需要优化。 - mpez0
4个回答
5

一个好的方法是使用类似kd-tree的数据结构进行最近邻搜索。幸运的是，您不必自己实现此数据结构，因为它已经有了。我推荐使用这个库，但也有其他选择：

http://www.cs.umd.edu/~mount/ANN/

由于我的现有代码是用Python编写的，所以我不打算使用这个库。我想使用http://gamera.sourceforge.net/doc/html/kdtree.html。但是，最重要的是使用kd树的概念来实现相同的功能。谢谢！ - user59634
PeterK：抱歉我误按了“接受”。现在你能否看一下编辑后的问题？ - user59634
我认为我们的选项越来越少了。 我认为有两种可能性：首先，在搜索最近邻居时，您可以使用某种逼近方法。提到的ANN库允许这样做，但不知道其他库是否也可以。 第二个选择是以某种方式预处理List1-例如计算某个大小的“聚类”。 通过聚类，我指的是非常相似的点，因此可以选择其中一个作为聚类的代表。 如果您对多个邻居运行NN搜索，则可能能够获得良好的结果（但仍取决于您要做什么）。 - PeterK
哦，还有一件事：你可以采用并行方式，同时进行更多的搜索。当然，这只有在你拥有多核处理器并且系统允许线程时才是合理的。此外，你需要确保kd树在搜索时是线程安全的。 - PeterK
2
不了解两个解决方案中点的分布情况，无法确定哪种算法最有效。但是，对于第一次猜测...

第一个算法不起作用——有两个原因：（1）错误的假设——我假设包围凸壳是不相交的；（2）对问题的错误理解——它不能找到每对点的最短边。

...计算这两组的凸壳：最接近的点必须在通过连接两个重心的直线的两个凸壳上的超平面上。

您可以通过计算中心点来计算凸壳，假设所有点都具有相等的质量和重心，并将列表从距离中心最远的点排序到最少。然后从列表中取出最远的点，将其添加到凸壳中，然后删除所有在迄今为止计算出的凸壳内的点（您需要计算许多10d超三角形才能完成此操作）。重复此操作，直到列表中没有任何未在凸壳上的点。

第二个算法：部分

计算List2的凸壳。 对于List1的每个点，如果该点在凸壳外，则像第一个算法那样找到超平面：最近的点必须在该面上。 如果它在面上，同样。 如果它在内部，则仍然可以通过将线从List1的点向外延伸来找到超平面：最近的点必须在包括List2重心的超球体内：在这里，您需要一个新算法来获取最近的点，也许是kd树方法。

性能

当List2类似均匀分布或正常分布时，这将很好地减少考虑的点数，并且应与kd-tree建议兼容。

但是，还有一些可怕的情况：如果List2仅包含位于环面表面上的点，其几何中心是列表的重心，则计算凸壳将非常昂贵，并且不会在减少考虑的点数方面提供太多帮助。

我的评价

这些几何技术可能是其他发布者的kd-trees方法的有用补充，但是您需要了解一些关于点分布的知识，才能确定是否值得应用它们。

即使问题是要找到整个最接近的点对（事实上他想要L1中每个点的最接近伙伴），最接近的点对也不一定在任何一个壳上。 L1中心附近的某些点可能比L2中心附近的任何壳点更靠近。 - j_random_hacker
@j_random：我已经根据您的评论编辑了帖子，并描述了修订后的算法。 - Charles Stewart
Charles：很抱歉我不太了解计算几何，因此凸包方法可能不是我可以快速使用的。非常感谢你的回答。 - user59634
更新很棒，但是... :) 如果船体的体积不相交，则L1船体上任意一点到最近点必须在L2船体上，但该点可能位于线段上而不是由L2实际点定义的角点处。（恐怕这更容易在图表上展示。）同样还不确定通过质心的线具有你所描述的属性（尽管它可能是一个很好的启发式方法）--你可以通过在边界附近添加许多点来将质心移动到任何位置。（抱歉我这么挑剔... :)) - j_random_hacker
@j_random：“L1的外壳上任何一点到最近点都必须在L2的外壳上某个地方”-我真的说过那个吗！实际上，即使你所说的也不一定是真的：最近点可以刚好在外壳内部。但它必须在该超平面的最小包围球内。第二个属性是正确的，即使L1和L2是平行的环面：在这种情况下，球可能会相当大！ - Charles Stewart
0
kd-tree非常快速。我在这篇论文中使用了这个算法，效果很好 Bentley - K-d trees for semidynamic point sets。
我相信有一些库可以使用，但是有时候了解内部工作原理也挺好的——Bentley解释得很清楚。
基本上，有多种方法可以搜索树：最近的N个邻居、给定半径内的所有邻居、给定半径内的最近N个邻居。有时候你可能想要搜索边界对象。
这个思想是，kd树通过递归地将空间划分成不同的区域。每个节点都沿着一个维度的轴线被分成两个部分。理想情况下，它应该垂直于节点的最长维度进行划分。你应该持续划分空间，直到每个桶里大约有4个点为止。
然后对于每个查询点，在递归访问节点时，你需要检查到特定节点的划分墙的距离。如果距离比搜索半径更近，你同时访问当前节点和它的兄弟节点。如果墙在搜索半径之外，只需搜索当前节点的子节点。

当你到达一个桶（叶节点）时，你会测试其中的点是否在半径范围内。

如果你想要最近的点，你可以从一个非常大的半径开始，并在递归过程中传递指针或引用 - 这样你就可以随着发现接近的点而缩小搜索半径 - 并快速找到最近的点。

实际上，你并不一定需要根据最长的维度来分割，其中一种效果非常好的技术是交替在每个维度上进行分割，总是按照相同的顺序进行。这也许不是最高效的方法，但它是可预测的，这也具有一些优点。 - Matthieu M.
谢谢！我想我会尝试一下。我猜这将加速构建，因为找出最长的维度可能是很昂贵的 - 即使在 Bentley 的论文中进行了优化 - 比如（使用一部分点来测量）。 - Julian Mann
找出哪个维度具有最大的扩展是非常昂贵的。引入一种近似方法（检查点的子集）可以使您获得相当大的加速（当然取决于子集的大小）。根据我的经验，这完全值得。 - PeterK
0
（一年后）在查看了所有2亿个点中的1百万个点后，可以提前退出kd树，在高维度下速度会更快。
结果只是在统计上接近于绝对最近的点，这取决于数据和度量方式；并没有免费的午餐。
（请注意，采样1百万个点，并仅对这1百万个点进行kd树处理，与情况有很大不同，效果更差。）

FLANN 用于128维图像数据，我相信它已经被集成到opencv中。快速而稳定的SciPy cKDTree 的本地修改也有截止值=。

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接