dtwclust (version 1.2.0)

dtw_lb: DTW calculation guided by Lemire's lower bound (LB_Improved)

Description

Calculation of a distance matrix with the Dynamic Time Warping (DTW) distance guided by Lemire's lower bound (LB).

Usage

dtw_lb(x, y = NULL, window.size = NULL, norm = "L1", error.check = TRUE)

Arguments

x

A matrix where rows are time series, or a list of time series.

y

An object similar to x.

window.size

Window size to use with the LB and DTW calculation. See details.

norm

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

error.check

Should inconsistencies in the data be checked?

Value

• The distance matrix with class crossdist.

Details

This function first calculates an initial estimate of a distance matrix between two sets of time series using Lemire's improved lower bound. Afterwards, it uses the estimate to calculate the true DTW distances between only the nearest neighbors of each series in x found in y. If only x is provided, the distance matrix is calculated between all its time series. This could be useful in case one is interested in only the nearest neighbor of one or more series among a dataset.

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

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.

See Also

lb_improved

Examples

# Load data
data(uciCT)

# Reinterpolate to same length
data <- lapply(CharTraj, reinterpolate, newLength = 205)

# Calculate the DTW distance between a certain subset aided with the lower bound
system.time(d <- dtw_lb(data[1:5], data[6:50], window.size = 20))

# Nearest neighbors
NN1 <- apply(d, 1, which.min)

# Calculate the DTW distances between all elements (about seven times slower)
system.time(d2 <- proxy::dist(data[1:5], data[6:50], method = "DTW",
                              window.type = "slantedband", window.size = 20))

# Nearest neighbors
NN2 <- apply(d2, 1, which.min)

# Same results?
all(NN1 == NN2)