dtwclust (version 2.1.1)

dtw_lb: DTW calculation guided by Lemire's lower bounds

Description

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

Usage

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

Arguments

x, y

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

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?

force.pairwise

Calculate pairwise distances. See the notes.

Value

• The distance matrix with class crossdist.

Parallel Computing

Please note that running tasks in parallel does not guarantee faster computations. The overhead introduced is sometimes too large, and it's better to run tasks sequentially.

The user can register a parallel backend, e.g. with the doParallel package, in order to attempt to speed up the calculations (see the examples).

Details

This function first calculates an initial estimate of a distance matrix between two sets of time series using LB_Improved. Afterwards, it uses the estimate to calculate the corresponding true DTW distance 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 within 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_keogh, lb_improved

Examples

# Load data
data(uciCT)

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

# 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 three 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)

#### Running DTW_LB with parallel support
# For such a small dataset, this is probably slower in parallel
require(doParallel)

# Create parallel workers
cl <- makeCluster(detectCores())
invisible(clusterEvalQ(cl, library(dtwclust)))
registerDoParallel(cl)

# Distance matrix
D <- dtw_lb(data[1:50], data[51:100], window.size = 20)

# Stop parallel workers
stopCluster(cl)

# Return to sequential computations
registerDoSEQ()

# Nearest neighbors
NN <- apply(D, 1, which.min)
cbind(names(data[1:50]), names(data[51:100][NN]))