Package elki.timeseries

Class OfflineChangePointDetectionAlgorithm

java.lang.Object

elki.timeseries.OfflineChangePointDetectionAlgorithm

All Implemented Interfaces:

Algorithm

@Title("Off-line Change Point Detection")
@Description("Detects multiple change points in a time series")
@Reference(authors="D. Picard",title="Testing and Estimating Change-Points in Time Series ",booktitle="Advances in Applied Probability Vol. 17",url="https://doi.org/10.2307/1427090",bibkey="doi:10.2307/1427090") @Reference(authors="E. S. Page",title="On Problems in which a Change in a Parameter Occurs at an Unknown Point",booktitle="Biometrika Vol. 44",url="https://doi.org/10.2307/2333258",bibkey="doi:10.2307/2333258") @Reference(authors="M. Basseville, I. V. Nikiforov",title="Section 2.6: Off-line Change Detection",booktitle="Detection of Abrupt Changes - Theory and Application",url="http://people.irisa.fr/Michele.Basseville/kniga/kniga.pdf",bibkey="books/prentice/BassevilleN93/C2")
public class OfflineChangePointDetectionAlgorithm
extends java.lang.Object
implements Algorithm

Off-line change point detection algorithm detecting a change in mean, based on the cumulative sum (CUSUM), same-variance assumption, and using bootstrap sampling for significance estimation.

References:

D. Picard
Testing and Estimating Change-Points in Time Series
Advances in Applied Probability Vol. 17

early results along these lines can be found in:

E. S. Page
On Problems in which a Change in a Parameter Occurs at an Unknown Point
Biometrika Vol. 44

also discussed in:

M. Basseville and I. V. Nikiforov
Section 2.6: Off-line Change Detection
Detection of Abrupt Changes - Theory and Application

Since:

0.7.5

Author:

Sebastian Rühl, Erich Schubert

Nested Class Summary

Nested Classes

Modifier and Type	Class	Description
(package private) class	OfflineChangePointDetectionAlgorithm.Instance	Instance for a single data set.
static class	OfflineChangePointDetectionAlgorithm.Par	Parameterization class.

Nested classes/interfaces inherited from interface elki.Algorithm

Algorithm.Utils

Field Summary

Fields

Modifier and Type	Field	Description
(package private) int	bootstrapSamples	Number of samples for bootstrap significance.
(package private) double	minConfidence	Mininum confidence.
(package private) RandomFactory	rnd	Random generator

Constructor Summary

Constructors

Constructor	Description
OfflineChangePointDetectionAlgorithm(double confidence, int bootstrapSteps, RandomFactory rnd)	Constructor

Method Summary

Modifier and Type	Method	Description
static DoubleIntPair	bestChangeInMean(double[] sums, int begin, int end)	Find the best position to assume a change in mean.
static void	cusum(double[] data, double[] out, int begin, int end)	Compute the incremental sum of an array, i.e. the sum of all points up to the given index.
TypeInformation[]	getInputTypeRestriction()	Get the input type restriction used for negotiating the data query.
ChangePoints	run(Relation<DoubleVector> relation)	Executes multiple change point detection for given relation
static void	shuffle(double[] bstrap, int len, java.util.Random rnd)	Fisher-Yates shuffle of a partial array

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Methods inherited from interface elki.Algorithm

autorun

Field Detail

bootstrapSamples

int bootstrapSamples

Number of samples for bootstrap significance.

minConfidence

double minConfidence

Mininum confidence.

rnd

RandomFactory rnd

Random generator

Constructor Detail

OfflineChangePointDetectionAlgorithm

public OfflineChangePointDetectionAlgorithm(double confidence,
                                            int bootstrapSteps,
                                            RandomFactory rnd)

Constructor

Parameters:

confidence - Confidence

bootstrapSteps - Steps for bootstrapping

Method Detail

getInputTypeRestriction

public TypeInformation[] getInputTypeRestriction()

Description copied from interface: Algorithm

Get the input type restriction used for negotiating the data query.

Specified by:

getInputTypeRestriction in interface Algorithm

Returns:

Type restriction

run

public ChangePoints run(Relation<DoubleVector> relation)

Executes multiple change point detection for given relation

Parameters:

relation - the relation to process

Returns:

list with all the detected change point for every time series

cusum

public static void cusum(double[] data,
                         double[] out,
                         int begin,
                         int end)

Compute the incremental sum of an array, i.e. the sum of all points up to the given index.

Parameters:

data - Input data

out - Output array (must be large enough).

bestChangeInMean

public static DoubleIntPair bestChangeInMean(double[] sums,
                                             int begin,
                                             int end)

Find the best position to assume a change in mean.

Parameters:

sums - Cumulative sums

begin - Interval begin

end - Interval end

Returns:

Best change position

shuffle

public static void shuffle(double[] bstrap,
                           int len,
                           java.util.Random rnd)

Fisher-Yates shuffle of a partial array

Parameters:

bstrap - Data to shuffle

len - Length of valid data

rnd - Random generator