ocd: A package for high-dimensional multiscale online changepoint detection

Description

The ocd package provides the S3 class ChangepointDetector that processes data sequentially using the getData function and aims to detect change as soon as it occurs online subject to false alarm rates.

References

Chen, Y., Wang, T. and Samworth, R. J. (2020) High-dimensional multiscale online changepoint detection Preprint. arxiv:2003.03668.

See Also

ChangepointDetector for detailed usage.

Examples

set.seed(2020)
p <- 100
thresh <- setNames(c(11.62, 179.48, 54.87), c('diag', 'off_d', 'off_s'))
detector <- ChangepointDetector(dim=p, method='ocd', beta=1, thresh=thresh)
old_mean <- rnorm(p); new_mean <- old_mean + c(rnorm(p/4), rep(0,3*p/4)) / sqrt(p/4)

# using functional semantics native in R
detector <- setStatus(detector, 'estimating')
for (i in 1:10000){
  x_new <- rnorm(p, mean=old_mean)
  detector <- getData(detector, x_new)
}
print(detector)

detector <- setStatus(detector, 'monitoring')
for (i in 1:200){
  x_new <- rnorm(p, old_mean * (i < 100) + new_mean * (i>=100))
  detector <- getData(detector, x_new)
}
print(detector)

## Not run: 
# alternative way to write the above using the piping semantics
library(magrittr)
detector %<>% reset
detector %<>% setStatus('estimating')
for (i in 1:10000){
  x_new <- rnorm(p, mean=old_mean)
  detector %<>% getData(x_new)
}
detector %>% print

detector %<>% setStatus('monitoring')
for (i in 1:200){
  x_new <- rnorm(p, old_mean * (i < 100) + new_mean * (i>=100))
  detector %<>% getData(x_new)
}
detector %>% print

## End(Not run)

Processing a new data point for the 'Chan' class

Description

This function implements the getData function to perform the online changepoint detection for the 'Chan' class.

Usage

Chan_update(x_new, X_recent, CUSUM, p0, w, lambda)

Arguments

Value

a list of

• stat: test statistic for the 'Chan' class.

• X_recent: the updated X_recent matrix

• CUSUM: the updated CUSUM matrix

References

Chan, H. P. (2017) Optimal sequential detection in multi-stream data. Ann. Statist., 45, 2736–2763.

Constructor for the ChangepointDetector S3 class

Description

Constructor for the ChangepointDetector S3 class

Usage

ChangepointDetector(dim, method = c("ocd", "Mei", "XS", "Chan"), thresh,
  patience = 5000, MC_reps = 100, beta = 1, sparsity = "auto",
  b = beta/sqrt(dim), p0 = 1/sqrt(dim), w = 200, lambda = sqrt(8) -
  2)

Arguments

Details

This function is a wrapper. The new_OCD, new_Mei, new_XS and new_Chan carry out the actual constructor implementation.

Value

An object of S3 class 'ChangepointDetector'. Depending on the method argument specified, the object also belongs to a subclass 'OCD', 'Mei', 'XS' or 'Chan' corresponding to method='ocd'. It contains the following attributes:

• class - S3 class and subclass

• data_dim - data dimension

• method - method used for changepoint detection

• param - a list of parameters used in the specific method: beta and sparsity for method ocd; b for method Mei; p0 and w for method XS; p0, w and lambda for method Chan.

• threshold - a named vector of thresholds used for detection (see the thresh argument)

• n_obs - number of observations, initialised to 0

• baseline_mean - vector of pre-change mean, initialised to a vector of 0, can be estimated by setting the changepoint detector into baseline mean and standard deviation estimating status, see setStatus, or set directly using setBaselineMean.

• baseline_sd - vector of standard deviation, initialised to a vector of 1, can be estimated by setting the changepoint detector into baseline mean and standard deviation estimating status, see setStatus, or set directly using setBaselineSD.

• tracked - a list of information tracked online by the changepoint detector: matrices A and tail for method ocd; vector R for method Mei; matrices X_recent and CUSUM for methods XS and Chan.

• statistics - a named vector of test statistics for changepoint detection: statistics with names diag, off_d and off_s for method ocd (note if sparsity is 'dense' or 'sparse', then only (S^diag, S^off,d) and (S^diag, S^off,s) are included in stat respectively.); statistics with names max and sum for method Mei; a single numeric value for methods XS and Chan.

