Changepoints.BSMethod
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

Changepoints.CROPSMethod
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 β₂.

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

Changepoints.MOSUMMethod
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).

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).

Changepoints.MOSUM_multi_scaleMethod
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.

Changepoints.NormalMeanSegmentFunction
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.

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)
Changepoints.PELTMethod
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.

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

Changepoints.WBSMethod
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.

Changepoints.changepoint_plotFunction
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.

Changepoints.elbow_plotFunction
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.

Changepoints.mosum_plotFunction
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.

Changepoints.sSICMethod
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

Changepoints.@BSMacro
@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(:?, β)
Changepoints.@PELTMacro
@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(:?, σ)
Changepoints.@changepoint_samplerMacro
@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

Changepoints.@segment_costMacro
@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:

The following others models are also available:

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)`