package jsat.driftdetectors;
import java.util.*;
import jsat.math.OnLineStatistics;
/**
* 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 {@code double} values passed when calling
* {@link #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 {@link #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
*/
public class ADWIN extends BaseDriftDetector
{
private static final long serialVersionUID = 3287510845017257629L;
private double delta;
private OnLineStatistics allStats;
/**
* List of all the stats summarizing the windows. New items are added to the
* tail end of the list so that we can iterate from the "head" down. This
* makes writing the logic somewhat easier.
* This means the head contains the oldest /largest items, and the tail
* contains the smallest / newest items. This is opposite of the ADWIN paper
*/
private LinkedList windows;
/*
* default: "We use, somewhat arbitrarily, M = 5 for all experiments" under
* section: 4 Experimental Validation of ADWIN2
*/
private int M = 5;
//Data used when a change is deteceted
private double leftMean = Double.NaN, leftVariance = Double.NaN;
private double rightMean = Double.NaN, rightVariance = Double.NaN;
/**
* 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.
* @param delta the desired false positive rate
*/
public ADWIN(double delta)
{
this(delta, 0);
}
/**
* Creates a new ADWIN object for detecting changes in the mean value of a
* stream of inputs.
* @param delta the desired false positive rate
* @param maxHistory the maximum history of objects to keep
*/
public ADWIN(double delta, int maxHistory)
{
super();
setDelta(delta);
setMaxHistory(maxHistory);
allStats = new OnLineStatistics();
windows = new LinkedList();
}
/**
* Copy constructor
* @param toCopy the object to copy
*/
public ADWIN(ADWIN toCopy)
{
super(toCopy);
this.delta = toCopy.delta;
this.allStats = toCopy.allStats.clone();
this.M = toCopy.M;
this.leftMean = toCopy.leftMean;
this.rightMean = toCopy.rightMean;
this.leftVariance = toCopy.leftVariance;
this.rightVariance = toCopy.rightVariance;
this.windows = new LinkedList();
for(OnLineStatistics stats : toCopy.windows)
this.windows.add(stats.clone());
}
/**
* Sets the upper bound on the false positive rate for detecting concept
* drifts
* @param delta the upper bound on false positives in (0,1)
*/
public void setDelta(double delta)
{
if(delta <= 0 || delta >= 1 || Double.isNaN(delta))
throw new IllegalArgumentException("delta must be in (0,1), not " + delta);
this.delta = delta;
}
/**
* Returns the upper bound on false positives
* @return the upper bound on false positives
*/
public double getDelta()
{
return delta;
}
/**
* This parameter controls the trade off of space and accuracy for the
* sliding window. The larger {@code M} becomes, the more accurate the
* window will be - but at the cost of execution speed.
* @param M the window space constant in [1, ∞)
*/
public void setM(int M)
{
if(M < 1)
throw new IllegalArgumentException("M must be positive, not " + M);
this.M = M;
}
/**
* Returns the accuracy / speed parameter for ADWIN
* @return the accuracy / speed parameter
*/
public int getM()
{
return M;
}
@Override
public boolean addSample(double value, V obj)
{
if(drifting)
throw new UnhandledDriftException("Drift must be handled before continuing");
time++;
addToHistory(obj);
//add to the window
allStats.add(value);
OnLineStatistics w = new OnLineStatistics();
w.add(value);
windows.addFirst(w);
//check if a change has occured
Iterator testIter = windows.descendingIterator();
OnLineStatistics leftStats = new OnLineStatistics();
OnLineStatistics rightStats = allStats.clone();
final double deltaPrime = delta/Math.log(allStats.getSumOfWeights());//will be > 1 in log, no issues
final double ln2delta = Math.log(2) - Math.log(deltaPrime);
final double variance_W = allStats.getVarance();
while(testIter.hasNext())
{
OnLineStatistics windowItem = testIter.next();
//accumulate left side statistics
leftStats.add(windowItem);
//decrament right side stats
rightStats.remove(windowItem);
double n_0 = leftStats.getSumOfWeights();
double n_1 = rightStats.getSumOfWeights();
double mu_0 = leftStats.getMean();
double mu_1 = rightStats.getMean();
// 1/(1/x+1/y) = x y / (x + y), and then inverse so (x+y)/(xy)
double mInv = (n_0 + n_1) / (n_0 * n_1);
double e_cut = Math.sqrt(2 * mInv * variance_W * ln2delta) + 2.0 / 3.0 * mInv * ln2delta;
if(Math.abs(mu_0 - mu_1) > e_cut)//CHANGE! OMG
{
drifting = true;
driftStart = (int) (n_0);
//set stats for them to find
leftMean = mu_0;
leftVariance = leftStats.getVarance();
rightMean = mu_1;
rightVariance = rightStats.getVarance();
/*
* we keep going incase there is a more recent start point for
* the drift, as the change in mean at the front could have been
* large enough / dramatic enough to make preciding cuts also
* look like drift
*/
}
}
compress();
return drifting;
}
/**
* Compresses the current window
*/
private void compress()
{
//compress
ListIterator listIter = windows.listIterator();
double lastSizeSeen = -Double.MAX_VALUE;
int lastSizeCount = 0;
while(listIter.hasNext())
{
OnLineStatistics window = listIter.next();
double n = window.getSumOfWeights();
if(n == lastSizeSeen)
{
if(++lastSizeCount > M)//compress, can only occur if there is a previous
{
listIter.previous();
window.add(listIter.previous());
listIter.remove();//remove the preivous
if(listIter.hasNext())
listIter.next();//back to where we were, which has been modified
//so nowe we must be looking at a new range since we just promoted a window
lastSizeSeen = window.getSumOfWeights();
lastSizeCount = 1;
}
}
else
{
lastSizeSeen = n;
lastSizeCount = 1;
}
}
}
/**
* Returns the mean value for all inputs contained in the current window
* @return the mean value of the window
*/
public double getMean()
{
return allStats.getMean();
}
/**
* Returns the variance for all inputs contained in the current window
* @return the variance for the window
*/
public double getVariance()
{
return allStats.getVarance();
}
/**
* Returns the standard deviation for all inputs contained in the current
* window.
* @return the standard deviation for the window
*/
public double getStndDev()
{
return allStats.getStandardDeviation();
}
/**
* 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.
* @return the number of items stored implicitly in the window
*/
public int getWidnowLength()
{
return time;
}
/**
* 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,
* {@link Double#NaN} will be returned.
* @return the mean for the old values.
*/
public double getOldMean()
{
return leftMean;
}
/**
* Returns the variance for the older values that we have
* drifted away from.
* If drifting has not occurred or has already been handled,
* {@link Double#NaN} will be returned.
* @return the variance for the old values
*/
public double getOldVariance()
{
return leftVariance;
}
/**
* Returns the standard deviation for the older values that we have
* drifted away from.
* If drifting has not occurred or has already been handled,
* {@link Double#NaN} will be returned.
* @return the standard deviation for the old values
*/
public double getOldStndDev()
{
return Math.sqrt(leftVariance);
}
/**
* Returns the mean value determined for the newer values that we have
* drifted into.
* If drifting has not occurred or has already been handled,
* {@link Double#NaN} will be returned.
* @return the mean for the newer values.
*/
public double getNewMean()
{
return rightMean;
}
/**
* Returns the variance for the newer values that we have
* drifted into.
* If drifting has not occurred or has already been handled,
* {@link Double#NaN} will be returned.
* @return the variance for the newer values
*/
public double getNewVariance()
{
return rightVariance;
}
/**
* Returns the standard deviation for the newer values that we have
* drifted into.
* If drifting has not occurred or has already been handled,
* {@link Double#NaN} will be returned.
* @return the standard deviation for the newer values
*/
public double getNewStndDev()
{
return Math.sqrt(rightVariance);
}
/**
* 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 {@code true} will result in the standard behavior of
* calling {@link #driftHandled() }.
* If {@code 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.
*
* @param dropOld {@code true} to drop the older values out of the window
* that we drifted away from, or {@code false} to drop the newer values and
* retain the old ones.
*/
public void driftHandled(boolean dropOld)
{
/*
* Iterate through and either drop everything to the left OR the right
* Track statiscits so that we can update allStats
*/
Iterator testIter = windows.descendingIterator();
OnLineStatistics leftStats = new OnLineStatistics();
while (testIter.hasNext())
{
OnLineStatistics windowItem = testIter.next();
//accumulate left side statistics
if(leftStats.getSumOfWeights() < driftStart)
{
leftStats.add(windowItem);
if(dropOld)
testIter.remove();
}
else
{
if(!dropOld)
testIter.remove();
}
}
if(dropOld)
allStats.remove(leftStats);
else
allStats = leftStats;
time = (int) allStats.getSumOfWeights();
leftMean = leftVariance = rightMean = rightVariance = Double.NaN;
//Calling at the end b/c we need driftStart's value
super.driftHandled();
}
@Override
public void driftHandled()
{
this.driftHandled(true);
}
@Override
public ADWIN clone()
{
return new ADWIN(this);
}
}
Ads help maintain this website.