python - 计算 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

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

最终目标是计算豪斯多夫距离。

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_dist 作为 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 中找到。以及之前发布的官方文档链接。