Package 'cpm' reference manual

Title:	Sequential and Batch Change Detection Using Parametric and Nonparametric Methods
Description:	Sequential and batch change detection for univariate data streams, using the change point model framework. Functions are provided to allow nonparametric distribution-free change detection in the mean, variance, or general distribution of a given sequence of observations. Parametric change detection methods are also provided for Gaussian, Bernoulli and Exponential sequences. Both the batch (Phase I) and sequential (Phase II) settings are supported, and the sequences may contain either a single or multiple change points. A full description of this package is available in Ross, G.J (2015) - "Parametric and nonparametric sequential change detection in R" available at <https://www.jstatsoft.org/article/view/v066i03>.
Authors:	Gordon J. Ross
Maintainer:	Gordon J. Ross <[email protected]>
License:	GPL-3
Version:	2.3
Built:	2024-11-08 06:35:42 UTC
Source:	CRAN

The Change Point Model Package

Description

An implementation of several different change point models (CPMs) for performing both parametric and nonparametric change detection on univariate data streams.

Details

The CPM framework is an approach to sequential change detection (also known as Phase II process monitoring) which allows standard statistical hypothesis tests to be deployed sequentially. The main two general purpose functions in the package are detectChangePoint and processStream for detecting single and multiple change points respectively. The remainder of the functions allow for more precise control over the change detection procedure. To cite this R package in a research paper, please use citation('cpm') to obtain the reference, and BibTeX entry.

Note: this package has a manual titled "Parametric and Nonparametric Sequential Change Detection in R: The cpm Package" available from www.gordonjross.co.uk, which contains a full description of all the functions and algorithms in the package, as well as detailed instructions on how to use it.

If you would like to cite this package, the citation information is "G. J. Ross - Parametric and Nonparametric Sequential Change Detection in R: The cpm Package, Journal of Statistical Software, 2015, 66(3), 1-20"

A Brief CPM Overview

Given a sequence $X_1,...,X_n$ of random variables, the CPM works by evaluating a two-sample test statistic at every possible split point. Let $D_{k,n}$ be the value of the test statistic when the sequence is split into the two samples $\{X_1, X_2,..., X_k\}$ and $\{X_{k+1}, X_{k+2} ,..., X_{n}\}$ , and define $D_n$ to be the maximum of these values. $D_n$ is then compared to some threshold, with a change being detected if the threshold is exceeded.

In the sequential context, the observations are processed one-by-one, with $D_t$ being computed based on the first t observations, $D_{t+1}$ being computed based on the first t+1 observations, and so on. The change detection time is defined as the first value of $t$ where the threshold is exceeded. Supposing this occurs at time $t=T$ , then the best estimate of the location of the change point is the value of $k$ which maximised $D_{k,T}$ . Writing $\hat{\tau}$ for this, we have that $\hat{\tau} \leq T$ .

The thresholds are chosen so that there is a constant probability of a false positive occurring after each observation. This leads to control of the Average Run Length ( $ARL_0$ ), defined as the expected number of observations received before a change is falsely detecting, assuming that no change has occurred.

The choice of test statistic in the CPM defines the class of changes which it is optimised towards detecting. This package implements CPMs using the following statistics. More details can be found in the references section:

Student: Student-t test statistic, as in [Hawkins et al, 2003]. Use to detect mean changes in a Gaussian sequence.
Bartlett: Bartlett test statistic, as in [Hawkins and Zamba, 2005]. Use to detect variance changes in a Gaussian sequence.
GLR: Generalized Likelihood Ratio test statistic, as in [Hawkins and Zamba, 2005b]. Use to detect both mean and variance changes in a Gaussian sequence.
Exponential: Generalized Likelihood Ratio test statistic for the Exponential distribution, as in [Ross, 2013]. Used to detect changes in the parameter of an Exponentially distributed sequence.
GLRAdjusted and ExponentialAdjusted: Identical to the GLR and Exponential statistics, except with the finite-sample correction discussed in [Ross, 2013] which can lead to more powerful change detection.
FET: Fishers Exact Test statistic, as in [Ross and Adams, 2012b]. Use to detect parameter changes in a Bernoulli sequence.
Mann-Whitney: Mann-Whitney test statistic, as in [Ross et al, 2011]. Use to detect location shifts in a stream with a (possibly unknown) non-Gaussian distribution.
Mood: Mood test statistic, as in [Ross et al, 2011]. Use to detect scale shifts in a stream with a (possibly unknown) non-Gaussian distribution.
Lepage: Lepage test statistics in [Ross et al, 2011]. Use to detect location and/ort shifts in a stream with a (possibly unknown) non-Gaussian distribution.
Kolmogorov-Smirnov: Kolmogorov-Smirnov test statistic, as in [Ross et al 2012]. Use to detect arbitrary changes in a stream with a (possibly unknown) non-Gaussian distribution.
Cramer-von-Mises: Cramer-von-Mises test statistic, as in [Ross et al 2012]. Use to detect arbitrary changes in a stream with a (possibly unknown) non-Gaussian distribution.

For a fuller overview of the package which includes a description of the CPM framework and examples of how to use the various functions, please consult the full package manual titled "Parametric and Nonparametric Sequential Change Detection in R: The cpm Package"

Author(s)

Gordon J. Ross [email protected]

References

Hawkins, D. , Zamba, K. (2005) – A Change-Point Model for a Shift in Variance, Journal of Quality Technology, 37, 21-31

Hawkins, D. , Zamba, K. (2005b) – Statistical Process Control for Shifts in Mean or Variance Using a Changepoint Formulation, Technometrics, 47(2), 164-173

Hawkins, D., Qiu, P., Kang, C. (2003) – The Changepoint Model for Statistical Process Control, Journal of Quality Technology, 35, 355-366.

Ross, G. J., Tasoulis, D. K., Adams, N. M. (2011) – A Nonparametric Change-Point Model for Streaming Data, Technometrics, 53(4)

Ross, G. J., Adams, N. M. (2012) – Two Nonparametric Control Charts for Detecting Arbitary Distribution Changes, Journal of Quality Technology, 44:102-116

Ross, G. J., Adams, N. M. (2013) – Sequential Monitoring of a Proportion, Computational Statistics, 28(2)

Ross, G. J., (2014) – Sequential Change Detection in the Presence of Unknown Parameters, Statistics and Computing 24:1017-1030

Ross, G. J., (2015) – Parametric and Nonparametric Sequential Change Detection in R: The cpm Package, Journal of Statistical Software, forthcoming

Tests Whether a CPM S4 Object Has Encountered a Change Point

Description

Tests whether an existing Change Point Model (CPM) S4 object has encountered a change point. It returns TRUE if a change has been encountered, otherwise FALSE.

Note that this function is part of the S4 object section of the cpm package, which allows for more precise control over the change detection process. For many simple change detection applications this extra complexity will not be required, and the detectChangePoint and processStream functions should be used instead.

For a fuller overview of this function including a description of the CPM framework and examples of how to use the various functions, please consult the package manual "Parametric and Nonparametric Sequential Change Detection in R: The cpm Package" available from www.gordonjross.co.uk

Usage

     changeDetected(cpm)
     changeDetected(cpm)

Arguments

cpm

The CPM S4 object which is to be tested for whether a change has occurred.

Value

TRUE if a change has been detected, otherwise FALSE.

Author(s)

Gordon J. Ross [email protected]

Examples

#generate a sequence containing a single change point
x <- c(rnorm(100,0,1),rnorm(100,1,1))

#use a Student CPM
cpm <- makeChangePointModel(cpmType="Student", ARL0=500)