• status - one of the following: 'estimating' (the detector is estimating the baseline mean and standard deviation with new data points), 'monitoring' (the detector is detecting changes from the baseline mean from new data points) and an integer recording the time of declaration of changepoint.

References

• Chen, Y., Wang, T. and Samworth, R. J. (2020) High-dimensional multiscale online changepoint detection Preprint. arxiv:2003.03668.

• Mei, Y. (2010) Efficient scalable schemes for monitoring a large number of data streams. Biometrika, 97, 419–433.

• Xie, Y. and Siegmund, D. (2013) Sequential multi-sensor change-point detection. Ann. Statist., 41, 670–692.

• Chan, H. P. (2017) Optimal sequential detection in multi-stream data. Ann. Statist., 45, 2736–2763.

See Also

accessor functions such as data_dim, the main function for processing a new data point getData, other methods for the ChangepointDetector class including reset, setBaselineMean, setBaselineSD, setStatus, normalisedStatistics and checkChange.

Examples

detector_ocd <- ChangepointDetector(dim=100, method='ocd',
                                    thresh=c(11.6, 179.5, 54.9), beta=1)
detector_Mei <- ChangepointDetector(dim=100, method='Mei',
                                    thresh=c(8.6, 125.1), b=0.1)
detector_XS <- ChangepointDetector(dim=100, method='XS', thresh=55.1)
detector_Chan <- ChangepointDetector(dim=100, method='Chan', thresh=8.7)

Compute Monte Carlo thresholds for the Chan method

Description

Compute Monte Carlo thresholds for the Chan method

Usage

MC_Chan(dim, patience, p0, w, lambda, MC_reps)

Arguments

Value

A numeric vector of computed thresholds.

Compute Monte Carlo thresholds for the Mei method

Description

Compute Monte Carlo thresholds for the Mei method

Usage

MC_Mei(dim, patience, b, MC_reps)

Arguments

Value

A numeric vector of computed thresholds.

Compute Monte Carlo thresholds for the XS method

Description

Compute Monte Carlo thresholds for the XS method

Usage

MC_XS(dim, patience, p0, w, MC_reps)

Arguments

Value

A numeric vector of computed thresholds.

Compute Monte Carlo thresholds for the OCD method

Description

Compute Monte Carlo thresholds for the OCD method

Usage

MC_ocd(dim, patience, beta, sparsity, MC_reps)

Arguments

Value

A numeric vector of computed thresholds.

Processing a new data point for the 'Mei' class

Description

This function implements the getData function to perform the online changepoint detection for the 'Mei' class.

Usage

Mei_update(x_new, R, b)

Arguments

Value

a list of

• stat: a vector of 2 test statistics for the 'Mei' class.

• R: the updated R vector

References

Mei, Y. (2010) Efficient scalable schemes for monitoring a large number of data streams. Biometrika, 97, 419–433.

Parkfield seismic sensor data

Description

Processed data from 39 ground motion sensors at 13 stations near Parkfield, California from 2.00-2.16am on December 23, 2004, with an earthquake measured at duration magnitude 1.47Md hit near Atascadero, California at 02:09:54.01.

Usage

data(ParkfieldSensors)

Format

A matrix with 39 columns and 14998 rows, with each column corresponding to a sensor and each row corresponding to a time after 2am. Column names corresponds to names of the sensors and row names are number of seconds after 2am.

Source

HRSN (2014), High Resolution Seismic Network. UC Berkeley Seismological Laboratory. Dataset. doi:10.7932/HRSN.

Examples

data(ParkfieldSensors)
head(ParkfieldSensors)

## Not run: 
plot(c(0, nrow(ParkfieldSensors) * 0.064), c(0, ncol(ParkfieldSensors)+1),
     pch=' ', xlab='seconds after 2004-12-23 02:00:00',
     ylab='sensor measurements')
x <- as.numeric(rownames(ParkfieldSensors))
for (j in 1:ncol(ParkfieldSensors)){
  y <- ParkfieldSensors[, j]
  y <- (y - max(ParkfieldSensors)) / diff(range(ParkfieldSensors)) + 0.5 + j
  points(x, y, pch='.')
}
abline(v = 9 * 60 + 54.01, col='blue', lwd=2, lty=3) # earthquake time

