# How do I find multiple change points in an online dataset?

I am trying to develop a Python based script connected to a SQLite3 database to identify distinct system changepoints in an "online" datastream. Changepoint must be identified in less than 2 minutes after occurance. Data is collected every 5 seconds and fed to the sqlite database. Below is a data plot showing a sample data stream with change points manually indentified.

I have reviewed papers discussing Singular Spectrum Analysis Algorithms and Direct Density Estimation to indentify the change points. Admittedly both are over my head and seem complicated from a programing standpoint. I've looked at using a moving mean or variation strategy but false positives show up and some change points have the same mean before and after the change point though its not very common.

Any thoughts on how to find change points given the type of data listed above?

• Your idea of moving averages is promising. Why do you think that the false positives occur? How did you choose the window lengths? Have you tried combining a short-term and a long term moving average? How large your dataset? Is the series you show your only series? Have you tried using the changepoint package in R so you can see what kind of approach might be successful to look into porting in Python? – usεr11852 Nov 17 '15 at 0:37
• The false positives are random anomalies that can occur in each process (I am trying to identify the change in process). Window lengths are somewhat arbitrary at this point. Dataset will be streaming, currently I have several hundred thousand data points with time durations between change points ranging between 3 minutes and 90 minutes. Processes run repeated times with varying durations and times. I have not yet played with R or the Changepoint package, but am looking into it (I have never used R before). Can you expand on the short vs long term moving window? – ghowe Nov 17 '15 at 18:59
• The basic idea behind it that the short term moving average would reflect the new regime/baseline before the long term does that. Or think of it as having two moving averages but the one has points that exponentially increase and the other where the point exponentially decrease. The first one will be affected more from past values and the later one from the most recent values. When their output suddenly diverge you have a changepoint. – usεr11852 Nov 17 '15 at 19:34
• I like the dual moving window idea... simple and elegant! I will play with it and see how it works. Not sure it addresses the false positives but I might be able to recursively eliminate those with the python code. – ghowe Nov 17 '15 at 20:11
• Glad I could help "a bit". I can't see how recursion would eliminate a FP but OK. Regarding your false positives you might want to consider building some sort of "memory" in your system. So only one change point can occur within a specific window. (So as soon as you report a CP you move your windows forward). – usεr11852 Nov 17 '15 at 20:38

Look up

'Iterated Cumulative Sum (CUSUM) Algorithm as per Inclan, C., & Tiao, G. C. (1994). 'Use of Cumulative Sums of Squares for Retrospective Detection of Changes of Variance. 'Journal of the American Statistical Association , 913-923.

• simply providing the reference may be helpful but it is not enough to be considered as an answer for this website. Please provide the gist of the reference. Thanks! – Antoine Jul 8 '16 at 11:21
• There doesn't seem to be change in variance - why are you suggesting this paper? Could you write something more or at least summarize it briefly? – Tim Jul 8 '16 at 11:21

Please find the description of the algorithm called SaRa here. It can be modified and used as an "online" version of Circular-Binary Segmentation algorithm.

HMM can be modified for your purposes (3 states: normal, above and below, after change point the state is switching to normal again, finding its location according to the online points in a robust way).

But you should also understand that your method will have some "resolution" and will not be able to detect short events if your noise level will be large enough.

Again, super-simple method is to look at mean/median ratio within a sliding window.

Also this paper can be considered as an answer.