dtwclust (version 3.1.1)

dtw_lb: DTW distance matrix guided by Lemire's improved lower bound

Description

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

Usage

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

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?

pairwise

Calculate pairwise distances?

dtw.func

Which function to use for core DTW the calculations, either "dtw" or "dtw_basic". See dtw and dtw_basic.

...

Further arguments for dtw.func or lb_improved.

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, and it continues iteratively until no changes in the nearest neighbors occur.

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 <- reinterpolate(CharTraj, new.length = max(lengths(CharTraj)))

# 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, 1L, which.min)

# Calculate the DTW distances between all elements (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, 1L, which.min)

# Calculate the DTW distances between all elements using dtw_basic (actually faster, see notes)
system.time(d3 <- proxy::dist(data[1:5], data[6:50], method = "DTW_BASIC",
                              window.size = 20))

# Nearest neighbors
NN3 <- apply(d3, 1L, which.min)

# Same results?
all(NN1 == NN2)
all(NN1 == NN3)

## Not run: 
# #### 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]))
# ## End(Not run)