7

我想计算双打流的平均值。这是一个简单的任务，只需要存储一个 double 和一个 int。我正在使用 apache commons SummaryStatistics 类来执行此操作。但是，在测试时，我注意到 SummaryStatistics 的平均值有浮点错误，而我自己的 python 实现没有。经过进一步检查，我发现 commons 正在使用以下算法的一个版本：

static double incMean(double[] data) {
    double mean = 0;
    int number = 0;
    for (double val : data) {
        ++number;
        mean += (val - mean) / number;
    }
    return mean;
}

这有时会导致小的浮点错误，例如

System.out.println(incMean(new double[] { 10, 9, 14, 11, 8, 12, 7, 13 }));
// Prints 10.500000000000002

这也是番石榴实用程序 DoubleMath.mean 使用的均值算法。我觉得很奇怪，他们都使用上述算法而不是更天真的算法：

static double cumMean(double[] data) {
    double sum = 0;
    int number = 0;
    for (double val : data) {
        ++number;
        sum += val;
    }
    return sum / number;
}

System.out.println(cumMean(new double[] { 10, 9, 14, 11, 8, 12, 7, 13 }));
// Prints 10.5

我可以想到为什么人们可能更喜欢前一种算法的原因有两个。一个是，如果您在流式传输期间大量查询平均值，则只需要复制一个值可能比进行除法更有效，除非更新步骤似乎要慢得多，这几乎总是超过这个成本（注意，我实际上并没有计时差异）。

另一种解释是前者防止溢出问题。浮点数似乎并非如此，至多这应该会导致均值下降。如果出现此错误，我们应该能够将结果与使用 BigDecimal 类完成的相同 cumMean 进行比较。这导致以下功能：

public static double accurateMean(double[] data) {
    BigDecimal sum = new BigDecimal(0);
    int num = 0;
    for (double d : data) {
        sum = sum.add(new BigDecimal(d));
        ++num;
    }
    return sum.divide(new BigDecimal(num)).doubleValue();
}

这应该是我们能得到的最准确的平均值。从以下代码的一些轶事运行来看，平均值和最准确的代码之间似乎没有显着差异。有趣的是，它们往往与数字上的准确平均值不同，而且两者总是比另一个更接近。

Random rand = new Random();
double[] data = new double[1 << 29];
for (int i = 0; i < data.length; ++i)
    data[i] = rand.nextDouble();

System.out.println(accurateMean(data)); // 0.4999884843826727
System.out.println(incMean(data));      // 0.49998848438246
System.out.println(cumMean(data));      // 0.4999884843827622

有没有人有理由解释为什么 apache commons 和 guava 都选择了前一种方法而不是后者？

编辑：我的问题的答案似乎很清楚，答案是 Knuth 在 The Art of Programming Vol II 4.2.2 (15) 中提出了它（感谢 Louis Wasserman 提供查看番石榴源的提示）。然而，在书中，Knuth 提出了这种计算均值的方法来引导标准差的稳健计算，不一定说这是最优均值计算。基于阅读更多章节，我实现了第四个意思：

static double kahanMean(double[] data) {
    double sum = 0, c = 0;
    int num = 0;
    for (double d : data) {
        ++num;
        double y = d - c;
        double t = sum + y;
        c = (t - sum) - y;
        sum = t;
    }
    return sum / num;
}

执行与上述相同的测试（几次，没有统计学意义），我得到与 BigDecimal 实现完全相同的结果。我可以想象 knuth 均值更新比使用更复杂的求和方法更快，但更复杂的方法在经验上似乎更准确地估计均值，我天真地期望这也会导致更好的标准差更新。除了可能更快之外，还有其他理由使用 knuth 方法吗？

4

1 回答 1

2

简短的回答：增量更新方法作为默认方法是首选，因为它避免了数值错误，并且不会比 sum-and-and-divide 方法花费更多的时间/空间。

当取大量样本的平均值时，增量更新方法在数值上更加稳定。可以看到，在incMean所有的变量中，总是一个典型数据值的顺序；但是在求和版本中，变量sum是有序的N*mean，由于浮点数学的有限精度，这种规模差异可能会导致问题。

在float's (16bits) 的情况下，可以构建人为的问题案例：例如，很少有稀有样本O(10^6)，其余样本O(1)（或更小），或者通常如果您有数百万个数据点，那么增量更新将提供更准确的结果。

这些有问题的情况不太可能使用doubles （这就是为什么您的测试用例都给出几乎相同的结果），但是对于具有大量值分布的非常大的数据集，可能会出现相同的数值问题，因此这是一个普遍接受的好处练习使用增量方法取平均值（和其他时刻！）

Kahan方法的优点是：

  1. 只有一个除法操作（增量方法需要N除法），

  2. 时髦的，几乎是循环的数学是一种减少在蛮力求和中出现的浮点错误的技术。将变量c视为适用于下一次迭代的“更正”。

但是，对增量方法进行编码（和阅读）更容易。

于 2014-06-03T19:35:34.953 回答