2016-02-15 Ryosuke Niwa <rniwa@webkit.org>
+ Extract the code specific to v2 UI out of shared statistics.js
+ https://bugs.webkit.org/show_bug.cgi?id=154277
+
+ Reviewed by Chris Dumez.
+
+ Extracted statistics-strategies.js out of statistics.js for v2 UI and detect-changes.js. The intent is to
+ deprecate this file once we implement refined statistics tools in v3 UI and adopt it in detect-changes.js.
+
+ * public/shared/statistics.js:
+ (Statistics.movingAverage): Extracted from the "Simple Moving Average" strategy.
+ (Statistics.cumultaiveMovingAverage): Extracted from the "Cumulative Moving Average" strategy.
+ (Statistics.exponentialMovingAverage): Extracted from the "Exponential Moving Average" strategy.
+ Use a temporary "movingAverage" to keep the last moving average instead of relying on the previous
+ entry in "averages" array to avoid special casing an array of length 1 and starting the loop at i = 1.
+ (Statistics.segmentTimeSeriesGreedyWithStudentsTTest): Extracted from "Segmentation: Recursive t-test"
+ strategy. Don't create the list of averages to match segmentTimeSeriesByMaximizingSchwarzCriterion here.
+ It's done in newly added averagesFromSegments.
+ (Statistics.segmentTimeSeriesByMaximizingSchwarzCriterion): Extracted from
+ "Segmentation: Schwarz criterion" strategy.
+ (.recursivelySplitIntoTwoSegmentsAtMaxTIfSignificantlyDifferent): Just store the start index to match
+ * public/v2/app.js:
+ (App.Pane.updateStatisticsTools):
+ (App.Pane._computeMovingAverageAndOutliers):
+ * public/v2/data.js:
+ * public/v2/index.html:
+ * public/v2/statistics-strategies.js: Added.
+ (StatisticsStrategies.MovingAverageStrategies): Added.
+ (averagesFromSegments): Extracted from "Segmentation: Schwarz criterion" strategy. Now used by both
+ "Segmentation: Recursive t-test" and "Segmentation: Schwarz criterion" strategies.
+ (StatisticsStrategies.EnvelopingStrategies): Moved from Statistics.EnvelopingStrategies.
+ (StatisticsStrategies.TestRangeSelectionStrategies): Moved from Statistics.TestRangeSelectionStrategies.
+ (createWesternElectricRule): Moved from statistics.js.
+ (countValuesOnSameSide): Ditto.
+ (StatisticsStrategies.executeStrategy): Moved from Statistics.executeStrategy.
+ * tools/detect-changes.js:
+ (computeRangesForTesting):
+
+2016-02-15 Ryosuke Niwa <rniwa@webkit.org>
+
v1 UI and v2 UI should share statistics.js
https://bugs.webkit.org/show_bug.cgi?id=154262
}
}
+ this.movingAverage = function (values, backwardWindowSize, forwardWindowSize) {
+ var averages = new Array(values.length);
+ // We use naive O(n^2) algorithm for simplicy as well as to avoid accumulating round-off errors.
+ for (var i = 0; i < values.length; i++) {
+ var sum = 0;
+ var count = 0;
+ for (var j = i - backwardWindowSize; j < i + backwardWindowSize; j++) {
+ if (j >= 0 && j < values.length) {
+ sum += values[j];
+ count++;
+ }
+ }
+ averages[i] = sum / count;
+ }
+ return averages;
+ }
+
+ this.cumulativeMovingAverage = function (values) {
+ var averages = new Array(values.length);
+ var sum = 0;
+ for (var i = 0; i < values.length; i++) {
+ sum += values[i];
+ averages[i] = sum / (i + 1);
+ }
+ return averages;
+ }
+
+ this.exponentialMovingAverage = function (values, smoothingFactor) {
+ var averages = new Array(values.length);
+ var movingAverage = 0;
+ for (var i = 0; i < values.length; i++) {
+ movingAverage = smoothingFactor * values[i] + (1 - smoothingFactor) * movingAverage;
+ averages[i] = movingAverage;
+ }
+ return averages;
+ }
+
+ // The return value is the starting indices of each segment.
+ this.segmentTimeSeriesGreedyWithStudentsTTest = function (values, minLength) {
+ if (values.length < 2)
+ return [0];
+ var segments = new Array;
+ recursivelySplitIntoTwoSegmentsAtMaxTIfSignificantlyDifferent(values, 0, values.length, minLength, segments);
+ segments.push(values.length);
+ return segments;
+ }
+
+ this.debuggingSegmentation = false;
+ this.segmentTimeSeriesByMaximizingSchwarzCriterion = function (values) {
+ if (values.length < 2)
+ return [0];
+
+ // Split the time series into grids since splitIntoSegmentsUntilGoodEnough is O(n^2).
+ var gridLength = 500;
+ var totalSegmentation = [0];
+ for (var gridCount = 0; gridCount < Math.ceil(values.length / gridLength); gridCount++) {
+ var gridValues = values.slice(gridCount * gridLength, (gridCount + 1) * gridLength);
+ var segmentation = splitIntoSegmentsUntilGoodEnough(gridValues);
+
+ if (Statistics.debuggingSegmentation)
+ console.log('grid=' + gridCount, segmentation);
+
+ for (var i = 1; i < segmentation.length - 1; i++)
+ totalSegmentation.push(gridCount * gridLength + segmentation[i]);
+ }
+
+ if (Statistics.debuggingSegmentation)
+ console.log('Final Segmentation', totalSegmentation);
+
+ totalSegmentation.push(values.length);
+
+ return totalSegmentation;
+ }
+
function recursivelySplitIntoTwoSegmentsAtMaxTIfSignificantlyDifferent(values, startIndex, length, minLength, segments) {
var tMax = 0;
var argTMax = null;
}
}
if (!tMax) {
- segments.push(values.slice(startIndex, startIndex + length));
+ segments.push(startIndex);
return;
}
recursivelySplitIntoTwoSegmentsAtMaxTIfSignificantlyDifferent(values, startIndex, argTMax, minLength, segments);
function oneSidedToTwoSidedProbability(probability) { return 2 * probability - 1; }
function twoSidedToOneSidedProbability(probability) { return (1 - (1 - probability) / 2); }
- this.MovingAverageStrategies = [
- {
- id: 1,
- label: 'Simple Moving Average',
- parameterList: [
- {label: "Backward window size", value: 8, min: 2, step: 1},
- {label: "Forward window size", value: 4, min: 0, step: 1}
- ],
- execute: function (backwardWindowSize, forwardWindowSize, values) {
- var averages = new Array(values.length);
- // We use naive O(n^2) algorithm for simplicy as well as to avoid accumulating round-off errors.
- for (var i = 0; i < values.length; i++) {
- var sum = 0;
- var count = 0;
- for (var j = i - backwardWindowSize; j < i + backwardWindowSize; j++) {
- if (j >= 0 && j < values.length) {
- sum += values[j];
- count++;
- }
- }
- averages[i] = sum / count;
- }
- return averages;
- },
-
- },
- {
- id: 2,
- label: 'Cumulative Moving Average',
- execute: function (values) {
- var averages = new Array(values.length);
- var sum = 0;
- for (var i = 0; i < values.length; i++) {
- sum += values[i];
- averages[i] = sum / (i + 1);
- }
- return averages;
- }
- },
- {
- id: 3,
- label: 'Exponential Moving Average',
- parameterList: [{label: "Smoothing factor", value: 0.1, min: 0.001, max: 0.9}],
- execute: function (smoothingFactor, values) {
- if (!values.length || typeof(smoothingFactor) !== "number")
- return null;
-
- var averages = new Array(values.length);
- var movingAverage = 0;
- averages[0] = values[0];
- for (var i = 1; i < values.length; i++)
- averages[i] = smoothingFactor * values[i] + (1 - smoothingFactor) * averages[i - 1];
- return averages;
- }
- },
- {
- id: 4,
- isSegmentation: true,
- label: 'Segmentation: Recursive t-test',
- description: "Recursively split values into two segments if Welch's t-test detects a statistically significant difference.",
- parameterList: [{label: "Minimum segment length", value: 20, min: 5}],
- execute: function (minLength, values) {
- if (values.length < 2)
- return null;
-
- var averages = new Array(values.length);
- var segments = new Array;
- recursivelySplitIntoTwoSegmentsAtMaxTIfSignificantlyDifferent(values, 0, values.length, minLength, segments);
- var averageIndex = 0;
- for (var j = 0; j < segments.length; j++) {
- var values = segments[j];
- var mean = Statistics.sum(values) / values.length;
- for (var i = 0; i < values.length; i++)
- averages[averageIndex++] = mean;
- }
-
- return averages;
- }
- },
- {
- id: 5,
- isSegmentation: true,
- label: 'Segmentation: Schwarz criterion',
- description: 'Adaptive algorithm that maximizes the Schwarz criterion (BIC).',
- // Based on Detection of Multiple Change–Points in Multivariate Time Series by Marc Lavielle (July 2006).
- execute: function (values) {
- if (values.length < 2)
- return null;
-
- var averages = new Array(values.length);
- var averageIndex = 0;
-
- // Split the time series into grids since splitIntoSegmentsUntilGoodEnough is O(n^2).
- var gridLength = 500;
- var totalSegmentation = [0];
- for (var gridCount = 0; gridCount < Math.ceil(values.length / gridLength); gridCount++) {
- var gridValues = values.slice(gridCount * gridLength, (gridCount + 1) * gridLength);
- var segmentation = splitIntoSegmentsUntilGoodEnough(gridValues);
-
- if (Statistics.debuggingSegmentation)
- console.log('grid=' + gridCount, segmentation);
-
- for (var i = 1; i < segmentation.length - 1; i++)
- totalSegmentation.push(gridCount * gridLength + segmentation[i]);
- }
-
- if (Statistics.debuggingSegmentation)
- console.log('Final Segmentation', totalSegmentation);
-
- totalSegmentation.push(values.length);
-
- for (var i = 1; i < totalSegmentation.length; i++) {
- var segment = values.slice(totalSegmentation[i - 1], totalSegmentation[i]);
- var average = Statistics.sum(segment) / segment.length;
- for (var j = 0; j < segment.length; j++)
- averages[averageIndex++] = average;
- }
-
- return averages;
- }
- },
- ];
-
- this.debuggingSegmentation = false;
-
function splitIntoSegmentsUntilGoodEnough(values) {
if (values.length < 2)
return [0, values.length];
return this.costMatrix[from][to - from - 1];
}
- this.EnvelopingStrategies = [
- {
- id: 100,
- label: 'Average Difference',
- description: 'The average difference between consecutive values.',
- execute: function (values, movingAverages) {
- if (values.length < 1)
- return NaN;
-
- var diff = 0;
- for (var i = 1; i < values.length; i++)
- diff += Math.abs(values[i] - values[i - 1]);
-
- return diff / values.length;
- }
- },
- {
- id: 101,
- label: 'Moving Average Standard Deviation',
- description: 'The square root of the average deviation from the moving average with Bessel\'s correction.',
- execute: function (values, movingAverages) {
- if (values.length < 1)
- return NaN;
-
- var diffSquareSum = 0;
- for (var i = 1; i < values.length; i++) {
- var diff = (values[i] - movingAverages[i]);
- diffSquareSum += diff * diff;
- }
-
- return Math.sqrt(diffSquareSum / (values.length - 1));
- }
- },
- ];
-
this.debuggingTestingRangeNomination = false;
- this.TestRangeSelectionStrategies = [
- {
- id: 301,
- label: "t-test 99% significance",
- execute: function (values, segmentedValues) {
- if (!values.length)
- return [];
-
- var previousMean = segmentedValues[0];
- var selectedRanges = new Array;
- for (var i = 1; i < segmentedValues.length; i++) {
- var currentMean = segmentedValues[i];
- if (currentMean == previousMean)
- continue;
- var found = false;
- for (var leftEdge = i - 2, rightEdge = i + 2; leftEdge >= 0 && rightEdge <= values.length; leftEdge--, rightEdge++) {
- if (segmentedValues[leftEdge] != previousMean || segmentedValues[rightEdge - 1] != currentMean)
- break;
- var result = Statistics.computeWelchsT(values, leftEdge, i - leftEdge, values, i, rightEdge - i, 0.98);
- if (result.significantlyDifferent) {
- selectedRanges.push([leftEdge, rightEdge - 1]);
- found = true;
- break;
- }
- }
- if (!found && Statistics.debuggingTestingRangeNomination)
- console.log('Failed to find a testing range at', i, 'changing from', previousMean, 'to', currentMean);
- previousMean = currentMean;
- }
- return selectedRanges;
- }
- }
- ];
-
- function createWesternElectricRule(windowSize, minOutlinerCount, limitFactor) {
- return function (values, movingAverages, deviation) {
- var results = new Array(values.length);
- var limit = limitFactor * deviation;
- for (var i = 0; i < values.length; i++)
- results[i] = countValuesOnSameSide(values, movingAverages, limit, i, windowSize) >= minOutlinerCount ? windowSize : 0;
- return results;
- }
- }
-
- function countValuesOnSameSide(values, movingAverages, limit, startIndex, windowSize) {
- var valuesAboveLimit = 0;
- var valuesBelowLimit = 0;
- var center = movingAverages[startIndex];
- for (var i = startIndex; i < startIndex + windowSize && i < values.length; i++) {
- var diff = values[i] - center;
- valuesAboveLimit += (diff > limit);
- valuesBelowLimit += (diff < -limit);
- }
- return Math.max(valuesAboveLimit, valuesBelowLimit);
- }
-
- this.AnomalyDetectionStrategy = [
- // Western Electric rules: http://en.wikipedia.org/wiki/Western_Electric_rules
- {
- id: 200,
- label: 'Western Electric: any point beyond 3σ',
- description: 'Any single point falls outside 3σ limit from the moving average',
- execute: createWesternElectricRule(1, 1, 3),
- },
- {
- id: 201,
- label: 'Western Electric: 2/3 points beyond 2σ',
- description: 'Two out of three consecutive points fall outside 2σ limit from the moving average on the same side',
- execute: createWesternElectricRule(3, 2, 2),
- },
- {
- id: 202,
- label: 'Western Electric: 4/5 points beyond σ',
- description: 'Four out of five consecutive points fall outside 2σ limit from the moving average on the same side',
- execute: createWesternElectricRule(5, 4, 1),
- },
- {
- id: 203,
- label: 'Western Electric: 9 points on same side',
- description: 'Nine consecutive points on the same side of the moving average',
- execute: createWesternElectricRule(9, 9, 0),
- },
- {
- id: 210,
- label: 'Mozilla: t-test 5 vs. 20 before that',
- description: "Use student's t-test to determine whether the mean of the last five data points differs from the mean of the twenty values before that",
- execute: function (values, movingAverages, deviation) {
- var results = new Array(values.length);
- var p = false;
- for (var i = 20; i < values.length - 5; i++)
- results[i] = Statistics.testWelchsT(values.slice(i - 20, i), values.slice(i, i + 5), 0.98) ? 5 : 0;
- return results;
- }
- },
- ]
-
- this.executeStrategy = function (strategy, rawValues, additionalArguments)
- {
- var parameters = (strategy.parameterList || []).map(function (param) {
- var parsed = parseFloat(param.value);
- return Math.min(param.max || Infinity, Math.max(param.min || -Infinity, isNaN(parsed) ? 0 : parsed));
- });
- parameters.push(rawValues);
- return strategy.execute.apply(strategy, parameters.concat(additionalArguments));
- };
-
})();
if (typeof module != 'undefined') {
}.property('chartData'),
updateStatisticsTools: function ()
{
- var movingAverageStrategies = Statistics.MovingAverageStrategies.map(this._cloneStrategy.bind(this));
+ var movingAverageStrategies = StatisticsStrategies.MovingAverageStrategies.map(this._cloneStrategy.bind(this));
this.set('movingAverageStrategies', [{label: 'None'}].concat(movingAverageStrategies));
this.set('chosenMovingAverageStrategy', this._configureStrategy(movingAverageStrategies, this.get('movingAverageConfig')));
- var envelopingStrategies = Statistics.EnvelopingStrategies.map(this._cloneStrategy.bind(this));
+ var envelopingStrategies = StatisticsStrategies.EnvelopingStrategies.map(this._cloneStrategy.bind(this));
this.set('envelopingStrategies', [{label: 'None'}].concat(envelopingStrategies));
this.set('chosenEnvelopingStrategy', this._configureStrategy(envelopingStrategies, this.get('envelopingConfig')));
- var testRangeSelectionStrategies = Statistics.TestRangeSelectionStrategies.map(this._cloneStrategy.bind(this));
+ var testRangeSelectionStrategies = StatisticsStrategies.TestRangeSelectionStrategies.map(this._cloneStrategy.bind(this));
this.set('testRangeSelectionStrategies', [{label: 'None'}].concat(testRangeSelectionStrategies));
this.set('chosenTestRangeSelectionStrategy', this._configureStrategy(testRangeSelectionStrategies, this.get('testRangeSelectionConfig')));
- var anomalyDetectionStrategies = Statistics.AnomalyDetectionStrategy.map(this._cloneStrategy.bind(this));
+ var anomalyDetectionStrategies = StatisticsStrategies.AnomalyDetectionStrategy.map(this._cloneStrategy.bind(this));
this.set('anomalyDetectionStrategies', anomalyDetectionStrategies);
}.on('init'),
_cloneStrategy: function (strategy)
if (!movingAverageIsSetByUser)
return null;
- var movingAverageValues = Statistics.executeStrategy(movingAverageStrategy, rawValues);
+ var movingAverageValues = StatisticsStrategies.executeStrategy(movingAverageStrategy, rawValues);
if (!movingAverageValues)
return null;
var testRangeCandidates = [];
if (movingAverageStrategy && movingAverageStrategy.isSegmentation && testRangeSelectionStrategy && testRangeSelectionStrategy.execute)
- testRangeCandidates = Statistics.executeStrategy(testRangeSelectionStrategy, rawValues, [movingAverageValues]);
+ testRangeCandidates = StatisticsStrategies.executeStrategy(testRangeSelectionStrategy, rawValues, [movingAverageValues]);
if (envelopingStrategy && envelopingStrategy.execute) {
- var envelopeDelta = Statistics.executeStrategy(envelopingStrategy, rawValues, [movingAverageValues]);
+ var envelopeDelta = StatisticsStrategies.executeStrategy(envelopingStrategy, rawValues, [movingAverageValues]);
var anomalies = {};
if (anomalyDetectionStrategies.length) {
var isAnomalyArray = new Array(currentTimeSeriesData.length);
for (var strategy of anomalyDetectionStrategies) {
- var anomalyLengths = Statistics.executeStrategy(strategy, rawValues, [movingAverageValues, envelopeDelta]);
+ var anomalyLengths = StatisticsStrategies.executeStrategy(strategy, rawValues, [movingAverageValues, envelopeDelta]);
for (var i = 0; i < currentTimeSeriesData.length; i++)
isAnomalyArray[i] = isAnomalyArray[i] || anomalyLengths[i];
}
}
if (typeof module != 'undefined') {
- Statistics = require('./js/statistics.js');
+ Statistics = require('../shared/statistics.js');
module.exports.Measurement = Measurement;
module.exports.RunsData = RunsData;
module.exports.TimeSeries = TimeSeries;
<script src="js/ember-data.js" defer></script>
<script src="js/d3/d3.min.js" defer></script>
<script src="../shared/statistics.js" defer></script>
+ <script src="statistics-strategies.js" defer></script>
<script src="data.js" defer></script>
<script src="app.js" defer></script>
<script src="manifest.js" defer></script>
--- /dev/null
+
+var StatisticsStrategies = {};
+
+(function () {
+
+StatisticsStrategies.MovingAverageStrategies = [
+ {
+ id: 1,
+ label: 'Simple Moving Average',
+ parameterList: [
+ {label: "Backward window size", value: 8, min: 2, step: 1},
+ {label: "Forward window size", value: 4, min: 0, step: 1}
+ ],
+ execute: function (backwardWindowSize, forwardWindowSize, values) {
+ return Statistics.movingAverage(values, backwardWindowSize, forwardWindowSize);
+ },
+ },
+ {
+ id: 2,
+ label: 'Cumulative Moving Average',
+ execute: Statistics.cumulativeMovingAverage,
+ },
+ {
+ id: 3,
+ label: 'Exponential Moving Average',
+ parameterList: [{label: "Smoothing factor", value: 0.1, min: 0.001, max: 0.9}],
+ execute: function (smoothingFactor, values) {
+ if (!values.length || typeof(smoothingFactor) !== "number")
+ return null;
+ return Statistics.exponentialMovingAverage(values, smoothingFactor);
+ }
+ },
+ {
+ id: 4,
+ isSegmentation: true,
+ label: 'Segmentation: Recursive t-test',
+ description: "Recursively split values into two segments if Welch's t-test detects a statistically significant difference.",
+ parameterList: [{label: "Minimum segment length", value: 20, min: 5}],
+ execute: function (minLength, values) {
+ return averagesFromSegments(values, Statistics.segmentTimeSeriesGreedyWithStudentsTTest(values, minLength));
+ }
+ },
+ {
+ id: 5,
+ isSegmentation: true,
+ label: 'Segmentation: Schwarz criterion',
+ description: 'Adaptive algorithm that maximizes the Schwarz criterion (BIC).',
+ // Based on Detection of Multiple Change–Points in Multivariate Time Series by Marc Lavielle (July 2006).
+ execute: function (values) {
+ return averagesFromSegments(values, Statistics.segmentTimeSeriesByMaximizingSchwarzCriterion(values));
+ }
+ },
+];
+
+function averagesFromSegments(values, segmentStartIndices) {
+ var averages = new Array(values.length);
+ var averageIndex = 0;
+ for (var i = 0; i < segmentStartIndices.length; i++) {
+ var segment = values.slice(segmentStartIndices[i - 1], segmentStartIndices[i]);
+ var average = Statistics.sum(segment) / segment.length;
+ for (var j = 0; j < segment.length; j++)
+ averages[averageIndex++] = average;
+ }
+ return averages;
+}
+
+
+StatisticsStrategies.EnvelopingStrategies = [
+ {
+ id: 100,
+ label: 'Average Difference',
+ description: 'The average difference between consecutive values.',
+ execute: function (values, movingAverages) {
+ if (values.length < 1)
+ return NaN;
+
+ var diff = 0;
+ for (var i = 1; i < values.length; i++)
+ diff += Math.abs(values[i] - values[i - 1]);
+
+ return diff / values.length;
+ }
+ },
+ {
+ id: 101,
+ label: 'Moving Average Standard Deviation',
+ description: 'The square root of the average deviation from the moving average with Bessel\'s correction.',
+ execute: function (values, movingAverages) {
+ if (values.length < 1)
+ return NaN;
+
+ var diffSquareSum = 0;
+ for (var i = 1; i < values.length; i++) {
+ var diff = (values[i] - movingAverages[i]);
+ diffSquareSum += diff * diff;
+ }
+
+ return Math.sqrt(diffSquareSum / (values.length - 1));
+ }
+ },
+];
+
+
+StatisticsStrategies.TestRangeSelectionStrategies = [
+ {
+ id: 301,
+ label: "t-test 99% significance",
+ execute: function (values, segmentedValues) {
+ if (!values.length)
+ return [];
+
+ var previousMean = segmentedValues[0];
+ var selectedRanges = new Array;
+ for (var i = 1; i < segmentedValues.length; i++) {
+ var currentMean = segmentedValues[i];
+ if (currentMean == previousMean)
+ continue;
+ var found = false;
+ for (var leftEdge = i - 2, rightEdge = i + 2; leftEdge >= 0 && rightEdge <= values.length; leftEdge--, rightEdge++) {
+ if (segmentedValues[leftEdge] != previousMean || segmentedValues[rightEdge - 1] != currentMean)
+ break;
+ var result = Statistics.computeWelchsT(values, leftEdge, i - leftEdge, values, i, rightEdge - i, 0.98);
+ if (result.significantlyDifferent) {
+ selectedRanges.push([leftEdge, rightEdge - 1]);
+ found = true;
+ break;
+ }
+ }
+ if (!found && Statistics.debuggingTestingRangeNomination)
+ console.log('Failed to find a testing range at', i, 'changing from', previousMean, 'to', currentMean);
+ previousMean = currentMean;
+ }
+ return selectedRanges;
+ }
+ }
+];
+
+
+
+function createWesternElectricRule(windowSize, minOutlinerCount, limitFactor) {
+ return function (values, movingAverages, deviation) {
+ var results = new Array(values.length);
+ var limit = limitFactor * deviation;
+ for (var i = 0; i < values.length; i++)
+ results[i] = countValuesOnSameSide(values, movingAverages, limit, i, windowSize) >= minOutlinerCount ? windowSize : 0;
+ return results;
+ }
+}
+
+function countValuesOnSameSide(values, movingAverages, limit, startIndex, windowSize) {
+ var valuesAboveLimit = 0;
+ var valuesBelowLimit = 0;
+ var center = movingAverages[startIndex];
+ for (var i = startIndex; i < startIndex + windowSize && i < values.length; i++) {
+ var diff = values[i] - center;
+ valuesAboveLimit += (diff > limit);
+ valuesBelowLimit += (diff < -limit);
+ }
+ return Math.max(valuesAboveLimit, valuesBelowLimit);
+}
+
+StatisticsStrategies.AnomalyDetectionStrategy = [
+ // Western Electric rules: http://en.wikipedia.org/wiki/Western_Electric_rules
+ {
+ id: 200,
+ label: 'Western Electric: any point beyond 3σ',
+ description: 'Any single point falls outside 3σ limit from the moving average',
+ execute: createWesternElectricRule(1, 1, 3),
+ },
+ {
+ id: 201,
+ label: 'Western Electric: 2/3 points beyond 2σ',
+ description: 'Two out of three consecutive points fall outside 2σ limit from the moving average on the same side',
+ execute: createWesternElectricRule(3, 2, 2),
+ },
+ {
+ id: 202,
+ label: 'Western Electric: 4/5 points beyond σ',
+ description: 'Four out of five consecutive points fall outside 2σ limit from the moving average on the same side',
+ execute: createWesternElectricRule(5, 4, 1),
+ },
+ {
+ id: 203,
+ label: 'Western Electric: 9 points on same side',
+ description: 'Nine consecutive points on the same side of the moving average',
+ execute: createWesternElectricRule(9, 9, 0),
+ },
+ {
+ id: 210,
+ label: 'Mozilla: t-test 5 vs. 20 before that',
+ description: "Use student's t-test to determine whether the mean of the last five data points differs from the mean of the twenty values before that",
+ execute: function (values, movingAverages, deviation) {
+ var results = new Array(values.length);
+ var p = false;
+ for (var i = 20; i < values.length - 5; i++)
+ results[i] = Statistics.testWelchsT(values.slice(i - 20, i), values.slice(i, i + 5), 0.98) ? 5 : 0;
+ return results;
+ }
+ },
+]
+
+StatisticsStrategies.executeStrategy = function (strategy, rawValues, additionalArguments)
+{
+ var parameters = (strategy.parameterList || []).map(function (param) {
+ var parsed = parseFloat(param.value);
+ return Math.min(param.max || Infinity, Math.max(param.min || -Infinity, isNaN(parsed) ? 0 : parsed));
+ });
+ parameters.push(rawValues);
+ return strategy.execute.apply(strategy, parameters.concat(additionalArguments));
+};
+
+})();
+
+if (typeof module != 'undefined') {
+ for (var key in StatisticsStrategies)
+ module.exports[key] = StatisticsStrategies[key];
+}
var data = require('../public/v2/data.js');
var RunsData = data.RunsData;
var Statistics = require('../public/shared/statistics.js');
+var StatisticsStrategies = require('../public/v2/statistics-strategies.js');
// FIXME: We shouldn't use a global variable like this.
var settings;
{
// FIXME: Store the segmentation strategy on the server side.
// FIXME: Configure each strategy.
- var segmentationStrategy = findStrategyByLabel(Statistics.MovingAverageStrategies, strategies.segmentation.label);
+ var segmentationStrategy = findStrategyByLabel(StatisticsStrategies.MovingAverageStrategies, strategies.segmentation.label);
if (!segmentationStrategy) {
console.error('Failed to find the segmentation strategy: ' + strategies.segmentation.label);
return;
}
- var testRangeStrategy = findStrategyByLabel(Statistics.TestRangeSelectionStrategies, strategies.testRange.label);
+ var testRangeStrategy = findStrategyByLabel(StatisticsStrategies.TestRangeSelectionStrategies, strategies.testRange.label);
if (!testRangeStrategy) {
console.error('Failed to find the test range selection strategy: ' + strategies.testRange.label);
return;
var currentTimeSeries = results[0].timeSeriesByCommitTime();
var analysisTasks = results[1];
var rawValues = currentTimeSeries.rawValues();
- var segmentedValues = Statistics.executeStrategy(segmentationStrategy, rawValues);
+ var segmentedValues = StatisticsStrategies.executeStrategy(segmentationStrategy, rawValues);
- var ranges = Statistics.executeStrategy(testRangeStrategy, rawValues, [segmentedValues]).map(function (range) {
+ var ranges = StatisticsStrategies.executeStrategy(testRangeStrategy, rawValues, [segmentedValues]).map(function (range) {
var startPoint = currentTimeSeries.findPointByIndex(range[0]);
var endPoint = currentTimeSeries.findPointByIndex(range[1]);
return {
git://git.webkit.org / WebKit-https.git / commitdiff