Welford算法-方差计算

最近在看《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/

作者:
该日志由 zktang 于2012年02月26日发表在计算机科学分类下, 你可以发表评论,并在保留原文地址及作者的情况下引用到你的网站或博客。
转载请注明: Welford算法-方差计算
标签: , ,
【上一篇】
【下一篇】

您可能感兴趣的文章: