• Python port of R's Comprehensive Dynamic Time Warp algorithm package version: 1.1.10
• Python version: Python 3.9.7 (default, Nov 4 2021, 19:19:42)
• Operating System: macOS Monterrey 12.1

Description

Describe what you were trying to get done. I'm trying to correlate two 1-D series with the DTW algorithm and wanted to control the window size used during warping. Applying the sakoechiba window constraint seems to massively slow down the algorithm execution. Is this intended?

My query and reference curves are of length ~12000.

Tell us what happened, what went wrong, and what you expected to happen. I expected using windowing would in fact speed up execution rather than slow it down?

What I Did

start = time()
alignment = dtw(
    query,
    reference,
    dist_method="euclidean",
    window_type="sakoechiba",
    window_args={"window_size": 20},
    keep_internals=True,
)
duration = time() - start
print(f"{duration=}")

output: 194.4200530052185

start = time()
alignment = dtw(
    query,
    reference,
    dist_method="euclidean",
    window_type=None,
    keep_internals=True,
)
duration = time() - start
print(f"{duration=}")

output: 19.95380139350891

• Python port of R's Comprehensive Dynamic Time Warp algorithm package version: 1.1.7
• Python version: 3.8
• Operating System: Ubuntu

Description

import crashing

What I Did

> import dtw

---------------------------------------------------------------------------
ValueError                                Traceback (most recent call last)
<ipython-input-4-516d6c3d3d57> in <module>
----> 1 import dtw

/usr/local/lib/python3.8/dist-packages/dtw/__init__.py in <module>
     15 
     16 # List of things to export on "from dtw import *"
---> 17 from dtw.dtw import *
     18 from dtw.stepPattern import *
     19 from dtw.countPaths import *

/usr/local/lib/python3.8/dist-packages/dtw/dtw.py in <module>
     34 from dtw.stepPattern import *
     35 from dtw._backtrack import _backtrack
---> 36 from dtw._globalCostMatrix import _globalCostMatrix
     37 from dtw.window import *
     38 from dtw.dtwPlot import *

/usr/local/lib/python3.8/dist-packages/dtw/_globalCostMatrix.py in <module>
      1 import numpy
      2 from dtw.window import noWindow
----> 3 from dtw._dtw_utils import _computeCM_wrapper
      4 
      5 

/usr/local/lib/python3.8/dist-packages/dtw/_dtw_utils.pyx in init dtw._dtw_utils()

ValueError: numpy.ndarray size changed, may indicate binary incompatibility. Expected 88 from C header, got 80 from PyObject

Hello, thanks for this excellent package. In the current version, running

import dtw

Leads to the following being placed in standard output

  Importing the dtw module. When using in academic works please cite:
    T. Giorgino. Computing and Visualizing Dynamic Time Warping Alignments in R: The dtw Package.
    J. Stat. Soft., doi:10.18637/jss.v031.i07.

I absolutely agree with the need to prompt users to cite sources, but printing this to standard output is somewhat unconventional compared to other Python projects based on published works. I am currently running a large benchmarking experiment, and I need to manually suppress this print statement every time I import a model that uses dtw internally.

Would you consider printing this using warnings.warn? In my opinion, that would be a bit more consistent with how other repos handle this issue. Warnings and exceptions are also a bit easier to manage than stdout. Thank you!

Could not find a R specific repo so apologies for posting here.

I'm trying to integrate the dtw twoWay plot into a shiny dashboard but unfortunately keep getting API errors/mismatches when using renderPlot to get the output to a window. I assume this is because the dtw plot output is different from base or ggplot outputs and so I was curious if there is any way around this (rather then me trying to reinvent the plotting function into ggplot somehow..)

I noticed that in certain cases, setting open_end=True and/or open_begin=True can lead to not finding a warping function. I found this surprising, as intuitively, I would have expected the removal of one or several constraints (i.e., start and end have to match) to make it easier to find a warping function, not harder.

I've attached two files for an example time series to reproduce the proplem:

>>> import numpy as np
>>> from dtw import *

