Created
November 13, 2012 08:51
-
-
Save qubyte/4064710 to your computer and use it in GitHub Desktop.
Calculate a running standard deviation.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
// A standard deviation object constructor. Running deviation (avoid growing arrays) which | |
// is round-off error resistant. Based on an algorithm found in a Knuth book. | |
function StandardDeviation(firstMeasurement) { | |
this.workData = firstMeasurement; | |
this.lastWorkData = null; | |
this.S = 0; | |
this.count = 1; | |
} | |
// Add a measurement. Also calculates updates to stepwise parameters which are later used | |
// to determine sigma. | |
StandardDeviation.prototype.addMeasurement = function (measurement) { | |
this.count += 1; | |
this.lastWorkData = this.workData; | |
this.workData = this.workData + (measurement - this.workData) / this.count; | |
this.S = this.S + (measurement - this.lastWorkData) * (measurement - this.workData); | |
}; | |
// Performs the final step needed to get the standard deviation and returns it. | |
StandardDeviation.prototype.get = function () { | |
return Math.sqrt(this.S / (this.count - 1)); | |
}; |
Improved version that adds replace and removeMeasurement. Based on the anwsers provided by marco and Deleting Values in Welford’s Algorithm for Online Mean and Variance
// A standard deviation object constructor. Running deviation (avoid growing arrays) which
// is round-off error resistant. Based on an algorithm found in a Knuth book.
function StandardDeviation(firstMeasurement) {
this.workData = firstMeasurement;
this.lastWorkData = null;
this.S = 0;
this.count = 1;
}
// Add a measurement. Also calculates updates to stepwise parameters which are later used
// to determine sigma.
StandardDeviation.prototype.addMeasurement = function (measurement) {
this.count += 1;
this.lastWorkData = this.workData;
this.workData = this.workData + (measurement - this.workData) / this.count;
this.S = this.S + (measurement - this.lastWorkData) * (measurement - this.workData);
};
// Performs the final step needed to get the standard deviation and returns it.
StandardDeviation.prototype.get = function () {
return Math.sqrt(this.S / (this.count - 1));
};
// Replaces the value x currently present in this sample with the
// new value y. In a sliding window, x is the value that
// drops out and y is the new value entering the window. The sample
// count remains constant with this operation.
StandardDeviation.prototype.replace = function (x, y) {
const deltaYX = y - x;
const deltaX = x - this.workData;
const deltaY = y - this.workData;
this.workData = this.workData + deltaYX / this.count;
const deltaYp = y - this.workData;
const countMinus1 = this.count - 1;
this.S = this.S - this.count / countMinus1 * (deltaX * deltaX - deltaY * deltaYp) - deltaYX * deltaYp / countMinus1;
};
// Remove a measurement. Also calculates updates to stepwise parameters which are later used
// to determine sigma.
StandardDeviation.prototype.removeMeasurement = function (x) {
this.lastWorkData = (this.count * this.workData - x) / (this.count - 1);
this.S -= (x - this.workData) * (x - this.lastWorkData);
this.workData = this.lastWorkData;
this.count -= 1;
};
Below is typescript version, it's more convenient to have a class with empty constructor since it imposes less constraints on when this class can be initialized (before you have your first value or after):
// A standard deviation object constructor. Running deviation (avoid growing arrays) which
// is round-off error resistant. Based on an algorithm found in a Knuth book.
export class StandardDeviation {
public v: number = 0;
private w: number = 0;
private S: number = 0;
private count: number = 0;
// Add a measurement. Also calculates updates to stepwise parameters which are later used
// to determine sigma.
public add(measurement: number) {
this.count += 1;
this.w = this.v;
this.v = this.v + (measurement - this.v) / this.count;
this.S = this.S + (measurement - this.w) * (measurement - this.v);
}
// Performs the final step needed to get the standard deviation and returns it.
public get() {
if (this.count < 2) {
// There are less measurements accumulated than necessary to perform computation
return 0.0;
} else {
return Math.sqrt(this.S / (this.count - 1));
}
}
// Replaces the value x currently present in this sample with the
// new value y. In a sliding window, x is the value that
// drops out and y is the new value entering the window. The sample
// count remains constant with this operation.
public replace(x: number, y: number) {
const deltaYX = y - x;
const deltaX = x - this.v;
const deltaY = y - this.v;
this.v = this.v + deltaYX / this.count;
const deltaYp = y - this.v;
const countMinus1 = this.count - 1;
this.S = this.S - this.count / countMinus1 * (deltaX * deltaX - deltaY * deltaYp) - deltaYX * deltaYp / countMinus1;
}
// Remove a measurement. Also calculates updates to stepwise parameters which are later used
// to determine sigma.
public remove(x: number) {
this.w = (this.count * this.v - x) / (this.count - 1);
this.S -= (x - this.v) * (x - this.w);
this.v = this.w;
this.count -= 1;
}
}
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
The beauty behind this algorithm is that it doesn't need an entire dataset to be kept (it's single pass), and it's reasonably resistant to floating point errors.