# How to group similar patterns together that are shifted along the x axis?

I have a set of time series plots that are shifted along the x-axis. I am looking for an algorithm using which I can group them together. My end goal is to average them.

While reviewing the literature on this topic, I found out that Fourier Transforms might help. Since all the patterns have a similar shape, I might be able to detect initial changes in frequency for each pattern and then group them all together. I was hoping that someone could elaborate on whether my approach is correct. I am also open to other approaches that could tackle this problem.

• Did you encounter the concept of "Dynamic type warping" (DTW)? – Laurent Duval Jul 14 at 19:14
• @LaurentDuval Yes, I did. DTW won't work in this case because the time series are too long and DTW has a time complexity of O(n^2). Since all these patterns are exactly similar, I am looking for a method that is much more facile than DTW. Anyway good point! – DGT Jul 14 at 19:16
• The length of the signals (and subsequent complexity) was not apparent initially. Due to their morphology, the signals are likely to endure subsampling. And the scale transform or representation? ee.columbia.edu/~dpwe/papers/Cohen93-scale.pdf – Laurent Duval Jul 14 at 19:21
• @LaurentDuval I went over the paper but I don't quite understand how it is relevant to the problem above? Could you please elaborate? – DGT Jul 14 at 19:28
• Your signals don't seem to shift only, but scale as well – Laurent Duval Jul 14 at 19:38

I'm a little confused about your plots. You say it is a time series plot, yet there are several places where your rises and falls "bend backward" so they aren't functions at all. I assume time is not going backward at those moments, so are these complex plane plots?

Disregarding that for a moment. You have a characteristic shape, so I think your best approach is to extract some characteristic values and use those for your comparisons. Prior to doing that, I would also recommend that your "smooth" your shapes to reduce the impact on any noise/jaggedness in your data.

Assuming they are a time series, x[n], with evenly in time sampled points, I would run a differentiating filter on them and locate the three points the define the top of the "M". It also looks like you have a local minimum ahead of the initial rise and one following the terminal fall. Locating those will give you five calibration points for each graph to align them along the x axis. The best displacement value can be found by doing a least squares fit. If they need to be rescaled, it get a little bit more complicated, but still doable.

Same is true for vertical rescaling.

For the smoothing and differentiating, my technique of choice is to do a forward exponential smoothing, a backward exponential smoothing, then average the two for a smoothed function, and subtract the forward from the backward to get a smoothed "derivative". It's not exactly the derivative, but close. Details in this article of mine:

Basically, any smoothing or differentiating technique you choose should work as you are looking for characteristic values and as long as you apply the same approach to each graph you will get consistent compare-able results.

If you are looking to find parametric equations that define your characteristic shapes, then want to compare parameters, that's a different topic. If you do, I would align them as much as possible on the location of characteristic points first for better results. Fourier series would be good for that.

That should get you started.

Ced