Reservoir Sampling / 蓄水池采样（算法）

在粗读 Reservoir-based sampling over large graph streams to estimate triangle counts and node degrees 论文的时候，第一句就读到不认识的东西，真是开幕雷击= =

在详细了解后，发现蓄水池采样算法本身是一个十分简单的算法，采用巧妙的方法解决了一个如下的“简单”问题：

如何在内容和长度均未知的数据流中，仅遍历一遍，且在O(n)的时间复杂度内，任意、随机地选出m个数据来？*

* 问题相较于参考资料有所改变，将在文尾具体解释。

长度和内容均未知的数据流带来了以下问题：

不一定能够使用存储设备完全储存（进一步说的话，可以特指内存）；
不能预测且无法回看。

针对于题目的任意和随机性来看的话，上述第2点带来的问题就是，必须要对当前数据流中的任意元素进行等价的操作。也就是说，决定任何一个数据去或留（即是否加入最终选出的m个元素的集合）的时机，对于任何元素来说都应该是一样的。对于这种意义下的“操作时机”，我认为可以大致分为三类：

“当机立断”：获取到该数据的同时就对于数据的去向进行决定。此时，程序的内存占用量是可预测的，（按照单线程考虑的话）同一时刻内不会存有两个数据流内的数据；
“前看”：类似于编译原理中的前看原理，但是需要通过在程序中自行设立单独的“前看缓冲区”，通常来说，前看的深度是固定的；
“我全都要”：最让人喜闻乐见的方式，全读入内存，慢慢折腾。

显然，3是首先要排除的。题目中有提到数据流的长度是未知的，很有可能超出当前可能的内存容量。

那么问题的解决策略只能在1或者2中着手。由于本人数学水平实在有限，无法断定并证明其中某种思路的可行性，因而在此，只能说明，蓄水池采样算法是使用思路1，借助随机函数实现对于任意长度序列的所及元素选择。

接下来对于算法，使用类Java伪代码进行描述：

InputStream in;                    // 数据流
Data current;                      // 当前数据
Data ans[] = new Data[m];          // 为要选出的元素预留空间
Random rand = new Random();        // 随机数产生器
Integer index = 0;                 // 已读取的数据数量计数

while(in.hasNext()) {
    current = in.next(); index++;  // 读取了一个数据
    if(index <= m) {
        // 先把“蓄水池”填满，此时不存在元素冲突问题
        // 下标=元素个数-1
        ans[index - 1] = current;
    } else {
        // 从当前已读取的数据编号范围内选出一个，把刚读入的数据“放到”这个位置
        // 这里的randInt取值区间是左闭右开的
        Integer slot = rand.nextInt(0, index);
        if(slot < m) {
            // 若是这个位置是前m个之内的话，替换数据
            ans[slot] = current;
        }
        /* 否则不做任何处理 */
    }
}
return ans;

然后就是简单扼要的原理说明了。

先说结论：使用蓄水池采样算法，可以在仅遍历一遍数据流、且在O(n)时间复杂度的情况下，使得每个数据被选出的概率均为\frac{m}{N}。

证明如下：

将“数据能够在蓄水池中保留至结束”这一事件S(Select)分解为两个互相独立、串联的事件 [数据能够进入蓄水池I(In), 数据能够保留在蓄水池中K(Keep)]，则可以表示如下：

P(S)=P(I) \times P(K)

从上面的算法描述代码可以看出，第1 \sim m个元素进入蓄水池的概率为1，即

\tag{1} \forall i \in \{1, 2, ..., m\}, P(I_{i}) = 1

而第1 \sim m个元素中的任意一个要保留到最终的话，假设数据流长度为N，则应该要在接下来N-m次数据读取的操作中均不被替换掉。由于第j个数据输入时共有j种选择，则每一次替换时，蓄水池中的第i个元素有\frac{j-1}{j}的概率不被替换。由此则有第1 \sim m中任意一个元素保留到最终的概率为

\tag{2} \forall i \in \{1, 2, ..., m\}, P(K_{i}) = \frac{m}{m+1} \times \frac{m+1}{m+2} \times ... \times \frac{N-1}{N} = \frac{m}{N}

由(1)(2)可得

\tag{3} \forall i \in \{1, 2, ..., m\}, P(S_{i}) = P(I_{i}) \times P(K_{i}) = \frac{m}{N}

对于第m+1 \sim N个元素，由于此时蓄水池中已经装满元素了，需要以一定概率来替换已有元素，才能决定是否进入集合。由于新元素要进入集合只需替换原有集合中的任意一个即可，则有：

\tag{4} \forall i \in \{m+1, m+2, .... N\}, P(I_{i}) = \frac{m}{i}

可以发现此时位置不同的元素进入蓄水池的几率是随着位置向后推移而逐渐降低的。

继续计算这些元素保留到最终的概率，原理同公式(2)：

\tag{5} \forall i \in \{m+1, m+2, ..., N\}, P(K_{i}) = \frac{i}{i+1} \times \frac{i+1}{i+2} \times ... \times \frac{N-1}{N} = \frac{i}{N}

此时由(4)(5)可得：

\tag{6} \forall i \in \{m+1, m+2, ..., N\}, P(S_{i}) = P(I_{i}) \times P(K_{i}) = \frac{m}{N}

合并(3)(6)，神奇的事情发生了：

\forall i \in \{1, 2, ..., N\}, P(S_{i}) = \frac{m}{N}

证毕。

这也正是本算法的巧妙之处：不论原始数据流有多长，只要带选出的数据量m小于原始数据流的长度N，总能有办法随机、等概率地选出m个元素，即使N完全未知。

原文来自 https://www.jianshu.com/p/7a9ea6ece2af ，作者：邱simple。

在原文中，作者还讲述了分布式蓄水池抽样算法，并给出了Java代码的实现，如有需要可自行浏览。

这里简要说明一下开头提到的与原文中问题的区别。原文中问题还添加了“选出的元素不重复”这一限制条件，但是我认为，添加了该条件后，代码需要做出相应的改动（替换元素时的一些if条件），也不能称之为对原始数据流的等概率选取了，因而在本文中对命题进行了修改。如果有细心的读者发现了我的逻辑问题的话（万一有呢~~指读者~~），欢迎指正与交流。

Reservoir Sampling / 蓄水池采样（算法）

添加新评论