dtwclust (version 2.1.1)

lb_keogh: Keogh's DTW lower bound

Description

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

Usage

lb_keogh(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

• A list with:
  • d: The lower bound of the DTW distance.
  • upper.env: The time series ofy's upper envelope.
  • lower.env: The time series ofy's lower envelope.

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

Keogh E and Ratanamahatana CA (2005). ``Exact indexing of dynamic time warping.'' Knowledge and information systems, 7(3), pp. 358-386.

Examples

# Sample data
data(uciCT)

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

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

d.lbk <= d.dtw

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

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

D.lbk <= D.dtw