scipy 和 numpy 中的快速距离计算

Question

设A,B为((day,observation,dim))数组。对于给定的一天，每个数组都包含相同数量的观察值，一个观察值是一个具有暗维度的点（即暗浮点数）。对于每一天，我想计算当天 A 和 B 中所有观测值之间的空间距离。

例如：

import numpy as np
from scipy.spatial.distance import cdist

A, B = np.random.rand(50,1000,10), np.random.rand(50,1000,10)

output = []
for day in range(50):
    output.append(cdist(A[day],B[day]))

我在哪里使用 scipy.spatial.distance.cdist.

有更快的方法吗？理想情况下，我想为 output 获取一个 ((day,observation,observation)) 数组，其中包含每天 A 和 B 中观测值之间的成对距离，同时以某种方式避免循环几天。

Answer 1

编辑：我是个白痴，忘记了 python 的 map 是懒惰求值的。我的 "faster" 代码实际上没有做任何工作！强制评估消除了性能提升。

我认为您的时间将主要花在 scipy 函数中。我会使用 map 而不是循环，因为我认为它更简洁一些，但我认为没有任何神奇的方法可以在这里获得巨大的性能提升。也许使用 cython 或使用 numba 编译代码会有所帮助。

Answer 2

一种方法（尽管需要大量内存）是巧妙地使用数组广播：

output = np.sqrt( np.sum( (A[:,:,np.newaxis,:] - B[:,np.newaxis,:,:])**2, axis=-1) )

编辑

但经过一些测试，似乎 scikit-learn 的 euclidean_distances 可能是大型数组的最佳选择。（请注意，我已将您的循环重写为列表理解。）

这是每天 100 个数据点：

# your own code using cdist
from scipy.spatial.distance import cdist
%timeit dists1 = np.asarray([cdist(x,y) for x, y in zip(A, B)])

100 loops, best of 3: 8.81 ms per loop

# pure numpy with broadcasting
%timeit dists2 = np.sqrt( np.sum( (A[:,:,np.newaxis,:] - B[:,np.newaxis,:,:])**2, axis=-1) )

10 loops, best of 3: 46.9 ms per loop

# scikit-learn's algorithm
from sklearn.metrics.pairwise import euclidean_distances
%timeit dists3 = np.asarray([euclidean_distances(x,y) for x, y in zip(A, B)])
100 loops, best of 3: 12.6 ms per loop

这是每天 2000 个数据点：

In [5]: %timeit dists1 = np.asarray([cdist(x,y) for x, y in zip(A, B)])
1 loops, best of 3: 3.07 s per loop

In [7]: %timeit dists3 = np.asarray([euclidean_distances(x,y) for x, y in zip(A, B)])

1 loops, best of 3: 2.94 s per loop

scipy 和 numpy 中的快速距离计算

Fast distance calculation in scipy and numpy

python

performance

numpy

scipy

multidimensional-array