jsat.driftdetectors

Class ADWIN<V>

java.lang.Object

jsat.driftdetectors.BaseDriftDetector<V>

jsat.driftdetectors.ADWIN<V>

All Implemented Interfaces:

Serializable, Cloneable

public class ADWIN<V>
extends BaseDriftDetector<V>

Adaptive Windowing (ADWIN) is an algorithm for detecting changes in an input stream. ADWIN maintains an approximated window of the input history, and works in O(log(n)) time and O(log(n)) memory, where n is the current window size. Whenever a drift is detected and handled, the size of the window will be reduced.

The window in ADWIN is only for the double values passed when calling addSample(double, java.lang.Object). The object paired with the numeric value will not be compressed and is added to on every update. It is important to control its size using BaseDriftDetector.setMaxHistory(int) when using ADWIN. By default, ADWIN will use a maximum history of 0.

See: Bifet, A.,&Gavalda, R. (2007). Learning from Time-Changing Data with Adaptive Windowing. In SIAM International Conference on Data Mining.

Author:

Edward Raff

See Also:

Serialized Form

Field Summary

Fields inherited from class jsat.driftdetectors.BaseDriftDetector

drifting, driftStart, history, maxHistory, time, warning

Constructor Summary

Constructors

Constructor and Description
ADWIN(ADWIN<V> toCopy) Copy constructor
ADWIN(double delta) Creates a new ADWIN object for detecting changes in the mean value of a stream of inputs.
ADWIN(double delta, int maxHistory) Creates a new ADWIN object for detecting changes in the mean value of a stream of inputs.

Method Summary

Modifier and Type	Method and Description
boolean	addSample(double value, V obj) Adds a new point to the drift detector.
ADWIN<V>	clone()
void	driftHandled() This method should be called once the drift is handled.
void	driftHandled(boolean dropOld) This implementation of ADWIN allows for choosing to drop either the old values, as is normal for a drift detector, or to drop the newer values.
double	getDelta() Returns the upper bound on false positives
int	getM() Returns the accuracy / speed parameter for ADWIN
double	getMean() Returns the mean value for all inputs contained in the current window
double	getNewMean() Returns the mean value determined for the newer values that we have drifted into.
double	getNewStndDev() Returns the standard deviation for the newer values that we have drifted into.
double	getNewVariance() Returns the variance for the newer values that we have drifted into.
double	getOldMean() Returns the mean value determined for the older values that we have drifted away from.
double	getOldStndDev() Returns the standard deviation for the older values that we have drifted away from.
double	getOldVariance() Returns the variance for the older values that we have drifted away from.
double	getStndDev() Returns the standard deviation for all inputs contained in the current window.
double	getVariance() Returns the variance for all inputs contained in the current window
int	getWidnowLength() This returns the current "length" of the window, which is the number of items that have been added to the ADWIN object since the last drift, and is reduced when drift occurres.
void	setDelta(double delta) Sets the upper bound on the false positive rate for detecting concept drifts
void	setM(int M) This parameter controls the trade off of space and accuracy for the sliding window.

Methods inherited from class jsat.driftdetectors.BaseDriftDetector

addToHistory, clearHistory, getDriftAge, getDriftedHistory, getMaxHistory, isDrifting, isWarning, setMaxHistory

Methods inherited from class java.lang.Object

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

Constructor Detail

ADWIN

public ADWIN(double delta)

Creates a new ADWIN object for detecting changes in the mean value of a stream of inputs. It will use a not keep any object history by default.

Parameters:

delta - the desired false positive rate

ADWIN

public ADWIN(double delta,
             int maxHistory)

Creates a new ADWIN object for detecting changes in the mean value of a stream of inputs.

Parameters:

delta - the desired false positive rate

maxHistory - the maximum history of objects to keep

ADWIN

public ADWIN(ADWIN<V> toCopy)

Copy constructor

Parameters:

toCopy - the object to copy

Method Detail

setDelta

public void setDelta(double delta)

Sets the upper bound on the false positive rate for detecting concept drifts

Parameters:

