0

我想快速计算平方欧几里得，如下所述：

在 python 中计算 RBF 内核的最快方法是什么？

注意1：我只对距离感兴趣，而不是RBF 内核。

注意2：这里我忽略numexpr了，只直接使用numpy。

简而言之，我计算：

|| x - y ||^2 = ||x||^2 + ||y||^2 - 2. * (x @ y.T)

~10与此相比，我能够更快地计算距离矩阵scipy.pdist。但是，我观察到数值问题，如果我取平方根来获得欧几里德距离，情况会变得更糟。我的值大约为1E-8 - 1E-7，应该完全为零（即重复点或到自身点的距离）。

问题：

有没有办法或想法来克服这些数值问题（最好在不牺牲太多评估速度的情况下）？或者数字问题是为什么这条路径首先没有被采用（例如 by scipy.pdist）的原因？

例子：

这是一个显示数值问题的小代码示例（不是加速，请查看上面链接的 SO 线程的答案）。

import numpy as np

M = np.random.rand(1000, 10)

M_norm = np.sum(M**2, axis=1)

res = M_norm[:, np.newaxis] + M_norm[np.newaxis, :] - 2. * M @ M.T
unique = np.unique(np.diag(res))  # analytically all diag values are exactly zero 
sqrt_unique = np.sqrt(unique)


print(unique)
print(sqrt_unique)

示例输出：

[-2.66453526e-15 -1.77635684e-15 -8.88178420e-16 -4.44089210e-16
  0.00000000e+00  4.44089210e-16  8.88178420e-16  1.77635684e-15
  3.55271368e-15]
[           nan            nan            nan            nan
 0.00000000e+00 2.10734243e-08 2.98023224e-08 4.21468485e-08
 5.96046448e-08]

正如您所看到的，一些值也是负数（这导致在nan取 sqrt 之后）。当然这些很容易捕捉——但是对于欧几里得情况来说，小的积极因素有很大的错误（例如abs_error=5.96046448e-08）

4

1 回答 1

0

根据我的评论，使用abs可能是清理该算法固有的数值稳定性的最佳选择。当您担心性能时，您可能应该使用变异赋值运算符，因为它们会导致创建的垃圾更少，因此可以更快。此外，当使用许多功能（例如 10k）运行它时，我发现pdist它比这个实现要慢。

综上所述，我们得到：

import numpy as np

def edist0(M):
    "calculate pairwise euclidean distance"
    M_norm = np.sum(M**2, axis=1)
    res = M_norm[:, np.newaxis] + M_norm[np.newaxis, :] - 2. * M @ M.T    
    return np.sqrt(np.abs(res))

def edist1(M):
    "optimised calculation of pairwise euclidean distance"
    M_norm = np.einsum('ij,ij->i', M, M)
    res = M @ M.T
    res *= -2.
    res += M_norm[:, np.newaxis]
    res += M_norm[np.newaxis, :]
    return np.sqrt(np.abs(res, out=res), out=res)

在 IPython 中计时：

from scipy.spatial import distance

M = np.random.rand(1000, 10000)

%timeit distance.squareform(distance.pdist(M))
%timeit edist0(M)
%timeit edist1(M)

我得到：

2.82 s ± 60.1 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)
296 ms ± 6.07 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)
153 ms ± 1.58 ms per loop (mean ± std. dev. of 7 runs, 10 loops each)

并且没有错误/警告sqrt

链接的问题还指出 scikit-learn 具有良好的距离内核良好的实现，欧几里德的pairwise_distances基准为：

from sklearn.metrics import pairwise_distances

%timeit pairwise_distances(M)

170 ms ± 5.51 ms per loop (mean ± std. dev. of 7 runs, 10 loops each)

如果您已经在使用该软件包，这可能会很好用

于 2020-01-19T12:16:16.260 回答