Extract the code specific to v2 UI out of shared statistics.js
authorrniwa@webkit.org <rniwa@webkit.org@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Tue, 16 Feb 2016 23:16:25 +0000 (23:16 +0000)
committerrniwa@webkit.org <rniwa@webkit.org@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Tue, 16 Feb 2016 23:16:25 +0000 (23:16 +0000)
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):

git-svn-id: http://svn.webkit.org/repository/webkit/trunk@196663 268f45cc-cd09-0410-ab3c-d52691b4dbfc

Websites/perf.webkit.org/ChangeLog
Websites/perf.webkit.org/public/shared/statistics.js
Websites/perf.webkit.org/public/v2/app.js
Websites/perf.webkit.org/public/v2/data.js
Websites/perf.webkit.org/public/v2/index.html
Websites/perf.webkit.org/public/v2/statistics-strategies.js [new file with mode: 0644]
Websites/perf.webkit.org/tools/detect-changes.js

index 10b5dd8..f377496 100644 (file)
@@ -1,5 +1,44 @@
 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
 
index af10437..9ef1e74 100644 (file)
@@ -116,6 +116,80 @@ var Statistics = new (function () {
         }
     }
 
+    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;
@@ -131,7 +205,7 @@ var Statistics = new (function () {
             }
         }
         if (!tMax) {
-            segments.push(values.slice(startIndex, startIndex + length));
+            segments.push(startIndex);
             return;
         }
         recursivelySplitIntoTwoSegmentsAtMaxTIfSignificantlyDifferent(values, startIndex, argTMax, minLength, segments);
@@ -191,131 +265,6 @@ var Statistics = new (function () {
     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];
@@ -432,149 +381,8 @@ var Statistics = new (function () {
         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') {
index 0fc6277..987e6b6 100644 (file)
@@ -547,19 +547,19 @@ App.Pane = Ember.Object.extend({
     }.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)
@@ -640,21 +640,21 @@ App.Pane = Ember.Object.extend({
         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];
                 }
index 8a563da..23dd8c2 100644 (file)
@@ -557,7 +557,7 @@ TimeSeries.prototype.nextPoint = function (point)
 }
 
 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;
index ed0bd27..034289a 100644 (file)
@@ -17,6 +17,7 @@
     <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>
diff --git a/Websites/perf.webkit.org/public/v2/statistics-strategies.js b/Websites/perf.webkit.org/public/v2/statistics-strategies.js
new file mode 100644 (file)
index 0000000..e3ae868
--- /dev/null
@@ -0,0 +1,217 @@
+
+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];
+}
index a13023a..36c71c4 100644 (file)
@@ -6,6 +6,7 @@ var https = require('https');
 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;
@@ -172,13 +173,13 @@ function computeRangesForTesting(server, strategies, platformId, metricId)
 {
     // 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;
@@ -204,9 +205,9 @@ function computeRangesForTesting(server, strategies, platformId, metricId)
         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 {