流式处理中随机选取元素 – 蓄水池算法

偶然的机会遇到的一个问题:如何在一个流动的数据集中,以确定的概率从中选取K个元素,下面是自己的思考过程,以作记录。

由于数据是流动的,对数据没有全局的视图,因此不能采用普通的固定数据集的抽样算法,即以1/n、1/(n-1)、1/(n-2)、… 1/(n-k+1)去采样一个每次缩小一个单位的数据集。这里的原理是对于任意一个元素,其被采中概率的均为 = 1/n + (n-1)/n * 1/(n-1) + (n-2)/(n-1) * 1/(n-2) = k/n

但其实思路可以继续沿用,流中每来一个新元素,它需要以k/n的概率被采中才符合对于流任意一个快照,被采中的元素都以k/n的概率被采中,然后从原来的k个元素中随机取出一个置换。下面以归纳法来证明。

  1. 在数据流出现n-1个元素时,这时已被抽样的k个元素的采样概率均为 k/(n-1)
  2. 数据流出现第n个元素,按上述算法处理后新元素的采中概率为k/n,下面看下原来的k的元素概率是否也变更为k/n
    1. 采中与原来的k个交换时,继续保持被采中的概率:k/(n-1) * k/n * (k-1)/k = k(k-1) / n(n-1)
    2. 没采中,不需要交换的概率:k/(n-1) * (n-k)/n = k(n-k) / n(n-1)
    3. 两种情况相加为 k(n-k+k-1) / n(n-1) = k/n
  3. 所以仍保证所有被留下的元素是以k/n的概率被采中

在实际的工程实现时,可以在每次遇到新元素在[1, n]随机生成一个数字 r;若r小于等于k,则直接和已采中的k个元素中的第r个交换,即完成了k/n的概率完成采样,同时以随机概率与原有的k个元素完成交换。

 

发表评论