计算 (x,y,z) 点列表中最近邻点的（欧氏）距离的最有效方法是什么？

Question

计算数组中每个点的最近邻居的（欧氏）距离的最有效方法是什么？

我有一个包含 100k (X,Y,Z) 个点的列表，我想计算一个最近邻距离列表。距离的索引将对应于点的索引。

我研究过 PYOD 和 sklearn 邻居，但那些似乎需要 "teaching"。我认为我的问题比这更简单。对于每个点：找到最近的邻居，计算距离。

示例数据：

points = [
     (0             0   1322.1695
      0.006711111   0   1322.1696
      0.026844444   0   1322.1697
      0.0604        0   1322.1649
      0.107377778   0   1322.1651
      0.167777778   0   1322.1634
      0.2416        0   1322.1629
      0.328844444   0   1322.1631
      0.429511111   0   1322.1627...)]

计算 k = 1 最近邻距离

结果格式：

results = [nearest neighbor distance]

示例结果：

results = [
0.005939372
0.005939372
0.017815632
0.030118587
0.041569616
0.053475883
0.065324964
0.077200014
0.089077602)
]

更新：

我已经实施了建议的两种方法。

使用scipy.spatial.cdist计算全距离矩阵
使用半径 R 内最近的 X 个邻居来查找每个点的邻居距离子集，return 最小的。

结果是方法 2 比方法 1 快，但实施起来要花更多的精力（有道理）。

似乎方法 1 的限制因素是运行完整计算所需的内存，尤其是当我的数据集接近 10^5 (x, y, z) 点时。对于我的 23k 点数据集，捕获最小距离需要大约 100 秒。

对于方法 2，速度缩放为 n_radius^2。也就是说，"neighbor radius squared"，这实际上意味着该算法与包含的邻居数量成线性关系。使用 ~ 5 的半径（给定的应用程序绰绰有余），对于 23k 点的集合，需要 5 秒才能提供与 point_list 本身顺序相同的分钟列表。 "exact solution"和方法2的差异矩阵基本为零

感谢大家的帮助！

Answer 1

这个怎么样？

from scipy.spatial import distance

A = (0.003467119 ,0.01422762 ,0.0101960126)
B = (0.007279433  ,0.01651597  ,0.0045558849)
C = (0.005392258  ,0.02149997  ,0.0177409387)
D = (0.017898802  ,0.02790659  ,0.0006487222)
E = (0.013564214  ,0.01835688  ,0.0008102952)
F = (0.013375397  ,0.02210725 ,0.0286032185)

points = [A, B, C, D, E, F]
results = []
for point in points:
    distances = [{'point':point, 'neighbor':p, 'd':distance.euclidean(point, p)} for p in points if p != point]
    results.append(min(distances, key=lambda k:k['d']))

结果将是一个对象列表，如下所示：

results = [
    {'point':(x1, y1, z1), 'neighbor':(x2, y2, z2), 'd':"distance from point to neighbor"},
...]

其中 point 是参考点，neighbor 是点的最近邻居。

Answer 2

您可用的最快选项可能是 scipy.spatial.distance.cdist，它会找到输入中所有点之间的成对距离。虽然查找所有这些距离可能不是查找最近邻居的最快算法，但 cdist 是在 C 中实现的，因此它可能运行比您在 Python 中尝试的任何方法都快。

import scipy as sp
import scipy.spatial
from scipy.spatial.distance import cdist

points = sp.array(...)
distances = sp.spatial.distance.cdist(points)

# An element is not its own nearest neighbor
sp.fill_diagonal(distances, sp.inf)

# Find the index of each element's nearest neighbor
mins = distances.argmin(0)

# Extract the nearest neighbors from the data by row indexing
nearest_neighbors = points[mins, :]

#  Put the arrays in the specified shape
results = np.stack((points, nearest_neighbors), 1)

理论上你可以使这个运行更快（主要是通过将所有步骤组合到一个算法中），但除非你用 C 编写，否则你将无法与 SciPy/NumPy.

(cdist 运行s in Θ(n²) 时间（如果每个点的大小固定），每隔一部分O(n) 时间的算法，所以即使你确实尝试优化 Python 中的代码，你也不会注意到少量数据的变化，并且改进会被 cdist 获取更多数据。）

Answer 3

类似于 Caleb 的回答，但如果距离大于之前的某个最小距离（抱歉 - 无代码），您可以停止迭代循环。

我曾经为视频游戏编程。计算两点之间的实际距离会花费太多CPU。我们所做的是将 "screen" 划分为更大的笛卡尔正方形，如果 Delta-X 或 Delta-Y 为 "too far away"，则避免实际距离计算 - 这只是减法，所以也许类似的东西可以限定需要实际的欧几里得距离度量计算（根据需要扩展到 n 维）？

编辑 - 扩展 "too far away" 候选对选择评论。为简洁起见，我将假设一个二维景观。取兴趣点 (X0,Y0) 和 "draw" 围绕该点的 nxn 正方形，原点为 (X0,Y0)。

遍历初始点列表并形成该方块内的候选点列表。这样做时，如果 DeltaX [ABS(Xi-X0)] 在正方形之外，则无需计算 DeltaY。

如果没有候选点，将方块变大并迭代

如果正好有一个候选点，并且在正方形内接圆的半径范围内，那就是你的最小值。

如果有"too many"个候选点，把方块变小，但是你只需要重新检查这个迭代的候选列表，而不是所有的点。

如果没有 "too many" 个候选者，则计算该列表的距离。这样做时，首先为第一个候选计算 DeltaX^2 + DeltaY^2。如果对于后续候选者，DetlaX^2 大于目前的最小值，则无需计算 DeltaY^2。

如果该计算的最小值在正方形内切圆的半径范围内，则该最小值就是最小值。

如果不是，您需要返回到之前的候选列表，该列表包括圆内具有该最小半径的点。例如，如果您以 2x2 正方形中的一个候选项结束，而该候选项恰好位于顶点 X=1、Y=1 上，则 distance/radius 将为 SQRT(2)。因此，返回到先前的候选列表，该列表的平方大于或等于 2xSQRT(2)。

如果有必要，生成一个新的候选列表，该列表仅包含 +/- SQRT(2) 方块内的点。如上所述计算那些候选点的距离 - 忽略任何超过目前计算的最小值的距离。

在只有一个候选者之前，无需计算 Delta^2 之和的平方根。

如何调整初始正方形的大小，或者它是否应该是矩形，以及如何增加或减少 square/rectangle 的大小可能会受到数据分布的应用知识的影响。

如果您使用的语言支持，我会考虑其中的一些递归算法。

计算 (x,y,z) 点列表中最近邻点的（欧氏）距离的最有效方法是什么？

What is the Most Efficient Way to Compute the (euclidean) Distance of the Nearest Neighbor in a List of (x,y,z) points?

python

nearest-neighbor

knn

euclidean-distance