dtwclust (version 2.1.1)

lb_improved: Lemire's improved DTW lower bound

Description

This function calculates an improved lower bound (LB) on the Dynamic Time Warp (DTW) distance between two time series. It uses a Sakoe-Chiba constraint.

Usage

lb_improved(x, y, window.size = NULL, norm = "L1", lower.env = NULL,
  upper.env = NULL)

Arguments

x

A time series (reference).

y

A time series with the same length as x (query).

window.size

Window size for envelope calculation. See details.

norm

Pointwise distance. Either L1 for Manhattan distance or L2 for Euclidean.

lower.env

Optionally, a pre-computed lower envelope for y can be provided.

upper.env

Optionally, a pre-computed upper envelope for y can be provided.

Value

• The improved lower bound for the DTW distance.

Details

The windowing constraint uses a centered window. The calculations expect a value in window.size that represents the distance between the point considered and one of the edges of the window. Therefore, if, for example, window.size = 10, the warping for an observation $x_i$ considers the points between $x_{i-10}$ and $x_{i+10}$, resulting in 10(2) + 1 = 21 observations falling within the window.

The reference time series should go in x, whereas the query time series should go in y.

References

Lemire D (2009). ``Faster retrieval with a two-pass dynamic-time-warping lower bound .'' Pattern Recognition, 42(9), pp. 2169 - 2180. ISSN 0031-3203, http://dx.doi.org/10.1016/j.patcog.2008.11.030, http://www.sciencedirect.com/science/article/pii/S0031320308004925.

Examples

# Sample data
data(uciCT)

# Lower bound distance between two series
d.lbi <- lb_improved(CharTraj[[1]], CharTraj[[2]], window.size = 20)

# Corresponding true DTW distance
d.dtw <- dtw(CharTraj[[1]], CharTraj[[2]],
             window.type = "slantedband", window.size = 20)$distance

d.lbi <= d.dtw

# Calculating the LB between several time series using the 'proxy' package
# (notice how both argments must be lists)
D.lbi <- proxy::dist(CharTraj[1], CharTraj[2:5], method = "LB_Improved",
                     window.size = 20, norm = "L2")

# Corresponding true DTW distance
# (see dtwclust documentation for an explanation of DTW2)
D.dtw <- proxy::dist(CharTraj[1], CharTraj[2:5], method = "DTW2",
                     window.type = "slantedband", window.size = 20)

D.lbi <= D.dtw