Reservoir Sampling 蓄水池采样算法

为为为什么

发布于 2023-07-20 20:58:59

3440

发布于 2023-07-20 20:58:59

文章被收录于专栏：又见苍岚又见苍岚

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

简介

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

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

基本原理

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

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

证明

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

第 i 个元素被选中替换的概率即:

\frac{k}{k+1} \times \frac{1}{k}=\frac{1}{k+1}

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

p_i = 1\times \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}

不被替换的概率，即:

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}

因此对于每个元素，被保留的概率都是 \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} \times\left(1-\frac{1}{i+1}\right) \times \ldots \times\left(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

文章链接： /developer/article/2303820

本文参与?腾讯云自媒体分享计划，分享自作者个人站点/博客。

原始发表：2023年7月14日，如有侵权请联系 cloudcommunity@tencent.com 删除

sampling

本文分享自作者个人站点/博客?前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与?腾讯云自媒体分享计划? ，欢迎热爱写作的你一起参与！

登录后参与评论

0 条评论

热度