我有两个2D np.arrays
,我们称它们为A
和B
,它们都具有形状。对于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):计算一维数组之间的余弦距离。u
和v
之间的余弦距离定义为
其中u⋅v
是u
和v
的点积。
使用上述公式,我们将有一个使用`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