蓄水池抽样

最近在做监控的异常检测，而在异常检测中，一个很有名的算法叫RRCF，它是IsolationForest的改进版，适用于流式的数据，其中一个优化的点就是采用了蓄水池抽样的方法来获取数据。

一、问题描述

假设有N条数据，其中N非常非常大，如何遍历一次数据不重复抽取出m条数据，要求N中每条数据被选取到的概率相同。

二、解决思路

那么在解决这个问题时，我们需要注意到如下几点：

数据很大，我们无法一次性存入到内存中；
要求时间复杂度在O(N)；
要求每条数据被选取到的概率为$m/N$;

因此，对于第一条，我们就无法一次性讲数据存入到内存中，再在 $[0,N-1]$ 中随机选取出m个数，按照索引来选取数据；对于第二条，我们就无法分块来读取多次数据；对于第三条，需要确保其是完全随机。

解决方案：

step1：当接收数据$i<m$时，将数据放到蓄水池中；

step2：当接收数据$i>m$时，随机从$[0, i-1]$中生成随机数$j$，如果$j<m$，那么按照索引替换蓄水池中的第$j$个数，否则进行替换；

step3：重复step2；

这个算法可以在遍历一次第情况下，保证N中的每个数字被选取到的概率为 $m/N$

三、证明

接下来我们来验证一下这个方法的正确性，可以通过计算第 $i$ 个数载蓄水池的概率

$P(第i个数最终在蓄水池)=P(第i个数进入蓄水池)*P(不被i+1后的数据替换)$

这个时候我们需要分两种情况来讨论：

当 $i<=m$ 时，这个时候 $P(第i个数进入蓄水池)=1$，而 $P(不被m+1后的数据替换)=P(第m+1个数不替换它)*…*P(第N个数不替换它)=\prod \limits_{j=m+1}^N P(第j个数不替换它)$

$P(第j个数替换它)=\frac{1}{j}$

$P(不被m+1后的数据替换)=\prod \limits_{j=m+1}^N P(第j个数不替换它)=\prod \limits_{j=m+1}^N(1-P(第j个数替换它))=\prod \limits_{j=m+1}^N(1-\frac{1}{j})={\frac{m}{m+1}}·{\frac{m+1}{m+2}}·…{\frac{N-1}{N}}={\frac{m}{N}}$
当 $i>m$ 时，这个时候 $P(第i个数进入蓄水池)=\frac{m}{i}$，而

$P(不被i+1后的数据替换)=P(第i+1个数不替换它)*…*P(第N个数不替换它)=\prod \limits_{j=i+1}^N P(第j个数不替换它)$，

$P(第j个数替换它)=\frac{1}{j}$ ，

$P(不被i+1后的数据替换)=\prod \limits_{j=i+1}^N P(第j个数不替换它)=\prod \limits_{j=i+1}^N(1-P(第j个数替换它))=\prod \limits_{j=i+1}^N(1-\frac{1}{j})=\frac{i}{i+1}·\frac{i+1}{i+2}·…\frac{N-1}{N}=\frac{i}{N}$

因此不论是哪种情况，我们都可以得到$P(第i个数最终在蓄水池)=\frac{m}{N}$

四、应用

蓄水池抽样算法可以完美适用与流式数据中，在流式数据中，N是无穷大，我们可以通过这种方式来进行抽样数据来构建模型。蓄水池抽样伪代码实现如下所示：

// 定义蓄水池
val reservoir: Array[Double] = new Array[Double](256)

// 定义计数器
var count: Int = 0

if (count < 256){
  reservior(count) = data         // 蓄水池未满，数据直接入池子
}else{
  randNum = Random.nextInt(count) // 蓄水池满了，生成随机数来判断是否要进行替换操作
  if (randNum < 256){
    reservior(randNum) = data
  }
}