dtwclust (version 1.0.0)

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")

Arguments

x

A time series.

y

A time series with the same length as x.

window.size

Window size for envelope calculation. See details.

norm

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

Value

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

Details

The lower bound is defined for time series of equal length only.

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.

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