BS(segment_cost, n[, β = log(n)])

Runs the Binary segmentation algorithm for the cost function segment_cost for a time series of length n and a penalty β and returns the position of found changepoints, and the cost of this segmentation.

See also: @BS, @segment_cost

Returns

• CP::Vector{Int}: Vector of indices of detected changepoints
• cost::Float64: Cost of optimal segmentation

Example

# Sample Normal time series with changing mean
n = 1000
λ = 100
μ, σ = Normal(0.0, 10.0), 1.0
sample, cps = @changepoint_sampler n λ Normal(μ, σ)
# Run binary segmentation
seg_cost = NormalMeanChange(sample, σ)
BS_cps, BS_cost = BS(seg_cost, n)

References

Scott, A.J. and Knott, M. (1974) A Cluster Analysis Method for Grouping Means in the Analysis of Variance, Biometrics 30(3), 507 - 512

CROPS(segment_cost, n, β₁, β₂)

Runs the CROPS algorithm for cost function segment_cost for range of penalties between β₁ and β₂. This calculates optimal segmentations using PELT for all penalties between β₁ and β₂.

See also: PELT, @PELT, @segment_cost

Returns

• out::Dict{String,Any}:
  • out["penalty"] : vector of penalties between minimum and maximum pen
  • out["number"] : vector of number of changepoints for each penalty
  • out["constrained"] : vector of optimal segmentation costs for each penalty
  • out["changepoints"] : vector of changepoints sets for each penalty

Example

# Sample time series with change points
n = 1000       # Length of time series
λ = 100        # Frequency of change points
μ, σ = Normal(0.0, 10.0), 1.0
sample, cps = @changepoint_sampler n λ Normal(μ, σ)

# Create cost function and run CROPS
seg_cost = NormalMeanSegment(sample)
pen = (4.0,100.0)
crops_output = CROPS(seg_cost, n, pen)

References

Haynes, K., Eckley. I.A., and Fearnhead, P., (2014) Efficient penalty search for multiple changepoint problems arXiv:1412.3617

CUSUM(data)

Create a cumulative sum segment cost function for univariate mean change setting

See also: NormalMeanSegment

ExponentialSegment(data)

Constructs a segment cost function for data assuming it follows an Exponential distribution with changing mean.

See also: NormalMeanSegment

GammaRateSegment(data, alpha)

Constructs a segment cost function for data assuming it follows a Gamma distribution with changing rate parameter and fixed shape parameter alpha.

See also: NormalMeanSegment

GammaShapeSegment(data, beta)

Constructs a segment cost function for data assuming it follows a Gamma distribution with changing shape parameter and fixed rate parameter beta.

See also: NormalMeanSegment

MOSUM(data, G[, var_est_method="mosum", alpha=0.1, criterion="eta", eta=0.4, epsilon=0.2])

Runs the MOSUM procedure for the univariate array data with bandwidth G, and returns the number and position of found changepoints.

Optionally, var_est_method specifies the variance estimator to normalise by; this can be the average mosum (default) or minimum mosum.min across windows. alpha determines the signicance level (default 0.1). criterion determines whether to use the eta (default) or epsilon location procedure (see references). eta and epsilon are tuning parameters for the mentioned procedures (default 0.4 and 0.2).

See also: @BS, MOSUM_multi_scale, mosum_plot

Returns

• out::Dict{String,Union{Bool, Float64, Int64, Array}}:
  • out["number"] : Integer number of detected changes
  • out["Reject"] : Boolean hypothesis test outcome
  • out["threshold"] : Float of testing threshold
  • out["detector"] : vector of mosum detector values
  • out["var.estimation"] : vector of estimated variance values

Example

# Sample Normal time series with changing mean
n = 1000
λ = 300
μ, σ = Normal(0.0, 10.0), 1.0
data, cps = @changepoint_sampler n λ Normal(μ, σ)
G = 150
# Run MOSUM procedure
MOSUM_out = MOSUM(data, G)
# Plot MOSUM detector
mosum_plot(MOSUM_out)

References

Eichinger, Birte, and Claudia Kirch. "A MOSUM procedure for the estimation of multiple random change points." Bernoulli 24.1 (2018): 526-564. Meier, Aledataander, Claudia Kirch, and Haeran Cho. "mosum: A package for moving sums in change point analysis." (2018).

MOSUM_multi_scale(data, Gset[, var_est_method="mosum", alpha=0.1, criterion="eta", eta=0.4, epsilon=0.2])

Runs the Multiple Filtre MOSUM procedure for the univariate array data with multiple bandwidths Gset, and returns the position of found changepoints. For optional arguments, see ?MOSUM.

See also: MOSUM

Returns

• cps : Integer array of estimated change points

Edataample

