algorithm - 时间窗在线方差算法

Question

我正在尝试寻找一种有效的在线算法来计算预定义时间 窗口(例如最后 5 分钟)内的滚动方差。它需要高效，因为我无法保留时间窗口内的所有数据点，因为它们以每秒 10M 数据点的频率到达。理想情况下，算法也应该在数值上稳定。我知道 Welford's algorithm对于非窗口滚动方差。

我知道固定大小 窗口的其他 SO 答案。我相信这是一个不同的问题。

Answer 1

我想你会遇到完全按照说明解决这个问题的问题。

考虑编码为浮点样本对的比特流 1 = {0.0, 0.0} 0 = {-1.0, 1.0}。如果我将窗口大小的任意比特流的编码结果提供给你的算法，然后发送一个零流，你的算法报告的方差将波动，这取决于刚刚从窗口的远边缘掉落的样本对是 {0.0, 0.0} 或 {-1.0, 1.0}。

所以我可以用你的算法来记住大约滑动窗口一半大小的比特流。因此，如果不使用大约这么多存储空间，就无法实现您的算法。

也许您可以使用某种形式的指数平滑。简单指数平滑相当于加权平均，其中权重呈指数衰减，如果对平方值进行平滑处理，您将获得指数加权平方和。如果您还有未平方值的指数加权和，则可以将两者结合起来，以获得与某个中心值的偏差平方和的指数加权和，对于任何所需的中心值。当然，您需要显着改进这个想法才能获得数值稳定的东西 - 也许这在您引用的维基百科文章末尾的一种加权方差算法的详细信息中有所介绍。