6
$\begingroup$

I am performing a comparison among time series by using Dynamic Time Warping (DTW). However, it is not a real distance, but a distance-like quantity, since it doesn't assure the triangle inequality to hold.

Reminder:d:MxM->R is a distance if for all x,y in M:

1 - d(x,y) ≥ 0, and d(x,y) = 0 if and only if x = y
2 - It is symmetric: d(x,y) = d(y,x)
3 - Triangle inequality: d(x,z) ≤ d(x,y) + d(y,z)

There is any equivalent measure that ensures the condition of distance in a matemathical sense? Obviously, I am not looking for a Euclidean distance, but one that ensures the proper classification of my series in a future clustering. If so, there is any solid implementation in a R or Python package?

Improve this question
$\endgroup$
3
  • $\begingroup$ What about of the average of the DTW in both directions? $dist(x, y) = \frac{1}{2}(DTW(x,y) + DTW(y,x))$. $\endgroup$
    – noe
    Commented Mar 26, 2018 at 10:39
  • $\begingroup$ Why does that ensure the triangle inequality? I see it ensures symmetry when there is not (but in this case there is) $\endgroup$
    – Ripstein
    Commented Mar 26, 2018 at 11:13
  • $\begingroup$ I stand corrected, thanks. I DID address the actual question, by noting that DTW IS a real measure. $\endgroup$
    – Eamonn Keogh
    Commented Mar 30, 2018 at 4:58

2 Answers 2

Reset to default
3
+50
$\begingroup$

Like suggested in one answer on this SO question, you could use elastic matching with Levenshtein distance to your task. Levenshtein distance obeys triangle inequality and is therefore a metric distance.

Use of elastic matching was suggested for time series data comparison. Levenshtein distance works with characters data.

There is an implementation of elastic matching and Levenshtein distance calculation in Python.

To put them together you most probably need to build your own implementation.

Improve this answer
$\endgroup$
-1
$\begingroup$

When you say "However, it is not a real distance, but a distance-like quantity," you really mean, it is a measure, not a metric.

Why do you think you need a metric?

Consider the following common American girl names:

[Lisabeth, Beth, Lisa, Maryanne, Anne, Mary]

If asked to cluster these names into two groups, we would surely expect [{Lisabeth, Lisa, Beth}, {Maryanne, Mary, Anne}].

However, no distance measure that insists on the triangular inequality would give us “Beth” and “Lisa” in the same group; since they do not share a single character with each other. Yet, both share one character with “Anne”.

There is a tutorial on DTW here http://www.cs.unm.edu/~mueen/DTW.pdf

Improve this answer
$\endgroup$
2
  • 1
    $\begingroup$ The bold paragraph is false. Define d(x, y) to be the length of shortest chain of words from the given word set where two words are connected if one is a substring of the other. If there is no such chain, let d(x, y) be the total number of words in the set. This is a metric (triangle inequality holds) and it clusters the names in your example exactly as expected. Metrics don't have to be based on counting characters. Also, this does not address the actual question. $\endgroup$
    – user380
    Commented Mar 27, 2018 at 19:05
  • $\begingroup$ I agree on the point @SFTP made, I don't see why a PAM with Euclidean distance (a real distance) wouldn't give us the clusters you proposed, taking Lisabeth and Maryann as the 2 medoids. $\endgroup$
    – Ripstein
    Commented Mar 28, 2018 at 6:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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