流数据抽样——Reservoir Sampling

Reservoir Sampling

首先我们再重新描述一下问题：假设有一组数据流元素有 N 个（事先不知道 N 具体值），我们希望选择 n 个样本（N >= n），使用怎样的策略进行抽样可以使得数据流中每个元素被选择的概率恰为 n / N?

Insight

由于事先不知道元素个数，所以必须要逐元素处理，对于第 i 个要处理的元素（i > n），假设数据就此终止（N = i）,那么我们此时对这个元素的选择策略必定为以 n / N （n / i）的概率予以保留方能满足要求。

Reservoir Sampling 策略

我们维护一个大小为 n 的容器，对于数据流中的前 n 个数据，我们以100%的概率进行保留，对于之后的第 i （n < i <= N）个数据，我们以 n / i 的概率将其保留；若这个新数据在这一步中被保留，那么从容器中均匀随机抽样一个旧数据（每个数据被抽到的概率为 1 / n），用新数据将旧数据替换即可。

我们下面证明，使用上述策略——Reservoir Sampling 抽样得到的 n 个数满足数据流中的每个元素被均匀抽到，概率为 n / N。

证明

我们用数学归纳法证明。

代码实现

根据上述策略我们代码写起来就很容易啦。代码的关键部分在sampling那里。