首页 > 代码库 > 算法学习之---蓄水池抽样问题

算法学习之---蓄水池抽样问题

问题如何在无限大的数据流中随机选取K个数据,保证当前遍历过的i个元素中每一个元素被选中的概率均为 k/i?从而对于n个元素,每个元素被选中的概率均为 k/n。

解:对于前k个元素,我们直接选中放入一个虚拟的蓄水池中,对于第 k+1 个元素,我们用 k/(k+1) 的概率选中它,一旦选中了,就随机替换掉蓄水池中的某一个元素,这样前 k 个被选中的元素在第 k+1 个元素到来时依然被选中的概率即为它不被替换掉的概率:

p = 1*(1-被替换掉的概率q)

        q = k/(k+1) * 1/k               #即前k个元素中某个元素被替换时,某个被替换的概率为 1/k

这样 p = k/(k+1)

     对于当前被遍历到的第 k+1 个元素,它被放到蓄水池中的概率就是它被选中的概率,即 k/(k+1),因为只要它被选中,就一定会替换掉蓄水池中的某个元素而留在水池中;

     同理,对于第 m +1 个元素(m>>k)的到来,前m个元素被选中的概率均为 k/m,进行第 m+1 次选择时,前 m 个元素依然保留在蓄水池中的概率为:

p = k/m * { 1 - [ k/(m+1) * 1/k ] } = k/(m+1)            #即 p=之前在水池中的概率*(1 - 被第m+1个元素替换替换掉的概率 )

或者 p = k/m * { (m+1-k)/(m+1) + [ k/(m+1) * (k-1)/k ] } = k/(m+1)    #即 p=之前在水池中的概率*(第m+1个元素未被选中的概率 + 第m+1个元素被选中但是替换了其他k-1个元素的概率)


代码实现时,遍历到第 i 个元素时(i>k),可以直接生成一个 (1,i)之间的随机数 r ,如果 r<=k,那么就让当前第 i 个元素替换蓄水池中的第 r 个元素即可,把选中和替换哪一个元素融合为一步了,概率是不变的,即被选中的概率为 k/i,蓄水池中的 k 个元素每一个被替换的概率也为 1/k 。



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


参考:http://blog.csdn.net/lxmky/article/details/7951099


算法学习之---蓄水池抽样问题