我有两个2D np.arrays,我们称它们为AB,它们都具有形状。对于2D数组A中的每个向量,我需要在矩阵B中找到具有最小余弦距离的向量。为此,我只有一个double for循环,我试图在其中寻找最小值。所以基本上我会执行以下操作:

from scipy.spatial.distance import cosine
l, res = A.shape[0], []
for i in xrange(l):
    minimum = min((cosine(A[i], B[j]), j) for j in xrange(l))
    res.append(minimum[1])


在上面的代码中,循环之一隐藏在理解之后。一切工作正常,但是double for循环使它变得太慢(我试图用double理解来重写它,这使事情有点快,但仍然很慢)。

我相信有一个numpy函数可以更快地完成以下操作(使用一些线性代数)。

那么有没有办法更快地实现我想要的?

最佳答案

cosine docs中,我们有以下信息-

scipy.spatial.distance.cosine(u,v):计算一维数组之间的余弦距离。

uv之间的余弦距离定义为

numpy - 查找两个矩阵之间的最小余弦距离-LMLPHP

其中u⋅vuv的点积。

使用上述公式,我们将有一个使用`NumPy's broadcasting capability的矢量化解决方案,如下所示:

# Get the dot products, L2 norms and thus cosine distances
dots = np.dot(A,B.T)
l2norms = np.sqrt(((A**2).sum(1)[:,None])*((B**2).sum(1)))
cosine_dists = 1 - (dots/l2norms)

# Get min values (if needed) and corresponding indices along the rows for res.
# Take care of zero L2 norm values, by using nanmin and nanargmin
minval = np.nanmin(cosine_dists,axis=1)
cosine_dists[np.isnan(cosine_dists).all(1),0] = 0
res = np.nanargmin(cosine_dists,axis=1)


运行时测试-

In [81]: def org_app(A,B):
    ...:    l, res, minval = A.shape[0], [], []
    ...:    for i in xrange(l):
    ...:        minimum = min((cosine(A[i], B[j]), j) for j in xrange(l))
    ...:        res.append(minimum[1])
    ...:        minval.append(minimum[0])
    ...:    return res, minval
    ...:
    ...: def vectorized(A,B):
    ...:     dots = np.dot(A,B.T)
    ...:     l2norms = np.sqrt(((A**2).sum(1)[:,None])*((B**2).sum(1)))
    ...:     cosine_dists = 1 - (dots/l2norms)
    ...:     minval = np.nanmin(cosine_dists,axis=1)
    ...:     cosine_dists[np.isnan(cosine_dists).all(1),0] = 0
    ...:     res = np.nanargmin(cosine_dists,axis=1)
    ...:     return res, minval
    ...:

In [82]: A = np.random.rand(400,500)
    ...: B = np.random.rand(400,500)
    ...:

In [83]: %timeit org_app(A,B)
1 loops, best of 3: 10.8 s per loop

In [84]: %timeit vectorized(A,B)
10 loops, best of 3: 145 ms per loop


验证结果-

In [86]: x1, y1 = org_app(A, B)
    ...: x2, y2 = vectorized(A, B)
    ...:

In [87]: np.allclose(np.asarray(x1),x2)
Out[87]: True

In [88]: np.allclose(np.asarray(y1)[~np.isnan(np.asarray(y1))],y2[~np.isnan(y2)])
Out[88]: True

09-07 22:20