非常庞大的数据集的平均值和标准差

Question

我想知道是否有算法计算未绑定数据集的平均值和标准差.

例如,我正在监测一个测量值,比如电流.我想得到所有历史数据的平均值.每当有新值出现时,更新均值和stdev？因为数据太大而无法存储,我希望它可以在不存储数据的情况下即时更新均值和stdev.

即使数据被存储,标准方式(d1 + ... + dn)/ n也不起作用,总和将吹灭数据表示.

我通过求和(d1/n + d2/n + ... d3/n),如果n为hugh,则误差太大并累积.此外,在这种情况下,n是未绑定的.

数据的数量肯定是未绑定的,无论何时,它都需要更新值.

有人知道是否有算法吗？

Answer 1

[这个问题改变了吗？也许我只读了一开始.我已更新/编辑以提供更好的答复:]

我所知道的并没有完美的解决方案(在恒定的记忆中),但我可以提供各种方法.

首先,对于基本计算,您只需要所有值(sum_x)的总和,它们的平方和(sum_x2)和总计数(n)的总和.然后:

mean = sum_x / n
stdev = sqrt( sum_x2/n - mean^2 )

并且所有这些值(sum_x,sum_x2,n)可以从流中进行更新.

问题(如你所说)是处理溢出和/或有限的精度.你可以看到这个,如果你考虑浮点,当sum_x2它太大,内部表示不包括单个平方值的大小的值.

避免问题的一种简单方法是使用精确算术,但这将越来越慢(并且还使用O(log(n))内存).

另一种可以帮助的方法是标准化值 - 如果你知道值通常是X那么你可以做计算x - X,使得总和更小(显然你然后添加X到平均值!).这有助于推迟精度丢失的点(并且可以/应该与此处的任何其他方法结合 - 例如,当分箱时,您可以使用前一个箱的平均值).有关如何逐步执行此操作,请参阅此算法(knuth的方法).

如果你不介意(小的常数因素)O(n)内存成本你可以重新启动每个N值(例如百万 - 更智能仍然是通过检测精度太低来调整这个值),存储先前的均值和stdev和然后合并为最终结果(因此您的平均值是来自最近运行总计和旧分箱值的适当加权值).

分箱方法可能会推广到多个级别(你开始分箱)并减少到O(log(n))内存使用,但我还没有弄清楚细节.

最后,一个更实际的解决方案可能是为1000个值做初始方法,然后并行开始一个新的求和.你可以显示两者的加权平均值,然后在另外1000个值之后,丢弃旧的总和(在逐渐减轻它们的重量之后)并开始一个新的集合.因此,您总是有两组总和,并在它们之间显示加权平均值,这样可以提供反映最后1000个值的连续数据(仅限).在某些情况下,这将是足够好的,我想(这不是一个确切的值,因为它只是"最近"的数据,但它是平滑和有代表性的,并使用固定数量的内存).

ps,后来发生的事情 - 真的,"永远"做这件事无论如何都没有多大意义,因为你将达到价值绝对由旧数据支配的程度.最好使用"运行平均值",它可以降低旧值的权重.例如,请参阅https://en.wikipedia.org/wiki/Moving_average - 但是,我不知道与stdev相同的常见内容.

Answer 2

有趣的问题。

让我们先讨论平均值，只是因为它更简单一些。

您对运行总计的舍入误差的看法是正确的。对于足够大的数据集，它会降低你的准确性。您想要对数据进行预排序，首先对小数据进行总计；但当然这对你来说是不可能的。但是，您可以通过保留多个运行总计来实现排序数据的大部分好处。

一个概念性示例，C 或 C++ 风格：

const double max_small  =    0.001;
const double max_medium = 1000.0;

double total_small;
double total_medium;
double total_large;

while(true) {
    const double datum = get_datum(); // (Use here whatever function you use to get a datum.)
    if (!is_datum_valid()) break;
    if (abs(datum) <= max_small) total_small += datum;
    else if (abs(datum) <= max_medium) total_medium += datum;
    else total_large += datum;
}

double total = 0.0;
total += total_small;
total += total_medium;
total += total_large;

在实际代码中，您可能会保留三个以上的运行总计 - 当然，您还会继续运行数据平方的总计 - 但上面的示例传达了这个想法。您可以填写详细信息。

另外，适应@andrewcooke的想法，您可以以如下方式扩展循环：

while(true) {
    const double datum = get_datum();
    if (!is_datum_valid()) break;
    if (abs(datum) <= max_small) {
        total_small += datum;
        if (abs(total_small) > max_medium) {
            total_large += total_small;
            total_small = 0.0;
        }
    }
    else if (abs(datum) <= max_medium) total_medium += datum;
    else total_large += datum;
}

再次，您可以填写详细信息。祝你好运。

附录：标准差的实际计算

这里的各种评论线程中提出了一个很好的问题，即如何在事先不知道平均值的情况下计算标准差。幸运的是，有一个已知的技巧可以计算标准差。我准备了两页注释来解释这里的技巧（PDF 格式）。

无论如何，在运行统计中包含标准差所需要做的就是不仅要对数据进行求和，还要对数据进行平方求和；当然，可以按照与数据本身类似的方式对平方进行求和，遵循与上面代码中相同的模式。