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. 17early 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. 44also 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
All Methods Static Methods Instance Methods Concrete Methods 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 relationstatic void
shuffle(double[] bstrap, int len, java.util.Random rnd)
Fisher-Yates shuffle of a partial array
-
-
-
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
- ConfidencebootstrapSteps
- 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 interfaceAlgorithm
- 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 dataout
- 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 sumsbegin
- Interval beginend
- 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 shufflelen
- Length of valid datarnd
- Random generator
-
-