是否有算法来估计值集的中值,模式,偏度和/或峰度,但这不需要一次将所有值存储在内存中？
我想计算基本的统计数据:
平均值:算术平均值
方差:平均偏差的平均值
标准差:方差的平方根
中位数:将较大一半的数字与较小的一半分开的值
mode:在集合中找到最频繁的值
偏斜:tl; 博士
峰度:tl; 博士
计算任何这些的基本公式是小学算术,我知道它们.还有许多统计库可以实现它们.
我的问题是我正在处理的集合中的大量(数十亿)值:在Python中工作,我不能只使用数十亿个元素创建列表或哈希.即使我用C语言编写,十亿元素数组也不太实用.
数据未排序.它是由其他过程随机,即时生成的.每组的大小变化很大,并且不会提前知道大小.
我已经弄清楚如何很好地处理均值和方差,以任何顺序迭代集合中的每个值.(实际上,在我的情况下,我按照它们生成的顺序来看它们.)这是我正在使用的算法,礼貌http://en.wikipedia.org/wiki/Algorithms_for_calculating_variance#On-line_algorithm:
初始化三个变量:count,sum和sum_of_squares
对于每个值:
增量计数.
将值添加到sum.
将值的平方添加到sum_of_squares.
按计数除以总和,作为变量均值存储.
将sum_of_squares除以count,存储为变量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)
其中eta是一个小的学习速率参数(例如0.001),而sgn()是signum函数,它返回{-1,0,1}中的一个.(如果数据是非平稳的并且您想跟踪随时间的变化,则使用常数eta ;否则,对于静止源,您可以使用类似eta = 1/n的值作为平均估计量,其中n是所见的样本数远......不幸的是,这似乎不适用于中位数估算器.)
这种类型的增量平均估计似乎在所有地方都被使用,例如在无监督的神经网络学习规则中,但中位数似乎不太常见,尽管其有益(对异常值的鲁棒性).似乎在许多应用中,中值版本可以用作平均估计量的替代.
我很想看到类似形式的增量模式估算器......
UPDATE
我刚刚修改了增量中值估计量来估计任意分位数.通常,分位数函数(http://en.wikipedia.org/wiki/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,这会降低到中值估计量.
偏斜和Kurtosis
对于Skewness和Kurtosis的在线算法(沿着方差线),请在同一个wiki页面中查看更高时刻统计的并行算法.
中位数
没有分类数据,中位数很难.如果你知道,你有多少数据点,理论上你只需要部分排序,例如使用选择算法.然而,这对数十亿的价值观没有多大帮助.我建议使用频率计数,请参阅下一节.
具有频率计数的中位数和模式
如果它是整数,我会计算 频率,可能会切断超出某个值的最高值和最低值,我确信它不再相关.对于浮点数(或者整数太多),我可能会创建存储桶/间隔,然后使用与整数相同的方法.(近似)模式和中值计算比根据频率表变得容易.
常规分布随机变量
如果它是正态分布的,我会使用总体样本均值,方差,偏度和峰度作为小子集的最大似然估计.用于计算这些的(在线)算法,你现在已经.例如,读取数十万或数百万个数据点,直到您的估计误差变得足够小.只需确保从您的集合中随机选择(例如,您不会通过选择前100'000值来引入偏差).相同的方法也可以用于估计正常情况的模式和中值(对于样本均值是估计量).
进一步评论
上述所有算法都可以并行运行(包括许多排序和选择算法,例如QuickSort和QuickSelect),如果这有帮助的话.
我一直假设(除了关于正态分布的部分)我们讨论样本矩,中位数和模式,而不是给定已知分布的理论矩的估计.
一般来说,对数据进行采样(即仅查看子集)应该非常成功,只要所有观察都是相同随机变量(具有相同的分布)以及时刻,模式和这个分布实际存在中位数.最后一个警告并非无害.例如,不存在Cauchy分布的均值(和所有更高的矩).在这种情况下,"小"子集的样本平均值可能与整个样本的样本平均值大量偏离.
我在一个名为LiveStats的简洁Python模块中实现了P-Square算法,用于动态计算分位数和直方图而无需存储观察.它应该非常有效地解决你的问题.除了模式之外,该库支持您提到的每个统计信息.我还没有找到一个令人满意的模式估计解决方案.
瑞恩,我担心你没有做出正确和差异的权利......这几周前就出现了.而在线版本的一个优点(实际上是韦尔福德方法的名称)是它特别准确和稳定的事实,请参阅此处的讨论.其中一个优点是你不需要存储总和或总和的总和......
我想不出任何模式和中位数的在线方法,这似乎需要立即考虑整个列表.但是,与方差和均值相似的方法很可能也适用于偏度和峰度......
京公网安备 11010802040832号 | 京ICP备19059560号-6 
