问题标签 [reservoir-sampling]

为了从大小未定的数组中检索k个随机数，我们使用了一种称为水库采样的技术。任何人都可以通过示例代码简要说明它是如何发生的吗？

这篇 MSDN 文章证明了Reservoir Sampling 算法的正确性如下：

1. 基本情况是微不足道的。对于第 k+1 种情况，位置 <= k 的给定元素 i 在 R 中的概率为 s/k。

2. i 被替换的概率是第 k+1 个元素被选择的概率乘以 i 被选择被替换，即：s/(k+1) * 1/s = 1/(k+1)，并且概率 i没有被替换的是 k/k+1。

3. 所以任何给定元素在 k+1 轮后持续的概率是：（在 k 步中选择，而不是在 k 步中删除）= s/k * k/(k+1)，即 s/(k+1)。

4. 因此，当 k+1 = n 时，任何元素都以概率 s/n 出现。

关于第 3 步：

• k+1 rounds提到了什么？

• 是什么chosen in k steps, and not removed in k steps？

• 为什么我们只计算第一步R之后已经存在的元素的这个概率s？

最近有人问另一个问题：给定一个未知长度的列表，通过仅扫描一次来返回其中的随机项目

我知道你不应该，我只是无法对为什么不做出规范的解释。

看示例代码：

为每个项目生成一个新的随机数的适当水库采样的选择非常均匀地分布，因为它应该是：

而当您对所有项目重复使用相同的随机数时，您会得到一个偏向于非常低数字的分布：

这里的数学是什么？为什么不能重复使用相同的随机数？

我想了解水库采样算法，我们从给定的 S 元素集合中选择 k 个元素，使得 k <= S。

在 wiki 上给出的算法中：

如果我理解正确的话，我们首先从集合中选择 k 个元素，然后不断解析 S 的 i 个元素，生成 1 到 i 范围内的随机 no j 并将元素 j 替换为 S[i]。

如果要采样的集合 K 非常大，它看起来很好，但是如果我想从无限大小（至少未知大小）的链表中随机选择 1 个元素，我将如何使用这个算法来做...... ?

我非常熟悉使用 Reservoir Sampling 在单次遍历数据中从一组未确定的长度中进行采样。在我看来，这种方法的一个限制是，在返回任何结果之前，它仍然需要遍历整个数据集。从概念上讲，这是有道理的，因为必须允许整个序列中的项目有机会替换以前遇到的项目以实现统一的样本。

有没有办法在评估整个序列之前产生一些随机结果？我正在考虑一种适合 python 的伟大 itertools 库的惰性方法。也许这可以在某些给定的容错范围内完成？我将不胜感激有关此想法的任何反馈！

只是为了稍微澄清一下这个问题，这张图总结了我对不同采样技术的内存与流式权衡的理解。我想要的是属于Stream Sampling类别的东西，我们事先不知道人口的长度。

显然，不知道先验长度并仍然获得统一样本似乎是矛盾的，因为我们很可能会将样本偏向于总体的开始。有没有办法量化这种偏见？是否需要权衡取舍？有没有人有一个聪明的算法来解决这个问题？

我对 Reservoir Sampling 算法非常熟悉，我在想如果N给出总大小会怎样。在这种情况下我们能得到什么好处？结果，这是算法：

乍一看似乎是正确的，但我发现很难证明。任何人都可以帮助我以正式的方式证明这个算法吗？

我的数据挖掘课程有一个项目，我必须在其中编写文件的水库采样算法。该程序将数字 k、输入文件的名称和要创建的输出文件的名称作为输入。输出文件必须包含来自输​​入的 k 个随机行。我尝试了一些东西，但输出错误。

这是我使用的代码：

该程序试图做的是从文件中读取前 k 行并将其存储在 (k,256) 大小的二维字符串数组中。然后为下一行生成一个随机数 j，如果该数小于 k，则将 buffer[j] 替换为从文件中获取的最新行。

然而，我得到的输出由 k 行组成}，这是输入的最后一个字符。像这样（例如 k=5）：

当我打印缓冲区以查看其内容时，它显示正确。但是当我写入文件时，它会写入错误的输出。

任何帮助将不胜感激！先感谢您！

我需要实施加权水库采样。我参考了这篇博客中提到的论文。我想编写测试用例来对我的实现进行单元测试，并且对如何计算不同元素在水库中的预期概率感到困惑。

我认为它应该与 成比例，但这里(weight_of_element/weight_of_all_elements)提到的测试用例计算它的方式不同。我该怎么做？

我正在尝试使用 java 实现水库采样算法。我有 N 个大小未知的数据流（来自到达接收器节点的传感器的读数）。为了简单起见，假设我有一个未知大小的流。

因此，其中一种水库采样算法建议创建一个大小为reservoirSize 的水库。假设它是 5。您获得的前五个读数，将它们存储在您的水库中。好的。现在，随着您获得越来越多的读数，每次读数都会生成一个从 0 到读数的随机数，如果该随机数小于水库大小，则将读数存储在水库 [randomNumber] 中。

所以可以说我有reservoirSize = 5，我刚刚得到了我的第10个读数。我将生成一个从 0 到 10 的随机数，如果该数字小于 5，我会将读数存储在随机数指向的位置。假设随机数是 3，所以我将读数 10 存储在水库 [3] 中。

这段代码的问题是，一旦 streamIndex 变得足够大（例如高于 4.000），我很少对任何读数进行采样。这确实是有道理的，因为生成从 0 到 4000 小于 5 的随机数的概率明显小于生成从 0 到 100 的随机数的概率，即小于 5。

我还从 Vitters 论文中实现了 AlgorthmR，并在此处描述了另一种方式：
Gregable ReservoirSampling

但所有实现都有同样的问题。流越大，采样频率就越小。因此，对于 0.5 秒的采样率，在我开始采样一小时后（这意味着已将大约 7000 个读数转发到汇节点），再过半小时即不会检测到测量量的变化，即读数表示更改将从水库中丢弃。

算法实现

Gregable 实现

这是算法的正常行为还是我在这里遗漏了什么？如果这是正常行为，有没有办法让它更“准确”地工作？

为了明确以下是问题：

给定一个不确定长度的输入流，你如何返回该流的随机成员（每个成员的概率相等），因为你不允许存储超过恒定数量的输入，并且你只能通过输入一次

这个问题的解决方案似乎是 Reservoir Sampling，它在下面说明。“首先，你想创建一个包含 1,000 个元素的容器（数组），并用流中的前 1,000 个元素填充它。这样，如果你正好有 1,000 个元素，算法就可以工作。这是基本情况。

接下来，您要处理第 i 个元素（从 i = 1,001 开始），以便在处理该步骤结束时，您的水库中的 1,000 个元素在您迄今为止看到的 i 个元素中随机抽样。你怎么能做到这一点？从 i = 1,001 开始。在第 1001 步之后，元素 1,001（或与此相关的任何元素）应该在 1,000 个元素的集合中的概率是多少？答案很简单：1,000/1,001。”

我无法理解最后一句“答案很简单：1,000/1,001”。在 1001 个元素的数组中找到 1 个元素的概率不应该是 1/1001 而不是 1000/1001 吗？样本空间不等于 1001 且有利的结果数不等于 1 吗？