在LeetCode上看到一个分类是Reservoir Sampling, 即蓄水池抽样. 以前完全没听过, 今天整理下.

内容整合自:
http://www.cnblogs.com/hrlnw/archive/2012/11/27/2777337.html

蓄水池抽样（Reservoir Sampling ）是一个很有趣的问题，它能够在o（n）时间内对n个数据进行等概率随机抽取，例如：从1000个数据中等概率随机抽取出100个。另外，如果数据集合的量特别大或者还在增长（相当于未知数据集合总量），该算法依然可以等概率抽样。

说蓄水池抽样之前，先说一下等概率随机抽取问题，等概率随机抽取是一个很有用的东西，因为在很多情况下，尤其是搞模式识别时，需要这个东西。比如，我们想从10000个样本中随机抽取5000个作为训练集，5000个作为测试集，那么等概率随机抽取便派上用场了。那么，究竟该如何做等概率随机抽取呢？一般的想法应该是，随机生成一个（0，n-1）之间的数x，然后抽取集合中第x个数据，如果本次生成的数x‘与之前某次生成的数x是相同的，那么继续随机生成，直到生成一个与之前所有生成过的数不同的数。并将这样的随机生成做m次。

这样做思路上是最简单的，但是问题却出现了，如果m比较小还好，比如n=10000，m=100，就是说10000个数里面随机挑100个，基本上没什么重合的概率，因为当做第100次随机生成时，之前才生成了99个，所以至多有99/10000≈1%的概率生成与之前重复的数。那么，我们可以很顺利的随机的、等概率的生成100个数，并且基本上只调用100次rand函数就行。但是如果m比较大呢？还是刚才那个例子，如果n=10000，m=5000呢？这涉及到一个求期望的问题，设sum为该算法调用rand函数的次数，我们来求一下E（sum）,由于每次随机生成的数都是独立的，因此E（sum）=E(num_1)+E(num_2)+…E(num_m),所以我们求出生成第i个数需要调用多少次rand函数即可。

假设前面已经生成了i个数，我们要生成第i+1个数，那么，有如下概率：

调用1次rand函数就成功生成该数的概率为：（1-i/n）

调用2次rand函数就成功生成该数的概率为：（i/n）*（1-i/n）

…

调用k次rand函数就成功生成该数的概率为：（i/n）^(k-1)*(1-i/n）

则E（num_i+1）=1（1-i/n）+2（i/n）（1-i/n）+…+k（i/n）^(k-1)*（1-i/n）+…

即E(num_i+1)=n/(n-i)

这个计算并不难，在此我仅给出我计算出的期望：n/(n-x)（默认x从0开始，程序员的习惯）

最后，E（sum）=n/n+n/(n-1)+n/(n-2)+….+n/(n-m+1)

这个期望就比较难算了，复杂度大概是O（n*（lg(n）-lg(n-m)））级别的。在n比较大，m也比较大的时候，这个规模比O（n）可大多了。因此，蓄水池抽样在这个时候就有优势了，而且，对于另一种比较变态的情况，假设n非常大，以至于我们并不知道n的确切数量，而且n还在动态的增长，我们要不停的随机等概率的抽取n的一定比例（例如10%），这种情况下，上面所介绍的普通抽样方法就很难做到了。

蓄水池抽样：从N个元素中随机的等概率的抽取k个元素，其中N无法确定

先给出代码：

Init : a reservoir with the size： k for i= k+1 to N M=random(1, i); if( M < k) SWAP the Mth value and ith value end for 　　

上述伪代码的意思是：先选中第1到k个元素，作为蓄水池的元素。然后依次对第i个元素(k + 1 <= i <= N), 以k/i的概率将其与蓄水池中的元素替换. 最后留在蓄水池中的元素即为抽样结果.

我们要证明: 以此方式选取时, 每个元素被选中的概率都是k/n.

当检查第k+1个元素时, 该元素被选中的概率为k/(k+1). 前k个元素, 每个被选中的概率都为1-1/(k+1)=k/(k+1).

当检查第k+2个元素时, 该元素被选中的概率为k/(k+2). 前k+1个元素, 每个被选中的概率都是k/(k+1) * (1 - 1/(k+2))=k/(k+2)

可以看出规律, 当检查完第n个元素后, 每个元素被选中的概率都将是k/n.