Dynamic time warping (DTW) distance C extension for Python
To compile and link the source code in the current directory, type:
python setup.py build_ext --inplace
or just execute the compilation script:
./compile_test
which will also run the test script.
If compilation is successful, you can manually run the test script, which generates two arrays of random numbers and computes the DTW distance and path between them, first using a window constraint and then without one. The test script can be run with zero, one, or two position arguments.
Zero
----
Generates two arrays with 10000 elements and a window size of 0.1. This takes
about a second to run on my machine.
Example
python test_dtw.py
One
---
Takes one command line argument, which is the size of the arrays.
Example
python test_dtw.py 10000
Two
---
Takes two command line arguments. The first argument is the size of the arrays
and the second argument is the window fraction.
The test script test_dtw.py can be run as follows:
Example input
-------------
python test_dtw.py 10000 0.1
Example output
--------------
Computing DTW distance...
DTW distance with window=0.1: 1528.85553244
Took 0.33991 seconds.
Computing DTW path...
[[9999 9999]
[9998 9999]
[9997 9999]
[9996 9999]
[9995 9999]]
...
[[1 4]
[0 3]
[0 2]
[0 1]
[0 0]]
Took 0.342164 seconds.
Computing DTW distance...
DTW distance with no window: 1528.85553244
Took 0.678301 seconds.
Computing DTW path...
[[9999 9999]
[9998 9999]
[9997 9999]
[9996 9999]
[9995 9999]]
...
[[1 4]
[0 3]
[0 2]
[0 1]
[0 0]]
Took 0.677329 seconds.
FUNCTIONS
dtw(...)
Compute the dynamic time warping (DTW) distance between two sequences.
Parameters
----------
x : numpy array of floats
First sequence
y : numpy array of floats
Second sequence
window_frac: float
Locality constraint, given as a fraction from 0 to 1 of the size of
the larger sequence.
Returns
-------
float
The DTW distance between x and y
dtw_path(...)
Determine the optimal warping between two sequences.
Parameters
----------
x : numpy array of floats
First sequence
y : numpy array of floats
Second sequence
window_frac: float
Locality constraint, given as a fraction from 0 to 1 of the size of
the larger sequence.
Returns
-------
numpy.ndarray
The pairings between the two sequences that provide the optimal
warping path.
In [1]: import numpy as np
In [2]: from _dtw import dtw, dtw_path
In [3]: x = np.array([3, 2, 2, 1, 3, 1, 1])
In [4]: y = np.array([1, 1, 3, 2, 1, 2])
In [5]: dtw(x, y, 0.5)
Out[5]: 6.0
In [6]: dtw.dtw_path(x, y, 0.5)
Out[6]:
array([[6, 5],
[5, 4],
[4, 3],
[4, 2],
[3, 1],
[2, 0],
[1, 0],
[0, 0]], dtype=int32)
Also refer to example in test_dtw.py