🌀蓄水池采样算法（Reservoir Sampling）
type
status
date
slug
summary
tags
category
icon
password
背景
等概率采样是模型训练前对样本进行处理的常见需求，但在大数据时代，经常要面对上亿的数据量，无法同时进行处理。因此，为了避免过大的时间和空间成本，同时又能达到等概率采样的效果，蓄水池采样（Reservoir Sampling）算法应运而生。
基本原理
假设需要选取的样本数为，
- 设定存储采样的蓄水池容量为
- 对总样本空间的样本依次进行处理（样本顺序不影响最终采样概率），对第个样本，处理流程如下：
- 如果蓄水池不满，当前样本直接被选中，进入采样池
- 如果蓄水池已满，当前样本按照概率进入采样池，并根据随机概率值替换相应位置的样本
证明
设当前样本的下标为，
- 对于顺序小于等于的样本（即）：
- 针对第个样本，第个样本被替换的概率为，不被替换的概率为
- 针对第个样本，第个样本不被替换的概率为
- 到达第个样本（当前样本空间中的最后一个样本），第个样本最终被选中的概率为
- 对于顺序大于的样本（即）：
- 当前样本被选中的概率为
- 针对第个样本，第个样本不被替换的概率为
- 到达第个样本（当前样本空间中的最后一个样本），第个样本最终被选中的概率为
综上，无论样本处于什么位置，最终被选中的概率均为