In statistical analysis, change detection or change point detection tries to identify times when the probability distribution of a stochastic process or time series changes. In general the problem concerns both detecting whether or not a change has occurred, or whether several changes might have occurred, and identifying the times of any such changes.
Specific applications, like step detection and edge detection, may be concerned with changes in the mean, variance, correlation, or spectral density of the process. More generally change detection also includes the detection of anomalous behavior: anomaly detection.
Offline change point detection it is assumed that a sequence of length is available and the goal is to identify whether any change point(s) occurred in the series. This is an example of post hoc analysis and is often approached using hypothesis testing methods. By contrast, online change point detection is concerned with detecting change points in an incoming data stream.
Background
A time series measures the progression of one or more quantities over time. For instance, the figure above shows the level of water in the Nile river between 1870 and 1970. Change point detection is concerned with identifying whether, and if so when, the behavior of the series changes significantly. In the Nile river example, the volume of water changes significantly after a dam was built in the river. Importantly, anomalous observations that differ from the ongoing behavior of the time series are not generally considered change points as long as the series returns to its previous behavior afterwards.
Mathematically, we can describe a time series as an ordered sequence of observations . We can write the joint distribution of a subset of the time series as . If the goal is to determine whether a change point occurred at a time in a finite time series of length , then we really ask whether equals . This problem can be generalized to the case of more than one change point.
Algorithms
Online change detection
Using the sequential analysis ("online") approach, any change test must make a trade-off between these common metrics: False alarm rate Misdetection rate Detection delay
In a Bayes change-detection problem, a prior distribution is available for the change time.
Online change detection is also done using streaming algorithms.
Offline change detection
Basseville (1993, Section 2.6) discusses offline change-in-mean detection with hypothesis testing based on the works of Page and Picard and maximum-likelihood estimation of the change time, related to two-phase regression. Other approaches employ clustering based on maximum likelihood estimation,, use optimization to infer the number and times of changes, via spectral analysis, or singular spectrum analysis.
Statistically speaking, change detection is often considered as a model selection problem. Models with more changepoints fit data better but with more parameters. The best trade-off can be found by optimizing a model selection criterion such as Akaike information criterion and Bayesian information criterion. Bayesian model selection has also been used. Bayesian methods often quantify uncertainties of all sorts and answer questions hard to tackle by classical methods, such as what is the probability of having a change at a given time and what is the probability of the data having a certain number of changepoints.
"Offline" approaches cannot be used on streaming data because they need to compare to statistics of the complete time series, and cannot react to changes in real-time but often provide a more accurate estimation of the change time and magnitude.
Applications
Change detection tests are often used in manufacturing for quality control, intrusion detection, spam filtering, website tracking, and medical diagnostics.