for (i in 1:length(x)) {

  #process each observation in turn
  cpm <- processObservation(cpm,x[i])
  
  if (changeDetected(cpm)) {
    print(sprintf("change detected at observation %s",i))
    break
  }
}
#generate a sequence containing a single change point
x <- c(rnorm(100,0,1),rnorm(100,1,1))

#use a Student CPM
cpm <- makeChangePointModel(cpmType="Student", ARL0=500)

for (i in 1:length(x)) {

  #process each observation in turn
  cpm <- processObservation(cpm,x[i])
  
  if (changeDetected(cpm)) {
    print(sprintf("change detected at observation %s",i))
    break
  }
}

Resets a CPM S4 Object

Description

Resets an existing Change Point Model (CPM) S4 object. Typically it will be used in situations where the CPM is processing a stream, and has encountered a change point. If the stream may contain multiple change points, the typical reaction procedure after detecting a change is to reset the CPM. This involves clearing its memory of all the observations prior to the change point, so that monitoring can be resumed starting with the next observation after the change point.

Usage

     cpmReset(cpm)
     cpmReset(cpm)

Arguments

cpm

The CPM S4 object which is to be reset.

Value

The reinitialised CPM.

Author(s)

Gordon J. Ross [email protected]

Examples

#generate a sequence containing two change points
x <- c(rnorm(200,0,1),rnorm(200,1,1),rnorm(200,0,1))

#vectors to hold the result
detectiontimes <- numeric()
changepoints <- numeric()

#use a Lepage CPM
cpm <- makeChangePointModel(cpmType="Lepage", ARL0=500)

i <- 0
while (i < length(x)) {
  i <- i + 1
  #process each observation in turn
  cpm <- processObservation(cpm,x[i])
  
  #if a change has been found, log it, and reset the CPM
  if (changeDetected(cpm) == TRUE) {
    print(sprintf("Change detected at observation %d", i))
    detectiontimes <- c(detectiontimes,i)
    
    #the change point estimate is the maximum D_kt statistic 
    Ds <- getStatistics(cpm)
    tau <- which.max(Ds)
    
    if (length(changepoints) > 0) {
      tau <- tau + changepoints[length(changepoints)]
    }
    changepoints <- c(changepoints,tau)
    
    #reset the CPM
    cpm <- cpmReset(cpm)
    
    #resume monitoring from the observation following the 
    #change point
    i <- tau
  }
}

     #generate a sequence containing two change points
x <- c(rnorm(200,0,1),rnorm(200,1,1),rnorm(200,0,1))

#vectors to hold the result
detectiontimes <- numeric()
changepoints <- numeric()

#use a Lepage CPM
cpm <- makeChangePointModel(cpmType="Lepage", ARL0=500)

i <- 0
while (i < length(x)) {
  i <- i + 1
  #process each observation in turn
  cpm <- processObservation(cpm,x[i])
  
  #if a change has been found, log it, and reset the CPM
  if (changeDetected(cpm) == TRUE) {
    print(sprintf("Change detected at observation %d", i))
    detectiontimes <- c(detectiontimes,i)
    
    #the change point estimate is the maximum D_kt statistic 
    Ds <- getStatistics(cpm)
    tau <- which.max(Ds)
    
    if (length(changepoints) > 0) {
      tau <- tau + changepoints[length(changepoints)]
    }
    changepoints <- c(changepoints,tau)
    
    #reset the CPM
    cpm <- cpmReset(cpm)
    
    #resume monitoring from the observation following the 
    #change point
    i <- tau
  }
}

Detect a Single Change Point in a Sequence

Description

This function is used to detect a single change point in a sequence of observations using the Change Point Model (CPM) framework for sequential (Phase II) change detection. The observations are processed in order, starting with the first, and a decision is made after each observation whether a change point has occurred. If a change point is detected, the function returns with no further observations being processed. A full description of the CPM framework can be found in the papers cited in the reference section.

Usage

     detectChangePoint(x, cpmType, ARL0=500, startup=20, lambda=NA) 
     detectChangePoint(x, cpmType, ARL0=500, startup=20, lambda=NA)

