DOCSEARCHbyAlgolia
Submit Docs

dtaidistance

repository·master·Indexed 22 days ago

https://github.com/wannesm/dtaidistance

A library for computing time series distances, primarily focusing on Dynamic Time Warping (DTW). It provides pure Python and high-performance C implementations compatible with Numpy and Pandas. Features include DTW distance and warping path calculation, distance matrix computation, time series clustering (Hierarchical, K-Means DBA, and K-Medoids), and Dynamic Subsequence Warping (DSW) for distance explanation. Version 2.4.0.

Tokens
18K
Snippets
32
Records
99
Agent score
79%

What's inside dtaidistance

  1. Optimize DTW complexity and tuning

    master

    DTW has quadratic time complexity. You can reduce this using several parameters:

    Complexity Reduction

    • window: Implements a Sakoe-Chiba band, limiting shifts allowed away from the diagonals.
    • max_dist: Avoids computing paths larger than this value. Returns infinity if no path is found within this limit.
    • use_pruning: When True, automatically sets max_dist to the Euclidean upper bound.
    • max_step: Limits the maximum step size allowed in a path.
    • max_length_diff: Returns infinity if the difference in sequence lengths exceeds this value.

    Cost Tuning

    • penalty: An additional cost applied during compression or expansion.
    • psi: (Psi-relaxation) Allows up to psi number of start/end points to be ignored to achieve a lower distance, useful for cyclical sequences.

  3. Compile dtaidistance with float or integer precision

    master

    By default, the fast C-based version of dtaidistance uses the double datatype. If your application requires float or int precision for performance or memory reasons, you can recompile the C code. This process requires a C compiler and the make utility.

    To compile with float precision, navigate to the jinja directory within the repository and run make float. To use integers, run make int instead.

    git clone https://github.com/wannesm/dtaidistance.git
cd dtaidistance/dtaidistance/jinja
make float
# make int
cd ../..
make build
pip install .

  4. Install dtaidistance via pip

    master

    You can install the package from PyPI. Note that this requires OpenMP to be available on your system for parallelization. If OpenMP is not available, you can install a version without it using the --noopenmp option.

    If you install a version without OpenMP, you may need to force the use of Python's multiprocessing library by providing the --use_mp=True option to avoid exceptions when parallelization is required.

  7. Perform K-Medoids Clustering

    master

    K-medoids clustering can be performed using a distance matrix via the clustering.KMedoids class. This class wraps the pyclustering package and allows you to pass a distance function (like dtw.distance_matrix_fast) and its options.

    from dtaidistance import dtw, clustering
import numpy as np

s = np.array([
             [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],
             [1., 2, 0, 0, 0, 0, 0, 1, 1]])

model = clustering.KMedoids(dtw.distance_matrix_fast, {}, k=3)
cluster_idx = model.fit(s)
model.plot("kmedoids.png")

  8. Perform Agglomerative Hierarchical Clustering

    master

    Agglomerative clustering can be performed using a distance matrix. You can use the clustering.Hierarchical class for basic clustering, or clustering.HierarchicalTree and clustering.LinkageTree if you need to keep track of the full clustering tree (available in model.linkage).

    To visualize the resulting hierarchy, use the .plot() method. You can customize the layout by passing a Matplotlib axes array, where the tree is expected on ax[0] and the time series on ax[1].

    # Custom Hierarchical clustering
model1 = clustering.Hierarchical(dtw.distance_matrix_fast, {})
cluster_idx = model1.fit(timeseries)

# Keep track of full tree by using the HierarchicalTree wrapper class
model2 = clustering.HierarchicalTree(model1)
cluster_idx = model2.fit(timeseries)

# You can also pass keyword arguments identical to instantiate a Hierarchical object
model2 = clustering.HierarchicalTree(dists_fun=dtw.distance_matrix_fast, dists_options={})
cluster_idx = model2.fit(timeseries)

# SciPy linkage clustering
model3 = clustering.LinkageTree(dtw.distance_matrix_fast, {})
cluster_idx = model3.fit(timeseries)

# Visualizing the tree
model2.plot("hierarchy.png")

# Advanced visualization with custom axes and labels
import matplotlib.pyplot as plt
fig, ax = plt.subplots(nrows=1, ncols=2, figsize=(10, 10))
show_ts_label = lambda idx: "ts-" + str(idx)
model2.plot("hierarchy.png", axes=ax, show_ts_label=show_ts_label,
           show_tr_label=True, ts_label_margin=-10,
           ts_left_margin=10, ts_sample_length=1)

  9. Generate DTAIDistance source code from templates

    master

    DTAIDistance uses Jinja2 templates to generate repetitive source code that is difficult to manage manually, such as code requiring C linking or variations for different techniques. To regenerate the source code files from these templates, run the make command within the jinja directory.

    Note: This is a build-time task for developers working on the library's source generation, not a standard runtime task for end-users.

    make

  10. Perform K-Means DBA Clustering

    master

    K-means clustering for time series requires an averaging strategy. DTAIDistance provides DTW Barycenter Averaging (DBA). Use the KMeans class to perform this clustering.

    Key Parameters:

    • k: Number of clusters.
    • max_it: Maximum number of iterations.
    • max_dba_it: Maximum number of DBA iterations.
    • dists_options: Dictionary of options passed to the distance function (e.g., {"window": 40}).

    Tip: Improving results with differencing If your time series have different baselines, you can apply differencing and smoothing using dtaidistance.preprocessing.differencing to focus on signal changes rather than absolute values.

    # Standard K-Means DBA
model = KMeans(k=4, max_it=10, max_dba_it=10, dists_options={"window": 40})
cluster_idx, performed_it = model.fit(series, use_c=True, use_parallel=False)

# K-Means with differencing and low-pass filter to handle baseline shifts
import dtaidistance.preprocessing
series = dtaidistance.preprocessing.differencing(series, smooth=0.1)
model = KMeans(k=4, max_it=10, max_dba_it=10, dists_options={"window": 40})
cluster_idx, performed_it = model.fit(series, use_c=True, use_parallel=False)

  12. Install dtaidistance via pip or conda

    master

    You can install the library using either pip or conda.

    Note: The pip installation requires Numpy as a dependency to compile Numpy-compatible C code (using Cython). However, this dependency is optional and can be removed after installation.

    $ pip install dtaidistance

# or

$ conda install -c conda-forge dtaidistance