delta - the upper bound on false positives in (0,1)

getDelta

public double getDelta()

Returns the upper bound on false positives

Returns:

the upper bound on false positives

setM

public void setM(int M)

This parameter controls the trade off of space and accuracy for the sliding window. The larger M becomes, the more accurate the window will be - but at the cost of execution speed.

Parameters:

M - the window space constant in [1, ∞)

getM

public int getM()

Returns the accuracy / speed parameter for ADWIN

Returns:

the accuracy / speed parameter

addSample

public boolean addSample(double value,
                         V obj)

Description copied from class: BaseDriftDetector

Adds a new point to the drift detector. If an escalation in state occurs, true will be returned. A change of state could be either drift occurring BaseDriftDetector.isDrifting() or a warning state BaseDriftDetector.isWarning(). If the detector was in a warning state and then goes back to normal, false will be returned.

For binary (true / false) drift detectors, value will be considered false if and only if its value is equal to zero. Any non zero value will be treated as true

Objects added with the value may or may not be added to the history, the behavior is algorithm dependent. Some may always add it to the history, while others will only begin collecting history once a warning state occurs.

Specified by:

addSample in class BaseDriftDetector<V>

Parameters:

value - the numeric value to add to the drift detector

obj - the object associated with this value. It may or may not be stored in the detectors history

Returns:

true if a drift has or may be starting.

getMean

public double getMean()

Returns the mean value for all inputs contained in the current window

Returns:

the mean value of the window

getVariance

public double getVariance()

Returns the variance for all inputs contained in the current window

Returns:

the variance for the window

getStndDev

public double getStndDev()

Returns the standard deviation for all inputs contained in the current window.

Returns:

the standard deviation for the window

getWidnowLength

public int getWidnowLength()

This returns the current "length" of the window, which is the number of items that have been added to the ADWIN object since the last drift, and is reduced when drift occurres.

Returns:

the number of items stored implicitly in the window

getOldMean

public double getOldMean()

Returns the mean value determined for the older values that we have drifted away from.
If drifting has not occurred or has already been handled, Double.NaN will be returned.

Returns:

the mean for the old values.

getOldVariance

public double getOldVariance()

Returns the variance for the older values that we have drifted away from.
If drifting has not occurred or has already been handled, Double.NaN will be returned.

Returns:

the variance for the old values

getOldStndDev

public double getOldStndDev()

Returns the standard deviation for the older values that we have drifted away from.
If drifting has not occurred or has already been handled, Double.NaN will be returned.

Returns:

the standard deviation for the old values

getNewMean

public double getNewMean()

Returns the mean value determined for the newer values that we have drifted into.
If drifting has not occurred or has already been handled, Double.NaN will be returned.

Returns:

the mean for the newer values.

getNewVariance

public double getNewVariance()

Returns the variance for the newer values that we have drifted into.
If drifting has not occurred or has already been handled, Double.NaN will be returned.

Returns:

the variance for the newer values

getNewStndDev

public double getNewStndDev()

Returns the standard deviation for the newer values that we have drifted into.
If drifting has not occurred or has already been handled, Double.NaN will be returned.

Returns:

the standard deviation for the newer values

driftHandled

public void driftHandled(boolean dropOld)

This implementation of ADWIN allows for choosing to drop either the old values, as is normal for a drift detector, or to drop the newer values. Passing true will result in the standard behavior of calling driftHandled().
If false is passed in to drop the newer values that drifted it is probably that continuing to add new examples will continue to cause detections.

Parameters:

dropOld - true to drop the older values out of the window that we drifted away from, or false to drop the newer values and retain the old ones.

driftHandled

public void driftHandled()

Description copied from class: BaseDriftDetector

This method should be called once the drift is handled. Once done, this method will clear the flags and prepare the detector to continue tracking drift again.
By using this method, one can continue to track multiple future drift changes without having to feed the history data (which may be incomplete) into a new detector object.

Overrides:

driftHandled in class BaseDriftDetector<V>

clone

public ADWIN<V> clone()

Specified by:

clone in class BaseDriftDetector<V>