水库抽样算法

简介

水库抽样算法是一个典型的空间亚线性算法。

空间亚线性算法： 由于大数据算法中涉及到的数据是海量的，数据难以放入内存计算，所以一种常用的处理办法是不对全部数据进行计算，而只向内存里放入小部分数据，仅使用内存中的小部分数据，就可以得到一个有质量保证的结果。 数据流算法： 是指数据源源不断地到来，根据到来的数据返回相应的部分结果。适用于两种情况：第一、数据量非常大仅能扫描一次时，可以把数据看成数据流，把扫描看成数据到来。第二、数据更新非常快，不能把所有数据都保存下来再计算结果，此时可以把数据看成是一个数据流。 在一些情况下，空间亚线性算法也叫数据流算法。

水库抽样的要求是，每一时刻取到的样本都是前面已经流过的全部数据的均匀抽样。

过程文字描述

连续输入一组未知大小的数据，输出这组数据的 k 个均匀抽样

1. 申请长度为 k 的数组A保存抽样 (此处下标用 1~k 表示)；
2. 首先保存接收到的前 k 个数据；
3. 当接收到第 i 个数据 t 时，生成 [1,i] 间的随机数 j, 若 j<=k, 则以 t 替换A[j]。

算法的关键在第三步，每当新来元素 t 时，生成随机数，一旦随机数落在数组范围之内，就替换掉。

代码实现

/***
     * 
     * @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;
    }

原理证明

对于每个新到来的元素 i，它是以 k/i 的概率被收入集合的，因为生成的随机数范围是 [1,i]，而当数字小于等于 k 时，才会被替换进数组 A。

当第 i+1 个元素到来时，第 i+1 个元素被替换进数组的概率是 Pi=k/(i+1)，而此时，前一个元素 i 被从中替换出来的概率为 Po=1/k。则当第 i+1 个元素到来时第 i 个元素被替换出去的概率为 Pi*Po，那么没有被替换出来的概率为 p=1-Pi*Po=1-1/(i+1)。

那么当第 i+2,i+3… 个元素到来时，第 i 个元素没有被替换出来的概率为 1-1/(i+2)，1-1/(1+3)…

那么当元素 i 被选入集合中，并且在后面的所有的替换中都没有被替换出来的概率： k i ∗ ( 1 − 1 i + 1 ) ∗ ( 1 − 1 i + 2 ) ∗ ⋯ ∗ ( 1 − 1 n ) = k n frac{k}{i}*(1-frac{1}{i+1})*(1-frac{1}{i+2})*cdots*(1-frac{1}{n})=frac{k}{n} ik∗(1−i+11)∗(1−i+21)∗⋯∗(1−n1)=nk

这样便得到，对于任意一个元素 i，其被选入样本的概率均为 k/n，证明其符合随机抽样。