>>> x = np.loadtxt("x.txt")
>>> y = np.loadtxt("y.txt")

# works fine
>>> _ = dtw(x, y, step_pattern="asymmetricP05")

# doesn't work
>>> _ = dtw(x, y, step_pattern="asymmetricP05", open_end=True)
ValueError: No warping path found compatible with the local constraints

Is this a bug, or am I missing something in my understanding of DTW?

x.txt y.txt

• Python port of R's Comprehensive Dynamic Time Warp algorithm package version: 1.3.1
• Python version: 3.8.13
• Operating System: Win64

Description

Both in R and Python, the implementation of open begin combined with the implementation of the rigid step pattern prevents alignment on the first element of the reference series. As far as I can tell from the literature, this is an unintended consequence. Other step patterns don't have this problem.

I'm primarily an R user, so I'll explain where it comes from using the R code, but because it works the same in Python, this holds there as well.

Adding the initial row of 0 to the distance matrix/cost matrix is done to account for all the other step matrices that look further back (from dtw.R)

if (open.begin) {
        if (is.na(norm) || norm != "N") {
            stop("Open-begin requires step patterns with 'N' normalization (e.g. asymmetric, or R-J types (c)). See papers in citation().")
        }
        lm <- rbind(0, lm)
        np <- n + 1
        precm <- matrix(NA, nrow = np, ncol = m)
        precm[1, ] <- 0
    }

For query <- c(1, 2, 3, 4); ref <- c(1, 2, 3, 4, 5, 6) the lm following from the above looks like this

# >     [,1] [,2] [,3] [,4] [,5] [,6]
# > [1,]    0    0    0    0    0    0
# > [2,]    0    1    2    3    4    5
# > [3,]    1    0    1    2    3    4
# > [4,]    2    1    0    1    2    3
# > [5,]    3    2    1    0    1    2

Which is then passed to globalCostMatrix() with the rigid step pattern

# >      [,1] [,2] [,3] [,4]
# > [1,]    1    1    1   -1
# > [2,]    1    0    0    1 

And produces this costMatrix and directionMatrix:

# > $costMatrix
# >      [,1] [,2] [,3] [,4] [,5] [,6]
# > [1,]    0    0    0    0    0    0
# > [2,]   NA    1    2    3    4    5
# > [3,]   NA   NA    2    4    6    8
# > [4,]   NA   NA   NA    3    6    9
# > [5,]   NA   NA   NA   NA    4    8

# > $directionMatrix
# >      [,1] [,2] [,3] [,4] [,5] [,6]
# > [1,]   NA   NA   NA   NA   NA   NA
# > [2,]   NA    1    1    1    1    1
# > [3,]   NA   NA    1    1    1    1
# > [4,]   NA   NA   NA    1    1    1
# > [5,]   NA   NA   NA   NA    1    1

I assume this can be fixed either on the initial distance/cost matrix handling, or on the rigid step pattern implementation. I don't know which is better. For me, since I'm only using the rigid step pattern, I made the following change, but it almost certainly will have unintended consequences with other step patterns:

if (open.begin) {
        if (is.na(norm) || norm != "N") {
            stop("Open-begin requires step patterns with 'N' normalization (e.g. asymmetric, or R-J types (c)). See papers in citation().")
        }
#        lm <- rbind(0, lm)
#        np <- n + 1
        np <- n
#        precm <- matrix(NA, nrow = np, ncol = m)
        precm <- matrix(NA, nrow = n, ncol = m)
#        precm[1, ] <- 0
        precm[1, ] <- lm[1, ]
    }

What I Did

It's easy to see the behavior with the following:

from dtw import *
import numpy as np
query = [1, 2, 3, 4]
reference = [1, 2, 3, 4, 5, 6]
alignment = dtw(query, reference, open_end=True, open_begin=True, step_pattern=rigid)
alignment.index1
alignment.index2

• Python port of R's Comprehensive Dynamic Time Warp algorithm package version: v1.2.0
• Python version: 3.9
• Operating System: Win10

Description

Using the dtwPlotTwoWay functions leads to a crash.

