dtwclust (version 3.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, force.symmetry = FALSE, error.check = TRUE)

Arguments

x

A time series (reference).

y

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

window.size

Window size for envelop calculation. See details.

norm

Vector norm. Either "L1" for Manhattan distance or "L2" for Euclidean.

lower.env

Optionally, a pre-computed lower envelop for y can be provided (non-proxy version only).

upper.env

Optionally, a pre-computed upper envelop for y can be provided (non-proxy version only).

force.symmetry

If TRUE, a second lower bound is calculated by swapping x and y, and whichever result has a higher distance value is returned. The proxy version can only work if a square matrix is obtained, but use carefully.

error.check

Check data inconsistencies?

Value

A list with:

• d: The lower bound of the DTW distance.
• upper.env: The time series of y's upper envelop.
• lower.env: The time series of y's lower envelop.

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