5
$\begingroup$

I am trying to find the similarity between two time series, but not in terms of distance, in something more sensible such as percentage of similarity. In other words I need something that shows the similarity, not dis-similarity.

The dynamic time warping gives a very good response, when trying to compare the time-series. But the distance computed by dynamic time warping depends on the duration of the time series and the magnitude of the template and the query. Moreover, it shows the distance, which demonstrates the dis-similarity.

Is there a way to convert the distance from DTW into some form of normalized similarity measure?

$\endgroup$
4
$\begingroup$

Sure. There's a straightforward way to convert an unnormalized distance metric into a normalized similarity measure. Basically, use

$$S(x,y) = \frac{M - D(x,y)}{M},$$

where $D(x,y)$ is the distance between $x$ and $y$, $S$ is the normalized similarity measure between $x$ and $y$, and $M$ is the maximum value that $D(x,y)$ could be.

In the case of dynamic time warping, given a template $x$, one can compute the maximum possible value of $D(x,y)$. This will depend on the template, so $M$ becomes $M(x)$, and the formula becomes

$$S(x,y) = \frac{M(x) - D(x,y)}{M(x)}.$$

So how do you compute $M(x)$? Basically, multiply the length of the template (the number of samples in the time series), times the maximum value of each sample. If each sample is in the range $[0,1]$, then the maximum value of each sample is 1, so $M(x)$ becomes just the length of $x$. This gives a simple upper bound on $D(x,y)$. [Trivia: in fact one could compute a slightly tighter upper bound, but in practice that's probably not necessary.]

It is easy to verify that the similarity measure is always in the range $[0,1]$ and thus is normalized as you were hoping for.

$\endgroup$
  • 1
    $\begingroup$ Thank you very much. The measure of similarity is very intuitive and nice. I have a couple of questions: 1- Why this multiplication (length (templaye)*max(template)) results in the farest distant? 2- We are talking about absolute maximum, right? $\endgroup$ – Amin Ghaderi Feb 18 '16 at 15:56
  • 1
    $\begingroup$ I think we should some hoe take the magnitude of the signal being checked against the sample into account. Let's assume the following condition: a=[1,2,3,4,5] Then the time-series that result in highest distance will be: b=[25,25,25,25,25]% from max(a)*length(a) The result DTW distance is: 49.29 But if we now just increase b by 1: b2=[26,26,26,26,26], we reach to even higher distance = 51.52. Am I missing some thing here? $\endgroup$ – Amin Ghaderi Feb 18 '16 at 16:06
  • 1
    $\begingroup$ @AminGhaderi, it's easiest to think about it in the case where each sample in the time series is required to be in the range $[0,1]$. In practice usually each sample must come from some bounded range -- the samples can't be arbitrarily large -- so they can be normalized to the range $[0,1]$. $\endgroup$ – D.W. Feb 18 '16 at 17:53
  • 1
    $\begingroup$ This is great. Thank you for the very nice responses. How about if the magnitude (range) of the time series is also an informative feature for this specific application. In other words, we might have two time distinctive time series that have same shape (i.e. negligible distance if normalized to [0,1]), but since their magnitude is different, they have different they are not the same. $\endgroup$ – Amin Ghaderi Feb 18 '16 at 18:25

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.