52

For data that is known to have seasonal, or daily patterns I'd like to use fourier analysis be used to make predictions. After running fft on time series data, I obtain coefficients. How can I use these coefficients for prediction?

I believe FFT assumes all data it receives constitute one period, then, if I simply regenerate data using ifft, I am also regenerating the continuation of my function, so can I use these values for future values?

Simply put: I run fft for t=0,1,2,..10 then using ifft on coef, can I use regenerated time series for t=11,12,..20 ?

BBSysDyn
  • 4,389
  • 8
  • 48
  • 63

4 Answers4

60

I'm aware that this question may be not actual for you anymore, but for others that are looking for answers I wrote a very simple example of fourier extrapolation in Python https://gist.github.com/tartakynov/83f3cd8f44208a1856ce

Before you run the script make sure that you have all dependencies installed (numpy, matplotlib). Feel free to experiment with it. enter image description here P.S. Locally Stationary Wavelet may be better than fourier extrapolation. LSW is commonly used in predicting time series. The main disadvantage of fourier extrapolation is that it just repeats your series with period N, where N - length of your time series.

Community
  • 1
  • 1
tartakynov
  • 2,768
  • 3
  • 26
  • 23
  • So, sorry just making sure I understand. x (blue line) is the observed data? extrapolation (red line) is the prediction? – jeffery_the_wind Apr 01 '15 at 15:56
  • @jeffery_the_wind Yes, the red line is the prediction and blue is observed data. Obviously there is overfitting in this example, to avoid that you can adjust the number of harmonics in the model. – tartakynov Apr 01 '15 at 17:05
  • 11
    This good visual example demonstrates the weakness pointed out in the other posts: the frequency domain, by its nature, produces fixed cycles in the time domain. The red line extrapolation above is simpy a copy of the beginning segment of the blue (observed) line, albeit de-noised slightly. Therefore, to do any meaningful short-term prediction over horizon *h* time units, where *h* ≪ the number of historical observations, only the most significant **high** frequency coefficients should be used in the extrapolation. A "high" frequency threshold can be arbitrarily defined in relation to *h*. – Special Sauce May 30 '15 at 20:26
  • 1
    To further clarify my previous comment, the extrapolated red hump at time ~350 is just a copy of the blue hump at ~50. If the historical period had instead been initiated right before the hump at 50, then the very first predicted units would have that hump copy, which seems a bit silly and arbitrary. Thus, by either eliminating and down-weighting the lower frequency components, we can reduce the arbitrariness induced by the historical data starting point. – Special Sauce May 30 '15 at 20:41
  • I'm a bit confused by this script, mainly the line that reads `for i in indexes[:1 + n_harm * 2]:` you sort the indices by frequency value before doing this, guaranteeing that you get the `n_harm` lowest frequencies. Would you not want the `n_harm` frequencies associated with the highest peaks instead? Should the indices not be sorted by absolute value of `x_freqdom `? Maybe I misunderstand but that seems to be the best way to denoise. – Mike Jul 21 '15 at 15:31
  • @Mike you're right, I wanted to extract lowest frequencies as I suggested that they're best describe cycles and periods in the data, while highest frequencies usually are noise. And of course, this suggestion may be wrong in your case – tartakynov Jul 22 '15 at 16:22
30

It sounds like you want a combination of extrapolation and denoising.

You say you want to repeat the observed data over multiple periods. Well, then just repeat the observed data. No need for Fourier analysis.

But you also want to find "patterns". I assume that means finding the dominant frequency components in the observed data. Then yes, take the Fourier transform, preserve the largest coefficients, and eliminate the rest.

X = scipy.fft(x)
Y = scipy.zeros(len(X))
Y[important frequencies] = X[important frequencies]

As for periodic repetition: Let z = [x, x], i.e., two periods of the signal x. Then Z[2k] = X[k] for all k in {0, 1, ..., N-1}, and zeros otherwise.

