在一些统计或者排序的算法中，常常要用到样本方差这个东西，来判断一组数据的离散程度。
这是样本方差的公式：
然而，在计算机编程中，往往需要计算运行方差（running variance），因为样本的个数总是的在不断变化的，确切将是不断递增；如果每次增加，都要重新计算平均值，再按次公式，计算出方差；虽可以实现，但计算量会随着数据的增长变的太大。
因此，递推的公式就显得格外重要；通过n-1个样本时的方差值
，和新增的样本
，就能得到此时这N个样本的方差；这样计算量不会变同时保持在一个很小的值，可大大提高程序的计算效率。递推公式如下：
Mn = Mn-1+ (xn - Mn-1)/n
Sn = Sn-1 + (xn - Mn-1)*(xn - Mn)
Mn为平均值，初始时： M1 = x1, S1 = 0 （此等式的推导证明，我后面给出），而样本方差 s =Sn/(n - 1)
下面是我自己给出的简单实现（若有更好的实现，请不吝赐教）
package com.mycode.math;
public final class RunningVariance {
private int count;// 样本的个数
private double mk;// 平均值
private double sk;// Sn
private double runVar;// 样本方差
public RunningVariance() {
this(0, 0.0, 0.0);
}
public RunningVariance(int count, double mk, double sk) {
this.count = count;
this.mk = mk;
this.sk = sk;
recomputeRunVar();
}
public double getMk() {
return mk;
}
public double getSk() {
return sk;
}
/**
* 获取运行时样本方差
*
* @return
*/
public synchronized double getRunningVariance() {
return runVar;
}
/**
* 增加样本
*
* @param sample
*/
public synchronized void addSample(double sample) {
if (++count == 1) {
mk = sample;
sk = 0.0;
} else {
double oldmk = mk;
double diff = sample - oldmk;
mk += diff / count;
sk += diff * (sample - mk);
}
recomputeRunVar();
}
/**
* 移除样本
*
* @param sample
*/
public synchronized void removeSample(double sample) {
int oldCount = getCount();
double oldmk = mk;
if (oldCount == 0) {
throw new IllegalStateException();
}
if (--count == 0) {
mk = Double.NaN;
sk = Double.NaN;
} else {
mk = (oldCount * oldmk - sample) / (oldCount - 1);
sk -= (sample - mk) * (sample - oldmk);
}
recomputeRunVar();
}
private synchronized void recomputeRunVar() {
int count = getCount();
runVar = count > 1 ? sk / (count - 1) : Double.NaN;
// 若需要计算标准差
// runVar = count > 1 ? Math.sqrt(sk / (count - 1)) : Double.NaN;
}
public synchronized int getCount() {
return count;
}
}
对于递推公式 Sn = Sn-1 + (xn - Mn-1)*(xn - Mn)，我自己做了个简单的推导证明，如下图：
另：图中所提的 等式1 即是 平均数的递推公式：Mn = Mn-1+ (xn - Mn-1)/n
原创blog，转载请注明http://my.oschina.net/BreathL/blog/41063
