蓄水池抽样

等概率抽样

在平时处理问题的时候，我们经常会遇到有关于概率问题的处理，比如我们在运用启发式算法的时候经常会加入一些随机因素来防止搜索解的过程在局部最优解无限循环。当然，遇到最多的还是抽样的问题，我们在处理海量数据集的时候，有时候是没有必要把所有数据拿来处理的，这时候我们就可以用抽样来用一部分数据集来代表整个海量数据。既然这样的话，我们就有必要保证抽样的过程是等概率的，否则抽样的结果就不正确了。

问题定义

这里，我们假设一种情况：从N个元素中随机的等概率的抽取k个元素，其中N是动态变化无法确定的，或者N很大无法将所有数据一次读入内存，只能用流的方式逐个读入数据。这样的话，我们是无法简单地用random函数来抽样的。

我们换一个比较准确的说法来描述我们要学习的蓄水池抽样问题：

“给出一个数据流，这个数据流的长度很大或者未知。并且对该数据流中数据只能访问一次。请写出一个随机选择算法，使得数据流中所有数据被选中的概率相等。”

Solution

问题：从N个元素中随机的等概率的抽取k个元素，N动态变化。（其中N个元素序号从1-N）

蓄水池取样算法的过程：首先，我们选择序号1-k的k个元素初始化容积为k的蓄水池。然后从序号k＋1开始的元素（这里假设该元素序号为x）我们对每个元素做如下处理：每个元素被选中进容积为k的蓄水池的概率为 k/x ，选中之后以1/k的概率在原蓄水池中抽取1个元素与之替换。这样我们就保证了蓄水池中的元素被选中的概率都是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

证明

我们可以使用数学归纳法来证明其正确性，具体过程不再这里重复，但是需要我们注意的是，蓄水池中的元素不是固定不变的，在数据流的读取过程中池中的元素被选中的概率是会变的，也正是因为此我们才能保证N无法确定的情况时做到等概率抽样。