Z = scipy.zeros(2*len(X))
Z[::2] = X
Steve Tjoa
  • 59,122
  • 18
  • 90
  • 101
  • 1
    So you are repeating most important coefficients in Z (twice in the above example), and if use ifft to regenerate my time series, this new series will be longer than the original and by definition will have predictions in it. – BBSysDyn Dec 18 '10 at 20:28
  • 1
    I guess by denoising you mean picking the most important coefficients. – BBSysDyn Dec 18 '10 at 20:30
  • 1
    `Z = [X[0], 0, X[1], 0, X[2], 0, ..., X[N-1], 0]`. If that's what you mean, then yes. And yes, preserving the most important coefficients will have a "smoothing" or "blurring" or "denoising" effect on the signal. – Steve Tjoa Dec 18 '10 at 20:46
  • I just realized I can keep calling Y[ctr] * (np.cos(x*ctr*2*pi/N) + 1j*np.sin(x*ctr*2*pi/N)) where x is new values and Y is coefficients, and ctr is coef indexes, and add this up; this will essentially forecast. What do you think? – BBSysDyn Dec 18 '10 at 20:58
  • Yes, that is basically isolating a single complex sinusoid in the time domain. But the answer will be complex. You also need the component `Y[N-ctr]` in order to get a real signal. (`x` is a real signal iff `X` has conjugate symmetry, i.e., `X[k] = X*[-k]`.) – Steve Tjoa Dec 18 '10 at 21:34
10

When you run an FFT on time series data, you transform it into the frequency domain. The coefficients multiply the terms in the series (sines and cosines or complex exponentials), each with a different frequency.

Extrapolation is always a dangerous thing, but you're welcome to try it. You're using past information to predict the future when you do this: "Predict tomorrow's weather by looking at today." Just be aware of the risks.

I'd recommend reading "Black Swan".

duffymo
  • 305,152
  • 44
  • 369
  • 561
  • 2
    I read Black Swan. I am not talking about stock prices necessarily. Let's say .. harvesting data, which is very seasonal, or the famous sunspots data. So I am talking about something predictable. – BBSysDyn Dec 18 '10 at 18:53
  • Let me clarify little further: Let's say I pinpointed a frequency that is pretty dominant in the data. How do I tie this back to points in the time domain data, so I can jump ahead and in the future and do prediction. – BBSysDyn Dec 18 '10 at 18:56
  • 2
    +1. Extrapolation is dangerous, yes. Usually, people make models, and assume that the future will behave like the model says. Models depends on parameters, which are estimated with present or past observations. So you don't "predict" anything, you only fit a model. – Alexandre C. Dec 18 '10 at 18:57
  • @user: this is a very difficult and probably too broad question. – Alexandre C. Dec 18 '10 at 18:57
  • 2
    @Alexandra C: I am talking about data that is known to repeat itself. – BBSysDyn Dec 18 '10 at 18:59
3

you can use the library that @tartakynov posted and, to not repeat exactly the same time series in the forcast (overfitting), you can add a new parameter to the function called n_param and fix a lower bound h for the amplitudes of the frequencies.

def fourierExtrapolation(x, n_predict,n_param):

usually you will find that, in a signal, there are some frequencies that have significantly higher amplitude than others, so, if you select this frequencies you will be able to isolate the periodic nature of the signal

you can add this two lines who are determinated by certain number n_param

h=np.sort(x_freqdom)[-n_param]
x_freqdom=[ x_freqdom[i] if np.absolute(x_freqdom[i])>=h else 0 for i in range(len(x_freqdom)) ]

just adding this you will be able to forecast nice and smooth

another useful article about FFt: forecast FFt in R

Pablo
  • 3,135
  • 4
  • 27
  • 43
  • Hi the link you have provided is broken. Can you please post again if possible or If you have? Thank you. – dhinar1991 Aug 22 '17 at 06:21
  • 1
    @DhivyaNarayanasamy fixed ;) – Pablo Aug 22 '17 at 17:40
  • Very interesting but wouldn't you want to bias the prediction with more weight on the last half (more recent) values given? That is try this with data that is a flat line for the first half but a slopped line for the other half. The sloped line should have more emphasis that the flat part. – anthony Mar 29 '18 at 06:04