水库抽样算法
问题描述
输入：一组数据，大小未知
输出：这组数据的K个均匀抽取
要求：仅扫描一次
总体要求：从N个元素中随机的抽取k个元素，其中N无法确定，保证每个元素抽到的概率相同
解决方案
一些符号：k为要抽样的个数，N为总体个数位置，n为当前遍历的元素的位置。pool为k大小的数组，用来保存抽到的样本
n<=k，把当前值放入pool中，构成初步样本
n>k，生成一个随机数p，如果p<k/n，那么把pool中的任意一个数替换为第n个数。如果p>=k/n，继续保留前面的数。直到数据流结束，返回此k个数。但是为了保证计算机计算分数额准确性，一般是生成一个0到n的随机数，跟k相比，道理是一样的。
特殊情况：当k=1时，从n(n>=2)开始以1/n的概率决定是否保留替换原来pool中元素
证明—归纳法
假设:当第n个元素以k/n，前n-1个元素也被选中的概率也为k/n
证明：
1）当n<=k时，出现在pool中的每个元素概率都是相同的，都为1
2）当n=k+1时,计算前k个元素在pool的概率
==a==.前k个元素在pool中的元素概率都为1
==b==.由假设得，第k+1个元素被选中的概率为：k/(k+1)，pool任意元素被替换的概率为(k/(k+1))*(1/k)=1/(k+1)，没被替换(即选中)的概率为1-1/(k+1)=k/(k+1).
由a*b=1*k/(k+1)=k/(k+1),前k个元素和k+1元素被选中的概率都为k/k+1。
3）当n>k+1时，计算前n-1个元素在pool的概率
==a==.前n-1个元素在pool中被选择的的概率为k/(n-1)
==b==.由假设得,第n个元素被选中的概率为：k/n，pool任意元素被替换的概率为(k/n)*(1/k)=1/n，没被替换(即选中)的概率为1-1/n=(n-1/)n。
由a*b=(k/(n-1))*((n-1)/n)=k/n,前k个元素和k+1元素被选中的概率都为k/n。
因为假设成立，所以到数据结束时，所有元素的抽到的概率都为k/N
原文链接 https://blog.csdn.net/u012397189/article/details/52181005
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
文章由极客之音整理，本文链接：https://www.bmabk.com/index.php/post/115428.html
