View source: R/DISTANCES-dtw-lb.R

dtw_lb | R Documentation |

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

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

`x, y` |
A matrix or data frame 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` |
Either |

`error.check` |
Logical indicating whether the function should try to detect inconsistencies and give more informative errors messages. Also used internally to avoid repeating checks. |

`pairwise` |
Calculate pairwise distances? |

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

`nn.margin` |
Either 1 to search for nearest neighbors row-wise, or 2 to search column-wise.
Only implemented for |

`...` |
Further arguments for |

This function first calculates an initial estimate of a distance matrix between two sets of time
series using `lb_improved()`

(the `proxy::dist()`

version). 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,
effectively returning a matrix filled with the LB_Improved values.

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.

The distance matrix with class `crossdist`

.

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.

This function uses the `RcppParallel`

package
for parallelization. It uses all available threads by default (see
`RcppParallel::defaultNumThreads()`

), but this can
be changed by the user with
`RcppParallel::setThreadOptions()`

.

An exception to the above is when this function is called within a
`foreach`

parallel loop **made by dtwclust**. If the parallel
workers do not have the number of threads explicitly specified, this function will default to 1
thread per worker. See the parallelization vignette for more information
(`browseVignettes("dtwclust")`

).

This function uses a lower bound that is only defined for time series of equal length.

The `proxy::dist()`

version simply calls this function.

A considerably large dataset is probably necessary before this is faster than using `dtw_basic()`

with `proxy::dist()`

. Also note that `lb_improved()`

calculates warping envelopes for the series
in `y`

, so be careful with the provided order and `nn.margin`

(see examples).

Alexis Sarda-Espinosa

Lemire D (2009). “Faster retrieval with a two-pass dynamic-time-warping lower bound .” *Pattern
Recognition*, **42**(9), pp. 2169 - 2180. ISSN 0031-3203,
doi: 10.1016/j.patcog.2008.11.030,
https://www.sciencedirect.com/science/article/pii/S0031320308004925.

`lb_keogh()`

, `lb_improved()`

# 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 = 20L)) # 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 = "sakoechiba", window.size = 20L)) # Nearest neighbors NN2 <- apply(d2, 1L, which.min) # Calculate the DTW distances between all elements using dtw_basic # (might be faster, see notes) system.time(d3 <- proxy::dist(data[1:5], data[6:50], method = "DTW_BASIC", window.size = 20L)) # Nearest neighbors NN3 <- apply(d3, 1L, which.min) # Change order and margin for nearest neighbor search # (usually fastest, see notes) system.time(d4 <- dtw_lb(data[6:50], data[1:5], window.size = 20L, nn.margin = 2L)) # Nearest neighbors *column-wise* NN4 <- apply(d4, 2L, which.min) # Same results? identical(NN1, NN2) identical(NN1, NN3) identical(NN1, NN4)

Embedding an R snippet on your website

Add the following code to your website.

For more information on customizing the embed code, read Embedding Snippets.