C++ 中的蓄水池抽样算法

采样在数据科学和统计学中发挥着作用，使我们能够从较大的总体中提取一个子集。一种有效的方法是水库采样，它涉及从大小为 (n) 的数据集或流中选择固定数量的项目 (k)。

本文旨在概述水库采样算法，并演示其在 C++ 中的实现。当从无法完全存储在内存中的海量数据集中提取样本时，水库采样非常方便。它在处理流中的每个项目时，都会维护一个固定大小的水库。

在展示说明其在 C++ 中实现的示例代码之前，我们将深入探讨其原理。此代码将涵盖初始化水库、概率替换元素以及显示输出等方面。此演示显示了随着从流中处理更多数据点，水库如何持续维护样本。

在分析、A/B 测试、推荐系统和有效处理大型真实世界数据集等领域，理解水库采样具有重要价值。

C++ 实现展示了该算法如何在通用编程语言中应用。让我们开始深入探讨水库采样的概念。

什么是水库采样算法？

水库采样旨在从 n 个项目的池中选择 k 个项目，其中 n 可能是未知的。此技术使您能够通过一次数据遍历从潜在的海量数据集中获取 k 个项目的分布式样本。

水库采样的关键思想是：

• 维护一个大小为 k 的水库以存储随机样本
• 用数据流中的前 k 个项目填充水库
• 对于后续项目，以 k/i 的概率随机替换水库中的一个项目，其中 i 是新项目的索引。

这样，每个项目最终进入水库的概率相等，都是 k/n。因此，我们得到一个均匀的随机样本。

该算法的工作原理如下：

1. 初始化一个大小为 k 的水库数组以存储随机样本
2. 将流中的前 k 个项目插入水库数组
3. 对于项目 i，其中 i > k
   • 生成一个介于 0 和 1 之间的随机数
   • 如果随机数 < k/i，则用项目 i 替换水库中的一个随机元素
   • 否则，忽略项目 i
4. 处理完所有 n 个项目后，水库数组包含随机选择的 k 个项目。

随着 i 的增加，概率 k/i 逐渐减小，因此每个项目替换水库中现有项目的可能性就越小。这使得每个项目都有相等的选择概率。随着更多项目的处理，水库维护着一个均匀的样本。

水库采样算法效率很高，处理 n 个项目只需要 O(n) 的时间复杂度，水库的大小固定为 k 个项目。它只需要对数据进行一次遍历。这使其适用于无法完全存储在内存中的大型数据流。

应用场景和使用地点

• 处理大型数据流：当您必须从无法完全放入内存的海量数据流中进行采样时，水库采样非常有用。它只需要固定大小的水库，并按顺序处理项目。
• 未知数据大小：即使项目数量 n 事先未知，该算法也有效。无论 n 如何，它都会在水库中维护均匀的随机样本。
• 获取代表性样本：水库包含统计上代表更大总体的一个随机子集。这对于下游分析非常有用。
• A/B 测试：水库采样允许将用户分成均匀的随机样本进行对照实验。例如，在样本用户上测试新功能。
• 推荐系统：通过均匀采样用户、项目或产品评分，可以在无偏见的样本上训练推荐模型，以推荐内容。
• 机器学习：在数据点的随机子集上训练机器学习模型可以减少偏差，并带来更好的模型泛化能力。
• 数据分析：分析随机样本有助于计算正确反映完整数据分布的统计数据或可视化。
• 时间序列采样：水库算法可以对来自服务器日志、股票行情数据或传感器读数等流的固定间隔进行采样。

总而言之，水库采样提供了一种从连续生成的大数据流中获取小型均匀样本的方法。它在许多领域都可用于对海量真实世界数据进行统计采样和分析。

示例

用于随机选择未知大小 n 的流中的 k 个项目的 C++ 水库采样算法代码。

输出

Random k = 5 items out of stream are: 55 9 61 8 12

这里的核心思想是，随着对流中的项目扫描得越多，我们随机替换水库数组中的元素，概率逐渐降低。它确保了后面的项目有机会像前面的项目一样被选中。

说明

1. 导入必要的。设置常量；

包括 cstdlib 以使用 rand() 和 srand()

使用 ctime 为 srand() 提供种子

定义 k 作为水库大小

2. 创建一个大小为 k 的数组来保存项目

3. 开发 reservoirSampling() 函数，该函数以流和大小 n 作为参数

4. 使用时间初始化数字生成器

5. 将前 k 个项目直接添加到水库数组

它用 k 个项目设置水库

6. 开始一个从 k 到 n-1 的循环来处理剩余的流项目

7. 生成一个介于 0 和 i-1 之间的数字 j，其中 i 从 k 到 n-1

8. 如果 j 介于 0 和 k-1 之间，则用项目 i 替换水库中索引 j 处的项目

此过程以递减的概率随机交换现有项目

. 概率 = k/(i+1)

9. 输出水库数组中的 k 个项目。

我们首先用 k 个项目设置水库数组。然后，当我们从 k 到 n-1 遍历流时，我们会用项目随机地交换数组中的元素。这个过程保证了我们在替换过程中实现了随机选择。

结论

水库采样算法使我们能够在不知道项目数量的情况下，从数据流中随机选择 k 个项目，从而以 O(n) 的时间复杂度和 **O(k) 的空间复杂度有效地解决了问题。

C++ 实现中的关键点；

• 它首先用 k 个流项目填充固定大小的水库数组，将随机数据引入水库。
• 主要策略是使用替换方法，随着扫描更多流项目，概率从 k/n 降低到 k/(n+1)。它确保所有项目都被均匀且随机地选择包含在水库中。
• 来自 cstdlib 的 rand() 和 srand() 函数用于生成用于选择策略的数字。Srand() 使用时间进行初始化，以便在每次运行时生成不同的输出。
• 代码简洁、设计精良，并准确捕捉了水库采样的精髓。即使不知道总人口数量，它也能产生样本。
• 总之，此 C++ 实现使用了内置函数、线性时间复杂度、常数空间复杂度、概率选择技术和简单的逻辑，有效地从固定大小的数据流中创建样本子集。它可作为在应用程序中实现水库采样的参考。
• 水库采样方法在数据流和随机化场景中都有应用。例如，它可以用于分析传感器数据、监控搜索引擎上的搜索趋势、模拟金融数据流、随机选择数据包进行网络监控等等。