tslearn.metrics.lcss_path_from_metric

tslearn.metrics.lcss_path_from_metric(s1, s2=None, eps=1, metric='euclidean', global_constraint=None, sakoe_chiba_radius=None, itakura_max_slope=None, be=None, **kwds)

Compute the Longest Common Subsequence (LCSS) similarity measure between (possibly multidimensional) time series using a distance metric defined by the user and return both the path and the similarity.

Having the length of the longest commom subsequence between two time-series, the similarity is computed as the percentage of that value regarding the length of the shortest time series.

It is not required that both time series share the same size, but they must be the same dimension. LCSS was originally presented in [1].

Valid values for metric are the same as for scikit-learn pairwise_distances function i.e. a string (e.g. “euclidean”, “sqeuclidean”, “hamming”) or a function that is used to compute the pairwise distances. See scikit and scipy documentations for more information about the available metrics.

Parameters:

s1array-like, shape=(sz1, d) or (sz1,) if metric!=”precomputed”, (sz1, sz2) otherwise

A time series or an array of pairwise distances between samples. If shape is (sz1,), the time series is assumed to be univariate.

s2array-like, shape=(sz2, d) or (sz2,), optional (default: None)

A second time series, only allowed if metric != “precomputed”. If shape is (sz2,), the time series is assumed to be univariate.

epsfloat (default: 1.)

Maximum matching distance threshold.

metricstring or callable (default: “euclidean”)

Function used to compute the pairwise distances between each points of s1 and s2. If metric is “precomputed”, s1 is assumed to be a distance matrix. If metric is an other string, it must be one of the options compatible with sklearn.metrics.pairwise_distances. Alternatively, if metric is a callable function, it is called on pairs of rows of s1 and s2. The callable should take two 1 dimensional arrays as input and return a value indicating the distance between them.

global_constraint{“itakura”, “sakoe_chiba”} or None (default: None)

Global constraint to restrict admissible paths for LCSS.

sakoe_chiba_radiusint or None (default: None)

Radius to be used for Sakoe-Chiba band global constraint. If None and global_constraint is set to “sakoe_chiba”, a radius of 1 is used. If both sakoe_chiba_radius and itakura_max_slope are set, global_constraint is used to infer which constraint to use among the two. In this case, if global_constraint corresponds to no global constraint, a RuntimeWarning is raised and no global constraint is used.

itakura_max_slopefloat or None (default: None)

Maximum slope for the Itakura parallelogram constraint. If None and global_constraint is set to “itakura”, a maximum slope of 2. is used. If both sakoe_chiba_radius and itakura_max_slope are set, global_constraint is used to infer which constraint to use among the two. In this case, if global_constraint corresponds to no global constraint, a RuntimeWarning is raised and no global constraint is used.

beBackend object or string or None

Backend. If be is an instance of the class NumPyBackend or the string “numpy”, the NumPy backend is used. If be is an instance of the class PyTorchBackend or the string “pytorch”, the PyTorch backend is used. If be is None, the backend is determined by the input arrays. See our dedicated user-guide page for more information.

**kwds

Additional arguments to pass to sklearn pairwise_distances to compute the pairwise distances.

Returns:

list of integer pairs

Matching path represented as a list of index pairs. In each pair, the first index corresponds to s1 and the second one corresponds to s2.

float

Similarity score.

See also

lcss

Get only the similarity score for LCSS

lcss_path

Get both the matching path and the similarity score for LCSS

Notes

By using a squared euclidean distance metric as shown above, the output path and similarity is the same as the one obtained by using lcss_path (which uses the euclidean distance) simply because with the sum of squared distances the matching threshold is still not reached. Also, contrary to Dynamic Time Warping and variants, an LCSS path does not need to be contiguous.

References

[1]

M. Vlachos, D. Gunopoulos, and G. Kollios. 2002. “Discovering Similar Multidimensional Trajectories”, In Proceedings of the 18th International Conference on Data Engineering (ICDE ‘02). IEEE Computer Society, USA, 673.

Examples

Lets create 2 numpy arrays to wrap:

>>> import numpy as np
>>> rng = np.random.RandomState(0)
>>> s1, s2 = rng.rand(5, 2), rng.rand(6, 2)

The wrapping can be done by passing a string indicating the metric to pass to scikit-learn pairwise_distances:

>>> lcss_path_from_metric(s1, s2,
...                      metric="sqeuclidean")  
([(0, 1), (1, 2), (2, 3), (3, 4), (4, 5)], 1.0)

Or by defining a custom distance function:

>>> sqeuclidean = lambda x, y: np.sum((x-y)**2)
>>> lcss_path_from_metric(s1, s2, metric=sqeuclidean)  
([(0, 1), (1, 2), (2, 3), (3, 4), (4, 5)], 1.0)

Or by using a precomputed distance matrix as input:

>>> from sklearn.metrics.pairwise import pairwise_distances
>>> dist_matrix = pairwise_distances(s1, s2, metric="sqeuclidean")
>>> lcss_path_from_metric(dist_matrix,
...                      metric="precomputed")  
([(0, 1), (1, 2), (2, 3), (3, 4), (4, 5)], 1.0)

Examples using tslearn.metrics.lcss_path_from_metric

Longest Commom Subsequence with a custom distance metric

Longest Commom Subsequence with a custom distance metric