# How to detect trend changes in noise time series?

wget -q -O- https://i.stack.imgur.com/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.

• Do you know the shape of the time series (negative slope followed by an abrupt change to a plateau followed by...) or should the change point detection algorithm be more general? Nov 25, 2021 at 21:00
• why not "simply" using a moving average and track the standard deviation of it?
– Ben
Jul 21, 2022 at 12:57

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.

• Are you sure it works on this test data. The examples in the Kats link do not look alike to my example. Aug 17, 2021 at 3:11
• You would have to test it out and see. I would recommend testing all three models they include; CUSUMDetector, BOCPDetector and RobustStatDetector. Aug 17, 2021 at 3:14

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.

• The name is R not r! Aug 17, 2021 at 17:55

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.

• I am not sure that I follow the idea of total variation denoising. Also, what not use 1-norm? It seems that 1-norm would be more appropriate given the noise involved. Could you provide some working code using the data that I provide so that I can see how your proposed method works? Aug 17, 2021 at 13:09
• If you click the link, you will find some working code. Good luck! Aug 17, 2021 at 18:18

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