加速距离计算，滑动window

Question

我有两个时间序列 A 和 B。A 的长度为 m，B 的长度为 n。 m << n。两者都有维度 d.

我通过在 B 上滑动 A 来计算 A 和 B 中所有子序列之间的距离。在 python 中，代码如下所示。

def sliding_dist(A,B)
    n = len(B)
    dist = np.zeros(n)
    for i in range(n-m):
        subrange = B[i:i+m,:]
        distance = np.linalg.norm(A-subrange)
        dist[i] = distance
    return dist

现在这段代码执行起来要花很多时间，而且我有很多计算要做。我需要加快计算速度。我的猜测是我可以通过使用卷积和频域乘法 (FFT) 来做到这一点。但是，我一直无法实现。

有什么想法吗？ :) 谢谢

Answer 1

norm(A - subrange)本身不是卷积，但可以表示为：

sqrt(dot(A, A) + dot(subrange, subrange) - 2 * dot(A, subrange))

如何快速计算每一项：

dot(A, A) - 这只是一个常数。
dot(subrange, subrange) - 这可以使用递归方法在 O(1)（每个位置）中计算。
dot(A, subrange) - 此是在此上下文中的卷积。所以这可以通过 convolution theorem.¹

但是请注意，如果子范围大小仅为 10，则您不太可能看到性能提升。

_{1.又名 fast convolution.}

Answer 2

矩阵运算的实现，就像我在评论中提到的那样。想法是逐步评估规范。在你的例子中，我的值是：

d[i] = sqrt((A[0] - B[i])^2 + (A[1] - B[+1])^2 + ... + (A[m-1] - B[i+m-1])^2)

前三行计算平方和，最后一行做sqrt()。

加速约为 60 倍。

import numpy
import time

def sliding_dist(A, B):
    m = len(A)
    n = len(B)
    dist = numpy.zeros(n-m)
    for i in range(n-m):
        subrange = B[i:i+m]
        distance = numpy.linalg.norm(A-subrange)
        dist[i] = distance
    return dist

def sd_2(A, B):
    m = len(A)
    dist = numpy.square(A[0] - B[:-m])
    for i in range(1, m):
        dist += numpy.square(A[i] - B[i:-m+i])
    return numpy.sqrt(dist, out=dist)

A = numpy.random.rand(10)
B = numpy.random.rand(500)
x = 1000
t = time.time()
for _ in range(x):
    d1 = sliding_dist(A, B)
t1 = time.time()
for _ in range(x):
    d2 = sd_2(A, B)
t2 = time.time()

print numpy.allclose(d1, d2)
print 'Orig %0.3f ms, second approach %0.3f ms' % ((t1 - t) * 1000., (t2 - t1) * 1000.)
print 'Speedup ', (t1 - t) / (t2 - t1)

更新

这是您在矩阵运算中需要的 're-implementation' 范数。如果您想要 numpy 提供的其他规范，则它不灵活。不同的方法是可能的，创建 B 滑动 windows 的矩阵并对整个数组进行规范，因为 norm() 接收参数轴。这是该方法的实现，但加速约为 40 倍，比以前慢。

def sd_3(A, B):
    m = len(A)
    n = len(B)
    bb = numpy.empty((len(B) - m, m))
    for i in range(m):
        bb[:, i] = B[i:-m+i]
    return numpy.linalg.norm(A - bb, axis=1)

加速距离计算，滑动window

Speed up distance calculations, sliding window

python

algorithm

fft

sliding-window