计算“移动”的协方差

Question

我一直在尝试找出如何在移动窗口中高效地计算协方差，即从一组值(x[0]，y[0])..(x[n-1]，y[n-1])移动到一个新的值集合(x[1]，y[1])..(x[n]，y[n])。换句话说，值(x[0]，y[0])被值(x[n]，y[n])替换。出于性能原因，我需要逐步计算协方差，也就是说，我想用先前的协方差Cov(x[0]..x[n-1]，y[0]..y[n-1])来表示新的协方差Cov(x[1]..x[n]，y[1]..y[n])。

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

[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])

对于这个符号表示法，我很抱歉，希望我的表达大致清晰。

但是，我不确定这是否足够数值稳定。当处理大量的数据时，可能会遇到算术溢出或其他问题（例如抵消等）。

有没有更好的方法来解决这个问题？

感谢任何帮助。

- Stoyan

---

实际上，那个符号根本不清楚。看起来你试图将协方差公式表达为单行的编程语句？最好的解决方案涉及多个语句和变量。你尝试过在维基百科页面上实现其他算法吗？ - David

其实这不是一个编程问题。我的问题是，哪个公式适用于根据先前“窗口”（0..n-1）的协方差计算新“窗口”（1...n）的协方差，即无需查看中间所有数据点。 - Stoyan

假设数据点“掉出”是（x [0]，y [0]），新数据点是（x [n]，y [n]），我尝试找到一个公式，只需要先前的协方差、旧数据点、新数据点和各自序列的平均值... - Stoyan

维基百科页面在“在线算法”标题下有一个示例算法，我认为正是您想要的。 - David

是的，在线算法适合在添加新值对（x[n]，y[n]）时重新计算协方差。但是，我不知道如何将其扩展到还要删除旧值对... - Stoyan

Answer 1

看起来你正在尝试一种“添加新值并减去旧值”的方法。你的担忧是正确的：这种方法不是数值稳定的。以这种方式保持总和会出现漂移，但真正的问题在于，在每个步骤中，你都在从一个大数中减去另一个大数，得到的很可能是一个非常小的数。

一种改进方法是独立维护你的总和（x_i、y_i和x_i*y_i），并在每个步骤中从它们重新计算出朴素公式。你的运行总和仍然会漂移，朴素公式仍然不稳定，但至少你只有一个步骤存在数值不稳定性。

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

从评论中可以看出，你参考的维基百科页面包括一个关于Knuth在线算法的部分，这个算法相对稳定，但仍然容易漂移。你应该能够为协方差做类似的事情；并且每K*n个样本重置计算应该可以在最小的成本下限制漂移。

- comingstorm

---

你说得对，漂移很可能也会成为一个问题 :( - Stoyan

Answer 2

不确定为什么没有人提到这一点，但你可以使用Welford在线算法, 它依赖于运行平均值:

公式应该看起来像这样：

在线平均值为:

- lurscher

---

这将计算运行协方差（即从开始时的所有样本）。问题是寻找移动协方差（即最后N个样本的协方差）。 - digitalPhonix