How does a time series correlates with its past?

remote control and WarpScript

When working with a time series, one question that sometimes arises is whether it is similar to a past version of itself.

For this purpose, here comes the auto-correlation function (ACF). The ACF is a function of a lag τ, which is the correlation between the time series and itself when shifted back by τ. In other words, the greater the value of the ACF for lag τ, the more the time series correlates with itself when shifted back by τ. This is useful since for example, a high auto-correlation value means that the time series is seasonal.

This very interesting article - that I recommend to read - gives good examples of things you can do with the ACF.

However, since their data is stored in InfluxDB and that its query language is limited (its not a complete programming language like WarpScript™), their whole code is in Python, which introduces a processing overhead due to data conversion and serialization. If you are a user of Warp 10™ and Python, you may already know that this pitfall can be mitigated, see for example our previous articles on the Py4J plugin for Warp 10™ and WarpScript™ in Jupyter notebooks.

Moreover, the ACF can be directly computed in WarpScript™. This is the subject of the following sections. We will give examples using this dataset.

One incentive of doing a bigger part of your processing with WarpScript™ is that it is well integrated with the ecosystem. For example, you can use the integration with Spark to parallelize your warpscript.

Remember that you can reproduce the results on this article and play with this data in no time on the free Warp 10™ sandbox.

Calculating the ACF in WarpScript™

There are multiple way to compute the ACF of a time series in WarpScript™. The easiest is probably by using CORRELATE, which implements the correlation function.

CORRELATE takes 3 arguments:

  1. The input time series (bucketized and without missing values)
  2. A list of time series with which the correlation will be computed: for the ACF we will provide a singleton list with a duplicate of the first argument
  3. A list of lags for which the correlation will be computed

In our case, the result of CORRELATE will be a singleton list containing a GTS. The ticks of this GTS are the lags chosen by the 3rd argument, and its values are the associated ACF values.

For example, let us try it out on hourly temperature measurements in San Francisco:

// Fetching 3 years of data
[ '<insert-your-token-here>' 'temperature' { 'city' 'San Francisco' } NOW -24 365 3 * * ] FETCH
Hourly temperature measurements (in Kelvins) in San Francisco

Now we compute the ACF:

// Ensure 1-hour buckets and interpolate missing values
[ SWAP bucketizer.mean 0 1 h 0 ] BUCKETIZE INTERPOLATE
0 GET 'gts' STORE

// Compute ACF up to 1-year lag
$gts [ $gts ] [ 1 24 365 * <% h %> FOR ] CORRELATE

If we zoom in the result, we see that daily auto-correlation is obvious:

ACF plot zoomed up until 16-day lag. The auto-correlation is very clear every multiple of 1-day lag.

On the global picture, we can also notice a yearly auto-correlation:

Global ACF plot. It draws up to a yearly auto-correlation at the end.

Note that ticks on the horizontal axis are expressed in terms of lags, so that for instance "02 Jan" reads "1-day lag", and "Mar 1970" reads "2-month lag".

The fast ACF in WarpScript™

In the previous section, the computation of the ACF has complexity O(n²), which is prohibitive for most industrial (and bigger) datasets.

Hopefully, a fast approximation of the ACF can also be implemented using the fast fourier transform, that reduces the complexity to O(nlog(n)), according to the discrete case of the Wiener-Khinchin theorem.

Of course, WarpScript™ happens to have the FFT, and its inverse IFFT, ready off-the-shelf!

Let's modify the previous example for fast computation of the ACF:

// Compute the Fast Fourier Transform
$gts STANDARDIZE FFT

// To obtain the fast ACF, we compute the power spectrum and apply the Inverse Fast Fourier transform (Wiener-Khinchin theorem)
LIST-> DROP [ 're' 'im' NULL ] STORE
$re $re * $im $im * + $re $re - IFFT

// We shrink the result to the desired size (1 year), normalize using ACF(0) and rescale it to obtain interpretable results
24 365 * SHRINK DUP 0 ATINDEX 4 GET / 1 h TIMESCALE
Plot of Fast ACF

On the tested dataset, computing the ACF with the first warpscript took about 30s. With the later warpscript, it took only about 34ms, which is approximately 880 times faster.

Conclusion

In this article, we have presented the ACF, a function used to find out if a time series correlates with itself in the past. We showed how to implement it in WarpScript™, with an exact calculation (but slow), and a fast one using the FFT (which accuracy is excellent despite being much faster).

Share