Change Point Detection in a Time Series, Explained

A change point is not an outlier. An outlier is one observation that does not belong; a change point is the moment after which every observation comes from a different process. The distinction decides which algorithm you want and what a detection actually costs you.

Two different questions

Online detection asks: given everything up to now, has something changed? It runs as data arrives, it is allowed to be late, and it is judged on average run length — how long it takes to signal a real change, and how long it survives without falsely signalling when nothing has changed. Offline segmentation asks a different question: given this whole finished series, where are the boundaries? It sees the future of every candidate point, so it is far more accurate and it cannot be used for alerting.

Confusing them produces the most common disappointment in this area: an offline method evaluated on historical data, reporting boundaries crisply, then deployed on a live stream where it has to be re-run on a growing window and its answers change every time it runs. If you need an alert, start from the online method.

A CUSUM, worked to a signal

The tabular CUSUM is the canonical online detector and the arithmetic fits on one line. It keeps two running sums, one for upward shifts and one for downward, each floored at zero. The NIST/SEMATECH engineering statistics handbook gives them as

S_hi(i) = max(0, S_hi(i-1) + x_i - mu0 - k)
S_lo(i) = max(0, S_lo(i-1) + mu0 - k - x_i)
S_hi(0) = S_lo(0) = 0

signal when either sum exceeds h

Two parameters. The slack k is the size of shift you are prepared to ignore, conventionally half the shift you want to catch, and the decision interval h is the evidence threshold, conventionally four or five standard deviations. The floor at zero is the whole idea: while the process is on target, the increments average slightly negative because of k, so the sum keeps being reset and cannot accumulate a false alarm from a long quiet stretch.

Take a process on target at 100 with a standard deviation of 2, so k = 1 and h = 10, and this labelled series in which the mean shifts upward at observation 7:

i      1    2    3    4    5    6    7    8    9   10   11   12
x    101   99  100   98  102  100  104  105  103  106  104  107
x-101  0   -2   -1   -3   +1   -1   +3   +4   +2   +5   +3   +6
S_hi   0    0    0    0    1    0    3    7    9   14   ...  ...
                                                    ^ exceeds h = 10

S_lo   0    0    0    1    0    0    0    0    0    0    0    0

Follow the sums. Through the first six observations the process is on target and S_hi spends its time at zero: the +1 at observation 5 is wiped out by the −1 at observation 6. From observation 7 the increments are consistently positive, the sum climbs 3, 7, 9, 14, and at observation 10 it crosses the decision interval and the chart signals. S_lo registers a single 1 at observation 4 and returns to zero, which is exactly what a floored sum should do with one low reading.

Reading the change point off the run

The signal came at observation 10 but the shift began at observation 7, and the CUSUM contains the estimate of that. The change point is estimated as the last time the sum was at zero, because that is the last moment at which the accumulated evidence was empty. Here S_hi was zero at observation 6, so the estimated onset is observation 7 — the true one — and the detection delay is three observations.

That delay is not a defect to be tuned away; it is the price of the false alarm rate. Lower h and you signal sooner and more often when nothing happened. Lower k and you become sensitive to smaller shifts and simultaneously slower to reset. There is no setting that is fast and quiet, and the honest way to choose is to state the shift size that matters to you, pick k at half of it, then pick h from the false-alarm rate you can live with given how many series you run this on. A hundred series at one false alarm per thousand observations is a false alarm every ten observations somewhere.

Offline segmentation and the penalty

Offline methods take the whole series and choose a set of breakpoints minimising a cost, plus a penalty for each breakpoint added. Without the penalty the optimum is a breakpoint everywhere, since every segment of length one fits perfectly, so the penalty is not a regularisation nicety but the thing that makes the problem well posed.

The ruptures library, whose accompanying review by Truong, Oudre and Vayatis appeared in Signal Processing in 2020, implements the standard set: exact dynamic programming when you know the number of breakpoints in advance, PELT when you do not and want an exact answer under a linear penalty, binary segmentation as a fast greedy approximation, a sliding-window method, and kernel-based detection for changes that are not in the mean. The cost function is the other half of the specification, and choosing it is choosing what counts as a change: an L2 cost detects shifts in the mean, a normal cost detects shifts in mean or variance, an autoregressive cost detects shifts in the dependence structure while the mean stays put.

The practical consequence is that a series can have a change point that no mean-based method will ever find. A machine whose output level is unchanged but whose vibration variance has doubled has changed; run L2 on it and you will find nothing at any penalty.

What breaks it

• Seasonality reads as a change. Every quarter, the mean moves. Run a CUSUM on a raw seasonal series and it will signal on the seasonal peak, correctly and uselessly. Run it on the remainder from an STL decomposition instead, so the target mean is genuinely constant.
• Trend guarantees a signal. A slow drift accumulates in the same direction indefinitely, so the sum will cross any h eventually. Difference the series or detrend it first, and be clear that you are then detecting a change in the rate rather than in the level.
• The target mean has to come from somewhere. Estimating mu0 from a window that already contains the change biases it toward the new regime and delays or prevents detection. Fix it from a known-clean period, or re-estimate it only after a signal has been accepted.
• Autocorrelation inflates the false alarm rate. The standard design assumes independent observations. If neighbouring residuals are correlated, runs of same-signed deviations occur far more often than the design assumes and the actual false alarm rate is well above the nominal one. Model the correlation out, or widen h and accept that the nominal rate is fiction.