library(magrittr)
p <- ncol(ParkfieldSensors)
train_ind <- as.numeric(rownames(ParkfieldSensors)) <= 240
train <- ParkfieldSensors[train_ind, ]
test <- ParkfieldSensors[!train_ind, ]

# tuning parameters
gamma <- 24 * 60 * 60 / 0.064 # patience = 1 day
beta <- 150

# use theoretical thresholds suggested in Chen, Wang and Samworth (2020)
psi <- function(t){p - 1 + t + sqrt(2 * (p - 1) * t)}
th_diag <- log(24*p*gamma*log2(4*p))
th_off_s <- 8*log(24*p*gamma*log2(2*p))
th_off_d <- psi(th_off_s/4)
thresh <- setNames(c(th_diag, th_off_d, th_off_s), c('diag', 'off_d', 'off_s'))

# initialise ocd detector
detector <- ChangepointDetector(dim=p, method='ocd', beta=beta, thresh=thresh)

# use training data to update baseline mean and standard deviation
detector %<>% setStatus('estimating')
for (i in 1:nrow(train)) {
  detector %<>% getData(train[i, ])  
}  

# find changepoint in the test data
detector %<>% setStatus('monitoring')
for (i in 1:nrow(test)) {
  detector %<>% getData(test[i, ])
  if (is.numeric(detector %>% status)) break
}

if (is.numeric(detector %>% status)) {
  time_declared <- 240 + detector %>% status * 0.064
  abline(v = time_declared, col='orange', lwd=2, lty=3) # detection time
  cat('Change detected', time_declared, 'seconds after 2am.\n')
}

## End(Not run)

Processing a new data point for the 'XS' class

Description

This function implements the getData function to perform the online changepoint detection for the 'XS' class.

Usage

XS_update(x_new, X_recent, CUSUM, p0, w)

Arguments

Value

a list of

• stat: test statistic for the 'XS' class.

• X_recent: the updated X_recent matrix

• CUSUM: the updated CUSUM matrix

References

Xie, Y. and Siegmund, D. (2013) Sequential multi-sensor change-point detection. Ann. Statist., 41, 670–692.

Accessor functions to attributes of class ChangepointDetector

Description

Accessor functions to attributes of class ChangepointDetector

Usage

data_dim(detector)

ocdMethod(detector)

n_obs(detector)

patience(detector)

param(detector)

thresholds(detector)

baselineMean(detector)

baselineSD(detector)

tracked(detector)

statistics(detector)

status(detector)

Arguments

Details

Obtain various attributes of the class 'ChangepointDetector'

See Also

ChangepointDetector

Check if a mean change has occurred.

Description

Check if a mean change has occurred.

Usage

checkChange(detector)

Arguments

Details

The normalisedStatistics funcrtion is used to check if any of the test statistics are above the threshold level. If this happens, the status of the detector is changed to record the time of change and a message is printed to the standard output declaring the change.

Value

Updated object detector

See Also

normalisedStatistics, setStatus,

Processing a new data point

Description

This is the main function for the 'ChangepointDetector' class.

Usage

getData(detector, x_new)

## S3 method for class 'OCD'
getData(detector, x_new)

## S3 method for class 'Mei'
getData(detector, x_new)

## S3 method for class 'XS'
getData(detector, x_new)

## S3 method for class 'Chan'
getData(detector, x_new)

Arguments

Details

If the status of the detector object is 'estimating', the new data point is used to update the current estimate of pre-change mean and standard deviation. If the status of the detector object is monitoring', the new data point is used to detect if a mean change has occurred.

Value

Updated object detector

Methods (by class)

• OCD: Process a new data for subclass 'OCD'

• Mei: Process a new data for subclass 'Mei'

• XS: Process a new data for subclass 'XS'

• Chan: Process a new data for subclass 'Chan'

See Also

setBaselineMean for updating the pre-change mean estimate, setBaselineSD for updating the standard deviation estimate, checkChange for checking for change.

construtor for subclass 'Chan' in class 'ChangepointDetector'

Description

construtor for subclass 'Chan' in class 'ChangepointDetector'

Usage

new_Chan(dim, thresh, p0, w, lambda)

Arguments

Details

It is preferred to use ChangepointDetector for construction.

Value

An object of S3 subclass 'Chan' in class 'ChangepointDetector'.

References

Chan, H. P. (2017) Optimal sequential detection in multi-stream data. Ann. Statist., 45, 2736–2763.

