什么是水塘抽样算法(Reservoir Sampling)

问题描述:

给定一个数据流,数据流长度N很大,且N直到处理完所有数据之前都不可知,如何在只遍历一遍数据(O(N))的情况下,能够随机选取出这组数据的k个概率相等的均匀抽样。

要求:

(1)仅扫描数据一次。

(2)空间复杂度为O(K)。空间复杂度与整个数据量无关,只与抽样大小有关。

(3)扫描到数据的前n 个数据时(n>k),保存当前已扫描数据的k个均匀抽样。

根据要求,首先体积很大内存一次装不下,不能直接不能直接取N内的k个随机数,因为N的长度是未知的。此外也不能采用不能先遍历一遍,然后分块存储数据,再随机选取。最后要求是数据选取绝对随机的保证。

解法:采用水塘抽样算法(Reservoir Sampling)

代码非常简单,如下

/***
     * 
     * @param input 模拟的原始数组
     * @param k 采样的的个数
     * @return  返回采样的数据
     */
    public static int[]  sample(int []input,int k){
        Random random=new Random();
        int []ret=new int[k];

        for (int i = 0; i <input.length ; i++) {
            if(i<k){
                ret[i]=input[i]; //先取,前k个数字放在数组里面
            }else{//如果i>k,在1-i之间,取一个随机数字,如果这个随机数字小于k,就替换数组,否则就继续遍历,知道结束
               int rand=random.nextInt(i);//
               if(rand<k){
                   ret[rand]=input[i];
               }
            }
        }
     return  ret;
    }

算法思路如下:

(1)如果接受的数据量小于k,则依次放入采样数组中

(2)当接收到第i个数据,i大于等于k时,在[0,i]的范围内取一个随机数d 如果d落在了[0,k-1]的范围内,则取接收到的第i个数据替换采样数组中下标等于d位置上的值。

(3)重复步骤2。

该算法的精妙之处在于,当处理到数据源里面第n个数据时,采样数组里面的数据,总是均匀的抽样。

推导证明:

(1)第一步初始化。出现在水库中的前k个元素,直接保存在数组A中。前k个数被选中的概率都是一致的,都是1。 (2)第二步。在处理第k+1个元素时分两种情况:

情况1:第k+1个元素未被选中,数组中没有元素被替换;此时,数组中每个元素的出现概率肯定是一样的,这很显然。但具体是多少呢?就是第k+1个元素未被选中的概率:1-P(第k+1个元素被选中)=1-k/(k+1)=1/(k+1)。(由于第k+1个元素被选中的概率是k/(k+1)(根据公式k/i))

情况2:第k+1个元素被选中,数组中某个元素被第k+1个元素替换掉。第k+1个元素被选中的概率是k/(k+1)(根据公式k/i),所以这个新元素在水库中出现的概率就一定是k/(k+1)(不管它替换掉哪个元素)。下面来看水库中原有元素最终还能留在水库中的概率,水库中原有数据被替换的几率都相等为1/k。水库中任意一个元素被替换掉的概率是:(k/k+1)*(1/k)=1/(k+1),意即首先要第k+1个元素被选中,然后该元素在k个元素中被选中。那它未被替换的概率就是1-1/(k+1)=k/(k+1)。可以看出来,旧元素和新元素出现的概率是相等的。

(3)第k+1之后面每个元素都重复第二步,即第i (i>k+1)个元素以k/i的概率决定是否将它放入蓄水池,最终所有元素出现在水库中的概率相等。

总结:

其实,这种算法的能保证概率相等的前提就是: 当数据总量加1的时候,都会在当前总量的范围内,进行生成随机数,这样就能保证范围内的所有的数字出现概率都是相等的,然后根据概率均等随机数字来判断,是否落在了我们采样数组的边界中,如果落到了就替换原来数组中相同的位置的值,如果没有落到,就继续遍历选取,直到所有的数据处理完毕。

原文发布于微信公众号 - 我是攻城师(woshigcs)

原文发表时间:2018-12-05

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

扫码关注云+社区