渐进式计算平均值(Mean)和方差(Variance)

Tue 26 June 2018 / In categories Algorithms

statistics

本文介绍如何渐进式计算平均值(Mean)和方差(Variance)。

计算平均值(Mean)和方差(Variance)是统计数据时经常要用到的方法。这两个值的计算量跟数据集的大小有关系,以平均值为例,它要先把所有数据加起来,然后再除以个数才能得出。方差是在平均值的基础上做进一步的计算。

在数据集非常之大的情况下,按传统的方法计算这两个值需要先收集完完整的数据,然后才能进行计算。这不仅对提高存储的要求,而且把所有数相加的结果是一个非常大的值,容易导致精度溢出。那能不能改成,对数据集进行单步遍,历然后逐渐累积,最后得出结果值的方式来计算呢。这样的话,也不同等待数据全部收集完,减少缓存压力;也可以避免参加计算的数值过大,导致精度溢出。

从数学上讲,存在这种渐进式的平均值和方差计算方式,由*P. Welford*提出(请参考The Mindful Programmer: Welford’s method for computing variance)。在Accurately computing running variance一文中有C++的实现代码。

代码示例

渐进式计算平均值和方差的算法很简单,下面是Python代码示例。

计算平均值

class Mean:
  def __init__(self):
    self.count = 0
    self.value = 0
  def add(self, newData):
    self.count += 1
    self.value += (newData - self.value) / self.count

mean = Mean()
mean.add(1)
mean.add(2)
mean.add(3)

print("count %d, mean %f" % (mean.count, mean.value))

# 输出结果
# count 3, mean 2.000000

计算方差

class Variance:
  def __init__(self):
    self.count = 0
    self.mean = 0
    self.d = 0
    self.sampleVariance = 0
    self.populationVariance = 0
  def add(self, newData):
    self.count += 1
    oldMean = self.mean
    self.mean += (newData - self.mean) / self.count
    self.d += (newData - self.mean) * (newData - oldMean)
    self.populationVariance = self.d / self.count
    if self.count > 1:
      self.sampleVariance = self.d / (self.count - 1)

vari = Variance()
vari.add(1)
vari.add(2)
vari.add(3)
vari.add(4)

print("count %d, mean %f, population variance %f, sample variance %f" % (vari.count, vari.mean, vari.populationVariance, vari.sampleVariance))

# 输出结果
# count 4, mean 2.500000, population variance 1.250000, sample variance 1.666667

推导方式

具体的推导方式可以参考以下链接:

其他参考链接

Load Disqus Comments