da30e1d37db371ab9a3a30dae4daa9569ae334a3
[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 quantile in tDistributionQuantiles)
30             supportedProbabilities.push((1 - (1 - quantile) * 2).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 quantile = (1 - (1 - probability) / 2);
37         if (!(quantile in tDistributionQuantiles)) {
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 = tDistributionQuantiles[quantile];
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         var stat1 = sampleMeanAndVarianceForValues(values1);
62         var stat2 = sampleMeanAndVarianceForValues(values2);
63         var sumOfSampleVarianceOverSampleSize = stat1.variance / stat1.size + stat2.variance / stat2.size;
64         var t = (stat1.mean - stat2.mean) / Math.sqrt(sumOfSampleVarianceOverSampleSize);
65
66         // http://en.wikipedia.org/wiki/Welch–Satterthwaite_equation
67         var degreesOfFreedom = sumOfSampleVarianceOverSampleSize * sumOfSampleVarianceOverSampleSize
68             / (stat1.variance * stat1.variance / stat1.size / stat1.size / stat1.degreesOfFreedom
69                 + stat2.variance * stat2.variance / stat2.size / stat2.size / stat2.degreesOfFreedom);
70
71         // They're different beyond the confidence interval of the specified probability.
72         return Math.abs(t) > tDistributionQuantiles[probability || 0.9][Math.round(degreesOfFreedom - 1)];
73     }
74
75     function sampleMeanAndVarianceForValues(values) {
76         var sum = Statistics.sum(values);
77         var squareSum = Statistics.squareSum(values);
78         var sampleMean = sum / values.length;
79         // FIXME: Maybe we should be using the biased sample variance.
80         var unbiasedSampleVariance = (squareSum - sum * sum / values.length) / (values.length - 1);
81         return {
82             mean: sampleMean,
83             variance: unbiasedSampleVariance,
84             size: values.length,
85             degreesOfFreedom: values.length - 1,
86         }
87     }
88
89     // One-sided t-distribution.
90     var tDistributionQuantiles = {
91         0.9: [
92             3.077684, 1.885618, 1.637744, 1.533206, 1.475884, 1.439756, 1.414924, 1.396815, 1.383029, 1.372184,
93             1.363430, 1.356217, 1.350171, 1.345030, 1.340606, 1.336757, 1.333379, 1.330391, 1.327728, 1.325341,
94             1.323188, 1.321237, 1.319460, 1.317836, 1.316345, 1.314972, 1.313703, 1.312527, 1.311434, 1.310415,
95             1.309464, 1.308573, 1.307737, 1.306952, 1.306212, 1.305514, 1.304854, 1.304230, 1.303639, 1.303077,
96             1.302543, 1.302035, 1.301552, 1.301090, 1.300649, 1.300228, 1.299825, 1.299439, 1.299069, 1.298714,
97
98             1.298373, 1.298045, 1.297730, 1.297426, 1.297134, 1.296853, 1.296581, 1.296319, 1.296066, 1.295821,
99             1.295585, 1.295356, 1.295134, 1.294920, 1.294712, 1.294511, 1.294315, 1.294126, 1.293942, 1.293763,
100             1.293589, 1.293421, 1.293256, 1.293097, 1.292941, 1.292790, 1.292643, 1.292500, 1.292360, 1.292224,
101             1.292091, 1.291961, 1.291835, 1.291711, 1.291591, 1.291473, 1.291358, 1.291246, 1.291136, 1.291029,
102             1.290924, 1.290821, 1.290721, 1.290623, 1.290527, 1.290432, 1.290340, 1.290250, 1.290161, 1.290075],
103         0.95: [
104             6.313752, 2.919986, 2.353363, 2.131847, 2.015048, 1.943180, 1.894579, 1.859548, 1.833113, 1.812461,
105             1.795885, 1.782288, 1.770933, 1.761310, 1.753050, 1.745884, 1.739607, 1.734064, 1.729133, 1.724718,
106             1.720743, 1.717144, 1.713872, 1.710882, 1.708141, 1.705618, 1.703288, 1.701131, 1.699127, 1.697261,
107             1.695519, 1.693889, 1.692360, 1.690924, 1.689572, 1.688298, 1.687094, 1.685954, 1.684875, 1.683851,
108             1.682878, 1.681952, 1.681071, 1.680230, 1.679427, 1.678660, 1.677927, 1.677224, 1.676551, 1.675905,
109
110             1.675285, 1.674689, 1.674116, 1.673565, 1.673034, 1.672522, 1.672029, 1.671553, 1.671093, 1.670649,
111             1.670219, 1.669804, 1.669402, 1.669013, 1.668636, 1.668271, 1.667916, 1.667572, 1.667239, 1.666914,
112             1.666600, 1.666294, 1.665996, 1.665707, 1.665425, 1.665151, 1.664885, 1.664625, 1.664371, 1.664125,
113             1.663884, 1.663649, 1.663420, 1.663197, 1.662978, 1.662765, 1.662557, 1.662354, 1.662155, 1.661961,
114             1.661771, 1.661585, 1.661404, 1.661226, 1.661052, 1.660881, 1.660715, 1.660551, 1.660391, 1.660234],
115         0.975: [
116             12.706205, 4.302653, 3.182446, 2.776445, 2.570582, 2.446912, 2.364624, 2.306004, 2.262157, 2.228139,
117             2.200985, 2.178813, 2.160369, 2.144787, 2.131450, 2.119905, 2.109816, 2.100922, 2.093024, 2.085963,
118             2.079614, 2.073873, 2.068658, 2.063899, 2.059539, 2.055529, 2.051831, 2.048407, 2.045230, 2.042272,
119             2.039513, 2.036933, 2.034515, 2.032245, 2.030108, 2.028094, 2.026192, 2.024394, 2.022691, 2.021075,
120             2.019541, 2.018082, 2.016692, 2.015368, 2.014103, 2.012896, 2.011741, 2.010635, 2.009575, 2.008559,
121
122             2.007584, 2.006647, 2.005746, 2.004879, 2.004045, 2.003241, 2.002465, 2.001717, 2.000995, 2.000298,
123             1.999624, 1.998972, 1.998341, 1.997730, 1.997138, 1.996564, 1.996008, 1.995469, 1.994945, 1.994437,
124             1.993943, 1.993464, 1.992997, 1.992543, 1.992102, 1.991673, 1.991254, 1.990847, 1.990450, 1.990063,
125             1.989686, 1.989319, 1.988960, 1.988610, 1.988268, 1.987934, 1.987608, 1.987290, 1.986979, 1.986675,
126             1.986377, 1.986086, 1.985802, 1.985523, 1.985251, 1.984984, 1.984723, 1.984467, 1.984217, 1.983972],
127         0.99: [
128             31.820516, 6.964557, 4.540703, 3.746947, 3.364930, 3.142668, 2.997952, 2.896459, 2.821438, 2.763769,
129             2.718079, 2.680998, 2.650309, 2.624494, 2.602480, 2.583487, 2.566934, 2.552380, 2.539483, 2.527977,
130             2.517648, 2.508325, 2.499867, 2.492159, 2.485107, 2.478630, 2.472660, 2.467140, 2.462021, 2.457262,
131             2.452824, 2.448678, 2.444794, 2.441150, 2.437723, 2.434494, 2.431447, 2.428568, 2.425841, 2.423257,
132             2.420803, 2.418470, 2.416250, 2.414134, 2.412116, 2.410188, 2.408345, 2.406581, 2.404892, 2.403272,
133
134             2.401718, 2.400225, 2.398790, 2.397410, 2.396081, 2.394801, 2.393568, 2.392377, 2.391229, 2.390119,
135             2.389047, 2.388011, 2.387008, 2.386037, 2.385097, 2.384186, 2.383302, 2.382446, 2.381615, 2.380807,
136             2.380024, 2.379262, 2.378522, 2.377802, 2.377102, 2.376420, 2.375757, 2.375111, 2.374482, 2.373868,
137             2.373270, 2.372687, 2.372119, 2.371564, 2.371022, 2.370493, 2.369977, 2.369472, 2.368979, 2.368497,
138             2.368026, 2.367566, 2.367115, 2.366674, 2.366243, 2.365821, 2.365407, 2.365002, 2.364606, 2.364217]
139     };
140
141     this.MovingAverageStrategies = [
142         {
143             id: 1,
144             label: 'Simple Moving Average',
145             parameterList: [
146                 {label: "Backward window size", value: 8, min: 2, step: 1},
147                 {label: "Forward window size", value: 4, min: 0, step: 1}
148             ],
149             execute: function (backwardWindowSize, forwardWindowSize, values) {
150                 var averages = new Array(values.length);
151                 // We use naive O(n^2) algorithm for simplicy as well as to avoid accumulating round-off errors.
152                 for (var i = 0; i < values.length; i++) {
153                     var sum = 0;
154                     var count = 0;
155                     for (var j = i - backwardWindowSize; j < i + backwardWindowSize; j++) {
156                         if (j >= 0 && j < values.length) {
157                             sum += values[j];
158                             count++;
159                         }
160                     }
161                     averages[i] = sum / count;
162                 }
163                 return averages;
164             },
165
166         },
167         {
168             id: 2,
169             label: 'Cumulative Moving Average',
170             execute: function (values) {
171                 var averages = new Array(values.length);
172                 var sum = 0;
173                 for (var i = 0; i < values.length; i++) {
174                     sum += values[i];
175                     averages[i] = sum / (i + 1);
176                 }
177                 return averages;
178             }
179         },
180         {
181             id: 3,
182             label: 'Exponential Moving Average',
183             parameterList: [{label: "Smoothing factor", value: 0.1, min: 0.001, max: 0.9}],
184             execute: function (smoothingFactor, values) {
185                 if (!values.length || typeof(smoothingFactor) !== "number")
186                     return null;
187
188                 var averages = new Array(values.length);
189                 var movingAverage = 0;
190                 averages[0] = values[0];
191                 for (var i = 1; i < values.length; i++)
192                     averages[i] = smoothingFactor * values[i] + (1 - smoothingFactor) * averages[i - 1];
193                 return averages;
194             }
195         },
196     ];
197
198     this.EnvelopingStrategies = [
199         {
200             id: 100,
201             label: 'Average Difference',
202             description: 'The average difference between consecutive values.',
203             execute: function (values, movingAverages) {
204                 if (values.length < 1)
205                     return NaN;
206
207                 var diff = 0;
208                 for (var i = 1; i < values.length; i++)
209                     diff += Math.abs(values[i] - values[i - 1]);
210
211                 return diff / values.length;
212             }
213         },
214         {
215             id: 101,
216             label: 'Moving Average Standard Deviation',
217             description: 'The square root of the average deviation from the moving average with Bessel\'s correction.',
218             execute: function (values, movingAverages) {
219                 if (values.length < 1)
220                     return NaN;
221
222                 var diffSquareSum = 0;
223                 for (var i = 1; i < values.length; i++) {
224                     var diff = (values[i] - movingAverages[i]);
225                     diffSquareSum += diff * diff;
226                 }
227
228                 return Math.sqrt(diffSquareSum / (values.length - 1));
229             }
230         },
231     ];
232
233     function createWesternElectricRule(windowSize, minOutlinerCount, limitFactor) {
234         return function (values, movingAverages, deviation) {
235             var results = new Array(values.length);
236             var limit = limitFactor * deviation;
237             for (var i = 0; i < values.length; i++)
238                 results[i] = countValuesOnSameSide(values, movingAverages, limit, i, windowSize) >= minOutlinerCount ? windowSize : 0;
239             return results;
240         }
241     }
242
243     function countValuesOnSameSide(values, movingAverages, limit, startIndex, windowSize) {
244         var valuesAboveLimit = 0;
245         var valuesBelowLimit = 0;
246         var center = movingAverages[startIndex];
247         for (var i = startIndex; i < startIndex + windowSize && i < values.length; i++) {
248             var diff = values[i] - center;
249             valuesAboveLimit += (diff > limit);
250             valuesBelowLimit += (diff < -limit);
251         }
252         return Math.max(valuesAboveLimit, valuesBelowLimit);
253     }
254     window.countValuesOnSameSide = countValuesOnSameSide;
255
256     this.AnomalyDetectionStrategy = [
257         // Western Electric rules: http://en.wikipedia.org/wiki/Western_Electric_rules
258         {
259             id: 200,
260             label: 'Western Electric: any point beyond 3σ',
261             description: 'Any single point falls outside 3σ limit from the moving average',
262             execute: createWesternElectricRule(1, 1, 3),
263         },
264         {
265             id: 201,
266             label: 'Western Electric: 2/3 points beyond 2σ',
267             description: 'Two out of three consecutive points fall outside 2σ limit from the moving average on the same side',
268             execute: createWesternElectricRule(3, 2, 2),
269         },
270         {
271             id: 202,
272             label: 'Western Electric: 4/5 points beyond σ',
273             description: 'Four out of five consecutive points fall outside 2σ limit from the moving average on the same side',
274             execute: createWesternElectricRule(5, 4, 1),
275         },
276         {
277             id: 203,
278             label: 'Western Electric: 9 points on same side',
279             description: 'Nine consecutive points on the same side of the moving average',
280             execute: createWesternElectricRule(9, 9, 0),
281         },
282         {
283             id: 210,
284             label: 'Mozilla: t-test 5 vs. 20 before that',
285             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",
286             execute: function (values, movingAverages, deviation) {
287                 var results = new Array(values.length);
288                 var p = false;
289                 for (var i = 20; i < values.length - 5; i++)
290                     results[i] = Statistics.testWelchsT(values.slice(i - 20, i), values.slice(i, i + 5), 0.99) ? 5 : 0;
291                 return results;
292             }
293         },
294     ]
295
296 })();
297
298 if (typeof module != 'undefined') {
299     for (var key in Statistics)
300         module.exports[key] = Statistics[key];
301 }