de.lmu.ifi.dbs.elki.algorithm.timeseries

Class OfflineChangePointDetectionAlgorithm

java.lang.Object

de.lmu.ifi.dbs.elki.algorithm.AbstractAlgorithm<ChangePoints>

de.lmu.ifi.dbs.elki.algorithm.timeseries.OfflineChangePointDetectionAlgorithm

All Implemented Interfaces:

Algorithm

@Title(value="Off-line Change Point Detection")
 @Description(value="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 AbstractAlgorithm<ChangePoints>

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 and Description
(package private) class	OfflineChangePointDetectionAlgorithm.Instance Instance for a single data set.
static class	OfflineChangePointDetectionAlgorithm.Parameterizer Parameterization class.

Field Summary

Fields

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

Fields inherited from class de.lmu.ifi.dbs.elki.algorithm.AbstractAlgorithm

ALGORITHM_ID

Constructor Summary

Constructors

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

Method Summary

Modifier and Type	Method and 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.
protected Logging	getLogger() Get the (STATIC) logger for this class.
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 de.lmu.ifi.dbs.elki.algorithm.AbstractAlgorithm

run

Methods inherited from class java.lang.Object

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

Field Detail

LOG

private static final Logging LOG

Class logger

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

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

getInputTypeRestriction

public TypeInformation[] getInputTypeRestriction()

Description copied from class: AbstractAlgorithm

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

Specified by:

getInputTypeRestriction in interface Algorithm

Specified by:

getInputTypeRestriction in class AbstractAlgorithm<ChangePoints>

Returns:

Type restriction

getLogger

protected Logging getLogger()

Description copied from class: AbstractAlgorithm

Get the (STATIC) logger for this class.

Specified by:

getLogger in class AbstractAlgorithm<ChangePoints>

Returns:

the static logger