最近在看《Mahout in Action》的分类章节，里面在评估学习效果时不断用到一个公式来计算平均值（\( avg = avg + \frac{ll – avg}{mu} \) ），其中mu=Math.min(k + 1, 200)。之前一直从来没有看到过这样的式子，经查，终于知晓是Welford算法迭代计算均值和方差的。

但这里仅提到以下三种，即最最普通的算法、普通的算法，和Welford算法。

1、最最普通的算法

按照总体方差的公式定义如下：

$$ \sigma^{2} = \frac{\sum\limits_{i=1}^{n}{x_i}^2-\frac{{(\sum\limits_{i=1}^{n}{x_i}})^2}{n})}{n} $$

而计算n个样本总体方差的无偏估计，即样本方差公式则如下：

$$ \sigma^{2} = \frac{\sum\limits_{i=1}^{n}{x_i}^2-\frac{{(\sum\limits_{i=1}^{n}{x_i}})^2}{n})}{n-1} $$

于是有了第一版的算法，直接将该公式实现。

double naive_variance(int[] data){
    int n = 0;
    double sum = 0;
    double sum_sqr = 0;

    for(int x : data){
        n++;
        sum += x;
        sum_sqr += x*x;
    }
    double mean = sum / n;
    double variance = (sum_sql - sum*mean)/(n-1);
    return variance;
}

而这个算法的问题是精度较低，尤其是标准差比均值相对较小的话。当然，这一算法可以通过引进Assumed Mean的方法来改进。

2、普通的算法

另外的方法是使用不用的公式定义方差，而这好像才是我平常在概率论教材里面学到的公式，首先计算样本均值：

$$ \bar{x}=\frac{\sum\limits_{i=1}^{n}{x_i}}{n} $$

然后再计算方差：

$$ s^2 = \frac{\sum\limits_{i=1}^{n}{(x_i-\bar{x})}^2}{n-1} $$

所以算法如下：

double two_pass_variance(int[] data){
    int n = 0;
    double sum1 = 0;
    double sum2 = 0;

    for(int x : data){
        n++;
        sum1 += x;
    }
    mean = sum1 / n;

    for(int x : data){
        sum2 += (x-mean)*(x-mean);
    }
    variance = sum2 / (n-1);
    return variance;
}

这一算法在计算精度上还是可靠的。但上述两种算法都是在不断地求和的过程中对误差进行舍入，而引进Compensated Summation可在一定程度上处理该问题。

3、Welford算法

另外，由于在运算过程上对数据进行整批处理的要求太过死板，因此合适的Online均值和方差计算方法一直都在应用中出现。有公式定义如下：

均值：

$$ \bar{x}_n=\frac{(n-1)\bar{x}_{n-1}+x_n}{n}=\bar{x}_{n-1}+\frac{x_n-\bar{x}_{n-1}}{n} $$

又因为有如下公式：

$$ M_{2,n}=\sum\limits_{i=1}^n{(x_i-\bar{x}_n)^2}=M_{2,n-1}+(x_n-\bar{x}_n)(x_n-\bar{x}_{n-1}) $$

所以，总体方差：

$$ \sigma_n^2=\frac{M_{2,n}}{n} $$

样本方差：

$$ s_n^2=\frac{M_{2,n}}{n-1},   n>1 $$

算法如下：

double online_variance(int[] data){
    int n = 0;
    double mean = 0;
    double m2 = 0;

    for(int x : data){
        n++;
        delta = x - mean;
        mean += delta / n;
        if(n > 1){
            m2 += delta*(x-mean)
        }
    }
    variance_n = m2 / n;
    variance = m2 / (n-1)
    return variance
}

关于方差计算的方法还有很多，如并行Online更多详情请参见[1]所述，另外[2][3][4]也可参考。

参考：

[1] http://en.wikipedia.org/wiki/Algorithms_for_calculating_variance

[2] http://lingpipe-blog.com/2009/03/19/computing-sample-mean-variance-online-one-pass/

[3] http://www.johndcook.com/standard_deviation.html

[4] http://www.johndcook.com/blog/2008/09/26/comparing-three-methods-of-computing-standard-deviation/