从数据子集计算平均值和方差的在线算法

Question

我将这篇文章作为在线计算变量长度数据数组的方差和均值的参考：http://www.johndcook.com/standard_deviation.html。

数据是16位无符号值的集合，可能包含任意数量的样本（实际上，最小约为20个样本，最大约为2e32个样本）。

由于数据集可能太大而无法存储，因此我已经使用上述在线算法在C语言中实现了它，并验证了其正确性。

问题在于应用程序的以下要求：除了计算整个集合的方差和均值之外，我还需要为由中间50％的值组成的人群计算分离的结果（均值和方差），即忽略前25％和后25％的样本。未知样本数，因此必须在线计算额外的集合。

我知道我可以通过单独计算子集并使用类似于这里描述的operator+实现来添加和删除子集: http://www.johndcook.com/skewness_kurtosis.html（减去偏度和峰度的具体内容，因为我不需要它们）。减法可以从中派生出来。

问题是：我该如何维护这些子集？或者我应该尝试另一种技术？

- Alexandre Pereira Nunes

---

一个问题是即使知道25%和75%是什么也很难/复杂。据我所知，没有简单的在线算法可以保证分位数估计。 - Rob Neuhaus

Answer 1

如果空间是一个问题，并且您愿意接受近似值，建议从以下论文中的算法开始：M Greenwald, S Khanna, Space-Efficient Online Computation of Quantile Summaries。您可以使用该算法计算到目前为止观察到的25％和75％分位数的运行估计值。然后，您可以将那些落在两个百分位之间的观察值输入到John D Cook文章中介绍的Welford算法中，以计算运行均值和方差。

- NPE

---

一个近似值就足够了，但我不知道如何进行“feeding”（你解释的最后一部分）。 - Alexandre Pereira Nunes

@AlexandrePereiraNunes：你要舍弃掉低于第25个百分位和高于第75个百分位的所有数据，然后计算其余部分的滑动平均值和标准差。 - NPE

我需要计算所有采样的第二和第三个季度，即如果我捕获了1000个样本，则需要计算250到750之间所有样本的平均值和stddev。我无法存储足够的样本（假设1000可能最终变成1e32）以便在第二次通过中进行计算。我理解您所建议的是，我最终会计算大多数样本的中间50％，甚至包括整个集合开头和结尾的样本，而这些是我想要忽略的样本。不确定我是否表达清楚，也不确定我是否理解您的意思。 - Alexandre Pereira Nunes

@AlexandrePereiraNunes: 正如我所说的，这只是一个近似值。如果您需要确切的答案，就需要存储整个集合。为此，您可以利用数据仅包含65,536个不同值的事实，并计算您已经看到了多少个每个值，类似于计数排序（http://en.wikipedia.org/wiki/Counting_sort）。 - NPE

我认为一个近似值就足够了，只是我没有理解你的意思：你是建议我在我的兴趣领域中取等量的百分位数，并计算它们的（估计）平均值和标准差吗？如果是这样，那么谢谢你，因为我想这应该足够了，至少只要我能控制误差，就像你指出的那篇论文所建议的那样。 - Alexandre Pereira Nunes

另外，感谢您提到计数排序。我曾经想到过这个想法，但我认为它不值得考虑。有趣的事实是，在同一项目的未来应用中，我也需要完整的直方图，而这个解决方案一次性解决了所有问题。 - Alexandre Pereira Nunes