应用HyperLogLog算法对人口样本进行估计

Question

HyperLogLog 算法是 Flajolet 等人提出的一种巧妙的方法，只需使用极少的内存即可估计集合的基数。然而它需要考虑原始集合中的所有 N 个元素进行计算。如果我们只有原始 N 元素的一小部分随机样本（比如说只有 10%），那该怎么办呢？是否有关于如何将 HyperLogLog 或类似算法应用于这种情况的研究？我知道这本质上就是“不同值估计”问题，对此已经有丰富的研究（例如，请参阅这篇论文）。但是，我所知道的关于不同值估计的研究都使用了许多与 HyperLogLog 方法非常不同的临时估计器。因此，我想知道是否已经有人想到了将 HyperLogLog 应用于不同值估计问题。

- Jon Smark

---

我认为将此发布在stats.stackexchange.com上会更好。 - Lior Kogan

Answer 1

然而，我所知道的关于独特值估计的研究使用了许多与HyperLogLog方法非常不同的临时估计器。

是的，因为他们在解决非常不同的问题。

假设你刚刚没收了一批100万张假美元，并且你想知道有多少个不同的序列号。

采样其中的10万张（使用HyperLogLog，因为你的老式蒸汽驱动计数机只有1k内存），你会发现5000个不同的序列号，每个序列号大约出现20次。那么你可以相当确定整批货物只包含略多于5000个不同的序列号。

现在假设一个序列号出现了95001次，还有4999个序列号仅出现一次。显然，一些真正的银行票据进入了你的库存。现在你可以相当有信心地说这批货物中包含大约5%的诚实银行票据，因此整批货物包含大约50,000个不同的序列号。

请注意，您样本中频率的分布用于推断整个集合中分布的某些内容。这实际上是您引用的“基于采样估计不同值数量(..)”second paper中提到的“特设”（您的话）方法之一：

参数估计器的想法是将概率分布拟合到 不同属性值的观察相对频率。

还要注意，HyperLogLog和类似方法的结果完全不受样本在其值上的分布影响。但是，您的最终估计显然非常依赖于它！

我的建议：使用您选择的方法（如HyperLogLog）计算样本中不同值的数量，然后使用“基于采样估计”中的方法之一来估计整个多重集合中的值数，或者使用有关多重集合分布的先前知识来计算估计值（也许您看到了伪造者的印刷机，并且您知道它只能印刷一个序列号）。

- Hans Lub

Answer 2

引用搜索是一件很棒的事情。我对所提出的两个问题不是非常熟悉，所以这篇论文可能不完全符合您的意思。但至少他们确实谈到了HyperLogLog及其与该问题的关系，也许能满足您的好奇心。 “一个最优算法用于不同元素问题”

- FoolishSeth

---

我对那篇论文很熟悉。我可能有所遗漏（只是粗略地浏览了一下），但论文中描述的算法似乎属于流式估计器类别，这些估计器是基于整个总体而不仅仅是样本来提供估计值的（这正是我的问题所在）。 - Jon Smark