如何用Python计算二维点的动态时间规整距离？

Question

我看到过一个叫做 mlpy.dtw_std(x, y, dist_only=True) 的东西，但它似乎只支持一维的动态时间规整（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中，如何计算两个二维点列表之间的动态时间规整（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的GitHub链接：

https://github.com/wannesm/dtaidistance

安装的方法很简单，只需要：

pip install dtaidistance

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

dtw(x, y, step.pattern=symmetric2)$distance
# [1] 5.537319

所以我很确定R语言计算的值是正确的，只是你的期望可能和这个特定函数的默认设置不一致。

对于你的第二个例子，symetric2似乎符合你的期望。

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

我没有办法让你的第三个期望匹配。我建议你查看一下这个包的文档，了解更多细节。