2
$\begingroup$

I would like to know what is the best approach to detect on-line the occurrences of a new steps or changes in a time series.

I've attached a picture of the time series I'm talking about. I would be able to detect the step indicated by the red arrow.

enter image description here

Each data point is collected every 2 seconds and I need to detect the changes in the time series as quick as possible, i.e. considering at most 5 samples ahead and avoiding if it is possible the outliers.

I'm completely stumped on how I might be able to do this - any ideas?

I have read something on Bayesian Analysis but before studying in depth I would like to know if there are other useful approach in term of detection speed, robustness to outliers and detection accuracy.

Thanks for your help.

|cite|improve this question
$\endgroup$
  • 2
    $\begingroup$ Possible duplicate of Determine breakpoints in time series data where values change significantly $\endgroup$ – Aksakal Oct 14 '15 at 13:49
  • $\begingroup$ @Aksakal This question differs from the apparent duplicate in that it requires the changepoints to be detected without looking too far ahead. $\endgroup$ – whuber♦ Oct 14 '15 at 15:07
  • $\begingroup$ It's impossible to do. Look at x=1444739000. There's no way to distinguish this jump from the marked point in 5 secs. It takes at least 20 secs. $\endgroup$ – Aksakal Oct 14 '15 at 19:37
  • $\begingroup$ I know that it is impossible in 5 seconds, but I have written in 5 samples where each sample is taken every 2 seconds. But the problem is that I need to detect a abrupt changes (the beginning and the end) in a short time, where a time series has this changes only when there are an abrupt changes in the workload to. $\endgroup$ – ugogiordano Oct 14 '15 at 21:18
1
$\begingroup$

Bayesian filter under the markov-chain assumption is the best tool for this kind of question. The basic idea is to use the past sampling to get your prior, then try to predict the current sample. The online detection is done by threshold on the prediction error.

Things like Kalman filter or particle filter is fairly easy to implement. Depending on what computer language you are familiar with, there are many parkage you can use out of the box.

|cite|improve this answer
$\endgroup$
  • $\begingroup$ Can you suggest me any example in R, applicable only a single vector which represents my time series? $\endgroup$ – ugogiordano Oct 14 '15 at 14:39
1
$\begingroup$

(Edited as per comments below)

Generalized fluctuation tests (GFL) (Kuan and Hornik 1995; Kuan 1998) and F tests (Hansen 1992; Andrews 1993; Andrews and Ploberger 1994) are of the most important classes of tests on structural change. Zeileis 2002 has reviewed such tests for monitoring structural change where new observations arrive over time.

References,

C.-M. Kuan and K. Hornik. The generalized fluctuation test: A unifying view. Econometric Reviews, 14, 135-161, 1995.

C.-M. Kuan. Tests for changes in models with a polynomial trend. Journal of Econometrics, 84, 75-91, 1998.

B. E. Hansen. Tests for parameter instability in regressions with I(1) processes. Journal of Business & Economic Statistics, 10:321–335, 1992.

D. W. K. Andrews. Tests for parameter instability and structural change with unknown change point. Econometrica, 61:821–856, 1993.

D. W. K. Andrews and W. Ploberger. Optimal tests when a nuisance parameter is present only under the alternative. Econometrica, 62:1383–1414, 1994.

A. Zeileis, F. Leisch, K. Hornik, and C. Kleiber. strucchange: An R package for testing for structural change in linear regression models. Journal of Statistical Software, 7(2):1–38, 2002.

And try this implemented tool that performs online change detection?

strucchange: Testing, Monitoring, and Dating Structural Changes

|cite|improve this answer
$\endgroup$
  • $\begingroup$ This should be a comment. $\endgroup$ – gung♦ Oct 14 '15 at 15:24
0
$\begingroup$

The preferred approach is to use Intervention Detection procedures which can incorporate any appropriate ARIMA structure while isolating anomalies (pulses) . One can set the minimum, number in a group ( in your case 5 ) while also being able to optionally set a minimum change in step/level change that may be required in order to avoid false positives. The user simply specifies a level of confidence.

|cite|improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.