algorithm - "On-line"(迭代器)估计统计中位数、众数、偏度、峰度的算法？

Question

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

我想计算基本统计数据:

• 平均值:算术平均值
• 方差:与均值的平方偏差的平均值
• 标准差:方差的平方根
• 中位数:将较大一半数字与较小一半数字分开的值
• mode:在集合中找到的最频繁的值
• 偏度:tl；博士
• 峰度:tl；博士

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

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

数据未排序。它是由其他进程随机、即时生成的。每组的大小是高度可变的，并且大小不会事先知道。

我已经想出如何很好地处理均值和方差，以任意顺序遍历集合中的每个值。 (实际上，在我的例子中，我按照它们的生成顺序来处理它们。)这是我正在使用的算法，礼貌 http://en.wikipedia.org/wiki/Algorithms_for_calculating_variance#On-line_algorithm :

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

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

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

如果该库具有“在线”计算这些操作中的一个或多个的函数，那么向我指出现有的统计库也会有所帮助。

Answer 1

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

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

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

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

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

更新 (2011-09-19)

我刚刚修改了增量中值估计器来估计任意分位数。一般来说，quantile function告诉您将数据分成两个部分的值: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，A Perceptron-Like Online Algorithm for Tracking the Median .这是一个postscript version来自作者的网站。