最快的近似计数算法

Question

什么是获得输入文件或std out数据流的大致行数的最快方法.仅供参考,这是一个概率算法,我在网上找不到很多例子.

数据可能只是来自csv文件的awk脚本的一列或两列!让我们说我想在其中一个列上使用aprox groupby.我会使用数据库组,但行数超过6-7亿.我希望第一个近似结果在3到4秒内.然后在对先前做出决定之后运行贝叶斯或其他东西.关于一个非常粗略的初始组计数的任何想法？

如果你可以在python或java中提供算法示例,那将非常有帮助.

Answer 1

@Ben Allison的答案是一个很好的方法,如果你想计算总线数.既然你提到了贝叶斯和之前,我将在这个方向上添加一个答案来计算不同组的百分比.(请参阅我对你的问题的评论.我想如果你对总数有所了解,如果你想做一个groupby,估计不同群体的百分比更有意义).

递归贝叶斯更新:

我将首先假设您只有两个组(可以使扩展可以使其适用于多个组,请参阅后面的解释.),group1和group2.

对于您处理m group1的第一n行(行)中的s ,我们将该事件表示为M(m,n).显然你会看到n-m group2s因为我们认为他们是唯一两个可能的群体.因此,您知道M(m,n)给定百分比group1(s)的事件的条件概率,由具有n试验的二项分布给出.我们试图以s贝叶斯的方式估计.

二项式的共轭前缀是β分布.所以为简单起见,我们选择Beta(1,1)先验(当然,你可以在这里选择你自己的参数alpha和beta),这是(0,1)上的均匀分布.因此,对于这个beta发行版,alpha=1和beta=1.

二项式+ beta先验的递归更新公式如下:

if group == 'group1':
    alpha = alpha + 1
else:
    beta = beta + 1

后面s实际上也是一个beta分布:

                s^(m+alpha-1) (1-s)^(n-m+beta-1)
p(s| M(m,n)) = ----------------------------------- = Beta (m+alpha, n-m+beta)
                      B(m+alpha, n-m+beta)

其中B是β函数.要报告估算结果,您可以依赖Beta分布的均值和方差,其中:

mean = alpha/(alpha+beta)
var = alpha*beta/((alpha+beta)**2 * (alpha+beta+1))

python代码: groupby.py

所以几行python来处理你的数据stdin并估计百分比group1将如下所示:

import sys

alpha = 1.
beta = 1.

for line in sys.stdin:
    data = line.strip()
    if data == 'group1':
        alpha += 1.
    elif data == 'group2':
        beta += 1.
    else:
        continue

    mean = alpha/(alpha+beta)
    var = alpha*beta/((alpha+beta)**2 * (alpha+beta+1))
    print 'mean = %.3f, var = %.3f' % (mean, var)

样本数据

我向代码提供了几行数据:

group1
group1
group1
group1
group2
group2
group2
group1
group1
group1
group2
group1
group1
group1
group2  

近似估计结果

以下是我得到的结果:

mean = 0.667, var = 0.056
mean = 0.750, var = 0.037
mean = 0.800, var = 0.027
mean = 0.833, var = 0.020
mean = 0.714, var = 0.026
mean = 0.625, var = 0.026
mean = 0.556, var = 0.025
mean = 0.600, var = 0.022
mean = 0.636, var = 0.019
mean = 0.667, var = 0.017
mean = 0.615, var = 0.017
mean = 0.643, var = 0.015
mean = 0.667, var = 0.014
mean = 0.688, var = 0.013
mean = 0.647, var = 0.013

结果表明,在第15行处理之前,group1估计有64.7%的百分比(基于之前的beta(1,1)).你可能会注意到方差不断缩小,因为我们有越来越多的观察点.

多个组

现在,如果你有两个以上的组,只需将下划线分布从二项式更改为多项式,然后相应的共轭先验将是Dirichlet.其他一切你只是做出类似的改变.

进一步说明

你说你想在3-4秒内估计一下.在这种情况下,您只需对数据的一部分进行采样并将输出提供给上述脚本,例如,

head -n100000 YOURDATA.txt | python groupby.py

而已.希望能帮助到你.