快速计算平均值和方差的算法

原创
2022/02/23 09:28
阅读数 934
通常计算n个数的平均值和方差的方法,需要保存这n个数,然后求和,先求出平均,再计算方差。对于算力和存储很有限,而n又很大的情况,就难以处理。那是否有快速简便的计算平均值和方差的算法,不需要保存所有n个数即可计算呢?答案是肯定的。下面给出该算法,作为记录。
 
假设数列为xi: x0, x1, x2, ...., x(n-1)
令: mean = x0, var = 0
做循环
for (i = 0; i < n; i++) {
  oldm = mean;
  mean = oldm + (x[i] - oldm)/(i+1);
  var = var + (x[i] - oldm)*(x[i] - mean);
}
则平均值即为mean,方差即为var/n(有偏方差)或者var/(n-1)(无偏方差)。

注意上面的循环仅仅是为了模拟数据来源,实际上这个循环表示的是数据一个个过来,然后不断更新oldm, mean和var即可。然后根据要求多少个数的方差(比如n个数),对var除以n或者n-1即可。

 

下面给出python源代码供参考。

# -*- coding: utf-8 -*-

import random
import numpy

n = 20
datalist = []
for i in range(n):
    datalist.append(random.random())
    
oldm = 0
mean = datalist[0]
var = 0
for i in range(n):
    oldm = mean
    mean = oldm + (datalist[i]-oldm)/(i+1)
    var = var + (datalist[i] - mean)*(datalist[i] - oldm)
    
print("fast algorithm: ")
print("mean: ", mean, "\t var: ", var/n)

mean = 0
for i in range(n):
    mean += datalist[i]
    
mean = mean/n

var = 0
for i in range(n):
    var += (datalist[i]-mean)*(datalist[i]-mean)

print("traditional algorithm: ")
print("mean: ", mean, "\t var: ", var/n)

mean = numpy.mean(datalist)
var = numpy.var(datalist)

print("numpy: ")
print("mean: ", mean, "\t var: ", var)

可以看到,和传统算法相比,此算法首先不需要知道n,在更新oldm, mean和var的过程中随时可以计算平均值和方差。如果需要分段求平均和方差,只需将mean和var在合适的时候清零即可。虽然传统算法求平均值也可以做到这一点,但是方差必须先求出平均值才能计算,带来复杂性。

其次不需要保存数据,新数据随来随算。虽然例子中有datalist,但实际上此算法至始至终只用到最新的数据,之前的数据不需要保存。而传统算法的平均值虽然也可做到这一点,但方差需要保存所有数据再次计算,从而增加了计算和存储压力。

以上例子的计算结果如下:

展开阅读全文
加载中
点击引领话题📣 发布并加入讨论🔥
打赏
0 评论
0 收藏
0
分享
返回顶部
顶部