time series similarity heuristic

Question

What is a good heuristic for time series similarity. I'm ok with false positives bc I will then pass the results of the heuristic to an actual series similarity algo. Basically I want the heuristic to (1) be fast AND (2) to filter bad series before the more extensive time series similarity algo is applied to the most probable matching time series.

I've tried Pearson probabilities, Pearson on CUSUM of time series, Kendall probability, Kruskal probability and a few other models. Pearson gives the best results so far.

A problem I have with Pearson probability is that if 1 series is shifted it will not be able to tell that the time series match, so it eliminates some good matches.

I would be ok with using 2 or more FAST heuristics where each one is good at specific cases like say good at finding shifted time series similarities and one good at finding non shifted time series similarities.

This SO question https://stackoverflow.com/questions/6723157/how-to-compare-two-curves-arrays-of-points suggests using Sum of squares.

Any ideas on what heuristic to use?

Answer 1

Perhaps for each pair you want to compare, you can adjust for shift and scale then apply the different methods you mentioned. Specifically,

1. Lets say we want to compare a given pair of time series $T_1,T_2$,
2. Let $\sigma$ be a scale factor and $\tau$ be a shift term.
3. Select an goodness of fit metric between two time series $\theta(T_1,T_2)$ (e.g., LSE, MAD),
4. Find $(\tau^*,\sigma^*):= \min\limits_{\tau,\sigma} \theta(\sigma T_1+\tau,T_2)$
5. Perform a test of correlation. I would have thought that a non-parametric method would be better, but you may find the Pearson method is the best. This will be an empirical exercise, so I can't prescribe anything here.

All of the above can be automated, and each step does not involve a computationally intense algorithm. This might meet your needs.