# Sample Normal time series with changing mean
n = 1000
λ = 300
μ, σ = Normal(0.0, 10.0), 1.0
data, cps = @changepoint_sampler n λ Normal(μ, σ)
Gset = [25, 50, 100, 150]
# Run MOSUM procedure
multi_scale_out = MOSUM_multi_scale(data, Gset; alpha = 0.05)
# Plot change points
changepoint_plot(data, multi_scale_out)

References

Messer M, Kirchner M, Schiemann J, Roeper J, Neininger R, Schneider G (2014). “A Multiple Filter Test for the Detection of Rate Changes in Renewal Processes with Varying Variance.” The Annals of Applied Statistics, 8(4), 2027–2067.

NonparametricSegment(data, k)

Constructs a segment cost function for data using the Nonparametric model with parameter k.

See also: NormalMeanSegment

NormalMeanSegment(data[, σ = 1.0])

Constructs a function which calculates the cost of fitting a Normal distribution with unknown mean, and known standard deviation σ for a specified segment of data. By default, sigma is set to 1.0.

See also: NormalVarSegment, NormalMeanVarSegment, ExponentialSegment, PoissonSegment, GammaRateSegment, GammaShapeSegment, Nonparametric, PELT, BS

Returns

• cost::Function: Function which takes indices (s, t) where 0 ≤ s < t < n and n is the length of the time series and returns the cost of fitting distribution to the segment [s+1, ..., t]

Example

n = 1000
λ = 100
μ, σ = Normal(0.0, 10.0), 1.0
data, cps = @changepoint_sampler n λ Normal(μ, σ)
cost = NormalMeanSegment(data, σ = 1.0)
cps, cost = BS(cost, n)

NormalMeanVarSegment(data)

Constructs a segment cost function for data assuming it follows a Normal distribution with changing mean and variance.

See also: NormalMeanSegment

NormalVarSegment(data, μ)

Constructs a segment cost function for data assuming it follows a Normal distribution with changing variance and fixed mean μ.

See also: NormalMeanSegment

OLSSegment(data)

Create a segment cost function for piecewise linear regressions, fitted using OLS (assuming Normally distributed errors).

See also: NormalMeanSegment

PELT(segment_cost, n[, β = log(n)])

Runs the PELT algorithm using cost function segment_cost for a time series of length n and a penalty β and returns the position of changepoints and optimal segmentation cost.

See also: @PELT, @segment_cost, CROPS

Returns

• (CP::Vector{Int}, cost::Float64):
  • CP::Vector{Int}: Vector of indices of detected changepoints
  • cost::Float64: Cost of optimal segmentation

Example

n, λ = 1000, 100
μ, σ = Normal(0.0, 10.0), 1.0
sample, cps = @changepoint_sampler n λ Normal(μ, σ)  # Sample changepoints
seg_cost = NormalMeanChange(sample, σ)               # Create segment cost function
pelt_cps, pelt_cost = PELT(seg_cost, n)              # Run PELT

References

Killick, R., Fearnhead, P. and Eckley, I.A. (2012) Optimal detection of changepoints with a linear computational cost, JASA 107(500), 1590-1598

PoissonSegment(data)

Constructs a segment cost function for data assuming it follows Poisson distribution with changing mean.

See also: NormalMeanSegment

WBS(data; th_const = 1.3, sigma = 0.0, M = 5000, do_seeded = false, shrink = 1/sqrt(2), min_length = 10)

Runs the Wild Binary segmentation algorithm for univariate array data, using the CUSUM cost function. The test threshold is determined by th_const and the known or estimated standard deviation sigma. If sigma = 0.0 is entered, this will be estimated by Median Absolute Deviance (MAD). do_seeded determines whether to use seeded intervals. If true, shrink is the decay factor for interval length; if not, M random intervals are drawn, and returns the position of found changepoints, and the cost of this segmentation. min_length determines minimum segment length.

See also: @BS, @segment_cost

Returns

• result::Array{NamedTuple{s::Int64, e::Int64, cpt::Int64, CUSUM::Float64, min_th::Float64, scale::Int64}}:
  • s::Int64: Start of window in which maximum CUSUM was located
  • e::Int64: End of window in which maximum CUSUM was located
  • cpt::Int64: Location of maximum CUSUM
  • CUSUM::Float64: Value of maximum CUSUM
  • min_th::Float64: Threshold used
  • scale::Int64: Number of recursion iterations before the change point was detected

Example

using Statistics

# Sample Normal time series with changing mean
n = 1000
λ = 100
μ, σ = Normal(0.0, 10.0), 1.0
sample, cps = @changepoint_sampler n λ Normal(μ, σ)
# Run wild binary segmentation
WBS_return = WBS(sample; sigma = σ)

References