Changing both numpy.nan to 0 in line 166 and 167 in dtwPlot.py seems to solve the crash.

What I Did

#Using the dtwPlotTwoWay functions in a py file.
import numpy as np
from dtw import *

seq1 = range(5, 9)
seq2 = range(1, 9)

alignment_1_2 = dtw(seq1, seq2, keep_internals=True, step_pattern = asymmetric, open_end=True, open_begin=True)
alignment_2_1 = dtw(seq2, seq1, keep_internals=True, step_pattern = asymmetric, open_end=True, open_begin=True)

dtwPlotTwoWay(alignment_1_2, xts=seq1, yts=seq2, offset=1, ts_type='l', match_indices=None, match_col='gray', xlab='Index', ylab='Query value')


Traceback (most recent call last):
  File "C:\Users\name\Desktop\P2\DTWtest.py", line 10, in <module>
    dtw(seq1, seq2, keep_internals=True).plot(type="twoway", offset=1)
  File "C:\Users\name\AppData\Local\Packages\PythonSoftwareFoundation.Python.3.9_qbz5n2kfra8p0\LocalCache\local-packages\Python39\site-packages\dtw\dtw.py", line 124, in plot
    return dtwPlot(self, type, **kwargs)
  File "C:\Users\name\AppData\Local\Packages\PythonSoftwareFoundation.Python.3.9_qbz5n2kfra8p0\LocalCache\local-packages\Python39\site-packages\dtw\dtwPlot.py", line 70, in dtwPlot
    return dtwPlotTwoWay(x, **kwargs)
  File "C:\Users\name\AppData\Local\Packages\PythonSoftwareFoundation.Python.3.9_qbz5n2kfra8p0\LocalCache\local-packages\Python39\site-packages\dtw\dtwPlot.py", line 166, in dtwPlotTwoWay
    xts = numpy.pad(xts,(0,maxlen-len(xts)),"constant",constant_values=numpy.nan)
  File "<__array_function__ internals>", line 5, in pad
  File "C:\Users\name\AppData\Local\Packages\PythonSoftwareFoundation.Python.3.9_qbz5n2kfra8p0\LocalCache\local-packages\Python39\site-packages\numpy\lib\arraypad.py", line 803, in pad
    _set_pad_area(roi, axis, width_pair, value_pair)
  File "C:\Users\name\AppData\Local\Packages\PythonSoftwareFoundation.Python.3.9_qbz5n2kfra8p0\LocalCache\local-packages\Python39\site-packages\numpy\lib\arraypad.py", line 147, in _set_pad_area
    padded[left_slice] = value_pair[0]
ValueError: cannot convert float NaN to integer

Hey there,

See title. This would allow the user to actually use the returned ax object, e.g. to plot more things into these Axes. Currently the plt.show() command blocks this.

The usual pyplot way of things is to make the figure and axes, then plot stuff into it, customize the ticks etc, and then finally call plt.show() or plt.savefig() - as the user's responsibility.

Also, it would be great to have more parameters, e.g. for figure size

Cheers

A potential fix for small offsets when using a two way plot #22

Reference time series is now plotted on the same axis as the query. In the event of a non-zero offset, the reference values are adjusted by the offset and an offset twin axis is generated with the same scale of the original axis.

NOTE: This changes how each time series appears different in scale and should be considered as a design question.

For some alignments the two-way plot now looks different. Prior to the change, (with non-zero offset) each time series would be plot on its own axis and consequently would result in matplotlib auto-scaling each time series to best fit each axis. Time-series of different averages would then be shown to be of a similar average height. However, now they the time-series are being plot on the same axis, differences in scale become much more apparent and true to the values of the data.

Depending on the goal of the user/designers, this may or may not be beneficial. For example, if one was to look at two time-series with drastically differing averages and was trying to show common peaks between the two at certain time intervals while ignoring peak height, this could result in the alignment being much harder to see. Alternatively, if peak height was equally important as when peaks were present, then this change would result in a clearer graph. One could argue that pre-processing should be used normalize the data somewhat if the scales were originally different.

Before change with time series being of similar average heights:

