Reservoir Sampling 蓄水池采样算法

2023-07-20 20:58:59 浏览数 (1)

长数据流的随机采样可以使用蓄水池采样算法，本文记录相关内容。

简介

问题描述：给定一串很长的数据流，对该数据流中数据只能访问一次，使得数据流中所有数据被选中的概率相等。

解决类似这样的问题，就可以利用 蓄水池算法(Reservoir Sampling)。

基本原理

假设需要采样的数量为 k 。

  1. 首先构建一个 k 个元素的数组，将序列的前 k 个元素放入数组中。
  2. 对于从第 j 个元素 (j>k)$``$frac{k}{j} 的概率来决定该元素是否被替换到数组中，数组中的 k 个元素被替换的概率是相同的。
  3. 当遍历完所有元素之后，数组中剩下的元素即为采样样本

证明

假设我们真的按照 frac{k}{j} 的概率来决定该元素是否被替换到数组中，有如下结论：

  1. 第 i 个元素被选中替换的概率 即:
frac{k}{k 1} times frac{1}{k}=frac{1}{k 1}

那么，第 第 k 1 个元素不被替换的概率

p_i = 1times frac{k}{k 1} times frac{k 1}{k 2} times frac{k 2}{k 3} ldots times frac{n-1}{n}=frac{k}{n}
  1. 不被替换的概率，即:
p_j= frac{k}{j} times frac{j}{j 1} times frac{j 1}{j 2} ldots times frac{n-1}{n}=frac{k}{n}
  1. 因此对于每个元素，被保留的概率都是 frac{k}{n}

应用示例

考虑长度为 n 的数组，设定目标 t ，要求便利数组过程中挑出和 t 值相等的数字的下标，使得每个等于 t 的值被选中的概率相等。

应用

遍历长度为n的数组。当第 i 次遇到 t 的元素时，随机选择区间 [0, i) 内的一个整数，如果其等于0，则将返回值置为该元素的下标，否则返回值不变(也就是判定是否触发了 frac{1}{i} 的概率)

证明

设数组中有 k 个值为 t 的元素，该算法会保证这 k 个元素的下标最终返回值概率均为 1/k ，证明：

第i次遇到值为target的元素下标成为最终返回值的概率 = 第i次随机选择的值=0的概率 x 第 i 1 次随机选择的值!=0的概率x … x 第k次随机选择的值!=0的概率

p_i= frac{1}{i} timesleft(1-frac{1}{i 1}right) times ldots timesleft(1-frac{1}{k}right)=frac{1}{i} times frac{i}{i 1} times ldots times frac{k-1}{k}=frac{1}{k}

参考资料

  • https://zhuanlan.zhihu.com/p/505922792?utm_id=0

文章链接： https://cloud.tencent.com/developer/article/2303820

sampling 遍历 数据 数组 算法

0 人点赞