整体说明
- 蓄水池采样 (Reservoir Sampling) 算法是一种在数据流中进行随机抽样的方法
- 它的独特之处在于，不知道数据流的总长度 ，但可以实现对样本等概率采样
- 场景：处理一个无法放入内存的巨大文件，或者一个实时传入的无限数据流
- 在这种情况下，需要从这个流中随机选择 \(k\) 个元素，并且要确保每个元素被选中的概率是相等的
算法流程
- 蓄水池采样算法的核心思想是，随着数据流的不断输入，动态地更新一个大小为 \(k\) 的“蓄水池”
- 以下是该算法的详细流程：
- 第一步：初始化蓄水池
- 创建一个大小为 \(k\) 的数组或列表，这就是我们的蓄水池 (Reservoir)
- 1）从数据流中读取前 \(k\) 个元素
- 2）将这 \(k\) 个元素直接放入蓄水池中
- 创建一个大小为 \(k\) 的数组或列表，这就是我们的蓄水池 (Reservoir)
- 第二步：处理后续元素
- 从数据流中继续读取第 \(i\) 个元素，其中 \(i > k\)。对于每一个新元素，执行以下操作：
- 1）生成一个 \(1\) 到 \(i\) 之间的随机整数 \(j\)
- 2）如果 \(j\) 满足条件 \(1 \le j \le k\)，则将当前元素替换蓄水池中索引为 \(j\) 的元素
- 3）如果 \(j > k\)，则不做任何操作，直接丢弃该元素
- 从数据流中继续读取第 \(i\) 个元素，其中 \(i > k\)。对于每一个新元素，执行以下操作：
- 第三步：重复
- 1）重复第二步，直到数据流结束
- 2）当数据流处理完毕后，蓄水池中剩下的 \(k\) 个元素就是我们最终的随机样本
算法证明
- 蓄水池采样算法之所以有效，是因为它能确保数据流中的每个元素被选入蓄水池的概率都是 \(k/N\) ，其中 \(N\) 是数据流的总长度。我们通过数学归纳法来简单理解一下
- 初始阶段 ：前 \(k\) 个元素被直接放入蓄水池，因此它们被选中的概率是 \(1\)
- 第 \(i\) 个元素 (\(i > k\)):
- 第 \(i\) 个元素被选中的概率是 \(k/i\)。这是因为我们生成了一个 \(1\) 到 \(i\) 的随机数，只有当它落在前 \(k\) 个位置时，第 \(i\) 个元素才会被选中并替换掉蓄水池中的一个元素
- 关键是保持之前元素的概率不变。我们来看一下，在第 \(i\) 步，蓄水池中某个旧元素被保留的概率
- 在第 \(i-1\) 步结束时，蓄水池中的每个元素被选中的概率是 \(k/(i-1)\)
- 当第 \(i\) 个元素进入时，这个旧元素被替换的概率是 \(1/i\)（因为它有 \(1/i\) 的概率被选中并替换掉蓄水池中的一个随机位置）
- 所以，一个旧元素被保留的概率是 \(1 - 1/i = (i-1)/i\)
- 那么，这个旧元素在第 \(i\) 步结束后仍然留在蓄水池中的概率是：
$$P(\text{留在蓄水池}) = P(\text{在第 }i-1 \text{ 步被选中}) \times P(\text{在第 }i \text{ 步被保留}) = \frac{k}{i-1} \times \frac{i-1}{i} = \frac{k}{i}$$
- 通过这个过程，我们可以看到，在处理完第 \(i\) 个元素后，所有 \(i\) 个元素（包括新来的和之前的）被选中的概率都精确地保持在 \(k/i\)。当数据流结束时，假设总长度为 \(N\)，则每个元素被选中的概率都是 \(k/N\)