How well does DTW handle additional data?

Question

I have two time-series which I want to compare.

My first time-series is the ideal solution to my problem, the second is the time-series to check.

I know that in the second series the user might have repeated an action because he failed it when trying first. See also experiment-setup below.

Can DTW/How well does DTW handle this additional data?

---

Alternative: Break first time series into pieces and match them with subsequence DTW against second series. Assure order of subsequences is preserved. How well would that work?

---

Setup: A person is standing on a Wii balance board and tries to guide a marble through a maze. There is only one possible path from start to end, but multiple dead ends. The user can miss the optimal path at for example a T-junction. Instead of turning into the Junction he moves forward and backward along the straight path before turning. This generates movement not present in the optimal solution, but the user approaching the T-Junction and leaving it can be found in the optimal solution.

---

EDIT: In time series analysis, dynamic time warping (DTW) is an algorithm for measuring similarity between two temporal sequences which may vary in time or speed. (From Wikipedia). Basically DTW stretches the sequences to match each other as close as possible. It is required for example in speech recognition where People may speak in different speed (or in my case move with different speed). Taken from Wikipedia

The german Wiki-Page for DTW also contains a nice graphical explanation of the pathfinding in DTW. This site provides a somewhat lengthy, but well readable explanation with Implementation-Details.

Answer 1

If I understood correctly, "additional data" is random insertion of datapoint $X(t)$ in between the datapoints $X(t)$ and $X(t+1)$ such as in:

original: a = [1, 2, 3, 4]

additional_data: b = [1, 2, 2, 3, 4]

In this case, DTW handles additional data very well, as the distance between those two time-series is 0. They are - in means of DTW - considered equal. This works since DTW allows mapping of multiple points of the query to a single point of the reference time-series.

Limitations can arise from further constraints on DTW such as explained in this presentation in slide 14ff.

To prove my answer, I used this implementation in Python and modified it a little such as:

import numpy as np
def DTW(A, B, window = np.inf, d = lambda x,y: abs(x-y)):
    # create the cost matrix
    A, B = np.array(A), np.array(B)
    M, N = len(A), len(B)
    cost = np.inf * np.ones((M, N))

    # initialize the first row and column
    cost[0, 0] = d(A[0], B[0])
    for i in range(1, M):
        cost[i, 0] = cost[i-1, 0] + d(A[i], B[0])

    for j in range(1, N):
        cost[0, j] = cost[0, j-1] + d(A[0], B[j])
    # fill in the rest of the matrix
    for i in range(1, M):
        for j in range(max(1, i - window), min(N, i + window)):
            choices = cost[i - 1, j - 1], cost[i, j-1], cost[i-1, j]
            cost[i, j] = min(choices) + d(A[i], B[j])

    # find the optimal path
    n, m = N - 1, M - 1
    path = []

    while (m, n) != (0, 0):
        path.append((m, n))
        m, n = min((m - 1, n), (m, n - 1), (m - 1, n - 1), key = lambda x: cost[x[0], x[1]])

    path.append((0,0))
    return cost[-1, -1], path

Which does indeed yield:

a = [1, 2, 3, 4] 
b = [1, 2, 2, 3, 4]
DTW(a,b)

(0.0, [(3, 4), (2, 3), (1, 2), (1, 1), (0, 0)])