/*
* Copyright 2015, Yahoo Inc.
* Copyrights licensed under the GPL License.
* See the accompanying LICENSE file for terms.
*/
package com.yahoo.egads.models.adm;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Properties;
import org.json.JSONObject;
import org.json.JSONStringer;
import com.yahoo.egads.data.Anomaly.Interval;
import com.yahoo.egads.data.Anomaly.IntervalSequence;
import com.yahoo.egads.data.TimeSeries.DataSequence;
import com.yahoo.egads.utilities.ListUtils;
/**
* AdaptiveKernelDensityChangePointDetector implements density-based algorithm for change point detection.
*
* Input:
* 1. the residual time-series = actual - expected
* 2. PRE_WINDOW_SIZE: the size of PRE_WINDOW
* 3. POST_WINDOW_SIZE: the size of POST_WINDOW
* 4. CONFIDENCE: the confidence level at which the threshold for the KL-Divergence score is computed.
*
* Output: the time indices when the distribution of residual changes significantly
*
* In particular, the algorithm slides two side-by-side windows (PRE_WINDOW and POST_WINDOW) and computes the KL-divergence between
* the distribution of the residuals in two windows for each time index. The distribution of the residuals in each window is
* computed non-parametrically using Kernel Density Estimation with Gaussian kernels with adaptive bandwidths.
*
* Once the KL-divergence is computed for each time index, it is thresholded (where the threshold is directly proportional to 'CONFIDENCE').
* And finally for each continuous segment of the thresholded KL-divergence time-series, the index of the maximum value is reported as a
* change point.
*
* @author amizadeh
*
*/
public class AdaptiveKernelDensityChangePointDetector extends AnomalyDetectionAbstractModel {
// buffering the residuals
private LinkedList buffer = new LinkedList();
// buffering the standard deviations
private LinkedList sdBuffer = new LinkedList();
// buffering pre-window kernel sums
private LinkedList preKernelSum = new LinkedList();
// buffering post-window kernel sums
private LinkedList postKernelSum = new LinkedList();
// sum of residuals in the buffer
private float sumBuffer = 0;
// sum of squared residuals in the buffer
private float sqrSumBuffer = 0;
private int maxHrsAgo;
private long windowStart;
// KL score
private float[] score = null;
// level sets
private float[] level = null;
// pre-window size (input argument)
protected int preWindowSize = 24;
// post-window size (input argument)
protected int postWindowSize = 48;
// confidence level
protected float confidence = 0.8F;
// Model name.
private String modelName = "AdaptiveKernelDensityChangePointDetector";
public AdaptiveKernelDensityChangePointDetector(Properties config) {
super(config);
this.maxHrsAgo = new Integer(config.getProperty("MAX_ANOMALY_TIME_AGO"));
this.windowStart = new Long(config.getProperty("DETECTION_WINDOW_START_TIME"));
if (config.getProperty("PRE_WINDOW_SIZE") == null) {
throw new IllegalArgumentException("PRE_WINDOW_SIZE is NULL");
}
if (config.getProperty("POST_WINDOW_SIZE") == null) {
throw new IllegalArgumentException("POST_WINDOW_SIZE is NULL");
}
this.preWindowSize = new Integer(config.getProperty("PRE_WINDOW_SIZE"));
this.postWindowSize = new Integer(config.getProperty("POST_WINDOW_SIZE"));
if (config.getProperty("CONFIDENCE") == null) {
this.confidence = 0.8F;
} else {
this.confidence = new Float(config.getProperty("CONFIDENCE"));
}
}
@Override
public void toJson(JSONStringer json_out) throws Exception {
}
@Override
public void fromJson(JSONObject json_obj) throws Exception {
}
@Override
public String getType() {
return "change_point";
}
@Override
public String getModelName() {
return modelName;
}
@Override
public void reset() {
this.buffer.clear();
this.sdBuffer.clear();
this.preKernelSum.clear();
this.postKernelSum.clear();
this.sumBuffer = 0;
this.sqrSumBuffer = 0;
this.score = null;
this.level = null;
}
@Override
public void tune(DataSequence observedSeries, DataSequence expectedSeries, IntervalSequence anomalySequence)
throws Exception {
}
@Override
public IntervalSequence detect(DataSequence observedSeries, DataSequence expectedSeries) throws Exception {
if (observedSeries.size() != expectedSeries.size()) {
throw new Exception("The observed time-series must have the same length as the expected time-series.");
}
long unixTime = System.currentTimeMillis() / 1000L;
IntervalSequence result = new IntervalSequence();
int n = observedSeries.size();
float[] residuals = new float[n];
// Computing the residuals
for (int i = 0; i < n; ++i) {
residuals[i] = observedSeries.get(i).value - expectedSeries.get(i).value;
}
// Detecting change points
ArrayList changePoints =
detectChangePoints(residuals, this.preWindowSize, this.postWindowSize, this.confidence);
// Preparing the output
if (this.outputDest.equals("STD_OUT_ALL")) {
int j = 0;
for (int i = 0; i < n; ++i) {
boolean isCP = false;
if (!changePoints.isEmpty()) {
isCP = (changePoints.get(j) == i);
}
if (isCP && j < (changePoints.size() - 1)) {
j++;
}
logger.debug("TS:" + observedSeries.get(i).time + ",SC:" + String.join(":", arrayF2S(new Float[] {score[i]})) + ",LV:" + arrayF2S(new Float[] {level[i]}) + ",OV:" + observedSeries.get(i).value + ",EV:" + expectedSeries.get(i).value);
result.add(new Interval(observedSeries.get(i).time,
i,
new Float[] {score[i]},
new Float[] {level[i]},
observedSeries.get(i).value,
expectedSeries.get(i).value,
(isCP)));
}
} else {
for (int index : changePoints) {
if (isDetectionWindowPoint(maxHrsAgo, windowStart, observedSeries.get(index).time, observedSeries.get(0).time)) {
result.add(new Interval(observedSeries.get(index).time, index, new Float[] {score[index]},
new Float[] {level[index]}, observedSeries.get(index).value,
expectedSeries.get(index).value));
}
}
}
return result;
}
public ArrayList detectChangePoints(float[] residuals, int preWindowSize, int postWindowSize,
float confidence) {
int n = residuals.length;
score = new float[n];
level = new float[n];
ArrayList changePoints = new ArrayList();
float maxScore = Float.NEGATIVE_INFINITY;
int maxIndex = -1;
float delta = 0.00000001F;
int counter = 0;
for (int i = 0; i < n; ++i, ++counter) {
float[] temp = computeKLScore(residuals[i], preWindowSize, postWindowSize, confidence);
score[i] = temp[0];
level[i] = temp[1];
if (score[i] > delta) {
if (score[i] > maxScore) {
maxScore = score[i];
maxIndex = i;
}
} else if (score[i] < -delta) {
if (maxIndex >= 0) {
if (counter - i + maxIndex > postWindowSize) {
changePoints.add(maxIndex - postWindowSize + 1);
counter = i - maxIndex;
}
maxScore = Float.NEGATIVE_INFINITY;
maxIndex = -1;
}
}
}
if (maxIndex >= 0) {
changePoints.add(maxIndex - postWindowSize + 1);
}
return changePoints;
}
protected float[] computeKLScore(float residual, int preWindowSize, int postWindowSize, float confidence) {
float dKL = 0;
float levelThreshold = 0;
int len = buffer.size();
// Filling the pre-window
if (len < preWindowSize) {
buffer.addLast(residual);
postKernelSum.addLast(0F);
if (len == (preWindowSize - 1)) {
int n = preWindowSize;
sumBuffer = ListUtils.sumQ(buffer);
sqrSumBuffer = ListUtils.sum2Q(buffer);
float temp =
(float) Math.max(
1e-5,
Math.sqrt(2 * (n * sqrSumBuffer - sumBuffer * sumBuffer)
/ (n * (n - 1))));
ListUtils.repQ(sdBuffer, temp, n);
for (float x : buffer) {
preKernelSum.addLast(ListUtils.kernelSum(x, buffer, sdBuffer));
}
}
} else if (len < (preWindowSize + postWindowSize)) { // Filling the post-window
sumBuffer = sumBuffer + residual;
sqrSumBuffer = sqrSumBuffer + residual * residual;
int n = len + 1;
float temp =
(float) Math.max(1e-5,
Math.sqrt(2 * (n * sqrSumBuffer - sumBuffer * sumBuffer) / (n * (n - 1))));
sdBuffer.addLast(temp);
LinkedList tempQ1 = new LinkedList();
tempQ1.add(residual);
LinkedList tempQ2 = new LinkedList();
tempQ2.add(temp);
ListUtils.addQ(postKernelSum, ListUtils.kernelQ(buffer, tempQ1, tempQ2));
buffer.addLast(residual);
preKernelSum.addLast(ListUtils.kernelSubSum(residual, buffer, sdBuffer, 0, preWindowSize - 1));
postKernelSum.addLast(ListUtils.kernelSubSum(residual, buffer, sdBuffer, preWindowSize, buffer.size() - 1));
} else {
// updating the pre-stats
LinkedList preRemovedValues =
ListUtils.kernelQ(buffer, buffer.subList(0, 1), sdBuffer.subList(0, 1));
ListUtils.subtractQ(preKernelSum, preRemovedValues);
LinkedList midExchangedValues =
ListUtils.kernelQ(buffer, buffer.subList(preWindowSize, preWindowSize + 1),
sdBuffer.subList(preWindowSize, preWindowSize + 1));
ListUtils.addQ(preKernelSum, midExchangedValues);
// Computing the new sd
int n = len;
sumBuffer += (residual - buffer.getFirst());
sqrSumBuffer += (residual * residual - Math.pow(buffer.getFirst(), 2));
float temp =
(float) Math.max(1e-5,
Math.sqrt(2 * (n * sqrSumBuffer - sumBuffer * sumBuffer) / (n * (n - 1))));
// updating the post-stats
LinkedList tempQ1 = new LinkedList();
tempQ1.add(residual);
LinkedList tempQ2 = new LinkedList();
tempQ2.add(temp);
ListUtils.subtractQ(postKernelSum, midExchangedValues);
LinkedList postAddedValues = ListUtils.kernelQ(buffer, tempQ1, tempQ2);
ListUtils.addQ(postKernelSum, postAddedValues);
// updating the window
buffer.addLast(residual);
buffer.removeFirst();
sdBuffer.addLast(temp);
sdBuffer.removeFirst();
preKernelSum.addLast(ListUtils.kernelSubSum(residual, buffer, sdBuffer, 0, preWindowSize - 1));
postKernelSum.addLast(ListUtils.kernelSubSum(residual, buffer, sdBuffer, preWindowSize, preWindowSize
+ postWindowSize - 1));
preKernelSum.removeFirst();
postKernelSum.removeFirst();
float eps = 1e-10F;
LinkedList preDensity =
ListUtils.maxQ(preKernelSum.subList(preWindowSize, preWindowSize + postWindowSize), eps);
LinkedList postDensity =
ListUtils.maxQ(postKernelSum.subList(preWindowSize, preWindowSize + postWindowSize), eps);
tempQ1.clear();
tempQ1.addAll(preKernelSum.subList(0, preWindowSize));
tempQ2.clear();
tempQ2.add(1.0F / preWindowSize);
ListUtils.multiplyQ(tempQ1, tempQ2);
float levelSet = ListUtils.quantile(tempQ1, 1 - confidence);
levelThreshold =
(float) (-Math.log(levelSet) - Math.log(2 * Math.PI) / 2 - ListUtils.sumLog(sdBuffer
.subList(preWindowSize, preWindowSize + postWindowSize)) / postWindowSize);
// computing the KL-divergence
dKL =
(float) ((ListUtils.sumLog(postDensity) - ListUtils.sumLog(preDensity) + Math
.log(preWindowSize / postWindowSize))
/ postWindowSize
+ Math.log(levelSet * Math.sqrt(2 * Math.PI)) + ListUtils.sumLog(sdBuffer
.subList(preWindowSize, preWindowSize + postWindowSize)) / postWindowSize);
}
return new float[] {dKL, levelThreshold};
}
}
Ads help maintain this website.