用于估计统计中位数、众数、偏度、峰度的“在线”（迭代器）算法？

是否有一种算法可以估计一组值的中值、众数、偏度和/或峰度，但不需要立即将所有值存储在内存中？

我想计算一下基本统计数据：

• 平均数：算术平均数
• 方差：与平均值的平方偏差的平均值
• 标准差：方差的平方根
• 中位数：将较大的一半数字与较小的一半数字分开的值
• 众数：集合中出现次数最多的值
• 偏度：tl；博士
• 峰度：tl；博士

计算这些的基本公式是小学算术，我确实知道它们。还有许多统计库也实现了它们。

我的问题是我正在处理的集合中存在大量（数十亿）值：在Python中工作，我不能只创建包含数十亿个元素的列表或散列。即使我用 C 语言编写，十亿个元素的数组也不太实用。

数据未排序。它是由其他过程随机、即时生成的。每组的大小变化很大，并且无法提前知道大小。

我已经弄清楚如何很好地处理均值和方差，以任何顺序迭代集合中的每个值。 （实际上，就我而言，我按照它们生成的顺序获取它们。）这是我正在使用的算法，礼貌http://en.wikipedia.org/wiki/Algorithms_for_calculate_variance#On-line_algorithm:

• 初始化三个变量：count、sum 和 sum_of_squares
• For each value:
  • 增量计数。
  • 将值添加到总和中。
  • 将值的平方添加到 sum_of_squares。
• 将总和除以计数，存储为变量平均值。
• 将 sum_of_squares 除以计数，存储为变量mean_of_squares。
• 均方，存储为 square_of_mean。
• 从mean_of_squares中减去square_of_mean，存储为方差。
• 输出均值和方差。

这种“在线”算法有弱点（例如，精度问题，因为 sum_of_squares 很快变得大于整数范围或浮点精度），但它基本上给了我我需要的东西，而不必存储每个集合中的每个值。

但我不知道是否存在类似的技术来估计附加统计数据（中位数、众数、偏度、峰度）。只要处理 N 个值所需的内存远小于 O(N)，我就可以接受有偏差的估计器，甚至是在一定程度上损害准确性的方法。

如果该库具有“在线”计算其中一项或多项操作的功能，那么向我指出现有的统计库也会有所帮助。

我使用这些增量/递归均值和中值估计器，它们都使用常量存储：

mean += eta * (sample - mean)
median += eta * sgn(sample - median)

where eta是一个小的学习率参数（例如 0.001），并且sgn() 是返回 {-1, 0, 1} 之一的符号函数。 （使用常数eta如果数据不稳定并且您想要跟踪随时间的变化；否则，对于固定源，您可以使用类似的东西eta=1/n 对于均值估计器，其中 n 是迄今为止看到的样本数...不幸的是，这似乎不适用于中值估计器。）

这种类型的增量均值估计器似乎到处都在使用，例如在无监督的神经网络学习规则中，但中值版本似乎不太常见，尽管它有好处（对异常值的鲁棒性）。在许多应用中，中值版本似乎可以用作均值估计器的替代品。

我很想看到类似形式的增量模式估计器......

更新 (2011-09-19)

我刚刚修改了增量中值估计器来估计任意分位数。一般来说，一个分位数函数告诉您将数据分为两个分数的值：p 和 1-p。以下逐步估计该值：

quantile += eta * (sgn(sample - quantile) + 2.0 * p - 1.0)

p 值应在 [0,1] 范围内。这本质上改变了sgn() 函数的对称输出 {-1,0,1} 偏向一侧，将数据样本划分为两个大小不等的箱（数据的分数 p 和 1-p 分别小于/大于分位数估计值） ）。请注意，对于 p=0.5，这会减少到中值估计量。

更新 (2021-11-19)

有关此处描述的中值估计量的更多详细信息，我想重点介绍以下评论中链接的这篇论文：Bylander & Rosen，1997，用于跟踪中位数的类似感知器的在线算法。这里有一个后记版本来自作者的网站。