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). A typical use case of DTW 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.

  • $\begingroup$ Please comment if any additional data or clarification is needed. Please also comment if my initial question and the alternative should be broken into two questions. $\endgroup$ – JFBM Nov 12 '15 at 8:34
  • $\begingroup$ No explanation of DTW here. Those who have no idea what it means (e.g. me) won't be answering but they might be interested in a minimal explanation. I am not clear either whether those might answer will understand what your data are precisely. Examples never hurt. $\endgroup$ – Nick Cox Nov 12 '15 at 8:58
  • $\begingroup$ @Nick Sorry, hope it is more understandable now. I haven't found a specific DTW-Tag, otherwise I'd have used it. $\endgroup$ – JFBM Nov 12 '15 at 10:13

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]])

    return cost[-1, -1], path

Which does indeed yield:

a = [1, 2, 3, 4] 
b = [1, 2, 2, 3, 4]

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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.