edr_distance¶

edr_distance(x: ndarray, y: ndarray, window: float | None = None, epsilon: float | None = None, itakura_max_slope: float | None = None) → float[source]¶

Compute the EDR distance between two time series.

Edit Distance on Real Sequences (EDR) was proposed as an adaptation of standard edit distance on discrete sequences in [1], specifically for distances between trajectories. Like LCSS, EDR uses a distance threshold to define when two elements of a series match. However, rather than simply count matches and look for the longest sequence, EDR applies a (constant) penalty for non-matching elements where gaps are inserted to create an optimal alignment.

\[\begin{split}if \;\; |ai − bj | < ϵ\\ c &= 0\\ else\\ c &= 1\\ match &= D_{i-1,j-1}+ c)\\ delete &= D_{i-1,j}+ d({x_{i},g})\\ insert &= D_{i-1,j-1}+ d({g,y_{j}})\\ D_{i,j} &= min(match,insert, delete)\end{split}\]

EDR computes the minimum number of elements (as a percentage) that must be removed from x and y so that the sum of the distance between the remaining signal elements lies within the tolerance (epsilon). EDR was originally proposed in [1].

The value returned will be between 0 and 1 per time series. The value will represent as a percentage of elements that must be removed for the time series to be an exact match.

Parameters:

xnp.ndarray: First time series, either univariate, shape (n_timepoints,), or multivariate, shape (n_channels, n_timepoints).
ynp.ndarray: Second time series, either univariate, shape (n_timepoints,), or multivariate, shape (n_channels, n_timepoints).
windowfloat, default=None: The window to use for the bounding matrix. If None, no bounding matrix is used.
epsilonfloat, default=None: Matching threshold to determine if two subsequences are considered close enough to be considered ‘common’. If not specified as per the original paper epsilon is set to a quarter of the maximum standard deviation.
itakura_max_slopefloat, default=None: Maximum slope as a proportion of the number of time points used to create Itakura parallelogram on the bounding matrix. Must be between 0. and 1.

Returns:

float: EDR distance between x and y.

Raises:

ValueError: If x and y are not 1D or 2D arrays.

References

[1] (1,2)

Chen L, Ozsu MT, Oria V: Robust and fast similarity search for moving

object trajectories. In: Proceedings of the ACM SIGMOD International Conference on Management of Data, 2005

Examples

>>> import numpy as np
>>> from aeon.distances import edr_distance
>>> x = np.array([[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]])
>>> y = np.array([[11, 12, 13, 14, 15, 16, 17, 18, 19, 20]])
>>> edr_distance(x, y)
1.0