水塘抽样算法

水塘抽样算法是用于解决，对于一个未知长度的数据流进行随机采样的问题的。本文介绍几个算法及其变形。

说明：伪代码中S代表未知长度数据流，n为S的实际长度，S.CURRENT表示S当前值，S.NEXT代表S指针下移，R代表结果，k表示结果需要保留的个数。

简单抽样一个元素

Sample(S[1..n],R[1]) //s是未知长度的数据流  R[1]=S[1]          //取第一个值，初始化结果  count := 1         //计数器，记录当前为数据流中的第几位  while S has data    count++    j := random(0, 1)   //根据当前位置生成随机数[0,1)    if j < 1/count        R[1] = S.CURRENT    S.NEXT

证明：

一个元素的时候：被抽中的概率为1

两个元素的时候：第一个元素留下的概率为1-1/2，第二个元素留下的概率为 1/2

三个元素的时候：第一个元素留下的概率为(1-1/2)*(1-1/3)=1/3，第二个元素留下的概率为1/2*(1-1/3)=1/3,第三个元素留下的概率为1/3

以此类推，当判断到第i个元素时，第m（0<m<=i）个元素留下的概率为1/m*(1-1/(m+1))*(1-1/(m+2))...(1-1/(i))=1/i就可以保证所有元素的概率相等

算法R

ReservoirSample(S[1..n], R[1..k])  //使用前l个值初始化结果  for i = 1 to k      R[i] := S[i]  while S has next    i++    j := random(1, i)   //取1~i的随机数    if j <= k        R[j] := S[i]    //如果位置落在k之内则替换掉对应的R[j]

证明：

第m轮时，R中的每个元素被替换的概率为1/k*k/m=1/m，i能替换掉R中值的概率为k/m，所以到第i轮，第m（0<m<=i）个元素是k/m*(1-1/(m+1))*(1-1/(m+2))...*(1-1/i)=k/i

随机值排序水塘算法

ReservoirSample(S[1..?], R[1..k])  H = new max-priority-queue    //有序队列  while S has data    r = Random(0,1)    if H.Count < k      H.Insert(r, S.Current)    else      if H.Maximum > r        H.Extract-Max()        H.Insert(r, S.Current)    S.Next

该算法是对每个值进行随机值计算，并保留最大的k个随机值

带权重的随机值排序水塘算法

有些情况，采样的数据是有权重的，下面介绍几个带权重的水塘抽样算法

A-Res算法

ReservoirSample(S[1..?], R[1..k])  H = new min-priority-queue  while S has data    r = Random(0,1) ^ (1/S.Weight)  // 随机值取0-1随机值的1/weight的次方    if H.Count < k      H.Insert(r, S.Current)    else      if H.Minimum < r      //如果比队列中最小值大，则替换最小值        H.Extract-Min()         H.Insert(r, S.Current)    S.Next

该算法的随机值是使用了生成随机值的1/weight次方，可以增加高权重的随机值

分布式随机抽样

有些情况需要在分布式的情况下进行随机抽样，可以采用A-Res算法在分布式机器上运行，最后使用各机器上的值进行一起排序达到随机抽样的效果。

洗牌算法Fisher-Yates算法

一种需求是需要对所有的值进行乱序排序

shuffle(S[1..?])    for(i:= 1 .. n-1)        r:= random(0,i)     //[0,i]的随机值        swap(a[r],a[i])

JDK中的Collections.shuffle也是使用这个算法进行数组乱序的。

参考：