afa21e004f340fcb3da19cea96486384d15eb9f5
[WebKit-https.git] / Websites / perf.webkit.org / public / v2 / js / statistics.js
1 var Statistics = new (function () {
2
3     this.min = function (values) {
4         return Math.min.apply(Math, values);
5     }
6
7     this.max = function (values) {
8         return Math.max.apply(Math, values);
9     }
10
11     this.sum = function (values) {
12         return values.length ? values.reduce(function (a, b) { return a + b; }) : 0;
13     }
14
15     this.squareSum = function (values) {
16         return values.length ? values.reduce(function (sum, value) { return sum + value * value;}, 0) : 0;
17     }
18
19     // With sum and sum of squares, we can compute the sample standard deviation in O(1).
20     // See https://rniwa.com/2012-11-10/sample-standard-deviation-in-terms-of-sum-and-square-sum-of-samples/
21     this.sampleStandardDeviation = function (numberOfSamples, sum, squareSum) {
22         if (numberOfSamples < 2)
23             return 0;
24         return Math.sqrt(squareSum / (numberOfSamples - 1) - sum * sum / (numberOfSamples - 1) / numberOfSamples);
25     }
26
27     this.supportedConfidenceIntervalProbabilities = function () {
28         var supportedProbabilities = [];
29         for (var probability in tDistributionByOneSidedProbability)
30             supportedProbabilities.push(oneSidedToTwoSidedProbability(probability).toFixed(2));
31         return supportedProbabilities
32     }
33
34     // Computes the delta d s.t. (mean - d, mean + d) is the confidence interval with the specified probability in O(1).
35     this.confidenceIntervalDelta = function (probability, numberOfSamples, sum, squareSum) {
36         var oneSidedProbability = twoSidedToOneSidedProbability(probability);
37         if (!(oneSidedProbability in tDistributionByOneSidedProbability)) {
38             throw 'We only support ' + this.supportedConfidenceIntervalProbabilities().map(function (probability)
39             { return probability * 100 + '%'; } ).join(', ') + ' confidence intervals.';
40         }
41         if (numberOfSamples - 2 < 0)
42             return NaN;
43         var deltas = tDistributionByOneSidedProbability[oneSidedProbability];
44         var degreesOfFreedom = numberOfSamples - 1;
45         if (degreesOfFreedom > deltas.length)
46             throw 'We only support up to ' + deltas.length + ' degrees of freedom';
47
48         // d = c * S/sqrt(numberOfSamples) where c ~ t-distribution(degreesOfFreedom) and S is the sample standard deviation.
49         return deltas[degreesOfFreedom - 1] * this.sampleStandardDeviation(numberOfSamples, sum, squareSum) / Math.sqrt(numberOfSamples);
50     }
51
52     this.confidenceInterval = function (values, probability) {
53         var sum = this.sum(values);
54         var mean = sum / values.length;
55         var delta = this.confidenceIntervalDelta(probability || 0.95, values.length, sum, this.squareSum(values));
56         return [mean - delta, mean + delta];
57     }
58
59     // Welch's t-test (http://en.wikipedia.org/wiki/Welch%27s_t_test)
60     this.testWelchsT = function (values1, values2, probability) {
61         return this.computeWelchsT(values1, 0, values1.length, values2, 0, values2.length, probability).significantlyDifferent;
62     }
63
64     this.probabilityRangeForWelchsT = function (values1, values2) {
65         var result = this.computeWelchsT(values1, 0, values1.length, values2, 0, values2.length);
66         if (isNaN(result.t) || isNaN(result.degreesOfFreedom))
67             return {t: NaN, degreesOfFreedom:NaN, range: [null, null]};
68
69         var lowerBound = null;
70         var upperBound = null;
71         for (var probability in tDistributionByOneSidedProbability) {
72             var twoSidedProbability = oneSidedToTwoSidedProbability(probability);
73             if (result.t > tDistributionByOneSidedProbability[probability][Math.round(result.degreesOfFreedom - 1)])
74                 lowerBound = twoSidedProbability;
75             else if (lowerBound) {
76                 upperBound = twoSidedProbability;
77                 break;
78             }
79         }
80         return {t: result.t, degreesOfFreedom: result.degreesOfFreedom, range: [lowerBound, upperBound]};
81     }
82
83     this.computeWelchsT = function (values1, startIndex1, length1, values2, startIndex2, length2, probability) {
84         var stat1 = sampleMeanAndVarianceForValues(values1, startIndex1, length1);
85         var stat2 = sampleMeanAndVarianceForValues(values2, startIndex2, length2);
86         var sumOfSampleVarianceOverSampleSize = stat1.variance / stat1.size + stat2.variance / stat2.size;
87         var t = Math.abs((stat1.mean - stat2.mean) / Math.sqrt(sumOfSampleVarianceOverSampleSize));
88
89         // http://en.wikipedia.org/wiki/Welch–Satterthwaite_equation
90         var degreesOfFreedom = sumOfSampleVarianceOverSampleSize * sumOfSampleVarianceOverSampleSize
91             / (stat1.variance * stat1.variance / stat1.size / stat1.size / stat1.degreesOfFreedom
92                 + stat2.variance * stat2.variance / stat2.size / stat2.size / stat2.degreesOfFreedom);
93         var minT = tDistributionByOneSidedProbability[twoSidedToOneSidedProbability(probability || 0.8)][Math.round(degreesOfFreedom - 1)];
94         return {
95             t: t,
96             degreesOfFreedom: degreesOfFreedom,
97             significantlyDifferent: t > minT,
98         };
99     }
100
101     function sampleMeanAndVarianceForValues(values, startIndex, length) {
102         var sum = 0;
103         for (var i = 0; i < length; i++)
104             sum += values[startIndex + i];
105         var squareSum = 0;
106         for (var i = 0; i < length; i++)
107             squareSum += values[startIndex + i] * values[startIndex + i];
108         var sampleMean = sum / length;
109         // FIXME: Maybe we should be using the biased sample variance.
110         var unbiasedSampleVariance = (squareSum - sum * sum / length) / (length - 1);
111         return {
112             mean: sampleMean,
113             variance: unbiasedSampleVariance,
114             size: length,
115             degreesOfFreedom: length - 1,
116         }
117     }
118
119     function recursivelySplitIntoTwoSegmentsAtMaxTIfSignificantlyDifferent(values, startIndex, length, minLength, segments) {
120         var tMax = 0;
121         var argTMax = null;
122         for (var i = 1; i < length - 1; i++) {
123             var firstLength = i;
124             var secondLength = length - i;
125             if (firstLength < minLength || secondLength < minLength)
126                 continue;
127             var result = Statistics.computeWelchsT(values, startIndex, firstLength, values, startIndex + i, secondLength, 0.9);
128             if (result.significantlyDifferent && result.t > tMax) {
129                 tMax = result.t;
130                 argTMax = i;
131             }
132         }
133         if (!tMax) {
134             segments.push(values.slice(startIndex, startIndex + length));
135             return;
136         }
137         recursivelySplitIntoTwoSegmentsAtMaxTIfSignificantlyDifferent(values, startIndex, argTMax, minLength, segments);
138         recursivelySplitIntoTwoSegmentsAtMaxTIfSignificantlyDifferent(values, startIndex + argTMax, length - argTMax, minLength, segments);
139     }
140
141     var tDistributionByOneSidedProbability = {
142         0.9: [
143             3.077684, 1.885618, 1.637744, 1.533206, 1.475884, 1.439756, 1.414924, 1.396815, 1.383029, 1.372184,
144             1.363430, 1.356217, 1.350171, 1.345030, 1.340606, 1.336757, 1.333379, 1.330391, 1.327728, 1.325341,
145             1.323188, 1.321237, 1.319460, 1.317836, 1.316345, 1.314972, 1.313703, 1.312527, 1.311434, 1.310415,
146             1.309464, 1.308573, 1.307737, 1.306952, 1.306212, 1.305514, 1.304854, 1.304230, 1.303639, 1.303077,
147             1.302543, 1.302035, 1.301552, 1.301090, 1.300649, 1.300228, 1.299825, 1.299439, 1.299069, 1.298714,
148
149             1.298373, 1.298045, 1.297730, 1.297426, 1.297134, 1.296853, 1.296581, 1.296319, 1.296066, 1.295821,
150             1.295585, 1.295356, 1.295134, 1.294920, 1.294712, 1.294511, 1.294315, 1.294126, 1.293942, 1.293763,
151             1.293589, 1.293421, 1.293256, 1.293097, 1.292941, 1.292790, 1.292643, 1.292500, 1.292360, 1.292224,
152             1.292091, 1.291961, 1.291835, 1.291711, 1.291591, 1.291473, 1.291358, 1.291246, 1.291136, 1.291029,
153             1.290924, 1.290821, 1.290721, 1.290623, 1.290527, 1.290432, 1.290340, 1.290250, 1.290161, 1.290075],
154         0.95: [
155             6.313752, 2.919986, 2.353363, 2.131847, 2.015048, 1.943180, 1.894579, 1.859548, 1.833113, 1.812461,
156             1.795885, 1.782288, 1.770933, 1.761310, 1.753050, 1.745884, 1.739607, 1.734064, 1.729133, 1.724718,
157             1.720743, 1.717144, 1.713872, 1.710882, 1.708141, 1.705618, 1.703288, 1.701131, 1.699127, 1.697261,
158             1.695519, 1.693889, 1.692360, 1.690924, 1.689572, 1.688298, 1.687094, 1.685954, 1.684875, 1.683851,
159             1.682878, 1.681952, 1.681071, 1.680230, 1.679427, 1.678660, 1.677927, 1.677224, 1.676551, 1.675905,
160
161             1.675285, 1.674689, 1.674116, 1.673565, 1.673034, 1.672522, 1.672029, 1.671553, 1.671093, 1.670649,
162             1.670219, 1.669804, 1.669402, 1.669013, 1.668636, 1.668271, 1.667916, 1.667572, 1.667239, 1.666914,
163             1.666600, 1.666294, 1.665996, 1.665707, 1.665425, 1.665151, 1.664885, 1.664625, 1.664371, 1.664125,
164             1.663884, 1.663649, 1.663420, 1.663197, 1.662978, 1.662765, 1.662557, 1.662354, 1.662155, 1.661961,
165             1.661771, 1.661585, 1.661404, 1.661226, 1.661052, 1.660881, 1.660715, 1.660551, 1.660391, 1.660234],
166         0.975: [
167             12.706205, 4.302653, 3.182446, 2.776445, 2.570582, 2.446912, 2.364624, 2.306004, 2.262157, 2.228139,
168             2.200985, 2.178813, 2.160369, 2.144787, 2.131450, 2.119905, 2.109816, 2.100922, 2.093024, 2.085963,
169             2.079614, 2.073873, 2.068658, 2.063899, 2.059539, 2.055529, 2.051831, 2.048407, 2.045230, 2.042272,
170             2.039513, 2.036933, 2.034515, 2.032245, 2.030108, 2.028094, 2.026192, 2.024394, 2.022691, 2.021075,
171             2.019541, 2.018082, 2.016692, 2.015368, 2.014103, 2.012896, 2.011741, 2.010635, 2.009575, 2.008559,
172
173             2.007584, 2.006647, 2.005746, 2.004879, 2.004045, 2.003241, 2.002465, 2.001717, 2.000995, 2.000298,
174             1.999624, 1.998972, 1.998341, 1.997730, 1.997138, 1.996564, 1.996008, 1.995469, 1.994945, 1.994437,
175             1.993943, 1.993464, 1.992997, 1.992543, 1.992102, 1.991673, 1.991254, 1.990847, 1.990450, 1.990063,
176             1.989686, 1.989319, 1.988960, 1.988610, 1.988268, 1.987934, 1.987608, 1.987290, 1.986979, 1.986675,
177             1.986377, 1.986086, 1.985802, 1.985523, 1.985251, 1.984984, 1.984723, 1.984467, 1.984217, 1.983972],
178         0.99: [
179             31.820516, 6.964557, 4.540703, 3.746947, 3.364930, 3.142668, 2.997952, 2.896459, 2.821438, 2.763769,
180             2.718079, 2.680998, 2.650309, 2.624494, 2.602480, 2.583487, 2.566934, 2.552380, 2.539483, 2.527977,
181             2.517648, 2.508325, 2.499867, 2.492159, 2.485107, 2.478630, 2.472660, 2.467140, 2.462021, 2.457262,
182             2.452824, 2.448678, 2.444794, 2.441150, 2.437723, 2.434494, 2.431447, 2.428568, 2.425841, 2.423257,
183             2.420803, 2.418470, 2.416250, 2.414134, 2.412116, 2.410188, 2.408345, 2.406581, 2.404892, 2.403272,
184
185             2.401718, 2.400225, 2.398790, 2.397410, 2.396081, 2.394801, 2.393568, 2.392377, 2.391229, 2.390119,
186             2.389047, 2.388011, 2.387008, 2.386037, 2.385097, 2.384186, 2.383302, 2.382446, 2.381615, 2.380807,
187             2.380024, 2.379262, 2.378522, 2.377802, 2.377102, 2.376420, 2.375757, 2.375111, 2.374482, 2.373868,
188             2.373270, 2.372687, 2.372119, 2.371564, 2.371022, 2.370493, 2.369977, 2.369472, 2.368979, 2.368497,
189             2.368026, 2.367566, 2.367115, 2.366674, 2.366243, 2.365821, 2.365407, 2.365002, 2.364606, 2.364217]
190     };
191     function oneSidedToTwoSidedProbability(probability) { return 2 * probability - 1; }
192     function twoSidedToOneSidedProbability(probability) { return (1 - (1 - probability) / 2); }
193
194     this.MovingAverageStrategies = [
195         {
196             id: 1,
197             label: 'Simple Moving Average',
198             parameterList: [
199                 {label: "Backward window size", value: 8, min: 2, step: 1},
200                 {label: "Forward window size", value: 4, min: 0, step: 1}
201             ],
202             execute: function (backwardWindowSize, forwardWindowSize, values) {
203                 var averages = new Array(values.length);
204                 // We use naive O(n^2) algorithm for simplicy as well as to avoid accumulating round-off errors.
205                 for (var i = 0; i < values.length; i++) {
206                     var sum = 0;
207                     var count = 0;
208                     for (var j = i - backwardWindowSize; j < i + backwardWindowSize; j++) {
209                         if (j >= 0 && j < values.length) {
210                             sum += values[j];
211                             count++;
212                         }
213                     }
214                     averages[i] = sum / count;
215                 }
216                 return averages;
217             },
218
219         },
220         {
221             id: 2,
222             label: 'Cumulative Moving Average',
223             execute: function (values) {
224                 var averages = new Array(values.length);
225                 var sum = 0;
226                 for (var i = 0; i < values.length; i++) {
227                     sum += values[i];
228                     averages[i] = sum / (i + 1);
229                 }
230                 return averages;
231             }
232         },
233         {
234             id: 3,
235             label: 'Exponential Moving Average',
236             parameterList: [{label: "Smoothing factor", value: 0.1, min: 0.001, max: 0.9}],
237             execute: function (smoothingFactor, values) {
238                 if (!values.length || typeof(smoothingFactor) !== "number")
239                     return null;
240
241                 var averages = new Array(values.length);
242                 var movingAverage = 0;
243                 averages[0] = values[0];
244                 for (var i = 1; i < values.length; i++)
245                     averages[i] = smoothingFactor * values[i] + (1 - smoothingFactor) * averages[i - 1];
246                 return averages;
247             }
248         },
249         {
250             id: 4,
251             isSegmentation: true,
252             label: 'Segmentation: Recursive t-test',
253             description: "Recursively split values into two segments if Welch's t-test detects a statistically significant difference.",
254             parameterList: [{label: "Minimum segment length", value: 20, min: 5}],
255             execute: function (minLength, values) {
256                 if (values.length < 2)
257                     return null;
258
259                 var averages = new Array(values.length);
260                 var segments = new Array;
261                 recursivelySplitIntoTwoSegmentsAtMaxTIfSignificantlyDifferent(values, 0, values.length, minLength, segments);
262                 var averageIndex = 0;
263                 for (var j = 0; j < segments.length; j++) {
264                     var values = segments[j];
265                     var mean = Statistics.sum(values) / values.length;
266                     for (var i = 0; i < values.length; i++)
267                         averages[averageIndex++] = mean;
268                 }
269
270                 return averages;
271             }
272         },
273         {
274             id: 5,
275             isSegmentation: true,
276             label: 'Segmentation: Schwarz criterion',
277             description: 'Adaptive algorithm that maximizes the Schwarz criterion (BIC).',
278             // Based on Detection of Multiple Change–Points in Multivariate Time Series by Marc Lavielle (July 2006).
279             execute: function (values) {
280                 if (values.length < 2)
281                     return null;
282
283                 var averages = new Array(values.length);
284                 var averageIndex = 0;
285
286                 // Split the time series into grids since splitIntoSegmentsUntilGoodEnough is O(n^2).
287                 var gridLength = 500;
288                 var totalSegmentation = [0];
289                 for (var gridCount = 0; gridCount < Math.ceil(values.length / gridLength); gridCount++) {
290                     var gridValues = values.slice(gridCount * gridLength, (gridCount + 1) * gridLength);
291                     var segmentation = splitIntoSegmentsUntilGoodEnough(gridValues);
292
293                     if (Statistics.debuggingSegmentation)
294                         console.log('grid=' + gridCount, segmentation);
295
296                     for (var i = 1; i < segmentation.length - 1; i++)
297                         totalSegmentation.push(gridCount * gridLength + segmentation[i]);
298                 }
299
300                 if (Statistics.debuggingSegmentation)
301                     console.log('Final Segmentation', totalSegmentation);
302
303                 totalSegmentation.push(values.length);
304
305                 for (var i = 1; i < totalSegmentation.length; i++) {
306                     var segment = values.slice(totalSegmentation[i - 1], totalSegmentation[i]);
307                     var average = Statistics.sum(segment) / segment.length;
308                     for (var j = 0; j < segment.length; j++)
309                         averages[averageIndex++] = average;
310                 }
311
312                 return averages;
313             }
314         },
315     ];
316
317     this.debuggingSegmentation = false;
318
319     function splitIntoSegmentsUntilGoodEnough(values) {
320         if (values.length < 2)
321             return [0, values.length];
322
323         var matrix = new SampleVarianceUpperTriangularMatrix(values);
324
325         var SchwarzCriterionBeta = Math.log1p(values.length - 1) / values.length;
326
327         var BirgeAndMassartC = 2.5; // Suggested by the authors.
328         var BirgeAndMassartPenalization = function (segmentCount) {
329             return segmentCount * (1 + BirgeAndMassartC * Math.log1p(values.length / segmentCount - 1));
330         }
331
332         var segmentation;
333         var minTotalCost = Infinity;
334         var maxK = 50;
335
336         for (var k = 1; k < maxK; k++) {
337             var start = Date.now();
338             var result = findOptimalSegmentation(values, matrix, k);
339             var cost = result.cost / values.length;
340             var penalty = SchwarzCriterionBeta * BirgeAndMassartPenalization(k);
341             if (cost + penalty < minTotalCost) {
342                 minTotalCost = cost + penalty;
343                 segmentation = result.segmentation;
344             } else
345                 maxK = Math.min(maxK, k + 3);
346             if (Statistics.debuggingSegmentation)
347                 console.log('splitIntoSegmentsUntilGoodEnough', k, Date.now() - start, cost + penalty);
348         }
349
350         return segmentation;
351     }
352
353     function findOptimalSegmentation(values, costMatrix, segmentCount) {
354         // Dynamic programming. cost[i][k] = The cost to segmenting values up to i into k segments.
355         var cost = new Array(values.length);
356         for (var i = 0; i < values.length; i++) {
357             cost[i] = new Float32Array(segmentCount + 1);
358         }
359
360         var previousNode = new Array(values.length);
361         for (var i = 0; i < values.length; i++)
362             previousNode[i] = new Array(segmentCount + 1);
363
364         cost[0] = [0]; // The cost of segmenting single value is always 0.
365         previousNode[0] = [-1];
366         for (var segmentStart = 0; segmentStart < values.length; segmentStart++) {
367             var costBySegment = cost[segmentStart];
368             for (var count = 0; count < segmentCount; count++) {
369                 if (previousNode[segmentStart][count] === undefined)
370                     continue;
371                 for (var segmentEnd = segmentStart + 1; segmentEnd < values.length; segmentEnd++) {
372                     var newCost = costBySegment[count] + costMatrix.costBetween(segmentStart, segmentEnd);
373                     if (previousNode[segmentEnd][count + 1] === undefined || newCost < cost[segmentEnd][count + 1]) {
374                         cost[segmentEnd][count + 1] = newCost;
375                         previousNode[segmentEnd][count + 1] = segmentStart;
376                     }
377                 }
378             }
379         }
380
381         if (Statistics.debuggingSegmentation) {
382             console.log('findOptimalSegmentation with k=', segmentCount);
383             for (var i = 0; i < cost.length; i++) {
384                 var t = cost[i];
385                 var s = '';
386                 for (var j = 0; j < t.length; j++) {
387                     var p = previousNode[i][j];
388                     s += '(k=' + j;
389                     if (p !== undefined)
390                         s += ' c=' + t[j] + ' p=' + p
391                     s += ')';
392                 }
393                 console.log(i, values[i], s);
394             }
395         }
396
397         var currentIndex = values.length - 1;
398         var segmentation = new Array(segmentCount);
399         segmentation[0] = values.length;
400         for (var i = 0; i < segmentCount; i++) {
401             currentIndex = previousNode[currentIndex][segmentCount - i];
402             segmentation[i + 1] = currentIndex;
403         }
404
405         return {segmentation: segmentation.reverse(), cost: cost[values.length - 1][segmentCount]};
406     }
407
408     function SampleVarianceUpperTriangularMatrix(values) {
409         // The cost of segment (i, j].
410         var costMatrix = new Array(values.length - 1);
411         for (var i = 0; i < values.length - 1; i++) {
412             var remainingValueCount = values.length - i - 1;
413             costMatrix[i] = new Float32Array(remainingValueCount);
414             var sum = values[i];
415             var squareSum = sum * sum;
416             costMatrix[i][0] = 0;
417             for (var j = i + 1; j < values.length; j++) {
418                 var currentValue = values[j];
419                 sum += currentValue;
420                 squareSum += currentValue * currentValue;
421                 var sampleSize = j - i + 1;
422                 var stdev = Statistics.sampleStandardDeviation(sampleSize, sum, squareSum);
423                 costMatrix[i][j - i - 1] = sampleSize * Math.log1p(stdev * stdev - 1);
424             }
425         }
426         this.costMatrix = costMatrix;
427     }
428
429     SampleVarianceUpperTriangularMatrix.prototype.costBetween = function(from, to) {
430         if (from >= this.costMatrix.length || from == to)
431             return 0; // The cost of the segment that starts at the last data point is 0.
432         return this.costMatrix[from][to - from - 1];
433     }
434
435     this.EnvelopingStrategies = [
436         {
437             id: 100,
438             label: 'Average Difference',
439             description: 'The average difference between consecutive values.',
440             execute: function (values, movingAverages) {
441                 if (values.length < 1)
442                     return NaN;
443
444                 var diff = 0;
445                 for (var i = 1; i < values.length; i++)
446                     diff += Math.abs(values[i] - values[i - 1]);
447
448                 return diff / values.length;
449             }
450         },
451         {
452             id: 101,
453             label: 'Moving Average Standard Deviation',
454             description: 'The square root of the average deviation from the moving average with Bessel\'s correction.',
455             execute: function (values, movingAverages) {
456                 if (values.length < 1)
457                     return NaN;
458
459                 var diffSquareSum = 0;
460                 for (var i = 1; i < values.length; i++) {
461                     var diff = (values[i] - movingAverages[i]);
462                     diffSquareSum += diff * diff;
463                 }
464
465                 return Math.sqrt(diffSquareSum / (values.length - 1));
466             }
467         },
468     ];
469
470     this.debuggingTestingRangeNomination = false;
471
472     this.TestRangeSelectionStrategies = [
473         {
474             id: 301,
475             label: "t-test 99% significance",
476             execute: function (values, segmentedValues) {
477                 if (!values.length)
478                     return [];
479
480                 var previousMean = segmentedValues[0];
481                 var selectedRanges = new Array;
482                 for (var i = 1; i < segmentedValues.length; i++) {
483                     var currentMean = segmentedValues[i];
484                     if (currentMean == previousMean)
485                         continue;
486                     var found = false;
487                     for (var leftEdge = i - 2, rightEdge = i + 2; leftEdge >= 0 && rightEdge <= values.length; leftEdge--, rightEdge++) {
488                         if (segmentedValues[leftEdge] != previousMean || segmentedValues[rightEdge - 1] != currentMean)
489                             break;
490                         var result = Statistics.computeWelchsT(values, leftEdge, i - leftEdge, values, i, rightEdge - i);
491                         if (result.significantlyDifferent) {
492                             selectedRanges.push([leftEdge, rightEdge - 1]);
493                             found = true;
494                             break;
495                         }
496                     }
497                     if (!found && Statistics.debuggingTestingRangeNomination)
498                         console.log('Failed to find a testing range at', i, 'changing from', previousValue, 'to', currentValue);
499                     previousMean = currentMean;
500                 }
501                 return selectedRanges;
502             }
503         }
504     ];
505
506     function createWesternElectricRule(windowSize, minOutlinerCount, limitFactor) {
507         return function (values, movingAverages, deviation) {
508             var results = new Array(values.length);
509             var limit = limitFactor * deviation;
510             for (var i = 0; i < values.length; i++)
511                 results[i] = countValuesOnSameSide(values, movingAverages, limit, i, windowSize) >= minOutlinerCount ? windowSize : 0;
512             return results;
513         }
514     }
515
516     function countValuesOnSameSide(values, movingAverages, limit, startIndex, windowSize) {
517         var valuesAboveLimit = 0;
518         var valuesBelowLimit = 0;
519         var center = movingAverages[startIndex];
520         for (var i = startIndex; i < startIndex + windowSize && i < values.length; i++) {
521             var diff = values[i] - center;
522             valuesAboveLimit += (diff > limit);
523             valuesBelowLimit += (diff < -limit);
524         }
525         return Math.max(valuesAboveLimit, valuesBelowLimit);
526     }
527
528     this.AnomalyDetectionStrategy = [
529         // Western Electric rules: http://en.wikipedia.org/wiki/Western_Electric_rules
530         {
531             id: 200,
532             label: 'Western Electric: any point beyond 3σ',
533             description: 'Any single point falls outside 3σ limit from the moving average',
534             execute: createWesternElectricRule(1, 1, 3),
535         },
536         {
537             id: 201,
538             label: 'Western Electric: 2/3 points beyond 2σ',
539             description: 'Two out of three consecutive points fall outside 2σ limit from the moving average on the same side',
540             execute: createWesternElectricRule(3, 2, 2),
541         },
542         {
543             id: 202,
544             label: 'Western Electric: 4/5 points beyond σ',
545             description: 'Four out of five consecutive points fall outside 2σ limit from the moving average on the same side',
546             execute: createWesternElectricRule(5, 4, 1),
547         },
548         {
549             id: 203,
550             label: 'Western Electric: 9 points on same side',
551             description: 'Nine consecutive points on the same side of the moving average',
552             execute: createWesternElectricRule(9, 9, 0),
553         },
554         {
555             id: 210,
556             label: 'Mozilla: t-test 5 vs. 20 before that',
557             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",
558             execute: function (values, movingAverages, deviation) {
559                 var results = new Array(values.length);
560                 var p = false;
561                 for (var i = 20; i < values.length - 5; i++)
562                     results[i] = Statistics.testWelchsT(values.slice(i - 20, i), values.slice(i, i + 5), 0.98) ? 5 : 0;
563                 return results;
564             }
565         },
566     ]
567
568 })();
569
570 if (typeof module != 'undefined') {
571     for (var key in Statistics)
572         module.exports[key] = Statistics[key];
573 }