tslearn.metrics.lcss_path

tslearn.metrics.lcss_path(s1, s2, eps=1, global_constraint=None, sakoe_chiba_radius=None, itakura_max_slope=None)[source]

Compute the Longest Common Subsequence (LCSS) similarity measure between (possibly multidimensional) time series and return both the path and the similarity.

LCSS is computed by matching indexes that are met up until the eps threshold, so it leaves some points unmatched and focuses on the similar parts of two sequences. The matching can occur even if the time indexes are different, which can be regulated through the sakoe chiba radius parameter that defines how far it can go.

To retrieve a meaningful similarity value from the length of the longest common subsequence, the percentage of that value regarding the length of the shortest time series is returned.

According to this definition, the values returned by LCSS range from 0 to 1, the highest value taken when two time series fully match, and vice-versa. 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] and is discussed in more details in our dedicated user-guide page.

Parameters:
s1

A time series.

s2

Another time series.

eps : float (default: 1.)

Maximum matching distance threshold.

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

Global constraint to restrict admissible paths for LCSS.

sakoe_chiba_radius : int 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_slope : float 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.

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_from_metric
Compute LCSS using a user-defined distance metric

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

>>> path, sim = lcss_path([1., 2., 3.], [1., 2., 2., 3.])
>>> path
[(0, 1), (1, 2), (2, 3)]
>>> sim
1.0
>>> lcss_path([1., 2., 3.], [1., 2., 2., 4.])[1]
1.0

Examples using tslearn.metrics.lcss_path