计算流中的标准偏差

Question

使用Python,假设我正在运行已知数量的项目I,并且能够计算处理每个项目所需的时间t,以及运行的总处理时间T和到目前为止处理的项目数c.我正在计算飞行中的平均值,A = T / c但这可能会因为单个项目需要非常长的时间来处理(几秒钟而不是几毫秒).

我想展示一个正在运行的标准偏差.如何在不记录每个记录的情况下这样做t？

Answer 1

正如维基百科关于标准偏差的文章所述,它足以跟踪以下三个总和:

s0 = sum(1 for x in samples)
s1 = sum(x for x in samples)
s2 = sum(x*x for x in samples)

随着新值的到来,这些总和很容易更新.标准偏差可以计算为

std_dev = math.sqrt((s0 * s2 - s1 * s1)/(s0 * (s0 - 1)))

请注意,如果样本是浮点数并且标准差与样本的平均值相比较小,则这种计算标准偏差的方式可能会受到数值条件的影响.如果您期望这种类型的样本,您应该采用Welford的方法(参见接受的答案).

Answer 2

基于Welford的算法:

import numpy as np

class OnlineVariance(object):
    """
    Welford's algorithm computes the sample variance incrementally.
    """

    def __init__(self, iterable=None, ddof=1):
        self.ddof, self.n, self.mean, self.M2 = ddof, 0, 0.0, 0.0
        if iterable is not None:
            for datum in iterable:
                self.include(datum)

    def include(self, datum):
        self.n += 1
        self.delta = datum - self.mean
        self.mean += self.delta / self.n
        self.M2 += self.delta * (datum - self.mean)

    @property
    def variance(self):
        return self.M2 / (self.n - self.ddof)

    @property
    def std(self):
        return np.sqrt(self.variance)

更新每个新数据的方差:

N = 100
data = np.random.random(N)
ov = OnlineVariance(ddof=0)
for d in data:
    ov.include(d)
std = ov.std
print(std)

检查我们的结果与numpy计算的标准差:

assert np.allclose(std, data.std())

Answer 3

我使用Welford的方法,它可以提供更准确的结果.此链接指向John D. Cook的概述.这是一个段落,总结了为什么它是一种首选方法:

这种更好的计算差异的方法可以追溯到BP Welford在1962年发表的一篇论文,并在Donald Knuth的计算机程序设计,第2卷,第232页,第3版中有所介绍.尽管这种解决方案已有数十年的历史,但还不足以让人知道.大多数人可能没有意识到计算样本方差可能很难,直到他们第一次计算标准偏差并获得负数的平方根的例外.