2018-09-04 23:47:17 +0000   |     algorithm reservoir sampling math   |   Viewed times   |    

为什么需要蓄水池算法?

如果我们想从一组数字中随机取样,必须保证每个数字被抽取的概率相等。那么最简单的一个做法就是,

将这些数字保存在一个数组中,随机生成下标,然后抽取下标对应的数字。

这样可以保证,

对于长度为 n 的数组,每个数字被抽取的概率同为 1/n

比如数组[3,5,3,6,3,7,11,31,2]有9个数字,每次从下标区间[0,8]中间随机抽取一个偏移值,每个数被抽取的概率同为1/9

1/9 1/9 1/9 1/9 1/9 1/9 1/9  1/9  1/9
 |   |   |   |   |   |   |    |    |     
 3,  5,  3,  6,  3,  7,  11,  31,  2  

但是,能这么做有2个前提条件,

  1. 我们从一开始就知道全体数字的个数
  2. 而且数字不是很多,从而能全部读进内存(数组)

在大数据的背景下这两个条件都可能不满足。最典型就是样本以“数据流”的形式出现,数据流没有尽头,不断地会有新的数据加入,而且随时都有可能要求抽样。并且经常只有一次遍历数据流的机会。这时候就要用到蓄水池算法。

蓄水池算法到底怎么算?

最简单地讲就是,

先抽取第1个数字,后面第i个数字以1/i的概率替换被抽取的数字。以1-1/i的概率保持被抽取的数字不变。

还是考虑刚才的例子,

   1/1
    |   
    3,  5,  3,  6,  3,  7,  11,  31,  2,  8,  ...       

   1/1 1/2
    |   |   
    3,  5,  3,  6,  3,  7,  11,  31,  2,  8,  ...       

   1/1 1/2 1/3
    |   |   |   
    3,  5,  3,  6,  3,  7,  11,  31,  2,  8,  ...

   1/1 1/2 1/3 1/4
    |   |   |   |   
    3,  5,  3,  6,  3,  7,  11,  31,  2,  8,  ...

   1/1 1/2 1/3 1/4 1/5
    |   |   |   |   |   
    3,  5,  3,  6,  3,  7,  11,  31,  2,  8,  ...

先抽取第一个数字3,对于第2个数字5,有1/2的概率被用来替换被抽取的数字3。第3个数字又有1/3的概率替换前两个数字中幸存下来的那个。

这样根据数学归纳法, reservoir-sampling-a reservoir-sampling-b

推广到保存k个样本

上面说的是保存一个样本的情况,但同样可以推广到保存k个样本,

先抽取第k个数字,后面第i个数字以k/i的概率替换被抽取的数字。以1-k/i的概率保持被抽取的数字不变。

归纳法证明和上面类似,不赘述。

参考文献