Distance measures for time series
Project description
Time Series Distances
Library for time series distances (e.g. Dynamic Time Warping) used in the DTAI Research Group. The library offers a pure Python implementation and a fast implementation in C. The C implementation has only Cython as a dependency. It is compatible with Numpy and Pandas and implemented to avoid unnecessary data copy operations.
Documentation: http://dtaidistance.readthedocs.io
Wannes Meert, Kilian Hendrickx, & Toon Van Craenendonck. wannesm/dtaidistance (Version v2.0.0). Zenodo. http://doi.org/10.5281/zenodo.3981067
New in v2:
 Numpy is now an optional dependency, also to compile the C library (only Cython is required).
 Small optimizations throughout the C code to improve speed.
 The consistent use of
ssize_t
instead ofint
allows for larger data structures on 64 bit machines and be more compatible with Numpy.  The parallelization is now implemented directly in C (included if OpenMP is installed).
 The
max_dist
argument turned out to be similar to Silva and Batista's work on PrunedDTW [7]. The toolbox now implements a version that is equal to PrunedDTW since it prunes more partial distances. Additionally, ause_pruning
argument is added to automatically setmax_dist
to the Euclidean distance, as suggested by Silva and Batista, to speed up the computation (a new methodub_euclidean
is available).  Support in the C library for multidimensional sequences in the
dtaidistance.dtw_ndim
package.  DTW Barycenter Averaging for clustering (v2.2).
Installation
$ pip install dtaidistance
In case the C based version is not available, see the documentation for
alternative installation options. In case
OpenMP
is not available on your system add the noopenmp
global option.
The library has no dependency on Numpy. But if Numpy is available, some additional functionality is provided. If you want to make sure this is also installed then use:
$ pip install dtaidistance[numpy]
The source code is available at github.com/wannesm/dtaidistance.
Usage
Dynamic Time Warping (DTW) Distance Measure
from dtaidistance import dtw
from dtaidistance import dtw_visualisation as dtwvis
import numpy as np
s1 = np.array([0., 0, 1, 2, 1, 0, 1, 0, 0, 2, 1, 0, 0])
s2 = np.array([0., 1, 2, 3, 1, 0, 0, 0, 2, 1, 0, 0, 0])
path = dtw.warping_path(s1, s2)
dtwvis.plot_warping(s1, s2, path, filename="warp.png")
DTW Distance Measure Between Two Series
Only the distance measure based on two sequences of numbers:
from dtaidistance import dtw
s1 = [0, 0, 1, 2, 1, 0, 1, 0, 0]
s2 = [0, 1, 2, 0, 0, 0, 0, 0, 0]
distance = dtw.distance(s1, s2)
print(distance)
The fastest version (30300 times) uses c directly but requires an array as input (with the double type),
and (optionally) also prunes computations by setting max_dist
to the Euclidean upper bound:
from dtaidistance import dtw
import array
s1 = array.array('d',[0, 0, 1, 2, 1, 0, 1, 0, 0])
s2 = array.array('d',[0, 1, 2, 0, 0, 0, 0, 0, 0])
d = dtw.distance_fast(s1, s2, use_pruning=True)
Or you can use a numpy array (with dtype double or float):
from dtaidistance import dtw
import numpy as np
s1 = np.array([0, 0, 1, 2, 1, 0, 1, 0, 0], dtype=np.double)
s2 = np.array([0.0, 1, 2, 0, 0, 0, 0, 0, 0])
d = dtw.distance_fast(s1, s2, use_pruning=True)
Check the __doc__
for information about the available arguments:
print(dtw.distance.__doc__)
A number of options are foreseen to early stop some paths the dynamic programming algorithm is exploring or tune the distance measure computation:
window
: Only allow for shifts up to this amount away from the two diagonals.max_dist
: Stop if the returned distance measure will be larger than this value.max_step
: Do not allow steps larger than this value.max_length_diff
: Return infinity if difference in length of two series is larger.penalty
: Penalty to add if compression or expansion is applied (on top of the distance).psi
: Psi relaxation to ignore begin and/or end of sequences (for cylical sequences) [2].use_pruning
: Prune computations based on the Euclidean upper bound.
DTW Distance Measure all warping paths
If, next to the distance, you also want the full matrix to see all possible warping paths:
from dtaidistance import dtw
s1 = [0, 0, 1, 2, 1, 0, 1, 0, 0]
s2 = [0, 1, 2, 0, 0, 0, 0, 0, 0]
distance, paths = dtw.warping_paths(s1, s2)
print(distance)
print(paths)
The matrix with all warping paths can be visualised as follows:
from dtaidistance import dtw
from dtaidistance import dtw_visualisation as dtwvis
import random
import numpy as np
x = np.arange(0, 20, .5)
s1 = np.sin(x)
s2 = np.sin(x  1)
random.seed(1)
for idx in range(len(s2)):
if random.random() < 0.05:
s2[idx] += (random.random()  0.5) / 2
d, paths = dtw.warping_paths(s1, s2, window=25, psi=2)
best_path = dtw.best_path(paths)
dtwvis.plot_warpingpaths(s1, s2, paths, best_path)
Notice the psi
parameter that relaxes the matching at the beginning and end.
In this example this results in a perfect match even though the sine waves are slightly shifted.
DTW Distance Measures Between Set of Series
To compute the DTW distance measures between all sequences in a list of sequences, use the method dtw.distance_matrix
.
You can set variables to use more or less c code (use_c
and use_nogil
) and parallel or serial execution
(parallel
).
The distance_matrix
method expects a list of lists/arrays:
from dtaidistance import dtw
import numpy as np
series = [
np.array([0, 0, 1, 2, 1, 0, 1, 0, 0], dtype=np.double),
np.array([0.0, 1, 2, 0, 0, 0, 0, 0, 0, 0, 0]),
np.array([0.0, 0, 1, 2, 1, 0, 0, 0])]
ds = dtw.distance_matrix_fast(series)
or a matrix (in case all series have the same length):
from dtaidistance import dtw
import numpy as np
series = np.matrix([
[0.0, 0, 1, 2, 1, 0, 1, 0, 0],
[0.0, 1, 2, 0, 0, 0, 0, 0, 0],
[0.0, 0, 1, 2, 1, 0, 0, 0, 0]])
ds = dtw.distance_matrix_fast(series)
DTW Distance Measures Between Set of Series, limited to block
You can instruct the computation to only fill part of the distance measures matrix. For example to distribute the computations over multiple nodes, or to only compare source series to target series.
from dtaidistance import dtw
import numpy as np
series = np.matrix([
[0., 0, 1, 2, 1, 0, 1, 0, 0],
[0., 1, 2, 0, 0, 0, 0, 0, 0],
[1., 2, 0, 0, 0, 0, 0, 1, 1],
[0., 0, 1, 2, 1, 0, 1, 0, 0],
[0., 1, 2, 0, 0, 0, 0, 0, 0],
[1., 2, 0, 0, 0, 0, 0, 1, 1]])
ds = dtw.distance_matrix_fast(series, block=((1, 4), (3, 5)))
The output in this case will be:
# 0 1 2 3 4 5
[[ inf inf inf inf inf inf] # 0
[ inf inf inf 1.4142 0.0000 inf] # 1
[ inf inf inf 2.2360 1.7320 inf] # 2
[ inf inf inf inf 1.4142 inf] # 3
[ inf inf inf inf inf inf] # 4
[ inf inf inf inf inf inf]] # 5
Clustering
A distance matrix can be used for time series clustering. You can use existing methods such as
scipy.cluster.hierarchy.linkage
or one of two included clustering methods (the latter is a
wrapper for the SciPy linkage method).
from dtaidistance import clustering
# Custom Hierarchical clustering
model1 = clustering.Hierarchical(dtw.distance_matrix_fast, {})
cluster_idx = model1.fit(series)
# Augment Hierarchical object to keep track of the full tree
model2 = clustering.HierarchicalTree(model1)
cluster_idx = model2.fit(series)
# SciPy linkage clustering
model3 = clustering.LinkageTree(dtw.distance_matrix_fast, {})
cluster_idx = model3.fit(series)
For models that keep track of the full clustering tree (HierarchicalTree
or LinkageTree
), the
tree can be visualised:
model.plot("myplot.png")
Dependencies
Optional:
Development:
Contact
References
 T. K. Vintsyuk, Speech discrimination by dynamic programming. Kibernetika, 4:81–88, 1968.
 H. Sakoe and S. Chiba, Dynamic programming algorithm optimization for spoken word recognition. IEEE Transactions on Acoustics, Speech and Signal Processing, 26(1):43–49, 1978.
 C. S. Myers and L. R. Rabiner, A comparative study of several dynamic timewarping algorithms for connectedword recognition. The Bell System Technical Journal, 60(7):1389–1409, Sept 1981.
 Mueen, A and Keogh, E, Extracting Optimal Performance from Dynamic Time Warping, Tutorial, KDD 2016
 D. F. Silva, G. E. A. P. A. Batista, and E. Keogh. On the effect of endpoints on dynamic time warping, In SIGKDD Workshop on Mining and Learning from Time Series, II. Association for Computing MachineryACM, 2016.
 C. Yanping, K. Eamonn, H. Bing, B. Nurjahan, B. Anthony, M. Abdullah and B. Gustavo. The UCR Time Series Classification Archive, 2015.
 D. F. Silva and G. E. Batista. Speeding up allpairwise dynamic time warping matrix calculation, In Proceedings of the 2016 SIAM International Conference on Data Mining, pages 837–845. SIAM, 2016.