Fryzlewicz, P. (2014) Wild binary segmentation for multiple change-point detection, Annals of Statistics 42(6), 2243-2281 Kovács, S., Li, H., Bühlmann, P., & Munk, A. (2020). Seeded Binary Segmentation: A general methodology for fast and optimal change point detection. arXiv preprint arXiv:2002.06633.

changepoint_plot(data, cps)

Plots time series vector data as a line plot with vertical lines added to mark changepoints in vector cps. The Plots package needs to be loaded in order to use this functionality.

elbow_plot(crops_output)

Plots output of CROPS function as a so-called "elbow plot" which is useful for the purposes of selecting an appropriate changepoint penalty.

mosum_plot(mosum_output)

Plots output of MOSUM procedure. Detector statistic is overlaid with vertical lines marking detected changepoints threshold is marked horizontally. The Plots package needs to be loaded in order to use this functionality.

sSIC(data)

Create a strengthened Schwartz segment cost function for univariate mean change setting

See also: NormalMeanSegment

References

Fryzlewicz, P. (2014) Wild binary segmentation for multiple change-point detection, Annals of Statistics 42(6), 2243-2281

equivalent to [0; cumsum(x)]

@BS data changepoint_model [β₁]

Runs the Binary Segmentation algorithm using a specified changepoint_model for a given penalty β₁. If no penalty specified, use penalty log(length(data)) by default.

See also: BS, @segment_cost

Example

n = 1000   # Length of time series
λ = 100    # Frequency of changepoints
α, β = Uniform(0.0, 10.0), 1.0
# Samples changepoints from Gamma distribution with changing shape
sample, cps = @changepoint_sampler n λ Gamma(α, β)
# Run binary segmentation on sample
bs_cps = @BS sample Gamma(:?, β)

@PELT data changepoint_model [β₁ [β₂] ]

Runs the PELT algorithm on time series data using a specified changepoint_model and penalties. If no penalty β₁ provided, a default of value log(length(data)) is used. If two penalties β₁ and β₂ are provided then the CROPS algorithm is run which finds all optimal segmentations for all penalties between β₁ and β₂.

See also: PELT, CROPS

Example

n = 1000
λ = 100
μ, σ = Normal(0.0, 10.0), 1.0
# Samples changepoints from Normal distribution with changing mean
sample, cps = @changepoint_sampler n λ Normal(μ, σ)
# Run PELT on sample
pelt_cps, pelt_cost = @PELT sample Normal(:?, σ)

@changepoint_sampler(n, λ, Distribution(param1, param2, ...))

Generates sample of size n from Distribution with changes in parameters generated at random intervals. param1, param2, ... are parameters of the sampleable Distribution type, and may be fixed values, or themselves sampleable distributions. Changepoints occur at random times whose separation follows a Poisson distribution with rate λ. At each changepoint, new values for all parameters in param1, param2, ..., which are distributions are sampled.

Returns

• (data::Array, cps::Array{Int}) :
  • data : generated time series
  • cps : array of indices of changepoints

Example

```julia-repl n, λ = 1000, 100 μ, σ = Normal(0.0, 10.0), 1.0 sample, cps = @changepoint_sampler n λ Normal(μ, σ) # Sample changepoints

@segment_cost data changepoint_model

Creates a segment cost function given data and changepoint model expression.

Cost functions

changepoint_model is an expression which describes what segment cost function should be constructed for use with PELT. For parametric segment cost functions, this is represented by the name of a distribution (as in the Distributions package) with some parameters replaced by ':?' to indicate that the parameters change. The full list of available cost functions based on parametric distributions is as follows:

• Normal(:?, σ): Normal model with changing mean and fixed standard deviation σ (see also NormalMeanSegment)
• Normal(μ, :?): Normal model with fixed mean μ and changing standard deviation (see also NormalVarSegment)
• Normal(:?, :?): Normal model with changing mean and standard deviation (see also NormalMeanVarSegment)
• Exponential(:?): Exponential model with changing mean (see also ExponentialSegment)
• Poisson(:?): Poisson model with changing mean (see also PoissonSegment)
• Gamma(:?, β): Gamma model with fixed rate parameter β and changing shape parameter (see also GammaShapeSegment)
• Gamma(α, :?): Gamma model with fixed shape parameter α and changing rate parameter (see also GammaRateSegment)

The following others models are also available:

• Nonparametric(k): Nonparametric cost function with parameter k (see also NonparametricSegment)
• OLS : Cost function for piecewise linear regressions (see also OLSSegment)

Example

n = 1000
λ = 100
μ, σ = Normal(0.0, 10.0), 1.0
# Samples changepoints from Normal distribution with changing mean
sample, cps = @changepoint_sampler n λ Normal(μ, σ)
# Create cost function
seg_cost = @segment_cost sample Normal(:?, σ)
# Calculate changepoints using PELT and BS
pelt_cps, cost = PELT(seg_cost, n)
bs_cps = BS(seg_cost, n)