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

Question

我有两个二维 np.arrays让我们调用他们 A和 B ，两者都有形状。对于二维数组中的每个向量 A我需要在矩阵 B 中找到向量，具有最小余弦距离。为此，我只有一个双 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])

在上面的代码中，循环之一隐藏在理解之后。一切正常，但双 for 循环使它变得太慢(我试图用双重理解重写它，这使事情变得更快，但仍然很慢)。

我相信有一个 numpy 函数可以更快地实现以下目标(使用一些线性代数)。

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

Answer 1

来自 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