最近邻搜索问题有很多工作，所以我想知道我是否想做固定半径范围搜索，我可以利用这些算法进行最近邻搜索吗？
也许我可以一遍又一遍地进行 kth-nearest-neighbor 搜索，直到找到超出半径范围的点，但我想这可能会造成很多浪费。
问问题
2400 次
4 回答
4
不仅“最近邻搜索问题有很多工作”，而且还有很多问题要针对您的问题提出。最重要的是维度的数量。
如果您不确定为什么维度很重要，请务必检查我的答案。
高维空间
假设您的点位于高维空间中，您应该选择Locality-Sensitive Hashing (LSH)。该算法的一个很好的实现是E²LSH。他们还提供幻灯片，如果您想自己实现或更好地了解会发生什么。请注意，E²LSH 解决了 R 近邻问题的随机版本，他们称之为 (R, 1 − δ)-近邻问题，其中 δ 与近似值有关，正如他们在手册中提到的那样。
你也可以在这里查看我关于 LSH 的回答。我在 C++ 中使用过它，我强烈推荐它用于您想要执行的固定半径搜索！
低维空间
使用 CGAL 的空间搜索。我在 C++ 中多次使用它来处理这种情况。同样，如果您想自己实现，您可以在他们拥有的不错的文档中找到大量信息并进行相关的 google 查询。
顺便说一句，答案很好，所以你得到了我的 +1。:)
于 2015-04-23T14:59:29.257 回答
2
如果您只有一个查询，那么这个问题是固定的 O(n)，其中 n 是无论如何的点数。
如果您有多个查询，那么这个问题是很好探索的问题，但是它的解决方案比最近邻搜索更复杂。参考这篇文章：http ://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.95.3191&rep=rep1&type=pdf
于 2015-04-23T09:31:12.660 回答
2
作为维度d的数量和r半径，我知道您至少可以使用两种不同的方法：
使用空间哈希：
s想象问题空间被一个大小为的网格划分为超立方体s = r / sqrt(d)。
有趣的s = r / sqrt(d)是，这种大小的超立方体内的任何两点都保证距离等于或小于r。
您可以计算网格划分，以便每个超立方体都可以通过由其中一个角的索引形成的元组来识别。这些索引元组可以用作散列结构（空间散列）的键。
现在，这是困难的部分，您必须注意，对于网格的任何超立方体，A都有一组相邻超立方体N = (N1, N2, ...)，其到给定超立方体的最小距离等于或小于给定半径，在几何上它们看起来像一个超球体。您可以将集合的元素表示为N相对于 的网格索引的增量A。请注意，这些索引增量仅取决于d。
例如，在二维情况下，您具有以下几何结构：
NNN index deltas: (-1, 2) ( 0, 2) ( 1, 2)
NNNNN (-2, 1) (-1, 1) ( 0, 1) ( 1, 1) ( 2, 1)
NNANN (-2, 0) (-1, 0) ( 0, 0) ( 1, 0) ( 2, 0)
NNNNN (-2, -1) (-1, -1) ( 0, -1) ( 1, -1) ( 2, -1)
NNN (-1, -2) ( 0, -2) ( 1, -2)
因此，您已经拥有了对超球面内的点进行有效搜索所需的一切：
使用包含它们的超立方体的索引元组作为键将输入点推入空间散列。
给定一个点
p，搜索的方法是确定它所在的超立方体A，然后使用索引增量集，获取N可能包含比 更接近的点的相邻超立方体集r。从空间散列中检索属于超立方体的点
N，并检查哪些点足够接近p。
可以进行一些额外的优化，例如不检查 A 中的点，因为它们保证都足够接近。可以基于p相对于的位置对 N 进行预过滤A。
请注意，选择s = r / sqrt(d)在具有小超立方体和不太大的集合之间提供了一个很好的折衷N。
使用 kd 树或 quad/octo/...-tree：
每次在树上向下一层时，检查它所代表的空间是否与查询超球面相交。如果是这样，你继续下去，否则你完全从搜索中丢弃它。
于 2015-04-23T11:08:16.073 回答
0
一个简单的解决方案是在 sklearn.neighbors.KDTree 中使用 query_radius 函数：
格式为：
query_radius(X, r, return_distance=False, count_only=False, sort_results=False)
于 2020-05-27T17:11:27.650 回答