计算“移动”协方差

Question

我一直在尝试弄清楚如何有效地计算移动窗口中的协方差，即从一组值(x，y)..(xn-1，yn-1)移动到一组新的值(x1，y1)..(xn，yn)。换句话说，值(x，y)被值(xn，yn)替换。出于性能原因，我需要递增地计算协方差，因为我想用前一个协方差Cov(x..xn-1，y..yn-1)来表示新的协方差Cov(x1..xn，y1..yn)。

从这里描述的协方差的朴素公式开始：

[https://en.wikipedia.org/wiki/Algorithms_for_calculating_variance#Covariance][1]

我能想到的就是：

Cov(x[1]..x[n], y[1]..y[n]) =
Cov(x[0]..x[n-1], y[0]..y[n-1]) +
(x[n]*y[n] - x[0]*y[0]) / n -
AVG(x[1]..x[n]) * AVG(y[1]..y[n]) +
AVG(x[0]..x[n-1]) * AVG(y[0]..y[n-1])

我很抱歉这个符号，我希望我想表达的意思或多或少是清晰的。

然而，我不确定这在数值上是否足够稳定。处理较大的值时，我可能会遇到算术溢出或其他(例如，取消)问题。

有没有更好的方法来做这件事？

谢谢你的帮助。

Answer 1

看起来您正在尝试某种形式的“添加新值，减去旧值”。您的担心是正确的:此方法在数值上不稳定。以这种方式求和可能会发生漂移，但真正的杀手是这样一个事实:在每一步，你都是从一个大数字中减去一个大数字，得到一个很可能是非常小的数字。

一个改进是独立维护( x_i、y_i和x_i*y_i的)和，并在每一步重新计算它们的朴素公式。你运行的总和仍然会漂移，这个朴素的公式在数值上仍然是不稳定的，但至少你只会有一个数值不稳定的步骤。

解决这个问题的一种稳定方法是实现(稳定地)合并统计集的公式，并使用合并树评估总体协方差。移动窗口将更新其中一个叶子，需要将每个节点从该叶子更新到根。对于大小为n的窗口，该方法每次更新所需的时间为O(log )，而不是O(1)的初始计算量，但结果将是稳定和准确的。此外，如果您不需要每个增量步骤的统计信息，则可以为每个输出样本更新一次树，而不是为每个输入样本更新一次。如果每个输出样本有k个输入样本，则将每个输入样本的成本降低到O(1 + (log )/k)。

评论:您引用的维基百科页面包含Knuth在线算法的部分，该算法相对稳定，但仍容易漂移。你应该能够做一些比较协方差的事情；并且每K*n个样本重置你的计算应该以最小的代价限制漂移。

Answer 2

不知道为什么没有人提到这一点，但你可以使用依赖于运行均值的the Welford online algorithm：

方程式应如下所示：

​

给出的在线平均值为：

​