Examples

detector <- new_Chan(dim=100, thresh=8.7, p0=0.1, w=200, lambda=sqrt(8)-2)

constructor of subclass 'Mei' in class 'ChangepointDetector'

Description

constructor of subclass 'Mei' in class 'ChangepointDetector'

Usage

new_Mei(dim, thresh, b)

Arguments

Details

It is preferred to use ChangepointDetector for construction.

Value

An object of S3 subclass 'Mei' in class 'ChangepointDetector'.

References

Mei, Y. (2010) Efficient scalable schemes for monitoring a large number of data streams. Biometrika, 97, 419–433.

Examples

detector <- new_Mei(dim=100, thresh=c(8.6, 125.1), b=0.1)

constructor of subclass 'OCD' in class 'ChangepointDetector'

Description

constructor of subclass 'OCD' in class 'ChangepointDetector'

Usage

new_OCD(dim, thresh, beta, sparsity)

Arguments

Details

It is preferred to use ChangepointDetector for construction.

Value

An object of S3 subclass 'OCD' in class 'ChangepointDetector'.

References

Chen, Y., Wang, T. and Samworth, R. J. (2020) High-dimensional multiscale online changepoint detection Preprint. arxiv:2003.03668.

Examples

detector <- new_OCD(dim=100, thresh=c(11.6, 179.5, 54.9), beta=1, sparsity='auto')

constructor of subclass 'XS' in class 'ChangepointDetector'

Description

constructor of subclass 'XS' in class 'ChangepointDetector'

Usage

new_XS(dim, thresh, p0, w)

Arguments

Details

It is preferred to use ChangepointDetector for construction.

Value

An object of S3 subclass 'XS' in class 'ChangepointDetector'.

References

Xie, Y. and Siegmund, D. (2013) Sequential multi-sensor change-point detection. Ann. Statist., 41, 670–692.

Examples

detector <- new_XS(dim=100, thresh=55.1, p0=0.1, w=200)

Compute maximum ratio between detection statistic and its threshold

Description

Compute maximum ratio between detection statistic and its threshold

Usage

normalisedStatistics(detector)

Arguments

Value

maximum of the ratio between the current test statistics and their respective thresholds.

Processing a new data point for the 'OCD' class

Description

This function implements the getData function to perform the online changepoint detection for the 'OCD' class.

Usage

ocd_update(x_new, A, tail, beta, sparsity)

Arguments

Value

a list of

• stat: a vector of the test statistics for the 'OCD' class

• A: the updated A matrix

• tail: the updated tail matrix

References

Chen, Y., Wang, T. and Samworth, R. J. (2020) High-dimensional multiscale online changepoint detection Preprint. arxiv:2003.03668.

Printing methods for the 'ChangepointDetector' class

Description

Printing methods for the 'ChangepointDetector' class

Usage

## S3 method for class 'ChangepointDetector'
print(x, ...)

Arguments

Reset changepoint detector to initial state

Description

Reset changepoint detector to initial state

Usage

reset(detector)

## S3 method for class 'OCD'
reset(detector)

## S3 method for class 'Mei'
reset(detector)

## S3 method for class 'XS'
reset(detector)

## S3 method for class 'Chan'
reset(detector)

Arguments

Value

Updated object detector

Methods (by class)

• OCD: Reset object of subclass 'OCD'

• Mei: Reset object of subclass 'Mei'

• XS: Reset object of subclass 'XS'

• Chan: Reset object of subclass 'Chan'

Set baseline mean

Description

Set baseline mean

Usage

setBaselineMean(detector, mean)

Arguments

Value

Updated object detector

Set baseline standard deviation

Description

Set baseline standard deviation

Usage

setBaselineSD(detector, sd)

Arguments

Value

Updated object detector

Set changepoint detector status

Description

Set changepoint detector status

Usage

setStatus(detector, new_status)

Arguments

Details

If the status is set to 'estimating', new observations are used to update current estimate of pre-change mean and standard deviation. If the status is set to 'monitoring', new observations are used to check if mean change has occurred.

Value

Updated object detector

compute new mean and sd from old ones with one additional observation

Description

compute new mean and sd from old ones with one additional observation

Usage

update_param(old_mean, old_sd, x_new, n_obs)

Arguments

Value

list of two vectors: new mean and new standard deviation