计算循环缓冲区的标准偏差

作者: 雨儿
发布时间: 2025-01-16 07:07:57 (19天前)
转自：

4 条回复

0#
回复此人
蜡笔小辛 | 2019-08-31 10-32

<div class =“post-text”itemprop =“text”> 标准差可表示为： <pre> <code> stddev = sqrt(1/N * SUM(x[i]^2) - 1/N^2 * SUM(x[i])^2) </code> </pre> 对于未校正的样品标准偏差。对于更正的样本标准差，可以写： <pre> <code> stddev = sqrt(1/(N-1) * SUM(x[i]^2) - 1/(N^2-N) * SUM(x[i])^2) </code> </pre> 如果你保留两个累加器，一个用于 <code> SUM(x[i]^2) </code> 和一个 <code> SUM(x[i]) </code> ，然后对每个新值进行更新是微不足道的（减去最旧值的影响，并添加最新值的效果）。 <code> N </code> 当然是缓冲区的长度。 当然，如果你是在浮点运算，那么你可能会遇到舍入错误（ <code> (x + y) - x != y </code> ，一般来说）。我认为没有任何简单的解决办法。 </DIV>

编辑
1#
回复此人
林老爷的日常 | 2019-08-31 10-32

<div class =“post-text”itemprop =“text”> 最简单的方法是反转Knuth的公式（来自 <a href="http://en.wikipedia.org/wiki/Algorithms_for_calculating_variance#On-line_algorithm" rel="nofollow"> 维基百科文章 </A> 方差计算： 中号 <子> k-1的 </子> = M. <子> ķ </子> - （X <子> ķ </子> - M. <子> ķ </子> ）/（K-1） 小号 <子> k-1的 </子> = S. <子> ķ </子> - （X <子> ķ </子> - M. <子> k-1的 </子> ）（X <子> ķ </子> - M. <子> ķ </子> ） 但是，请注意浮点错误将累积过来 整个运行 ！这意味着您的均值和方差数将趋于漂移，并且此方法无法真正用作准确的在线方法。 一个稳定的在线方法，每个样本采用O（log N）操作（其中N是队列中元素的数量）将使用 二进制合并树 统计项目，使用维基百科文章中的“并行合并”公式，如下（以C ++形式）： <pre> <code> struct Statistic { int k; Element M; Element S; Statistic(Element x) : k(1) , M(x) , S(0) {} Statistic(Statistic a, Statistic b) : k(a.k + b.k) , M(a.M*a.k + b.M*b.k)/float(k) , S(a.S + b.S + (a.M-b.M)*(a.M-b.M)*(a.k*b.k/float(k))) {} }; </code> </pre> 对于稳定的O（log N）在线算法，维护上述统计的平衡二叉树，叶子代表各个元素;根将产生所需的在线统计数据。在更新元素时（以旋转缓冲区样式），将执行O（log N）操作以将每个更新从叶传播到根。 </DIV>

编辑
2#
回复此人
布偶的表弟派大星丶 | 2019-08-31 10-32

<div class =“post-text”itemprop =“text”> 为集合保留三个数字：值的计数，值的总和以及值的平方和。为方便起见，我们将这些称为k，sn和sn2。 如果，正如我认为你暗示的那样，新值总是替换循环队列中的旧值，那么计数可能是不变的。或者也许可能有一个不完整的队列。无论哪种方式： 每次向队列添加值时，将一个值添加到计数中，将此值添加到总和中，并将此值的平方值添加到平方和。也就是说，如果添加新值“n”，则k = k + 1，sn = sn + n，sn2 = sn2 + n ^ 2。 每次从队列中删除一个值时，从计数中减去一个，从总和中减去该值，并从平方和中减去该值的平方。也就是说，如果删除值“n”，则k = k-1，sn = sn-n，sn2 = sn2-n ^ 2。 然后，您可以在每次更改后轻松重新计算标准偏差，而无需重新计算所有内容。 请注意，这意味着您必须能够在真正删除之前“捕获”某个值。 注意：我怀疑这是我的袖珍计算器的功能，因为它具有转储sum（n）和sum（n ^ 2）的功能，我可以“删除”我从未添加的值，就像我可以说添加2和4到集合，然后删除3，它说没关系。所以我认为它没有列出一个清单：它必须保持计数和总和。 </DIV>

编辑

登录后才能参与评论