水塘抽样问题

今天写的这篇文章主要是介绍水塘抽样问题-如何在极大样本中保证抽样的随机性，并介绍了水塘抽样问题的两个版本：保证抽取1个样本的随机性到保证抽取k个样本的随机性及其证明，最后列出代码。

在高德纳的计算机程序设计艺术中，有如下问题：可否在一个未知大小的集合中，随机抽样一个元素？例如在一个很大，但未知行数的文字档中抽取任意一行。如果要确保每一行抽取的概率相等，即是说如果最后发现文字共有N行，则每一行被抽取的概率均为1/N。

而水塘抽样问题就是在n个元素中随机抽样k个数据，其中n为一很大或未知的数量，尤其适用于不能把所有n个元素都存放到主内存的情况。

其解决方案是蓄水池抽样，思想是保持一个集合作为蓄水池，依次遍历集合中所有元素时，以一定概率取代蓄水池中的某一元素。

首先来看k=1，从n个元素中取出一个元素，这里假设n已知：

n=1：只有一个数据，直接取出，概率为1/1。

n=2：首先将第一个元素作为蓄水池，取第二个元素时，要想每个数的概率为0.5，可以随机生成一个0到1的数据p，当p小于0.5，用第二个数据替换第一个数据，否则不变；此时每个数据的取出概率都是0.5。

n=3：事先分析，为满足条件每个数的取出概率都是1/3，在取前两个数据时，可以按n=2处理，取第三个数据，仍按p小于1/3的概率表示是否进行替换，而前面两个数据留下来的概率也是(1-1/3)*1/2=1/3...

由上面的分析得出：在取第n个数据的时候，我们生成一个0到1的随机数p，如果p小于1/n，保留第n个数替换蓄水池。大于1/n，继续保留前面的数。直到数据流结束，返回此数。

下面用数学归纳法证明此结论。

（1）当n=1时，第一个元素以1/1的概率返回，符合条件。

（2）假设当n=k时成立，即每个元素都以1/k的概率返回，先证明n=k+1时，是否成立。对于最后一个元素显然以1/k+1的概率返回，符合条件，对于前k个数据，被保留的概率为1/k * (1- 1/k+1)=1/k+1，满足题意。

再分析n=k，从n个元素取出k个数据，在上面的分析上，可以直接将结论替换为：在取第n个数据的时候，我们生成一个0到1的随机数p，如果p小于k /n，替换池中任意一个为第n个数。大于k /n，继续保留前面的数。直到数据流结束，返回此k个数。

但是为了保证计算机计算分数额准确性，一般是生成一个0到n的随机数，跟k相比，道理是一样的。

验证：

（1）初始时将前面k

（2）处理第k+1个数据时，有两种情况：保留第k+1个元素替换蓄水池中的某一个元素；不保留，蓄水池不变。

A. 第k+1个元素留下的概率为k/k+1。

B. 前面k个元素被保留的概率在两种情况讨论：

（1）前k个元素某一个要保留的概率：k/(k+1)*(1-1/k)即第k+1留下来且自身不被选中；

（2）前k个元素某一个要保留的概率：1/(k+1)，即第k+1个不留下来；两者相加即为k/(k+1).

（3）处理第n个数据时，有两种情况：保留第n个元素替换蓄水池中的某一个元素；不保留，蓄水池不变。第n个元素留下的概率为k/n。

前面n-1个元素被保留的概率在两种情况讨论：

A.选第n个，前n-1个元素某一个要保留的概率：k/n*(k/n-1)*(1-1/k)即第n保留且前n-1个一开始已被选入最后自身不被选中。

B.不选第n个，前n个元素某一个要保留的概率：（1-k/n）*（k/n-1），即第n个不保留且自身在前n-1个要被选中；两者相加即为k/n。

可证说明概率是相等的，代码如下：

importjava.util.Random;

publicclassReserviorSampling {

/**

*@paramstream:表示输入的未知数据流

*@paramreservior：表示蓄水池

*最终返回reservior随机序列

*/

publicvoidreserviorsampling(Item[]stream,Item[]reservior,intk){

//先取出k个放入蓄水池

for(inti= 0;i

reservior[i] =stream[i];

for(intj=k;stream!=null;j++){

//nextInt(j+1)随机生成[0,j]之间的数p

intp=newRandom().nextInt(j+1);

if(p

//若p小于k，则保留stream[j],并替换

reservior[p] =stream[j];

}

}

}

注意：

1. 在取出第n个元素时成一个0到1的随机数p，如果p小于k/n，替换池中任意一个为第n个数。若替换成生成0到n的随机数与k比，一定要注意概率替换成整数后就由连续型变成离散型，此时保留第n个元素的概率为k/n，也就是说生成的随机数范围一定要有n个整数，p``

2. 使用数组表示蓄水池时，一定要注意数组下标与取数序号的关系，序号n=下标+1，生成随机数范围是以序号为准，随机数范围要有n个，p``

山猫，一个专注于高级计算机技术分享的团队。

如果大家有什么问题或技术需求，可以后台留言或加山猫小墨的微信（二维码在页面底部）。

小墨简介：资深白帽，国内某互联网公司研发负责人，现从事机器学习、神经网络相关算法研究。