2
$\begingroup$

We have several time series, which are basiclly chunks of numeric values.

We use Dynamic Time Warping to calculate the distance between these time series. This is working well and gives us some distances like 75.397 or 3752.34.

Our goal is to have somekind of a threshold to determine when two series are "similar". For our test cases (where we know the data) this is currently a fixed threshold like 100.0, where two series are similar when the distance is less than 100.0.

However, since we don't know the actual data and bounds of time series in the future, we cannot assume a fixed threshold for every case.

Our idea for now is to use some probability between 0 and 1 instead, so we can say "these two series have a similarity of 92%".

Is there any common method to map arbitrary distances to such a probability?

Update:

Here is an image of a time series:

enter image description here

This example shows 7 of those chunks. We now want to check the similarity of two of them, e.g. chunk one and chunk three...

$\endgroup$
  • 1
    $\begingroup$ I think the selection of a good method crucially depends on the assumptions you can make about your data. Could you provide more detail on how the data is generated? How much error is in the measurement. Even better could you show some visualizations of several typical time series you work with? $\endgroup$ – Martin Modrák Feb 27 '18 at 16:28
  • $\begingroup$ The data is generated from different sensors like an energymeter and the data is a sequence of the total input power (watt). The only assumption we can say, is that the values are always between 0 and 80, but everything else is unknown. I also added an image. $\endgroup$ – Indivon Feb 28 '18 at 13:01
0
$\begingroup$

Well, this looks like a tough problem :-). A relatively simple approach that could still work would be to bootstrap. This basically means that you generate a large set $X = \{x_1,...x_N\}$ of random chunks (bootstrap samples). You can then approximate your confidence that chunks $a$ and $b$ are the same by the proportion of the bootstrap samples that have larger distance than the distance you observed:

$P(a \sim b) \simeq \frac{|\{x \in X | d(x,b) > d(a,b)\}|}{N}$

This procedure tends to be sensitive to the way you generate the bootstrap samples (the random chunks). In particular you need your bootstrap samples to be representative of the "population" of chunks that may actually occur. A reasonable first approximation might be to generate $X$ by randomly permuting the measurements in $a$ but you may get better results applying some domain - specific knowledge (e.g. it may make sense to permute the differences between successive points or rearrange larger blocks or just shuffle a few values or introduce noise to values, shuffle both $a$ and $b$ with the same permutation etc.).

Update: Just to clarify, the point of the bootstrap in this case is to estimate the distribution of values you would expect, if the data was of the same kind/scale/..., but the chunks were actually different. The method however only partially fulfills the requirements - $P(a \sim b)$ will almost always be at least 0.5 and for actually similar samples you could often get 1 or very close to it.

If the distribution of the distances from the bootstrap looks normal, you can also compute the z-score and the associated p-value, if that is your thing. The z-score also has the advantage that it can give you better resolution when $d(a,b)$ is in the tail of the bootstrap distribution.

$\endgroup$
  • $\begingroup$ Ok, that could be a possibility. I will try that. We have some knowledge: we have some other series (a set of chunks) where we know that they are definetely different, because they were labeled for another energymeter (or metered system) $\endgroup$ – Indivon Feb 28 '18 at 19:29
  • $\begingroup$ @Indivon Just to be clear, I added some more thoughts on the method, hope that helps. $\endgroup$ – Martin Modrák Feb 28 '18 at 20:45

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.