After change the reference time series has a much larger average. Additionally note the change in scale of the twin y axis:

• Python port of R's Comprehensive Dynamic Time Warp algorithm package version: 1.1.6
• Python version: 3.7
• Operating System: Ubuntu 18.04

Description

I want to find DTW score between two time series. To understand how these algorithm work I use two libraries, dtw-python and tslearn.

However, I'm getting different results and I don't know why. Any help would be appreciate :)

What I Did

import numpy as np
import tslearn.metrics as tsm
import dtw

x = np.linspace(0, 50, 100)

ts1 = pd.Series(3 * np.sin(x / .5))
ts2 = pd.Series(2 * np.sin(x))

Results

tsm.dtw(ts1, ts2) -> 16.578554103357583

dtw_result = dtw.dtw(x=ts1, y=ts2, dist_method="euclidean", step_pattern="symmetric2") -> 174.2896

Why do I have such a big difference? I tried all the available step_pattern functions for dtw-python library but without any success. Which one is correct result?

• Python port of R's Comprehensive Dynamic Time Warp algorithm package version: 1.1.12
• Python version: 3.9.10
• Operating System: Windows 10

Description

I'm working with timeseries data near zero. When trying to display a twoway plot of the alignment, I need to use small offset values to properly show alignments between the data. Small offset values seem to result in the alignment lines not fully touching the reference timeseries.

What I Did

A reproducible example which results in the following graph:

x = np.linspace(0, 4 * np.pi)
y = np.sin(x) * 0.001
y2 = np.sin(x) * 2 * 0.001

alignment = dtw(y, y2, keep_internals=True)
alignment.plot(type='twoway', offset=-0.005)

As well as an example from the data I was working with which caused me to notice the issue. The alignment lines become especially skewed between the 600-800 index range.

Potential Fix

I think the issue might have something to do with some rounding or scaling in matplotlibs backend having to do with the twin axis. I've been able to more or less mitigate the issue by modifying the dtwPlotTwoWay function to plot both time series on the same axis instead of plotting on the twin axis.

def adjusted_dtwPlotTwoWay(...):
...

    ax.plot(times, yts - offset, **kwargs) # Plot on the same axis, adjust the time series by the offset

    if offset != 0:
        ql, qh = ax.get_ylim()
        ax2.set_ylim(ql + offset, qh + offset)

...

Results of the change

Bumps pypa/cibuildwheel from 2.11.3 to 2.11.4.

Dependabot will resolve any conflicts with this PR as long as you don't alter it yourself. You can also trigger a rebase manually by commenting @dependabot rebase.

I'm trying to find the closest matches to a query graph of length 100 in a much longer time series of 100000 length. I'd like it to return all matches with a normalizedDistance < X. How would I do this?

This is what I have so far:

from dtw import *
import numpy as np
import matplotlib.pyplot as plt

data = np.cumsum(np.random.uniform(-0.5, 0.5, 1000000))
query = np.cumsum(np.random.uniform(-0.5, 0.5, 100))

alignment = dtw(query, data, window_type='sakoechiba', window_args={'window_size': 10}, step_pattern="asymmetricP05", open_begin=True, open_end=True)

print(alignment.normalizedDistance) # 0.8975468634096962

It works but it only returns a single result. How do I return all matches with a normalizedDistance < X?

• Python port of R's Comprehensive Dynamic Time Warp algorithm package version:
• Python version: 3.7.3
• Operating System: OS X

Description

If the query and reference series are of size N, then the warped series is always of size N-1. This can be explained by how the warp function is set up:

jset = alignment.index2 jmax = numpy.max(jset) ii = function(numpy.arange(jmax)) return ii

As Python starts counting from 0, jmax is always N-1. I was wondering whether this is the desired output or whether the length of the warped series should also be N.

What I Did

alignment = dtw(
+        y_pred,
+        y_true,
+        keep_internals=True,
+        step_pattern=step_pattern,
+        window_type="sakoechiba",
+        window_args={"window_size": 4},
+    )
+    warped_indices = warp(alignment, index_reference=False)
+    aligned_series = y_pred[warped_indices]