dtw_distance#

dtw_distance(x: numpy.ndarray, y: numpy.ndarray, window: Optional[float] = None, itakura_max_slope: Optional[float] = None, bounding_matrix: Optional[numpy.ndarray] = None, **kwargs: Any) → float[source]#

Compute the dynamic time warping (DTW) distance between two time series.

Originally proposed in [1] DTW computes the distance between two time series by considering their alignments during the calculation. This is done by measuring the pointwise distance (normally using Euclidean) between all elements of the two time series and then using dynamic programming to find the warping path that minimises the total pointwise distance between realigned series.

Mathematically dtw can be defined as:

\[dtw(x, y) = \sqrt{\sum_{(i, j) \in \pi} \|x_{i} - y_{j}\|^2}\]

Parameters

x: np.ndarray (1d or 2d array): First time series.
y: np.ndarray (1d or 2d array): Second time series.
window: float, defaults = None: Float that is the radius of the sakoe chiba window (if using Sakoe-Chiba lower bounding). Value must be between 0. and 1.
itakura_max_slope: float, defaults = None: Gradient of the slope for itakura parallelogram (if using Itakura Parallelogram lower bounding). Value must be between 0. and 1.
bounding_matrix: np.ndarray (2d of size mxn where m is len(x) and n is len(y)),: defaults = None

Custom bounding matrix to use. If defined then other lower_bounding params are ignored. The matrix should be structure so that indexes considered in bound should be the value 0. and indexes outside the bounding matrix should be infinity.
kwargs: Any: Extra kwargs.

Returns

float: Dtw distance between x and y.

Raises

ValueError: If the sakoe_chiba_window_radius is not a float. If the itakura_max_slope is not a float. If the value of x or y provided is not a numpy array. If the value of x or y has more than 2 dimensions. If a metric string provided, and is not a defined valid string. If a metric object (instance of class) is provided and doesn’t inherit from NumbaDistance. If a resolved metric is not no_python compiled. If the metric type cannot be determined If both window and itakura_max_slope are set

References

1: H. Sakoe, S. Chiba, “Dynamic programming algorithm optimization for spoken word recognition,” IEEE Transactions on Acoustics, Speech and Signal Processing, vol. 26(1), pp. 43–49, 1978.

Examples

>>> import numpy as np
>>> x_1d = np.array([1, 2, 3, 4])  # 1d array
>>> y_1d = np.array([5, 6, 7, 8])  # 1d array
>>> dtw_distance(x_1d, y_1d)
58.0

>>> x_2d = np.array([[1, 2, 3, 4], [5, 6, 7, 8]])  # 2d array
>>> y_2d = np.array([[9, 10, 11, 12], [13, 14, 15, 16]])  # 2d array
>>> dtw_distance(x_2d, y_2d)
512.0