How to detect trend changes in noise time series?

Question

wget -q -O- https://i.sstatic.net/xczQ1.gif | tail -c +43

R> with(f, plot(x, log10(y), type='l'))

I have a series whose data is above. It obviously has two parts (separated at around x=1100). What is the most appropriate way to detect such a change in this noisy time series and fit two connected straight line segments to it?

EDIT: It looks like a method along the line of the convex hull would probably be more appropriate? For example, one can start with the lowest-most point and find the edges to the left and right of the lowest point in the convex hull. This way the two segments of support from the above of the points can be easily determined.

Any better ideas?

I don't think the method mentioned by DavidGibson makes the most sense on this dataset.

Answer 1

I believe you are looking for Change point detection or Change Detection. One of the more common models for this is CUSUM Model.

There is also a pretty good notebook tutorial for Facebook's new Kats library that I recommend taking a look at.

• Kats 202 - Detection with Kats

Answer 2

There are quite a few algorithms. The simplest is (I believe I have the name right) Wild Binary Regression segmentation. Here our goal is to identify a place to split our time series into 2 and fit a regression for each with connectivity constraints. Then we get the residuals and fit on those and combine the two models (this is gradient boosting) then get residuals and fit again and so on and so forth until some criteria, either a number of changepoints or some criteria which typically takes into account the number of points like maybe the AICC with k replaced with the number of changepoints found. I believe that is the algorithm although I approach it from a pure gradient boosting perspective in this bit of messy code for python: https://github.com/tblume1992/ThymeBoost

I do have a much cleaner implementation on pip but there is no documentation for it yet but I have written out some other answers using it. Of course this is in python but the underlying algorithm of boosting with binary-segmented regressions is easy enough to whip up in r.

One issue with your data specifically is that the connectivity constraints may not work too nicely since the drop and increases are so drastic. So you may want to relax that constraint to allow it to have a intercept that is different then the other segment and just make sure you add that extra parameter (the new intercept) to whatever cost function that is monitoring everything.

Answer 3

Eyeballing the time-series suggests discontinuities at t=1100 and t=2100. My recommendation would be to try something like total variation denoising. In total variation denoising, we are trying to solve the following optimization problem: \begin{align} \min_{\mathbf{x}} \frac{1}{2} ||\mathbf{y} - \mathbf{x}||_2^2 + \lambda ||\mathbf{D} \mathbf{x}||_1 \end{align} where \begin{align} \mathbf{D} = \begin{bmatrix} -1 & 1 & & & \\ & -1 & 1 & & \\ & & \ddots & & \\ & & & -1 & 1\end{bmatrix} \end{align} The matrix operation $\mathbf{D} \mathbf{x}$ imposes a sparsity constraint on the first-order difference of the input signal. On solving for $\mathbf{x}$ with an appropriate regularization constant $\lambda$ and taking the first-order difference, i.e., $\mathbf{D} \mathbf{x}$, should generate spikes at the change points. Applying an appropriate threshold and determining the location of spikes that are above the threshold should help you solve the problem.

Answer 4

This should be good for your needs. It works well but often needs fine tuning of the control parameters

https://rdrr.io/cran/trendsegmentR/man/trendsegment.html

Based on the paper: H. Maeng and P. Fryzlewicz (2021), Detecting linear trend changes in data sequences https://arxiv.org/abs/1906.01939