5

获取输入文件或标准输出数据流的行数的近似计数的最快方法是什么。仅供参考，这是一个概率算法，我在网上找不到很多例子。

数据可能只是来自 csv 文件的 awk 脚本的一列或两列！可以说我想在其中一列上有一个 aprox groupby。我会使用数据库组，但行数超过 6-70 亿。我希望在 3 到 4 秒内获得第一个近似结果。然后在事先做出决定之后运行贝叶斯或其他东西。关于真正粗略的初始组数的任何想法？

如果您可以在 python 或 java 中提供算法示例，那将非常有帮助。

4

2 回答 2

5

如果您想计算总行数，@Ben Allison 的回答是一个好方法。既然你提到了贝叶斯和之前的，我会在那个方向添加一个答案来计算不同组的百分比。（请参阅我对您的问题的评论。我想如果您对总数有所了解，并且如果您想做一个groupby，估计不同组的百分比更有意义）。

递归贝叶斯更新：

我将首先假设您只有两个组（可以进行扩展以使其适用于多个组，请参阅后面的解释。），group1和group2.

对于您处理m group1的第一n行（行）中的 s，我们将事件表示为M(m,n)。显然你会看到n-m group2s 因为我们假设它们是仅有的两个可能的组。所以你知道给定( )M(m,n)百分比的事件的条件概率是由试验的二项分布给出的。我们试图以贝叶斯的方式进行估计。group1sns

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

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

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

的后验s其实也是一个贝塔分布：

                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)

beta 函数B在哪里。要报告估计结果，您可以依赖分布的均值和方差，其中：Beta

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

蟒蛇代码：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

结果显示 group1 估计有 64.7% 到第 15 行处理（基于我们之前的 beta(1,1)）。您可能会注意到方差不断缩小，因为我们有越来越多的观察点。

多组

现在，如果您有超过 2 个组，只需将下划线分布从二项式更改为多项式，然后相应的共轭先验将是 Dirichlet。其他一切你只需做类似的改变。

补充说明

您说您希望在 3-4 秒内进行粗略估计。在这种情况下，您只需对一部分数据进行采样并将输出提供给上述脚本，例如，

head -n100000 YOURDATA.txt | python groupby.py

就是这样。希望能帮助到你。

于 2012-11-26T23:34:37.183 回答
3

如果假设数据是 IID 是合理的（因此没有偏差，例如某些类型的记录出现在流的某些部分），那么只需进行二次抽样并按近似大小扩大计数。

假设前一百万条记录（这应该可以在几秒钟内处理）。它的大小是x个单位（MB、字符，无论你关心什么）。完整流的大小为y，其中y >> x。现在，从样本x中获取您关心的任何内容的计数，并简单地按因子y /*x* 对它们进行缩放以获得近似的完整计数。一个例子：您想大致了解在整个流中有多少条记录的第 1 列的值为v 。前一百万条记录的文件大小为 100MB，而总文件大小为 10GB。在前 100 万条记录中，有 150,000 条记录的价值为v对于第 1 列。因此，您假设在完整的 10GB 记录中，您将看到 150,000 * (10,000,000,000 / 100,000,000) = 15,000,000 具有该值。您对样本计算的任何统计数据都可以简单地按相同的因子进行缩放以产生估计值。

如果数据存在偏差，使得某些记录或多或少可能位于文件的某些位置，那么您应该从总集中随机（或均匀间隔）选择样本记录。这将确保一个公正的、有代表性的样本，但可能会产生更大的 I/O 开销。

于 2012-11-26T10:16:14.067 回答