水塘抽样：未知大小数据流的公平抽样
💡
原文中文，约22000字，阅读约需53分钟。
📝
内容提要
水塘抽样是一种在未知长度数据流中均匀抽取k个样本的算法。其核心思想是通过替换过程确保每个元素被选中的概率为k/n。文章介绍了经典的Algorithm R及其优化版本Algorithm L，后者通过跳跃策略减少随机数生成次数。此外，还讨论了加权水塘抽样和分布式场景下的合并策略，强调了其在A/B测试、数据库采样和机器学习中的应用。
🎯
关键要点
- 水塘抽样是一种在未知长度数据流中均匀抽取k个样本的算法，确保每个元素被选中的概率为k/n。
- Algorithm R是经典的水塘抽样算法，分为填充和替换两个阶段。
- Algorithm L是Algorithm R的优化版本，通过跳跃策略减少随机数生成次数，适用于n远大于k的场景。
- 加权水塘抽样算法A-Res通过计算元素的键来实现按权重采样，确保权重大的元素更可能被选中。
- 分布式水塘抽样策略包括带计数合并和键排序合并，确保在多个节点上独立抽样后能合并得到全局均匀样本。
- 水塘抽样在A/B测试、数据库采样和机器学习中有广泛应用，能够精确控制样本量并保证公平性。
❓
延伸问答
水塘抽样的核心思想是什么？
水塘抽样通过替换过程确保每个元素被选中的概率为k/n，从而在未知长度的数据流中均匀抽取k个样本。
Algorithm R和Algorithm L有什么区别？
Algorithm R是经典的水塘抽样算法，而Algorithm L是其优化版本，通过跳跃策略减少随机数生成次数，适用于n远大于k的场景。
加权水塘抽样是如何实现的？
加权水塘抽样算法A-Res通过计算元素的键，确保权重大的元素更可能被选中，从而实现按权重采样。
水塘抽样在实际应用中有哪些场景？
水塘抽样广泛应用于A/B测试、数据库采样和机器学习中，能够精确控制样本量并保证公平性。
分布式水塘抽样的合并策略是什么？
分布式水塘抽样的合并策略包括带计数合并和键排序合并，确保在多个节点上独立抽样后能合并得到全局均匀样本。
水塘抽样与Bernoulli采样相比有什么优缺点？
水塘抽样能够精确控制样本量且保证公平性，而Bernoulli采样实现简单但样本量不确定，且需要预估总数n。
🏷️
标签
➡️