Arguments

`x`	A vector containing the univariate data stream to be processed.
`cpmType`	The type of CPM which is used. With the exception of the FET, these CPMs are all implemented in their two sided forms, and are able to detect both increases and decreases in the parameters monitored. Possible arguments are: `Student`: Student-t test statistic, as in [Hawkins et al, 2003]. Use to detect mean changes in a Gaussian sequence. `Bartlett`: Bartlett test statistic, as in [Hawkins and Zamba, 2005]. Use to detect variance changes in a Gaussian sequence. `GLR`: Generalized Likelihood Ratio test statistic, as in [Hawkins and Zamba, 2005b]. Use to detect both mean and variance changes in a Gaussian sequence. `Exponential`: Generalized Likelihood Ratio test statistic for the Exponential distribution, as in [Ross, 2013]. Used to detect changes in the parameter of an Exponentially distributed sequence. `GLRAdjusted` and `ExponentialAdjusted`: Identical to the GLR and Exponential statistics, except with the finite-sample correction discussed in [Ross, 2013] which can lead to more powerful change detection. `FET`: Fishers Exact Test statistic, as in [Ross and Adams, 2012b]. Use to detect parameter changes in a Bernoulli sequence. `Mann-Whitney`: Mann-Whitney test statistic, as in [Ross et al, 2011]. Use to detect location shifts in a stream with a (possibly unknown) non-Gaussian distribution. `Mood`: Mood test statistic, as in [Ross et al, 2011]. Use to detect scale shifts in a stream with a (possibly unknown) non-Gaussian distribution. `Lepage`: Lepage test statistics in [Ross et al, 2011]. Use to detect location and/or shifts in a stream with a (possibly unknown) non-Gaussian distribution. `Kolmogorov-Smirnov`: Kolmogorov-Smirnov test statistic, as in [Ross et al 2012]. Use to detect arbitrary changes in a stream with a (possibly unknown) non-Gaussian distribution. `Cramer-von-Mises`: Cramer-von-Mises test statistic, as in [Ross et al 2012]. Use to detect arbitrary changes in a stream with a (possibly unknown) non-Gaussian distribution.
`ARL0`	Determines the $ARL_0$ which the CPM should have, which corresponds to the average number of observations before a false positive occurs, assuming that the sequence does not undergo a change. Because the thresholds of the CPM are computationally expensive to estimate, the package contains pre-computed values of the thresholds corresponding to several common values of the $ARL_0$ . This means that only certain values for the $ARL_0$ are allowed. Specifically, the $ARL_0$ must have one of the following values: 370, 500, 600, 700, ..., 1000, 2000, 3000, ..., 10000, 20000, ..., 50000.
`startup`	The number of observations after which monitoring begins. No change points will be flagged during this startup period. This must be set to at least 20.
`lambda`	A smoothing parameter which is used to reduce the discreteness of the test statistic when using the FET CPM. See [Ross and Adams, 2012b] in the References section for more details on how this parameter is used. Currently the package only contains sequences of ARL0 thresholds corresponding to lambda=0.1 and lambda=0.3, so using other values will result in an error. If no value is specified, the default value will be 0.1.

Value

`x`	The sequence of observations which was processed.
`changeDetected`	TRUE if any $D_t$ exceeds the value of $h_t$ associated with the chosen $ARL_0$ , otherwise FALSE.
`detectionTime`	The observation after which the change point was detected, defined as the first observation after which $D_t$ exceeded the test threshold. If no change is detected, this will be equal to 0.
`changePoint`	The best estimate of the change point location. If the change is detected after the $t^{th}$ observation, then the change estimate is the value of $k$ which maximises $D_{k,t}$ . If no change is detected, this will be equal to 0.
`Ds`	The sequence of maximised $D_t$ statistics, starting from the first observation until the observation after which the change point was detected