如何用Python计算2DPoints的动态时间扭曲距离？

Question

我见过^{}，但它似乎只支持1D-DTW。

我也试过用R:

def getDTW(A, B):
    """ Calculate the distance of A and B by greedy dynamic time warping.
    @param  list A list of points
    @param  list B list of points
    @return float  Minimal distance you have to move points from A to get B

    >>> '%.2f' % greedyMatchingDTW([{'x': 0, 'y': 0}, {'x': 1, 'y': 1}], \
                          [{'x': 0, 'y': 0}, {'x': 0, 'y': 5}])
    '4.12'
    >>> '%.2f' % greedyMatchingDTW([{'x': 0, 'y': 0}, {'x':0, 'y': 10}, \
                                    {'x': 1, 'y': 22}, {'x': 2, 'y': 2}], \
                          [{'x': 0, 'y': 0}, {'x': 0, 'y': 5}])
    '30.63'
    >>> '%.2f' % greedyMatchingDTW( [{'x': 0, 'y': 0}, {'x': 0, 'y': 5}], \
                                    [{'x': 0, 'y': 0}, {'x':0, 'y': 10}, \
                                    {'x': 1, 'y': 22}, {'x': 2, 'y': 2}])
    '30.63'
    """
    global logging
    import numpy as np

    import rpy2.robjects.numpy2ri
    from rpy2.robjects.packages import importr
    rpy2.robjects.numpy2ri.activate()
    # Set up our R namespaces
    R = rpy2.robjects.r
    DTW = importr('dtw')
    An, Bn = [], []
    for p in A:
        An.append([p['x'], p['y']])
    for p in B:
        Bn.append([p['x'], p['y']])
    alignment = R.dtw(np.array(An), np.array(Bn), keep=True)
    dist = alignment.rx('distance')[0][0]
    return dist

# I would expect 0 + sqrt(1**2 + (-4)**1) = sqrt(17) = 4.123105625617661
print(getDTW([{'x': 0, 'y': 0}, {'x': 1, 'y': 1}],
              [{'x': 0, 'y': 0}, {'x': 0, 'y': 5}]))
# prints 5.53731918799 - why?

但正如我在底部指出的，R并没有给出预期的解。

那么：如何计算Python中两个2D点列表之间的DTW？

Answer 1

DTW python库的比较及使用方法

from cdtw import pydtw
from dtaidistance import dtw
from fastdtw import fastdtw
from scipy.spatial.distance import euclidean
s1=np.array([1,2,3,4],dtype=np.double)
s2=np.array([4,3,2,1],dtype=np.double)

%timeit dtw.distance_fast(s1, s2)
4.1 µs ± 28.6 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each)
%timeit d2 = pydtw.dtw(s1,s2,pydtw.Settings(step = 'p0sym', window = 'palival', param = 2.0, norm = False, compute_path = True)).get_dist()
45.6 µs ± 3.39 µs per loop (mean ± std. dev. of 7 runs, 10000 loops each)
%timeit d3,_=fastdtw(s1, s2, dist=euclidean)
901 µs ± 9.95 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)

dtaidistance是目前最快的。在

以下是dtaidistance git：

https://github.com/wannesm/dtaidistance

要安装，只需：

^{pr2}$

Answer 2

你的期望似乎没有考虑到阶梯模式。如果在R中运行以下命令

library(dtw)
x <- cbind(c(0,1), c(0,1))
y <- cbind(c(0,0), c(0,5))
dtw(x, y, step.pattern=symmetric1)$distance
# [1] 4.123106

你得到了你期望的结果。默认的步骤模式是symetric2

^{pr2}$

所以我很确定R计算的值是正确的，只是你的期望值可能与那个函数的默认值不一致。在

对于第二个示例，symmetric2似乎符合您的期望

x <- cbind(c(0,0,1,2),c(0,10,22,2))
y <- cbind(c(0,0), c(0,5))
dtw(x, y, step.pattern=symmetric2)$distance
# [1] 30.63494

我没能达到你的第三个期望。我建议您阅读package documentation了解更多细节。在