initialize_plane: Initialize and navigate in the plane of possible fits

In IncDTW: Incremental Calculation of Dynamic Time Warping

Initialize and navigate in the plane of possible fits

Description

Initialize and navigate in the plane of possible fits to detect subsequences (of different lengths) in a long time series that are similar (in terms of DTW distance) to a query pattern: Initialize the plane of possible fits as .planedtw object. Increment and decrement the time series observations and respective DTW calculation. Reverse the time order to increment or decrement observations at the other end of the time horizon. Refresh the DTW calculation without changing the time series.

Usage

initialize_plane(Q, C, dist_method = c("norm1", "norm2", "norm2_square"),
                 step_pattern = c("symmetric2", "symmetric1"), ws = NULL)


## S3 method for class 'planedtw'
increment(x, newObs, direction = c("C", "Q"), ...)

## S3 method for class 'planedtw'
decrement(x, direction = c("C", "Q", "both"), 
          refresh_dtw = FALSE, nC = NULL, nQ = NULL, ...)

## S3 method for class 'planedtw'
refresh(x, ...)

## S3 method for class 'planedtw'
reverse(x, ...)

is.planedtw(x)  

Arguments

Q	a time series (vector or matrix for multivariate time series)
C	a time series (vector or matrix for multivariate time series)
dist_method	character, describes the method of distance measure. See also dtw.
step_pattern	character, describes the step pattern. See also dtw.
ws	integer, describes the window size for the sakoe chiba window. If NULL, then no window is applied. (default = NULL)
x	object of class planedtw (output from initialize_plane)
newObs	a time series (vector or matrix for multivariate time series). If Q and C are vectors, newObs must be a vector. If Q and C are matrices with nc columns, then newObs must also have nc columns. See details for the correct time order of newObs.
direction	character, gives the direction of increment or decrement. decrement() is a wrapper for dtw_partial and the direction parameter is translated to the respective partial_Q and partial_C parameters.
refresh_dtw	logical (default = FALSE), after decrementing the time series, should the DTW calculation be refreshed, or not.
nC	integer, default = NULL, if not NULL, then decrement subsets the time series C to the range of 1:nC, drops invalid interim calculation results, and refreshes if refresh_dtw = TRUE.
nQ	analog to nC
...	additional arguments (currently not used)

Details

All functions are wrapper functions for idtw2vec and dtw_partial.

• initialize_plane calculates the DTW distance between Q and C and saves the last column and row of the global cost matrix. It returns an object of class planedtw that contains all necessary information to incrementally update the DTW calculation with new observations. Also for decrementing the calcultions for skipping some observations at the end.

• increment updates the DTW calculation by appending new observations to C or Q (depends on the parameter direction) and calculating DTW by recycling previous results represented by gcm_lc_new and gcm_lr_new. A wrapper for idtw2vec

• decrement is a wrapper for dtw_partial and also returns a planedtw object.

• refresh serves to recalculate the gcm_lc_new and gcm_lr_new from scratch, if these objects are NULL (e.g. after decrementing with refresh_dtw = FALSE).

• reverse reverses the order of Q and C, and refreshes the calculation for the new order. This is useful for appending observations to Q or C at the other end, the beginning. For incrementing in the reverse order also apply the function increment. Then the time series in the parameter newObs also needs to be in reverse order. Assent et al. (2009) proved that the DTW distance is reversible for the step pattern "symmetric1", so dtw(Q, C) = dtw(rev(Q), rev(C)). Also see examples. For the step pattern "symmetric2" DTW is not exactly reversible, but empirical studies showed that the difference is realtive small. For further details please see the appendix A of the vignette "IncDTW: An R Package for Incremental Calculation of Dynamic Time Warping" on CRAN.

Value

distance	the DTW distance
normalized_distance	the DTW distance devided by the sum of the lengths of Q and C (see also dtw).
gcm_lc_new	the last column of the new global cost matrix
gcm_lr_new	the last row of the new global cost matrix
Q	the time series
C	the time series
control	list of input parameters and the lengths of the time series

References

• Leodolter, M.; Pland, C.; Brändle, N; IncDTW: An R Package for Incremental Calculation of Dynamic Time Warping. Journal of Statistical Software, 99(9), 1-23. doi: 10.18637/jss.v099.i09

• Assent, Ira, et al. "Anticipatory DTW for efficient similarity search in time series databases." Proceedings of the VLDB Endowment 2.1 (2009): 826-837.

Examples

## Not run: 

#--- 1. example: Increment too far and take a step back:
rw <- function(nn) cumsum(rnorm(nn))
Q <- sin(1:100)
C <- Q[1:90] + rnorm(90, 0, 0.1)
WS <- 40


# start with the initial calculation
x <- initialize_plane(Q, C, ws = WS)

# Then the incremental calculation for new observations
y1 <- Q[91:95] + rnorm(5, 0, 0.1)# new observations
x <- increment(x, newObs = y1)

# Again new observations -> just increment x
y2 <- c(Q[96:100] + rnorm(5, 0, 0.1), rw(10))# new observations
x <- increment(x, newObs = y2)

# Compare the results with the calculation from scratch
from_scratch <- dtw2vec(Q, c(C, y1, y2) , ws = WS)$normalized_distance
x$normalized_distance - from_scratch
plot(x)

# The plot shows alignments of high costs at the end 
# => attempt a decremtal step to find better partial matching
x <- decrement(x, direction = "C", refresh_dtw = TRUE)
x
plot(x)


#--- 2. example: First increment, then reverse increment
rw <- function(nn) cumsum(rnorm(nn))
Q <- rw(100)
C <- Q[11:90] + rnorm(80, 0, 0.1)
WS <- 40

# initial calculation
x <- initialize_plane(Q, C, ws = WS)
plot(x)

# incremental calculation for new observations that 
# are appened at the end of C
y1 <- Q[91:100] + rnorm(10, 0, 0.1)
x <- increment(x, newObs = y1)

# reverse the order of Q and C
x <- reverse(x)

# append new observations at the beginning: the new
# obervations must be in the same order as Q and C 
# => so newObs must be in reverse order, so y2 is 
# defined as Q from 10 to 6 (plus noise).
y2 <- Q[10:6] + rnorm(5, 0, 0.1)
x <- increment(x, newObs = y2)

# another incremental step in the reverse direction
y3 <- Q[5:1] + rnorm(5, 0, 0.1)
x <- increment(x, newObs = y3)

# compare with calculations from scratch, and plot x
from_scratch <- dtw2vec(rev(Q), rev(c(rev(y3), rev(y2), C, y1)),
                        ws = WS)$distance
x$distance - from_scratch
print(x)
plot(x)


## End(Not run)

IncDTW documentation built on March 18, 2022, 6:43 p.m.