2

我目前正在使用在线方差算法来计算给定序列的方差。这很好用，并且还提供了良好的数值稳定性和抗溢出性，但代价是一些速度，这很好。我的问题是，如果样本均值已知，是否存在比这更快的算法，同时具有相似的稳定性和抗溢出性（因此不像天真的方差计算）。

当前的在线方差计算是单遍算法，在主循环中包含除法和乘法（这是影响速度的因素）。来自维基百科：

def online_variance(data):
    n = 0
    mean = 0
    M2 = 0

    for x in data:
        n = n + 1
        delta = x - mean
        mean = mean + delta/n
        M2 = M2 + delta*(x - mean)

    variance = M2/(n - 1)
    return variance
4

1 回答 1

3

导致天真的方差计算变得不稳定的事实是，您分别对 X（以获得均值（x））和 X^2 值求和，然后取差值

var = mean(x^2) - (mean(x))^2

但是由于方差的定义是

var = mean((x - mean(x))^2)

你可以评估它，它会尽可能快。当您不知道均值时，您必须首先计算它以获得稳定性，或者使用“简单”的公式，该公式只遍历数据一次，以牺牲数值稳定性为代价。

编辑 现在您已经给出了“原始”代码，变得更好（更快）很容易。正如您正确指出的那样，内部循环中的划分正在减慢您的速度。试试这个进行比较：

def newVariance(data, mean):
  n = 0
  M2 = 0

  for x in data:
    n = n + 1
    delta = x - mean
    M2 = M2 + delta * delta

  variance = M2 / (n - 1)
  return variance

注意 - 这看起来很像Wikipedia 中的 two_pass_variance 算法，除了你不需要第一次通过来计算平均值，因为你说它是已知的。

于 2013-05-27T06:42:33.597 回答