Map distance between two time series to a probability

Question

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:

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...

Answer 1

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.