# Finding repeating patterns and their periods

I have a list of user-generated events stored together with the time it occurred. FWIW, the average is 216 event per day and a total of approximately 800000 events.

My goal is simply to find the repeating patterns and their periods and how they evolve through time. I expect to find at least two patterns with a period of 24 hours, 7 days, and maybe a third with a period of 1 year. But the interesting thing would be, of course, if I find more patterns.

I tried to count the number of event per hour and use a Fourier transform or an autocorrelation on that "signal", but none of those methods are completely satisfactory.

## Fourier Transform

My first thought was to aggregate the events per hour and plot a spectrogram from a short-term Fourier transform. Here is the result.

It works quite well, it shows a sharp line for 24 hours and some kind of line for 168 hours (7 days). But the major drawback is the period-resolution. It produce a very low resolution for large periods, and so much information for short periods that I any peak would be averaged out on the plot. If I try increase the blocksize to get a better precision for large periods, I would also increase the number of data points for short periods, which quickly become unmanageable in terms of CPU and memory needed to plot all that data.

## Autocorrelation

The second idea was to use an autocorrelation between a chunk and half of the chunk and only keep the values where there is a total overlap (called "valid" mode in numpy). This should show a high value for a lag equal to the period of a repeating pattern. Here is the result.

With this, I only get integer periods (which is fine), but the plot doesn't show peaks as sharp as the Fourier transform does. And it doesn't really show that there is a pattern every 168 hours, which limit its usefulness.

## Other idea

I'm open to any suggestion about another method. Here is one that might just be a stupid random thought. Why not make a continuous model of the event occurence with a kernel density estimate for instance, take its (continuous) Fourier transform, and then discretize this as I want? Any opinion on that? Here is the link to the math question exploring this idea.

Another idea might be to use some kind of hierarchical autocorrelation. In order to sharpen the peaks and weaken the repeats.

• You should add the seasonality tag. What is your "signal", i.e. what would be the $x$ axis in a $x[t]$ plot? If you have expected periods, then generic fourier analysis is probably not the way to go. – GeoMatt22 Sep 26 '16 at 0:37
• @GeoMatt22 I edited the question. Hope it's clearer. I indeed expect some periods to show up. I saw them by specifically looking for them. But I would want a more general method to show all the repeating patterns, even if they have a slightly changing period over the time. – Celelibi Sep 26 '16 at 1:19
• For a given period $T$, you can fit a sinusoid with a simple linear least squares, so it is easy to refine a periodogram peak using scalar optimization to search over $T$ values in the coarse-periodogram bin. (Roughly as described here, but I would definitely take advantage of the fact that the optimization is "separable".) – GeoMatt22 Oct 7 '16 at 3:28