计算numpy数组之间的距离

Question

我有两个数组，第一个 np.array 是来自的点，第二个 np.array 是我需要计算的所有距离。

例子：

 import numpy as np
 from_array = np.array([(0,1), (1,1), ..., (x,y)])
 to_array = np.array([(5,1), (3,1), ..., (x,y)])

我需要做的是取第一个条目from_array并计算from_array[0]到to_array中所有点之间的所有距离，然后保持最大距离。

所以我可以为此蛮力：

 def get_distances(from_array, to_array):
     results = []
     distances = []
     for pt in from_array:
        for to in to_array:
            results.append(calc_dist(pt, to))
        distances.append(results)
     return distances

但这很慢，我正在寻找一种优化的计算方式，因为我可以有数千个点。

最终目标是计算 Hausdorff 距离。

fhd = np.mean(np.min(SomeDistanceArray,axis=0))
rhd = np.mean(np.min(SomeDistanceArray,axis=1))
print (max(fhd, rhd))

我想用numpy的这个任务只。我的距离可以是欧氏距离或平方欧氏距离。

所以我正在寻找帮助是计算两个 np.arrays 的欧几里德距离方法的优化方法。应该注意的是，数组 1 的行数可能比数组 2 多。这意味着二维数组的长度 (x,y) 可以将 10 行与 30 行进行比较。

Answer 1

这是一种基于 NumPy 的方法np.einsum-

subs = from_array[:,None] - to_array
sq_eucliean_dist = np.einsum('ijk,ijk->ij',subs,subs)
eucliean_dist = np.sqrt(sq_eucliean_dist)

注意：如果你稍后计算np.mean(np.min(SomeDistanceArray,axis=0))，你可以跳过计算eucliean_dist并直接使用sq_eucliean_distas SomeDistanceArray，因为计算平方根会非常昂贵。

有什么作用np.einsum('ijk,ijk->ij',subs,subs)？它在同一个数组之间执行元素乘法subs，即基本上平方，然后沿最后一个轴进行总和减少，从而在该减少过程中失去它。

那么，为什么不明确地进行平方和求和呢？嗯，好处np.einsum是它可以一步完成平方和求和，为我们提供了显着的性能效率。

因此，最后如果from_array是(N x 2)数组并且to_array是(M x 2)数组，则来自的输出np.einsum将是平方欧几里得距离作为形状为 的二维数组(N x M)。有关字符串符号本身的更多信息将涉及更长的讨论，其中一些可以在this post之前发布的官方文档链接中找到。