logo标签列表

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

algorithmstatisticsiteratormedian
88

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

我想计算基本统计量：

  • 平均值: 算术平均值
  • 方差: 平均偏差的平方
  • 标准差: 方差的平方根
  • 中位数: 将数字中较大的一半与较小的一半分开的值
  • 众数: 集合中出现最频繁的值
  • 偏度: tl; dr
  • 峰度: tl; dr

计算任何一个这些基本统计量的公式都很简单，并且我知道它们。许多统计库也实现了它们。

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

数据没有排序。它是由其他进程随机生成的。每个集合的大小高度可变，并且大小不会事先知道。

我已经发现如何很好地处理平均值和方差，可以按任意顺序迭代每个集合中的值。（实际上，在我的情况下，我按它们生成的顺序来取）这是我正在使用的算法，由http://en.wikipedia.org/wiki/Algorithms_for_calculating_variance#On-line_algorithm提供：

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

    • 这种"在线"算法存在缺陷（例如，当sum_of_squares快速增长到超过整数范围或浮点精度时会出现精度问题），但它基本上可以给我需要的东西，而不必存储每个集合中的每个值。

    但我不知道是否存在类似的技术来估计其他统计信息（中位数、众数、偏度、峰度）。我可以接受有偏估算器，甚至是在一定程度上牺牲准确性的方法，只要处理N个值所需的内存远远小于O（N）。

    如果该库具有用于“在线”计算一个或多个这些操作的函数，则指向现有的统计库也将有所帮助。

    数据是否会按顺序传递，而且您是否提前知道输入数量？ - chillysapien
    Stephan：有些数据集是整数，有些是浮点数。人口分布非常接近正态（高斯）分布，因此我们可以建立置信区间，但没有硬性的范围边界（除了在某些情况下 x > 0）。 - Ryan B. Lynch
    @Ryan B. Lynch：啊，你的文本描述了朴素的单遍方差算法，所以我认为你不知道Welform的方法。而且我也无法帮助你解决其他问题。抱歉。 - dmckee --- ex-moderator kitten
    这些被称为流算法，顺便说一下 [http://scholar.google.com/scholar?&q=streaming+algorithm]。其中一些很容易，一些可以在任意ε内进行逼近（高概率），而有些则难以逼近。 - ShreevatsaR
    关于您对库的请求，我有一个Julia包可以解决这些问题：https://github.com/joshday/OnlineStats.jl。OnlineStats实现了用于均值、方差、偏度/峰度、直方图（从中可以估计分位数）和几种分位数近似算法的在线算法。 - joshday
    显示剩余5条评论
    14个回答
    0

    我会倾向于使用桶，这些桶可以是自适应的。桶大小应该是你需要的精度。然后，每当一个数据点进来时，你就将其加入到相应的桶计数中。

    这些将为您提供简单的中位数和峰度近似值，通过对每个桶进行计数，并将其值乘以其计数。

    唯一的问题可能是浮点数失去分辨率，经过数十亿次操作后，即使加1也不再改变其值！要解决这个问题，如果最大的桶大小超过了某个限制，您可以从所有计数中减去大量数字。

    0

    中位数和众数无法仅使用可用的恒定空间进行在线计算。然而，由于中位数和众数比“数量化”更具有“描述性”，因此可以通过对数据集进行抽样来估计它们。

    如果数据在长期内服从正态分布，则可以使用平均值来估计中位数。

    您还可以使用以下技术估计中位数：为数据流中的每个1,000,000个条目建立一个中位数估计M[i]，使得M[0]是前一百万个条目的中位数，M[1]是第二个一百万个条目的中位数等等。然后使用M[0]...M[k]的中位数作为中位数估计器。这当然可以节省空间，并且您可以通过“调整”参数1,000,000来控制要使用多少空间。这也可以递归地推广。

    -1
    for j in range (1,M):
    y=np.zeros(M) # build the vector y
    y[0]=y0

    #generate the white noise
    eps=npr.randn(M-1)*np.sqrt(var)

    #increment the y vector
    for k in range(1,T):
        y[k]=corr*y[k-1]+eps[k-1]

    yy[j]=y

list.append(y)
    1
    可以提供一些解释，以更好地将其与原问题联系起来。 - Erica
    网页内容由stack overflow 提供, 点击上面的
    可以查看英文原文，
    原文链接