最快的近似计数算法

Question

如何快速获取输入文件或标准输出数据流的行数近似计数？请注意，这是一种概率算法，网上很难找到许多示例。

数据可能只是来自 awk 脚本或 csv 文件中的一列或两列！假设我想对其中一列进行近似分组。我会使用数据库 group by，但行数超过 60-70 亿。我希望在 3 到 4 秒内获得第一个近似结果。然后，在进行先验决策之后运行贝叶斯或其他算法。有没有关于初始分组计数的粗略想法？

如果您可以提供 Python 或 Java 中的算法示例，那将非常有帮助。

- Horse Voice

---

你知道平均行长吗？如果知道，就将文件大小除以它。如果不知道，可以查看文件的前k行并从中估算出平均行长。 - j_random_hacker

是的，我会有apx行大小。但这将取决于数据流。它可能只是来自awk脚本或csv文件的一列或两列！这更或多或少类似于SQL中的近似分组。不关心数据的精确计数。只需要一个近似值。有什么想法吗？ - Horse Voice

你的第一段需要大概总行数的计数。你的第二段需要按组分组结果的大约计数。我认为这两个是不同的。@Ben Allison的答案适用于你的第一段，不需要任何训练。如果你有良好的特征提取，amit的答案应该能够更好地解决你的第二段问题。此外，在分组情况下，如果你有总计数，获取不同值的近似百分比会更有意义。 - greeness

Answer 1

@Ben Allison的回答是计算总行数的好方法。既然你提到了贝叶斯和先验，我将添加一个方向的答案来计算不同组的百分比。（请参见您问题上的评论。我猜如果您已经知道总数并且想要进行groupby，那么估计不同组的百分比更有意义）。

递归贝叶斯更新：

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

对于您处理的前n行中的m个group1，我们将该事件表示为M(m,n)。显然，您将看到n-m个group2，因为我们假设它们是唯一可能的两个组。因此，您知道在给定group1（s）的百分比的条件下，事件M(m,n)的条件概率由具有n次试验的二项分布给出。我们正在以贝叶斯方式估计s。

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

二项式分布 + 贝塔先验的递归更新公式如下：

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

< p > s的后验分布实际上也是一个贝塔分布：< /p >

                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函数。为了报告估计结果，您可以依靠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

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

多组情况下，如果您有超过2个组，请将下划线分布从二项式分布更改为多项式分布，然后相应的共轭先验将是Dirichlet分布。其他所有内容都需要进行类似的更改。

进一步的说明：您说您希望在3-4秒钟内得到近似估计。在这种情况下，您只需对数据的一部分进行采样，并将输出馈送到上述脚本中，例如：

head -n100000 YOURDATA.txt | python groupby.py

就是这样。希望有所帮助。

- greeness

---

请注意，这正是我建议的内容，并加上了先前的内容。除非您的先验方差很小（即alpha + beta与样本大小的数量级相同），否则后验均值和ML估计（我所建议的）在大多数实际情况下将是相同的。我不清楚贝叶斯方法在这里的优势是什么（这就是为什么我没有回答问题的那部分的原因 :)) - Ben Allison

同意。如果OP使用适当的先验或/和仅对其数据进行少量采样，则可能能够利用贝叶斯方法。否则，后验均值和最大似然估计几乎相同。 - greeness

Answer 2

如果可以合理地假设数据是独立同分布的（因此不存在偏差，如某些类型的记录出现在流的某些部分），那么只需对子样本进行抽样和计数，并通过近似大小来扩大计数。选择前一百万条记录（这应该可以在几秒钟内处理完）。它的大小为x个单位（MB、字符或任何你关心的东西）。完整的流大小为y，其中y>>x。现在，从你的样本x中派生出你所关心的计数，然后简单地按比例y/x缩放它们以获得近似的全局计数。例如：你想大致知道在完整流中有多少记录具有第1列的值v。前一百万条记录的文件大小为100MB，而总文件大小为10GB。在前一百万条记录中，有150,000条记录的第1列的值为v。因此，你假设在完整的100亿条记录中，你将看到150,000*(10,000,000,000/100,000,000)=15,000,000条记录具有该值。你计算的任何统计量都可以简单地按相同的因子缩放以产生一个估计值。

如果数据存在偏差，使得某些记录更或者不太可能出现在文件的某些位置上，那么你应该随机地（或均匀间隔地）从总集合中选择样本记录。这将确保一个无偏的、代表性的样本，但可能会产生更大的I/O开销。

- Ben Allison