CODEWITHSUNDEEP
pythonrartificial-intelligence
Martin Thoma
Martin Thoma

Reputation: 136595

How can I calculate the Dynamic Time Warping distance of 2D-Points with Python?

I have seen mlpy.dtw_std(x, y, dist_only=True) but that seems to support only 1D-DTW.

I've also tried to use 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?

But as I denoted at the bottom, R does not give back the expected solution.

So: How can I calculate the DTW between two lists of 2D points in Python?

Upvotes: 0

Views: 3894

Answers (2)

Felipe Mello
Felipe Mello

Reputation: 395

Comparison between DTW python libs and how to use them

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 is by far the fastest.

Here is dtaidistance git:

https://github.com/wannesm/dtaidistance

To install, just:

pip install dtaidistance

Upvotes: 1

MrFlick
MrFlick

Reputation: 206401

Your expectation does not seem to take into consideration the step pattern. If you run the following command in 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

You get the result you expect. The default step pattern is symetric2

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

So i'm pretty sure R is calculating the correct values, it's just that your expectations may have not been inline with the defaults for that particular function.

For your second example, symmetric2 seems to match your expectation

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

I was not able to match your third expectation. I suggest you read the package documentation for more details.

Upvotes: 1

Related Questions