License
DTAI distance code.
Copyright 20162021 KU Leuven, DTAI Research Group
Licensed under the Apache License, Version 2.0 (the "License");
you may not use this file except in compliance with the License.
You may obtain a copy of the License at
http://www.apache.org/licenses/LICENSE2.0
Unless required by applicable law or agreed to in writing, software
distributed under the License is distributed on an "AS IS" BASIS,
WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
See the License for the specific language governing permissions and
limitations under the License.
Project details
Release history Release notifications  RSS feed
Download files
Download the file for your platform. If you're not sure which to choose, learn more about installing packages.
Filename, size  File type  Python version  Upload date  Hashes 

Filename, size dtaidistance2.2.5cp39cp39macosx_10_15_x86_64.whl (820.9 kB)  File type Wheel  Python version cp39  Upload date  Hashes View 
Filename, size dtaidistance2.2.5.tar.gz (932.9 kB)  File type Source  Python version None  Upload date  Hashes View 
Hashes for dtaidistance2.2.5cp39cp39macosx_10_15_x86_64.whl
Algorithm  Hash digest  

SHA256  3b2d72ff83f898cdfa09aca018a8798a59063823da4df45d212d612d9d401e73 

MD5  46fc68540fc2d24806062087ff50e8b5 

BLAKE2256  32936c5eb6df53b43bdcd6235fdbd4f3ec207486f1cb67ca2ce5a5f94935de9d 