Reservoir sampling algorithm--蓄水池抽样算法的理解

一、算法代码：

def reservoir(num_seen_examples: int, buffer_size: int) -> int:
    """
    Reservoir sampling algorithm.
    :param num_seen_examples: the number of seen examples
    :param buffer_size: the maximum buffer size
    :return: the target index if the current image is sampled, else -1
    """
    if num_seen_examples < buffer_size:
        return num_seen_examples

    rand = np.random.randint(0, num_seen_examples + 1)
    if rand < buffer_size:
        return rand
    else:
        return -1

二、具体功能解释如下：

1. 参数说明：

   • num_seen_examples: 已经观察到的样本数。
   • buffer_size: 缓冲区的最大大小。

2. 判断是否需要替换：

   • 如果已经观察到的样本数 num_seen_examples 小于缓冲区的最大大小 buffer_size，说明蓄水池尚未填满，可以直接返回当前样本的索引作为替换的目标索引。

3. 执行蓄水池抽样：

   • 如果已经观察到的样本数超过了缓冲区的最大大小，执行蓄水池抽样。
   • 生成一个随机整数 rand，范围在 [0, num_seen_examples + 1) 之间。

4. 返回结果：

   • 如果生成的随机整数 rand 小于缓冲区的最大大小 buffer_size，则返回该随机整数作为抽样的目标索引，表示当前样本将被替换进蓄水池。
   • 否则，返回 -1，表示当前样本不被替换，不进入蓄水池。

三、蓄水池抽样函数的原理理解：

????????蓄水池抽样是一种经典的随机抽样算法，主要用于从一个数据流中等概率地随机抽取 k 个元素。这个算法的主要思想是在遍历数据流的过程中，以递增的概率选择元素，并在遇到新元素时以一定的概率替换已选取的元素。

3.1 算法的基本步骤如下：

1. 初始化： 遍历数据流的前 k 个元素，将它们放入蓄水池中。

2. 迭代： 对于第 i 个元素（i > k），以 k/i 的概率选择该元素并替换蓄水池中的一个已选元素。

这样，当遍历完整个数据流时，每个元素被选入蓄水池的概率都是 k/n（其中 n 是数据流中的元素总数），即保证了每个元素被选取的概率相等。

3.2 简单示例：

import numpy as np

def reservoir_sampling(data_stream, k):
    reservoir = []
    
    # 初始化，将前 k 个元素放入蓄水池
    for i in range(k):
        reservoir.append(data_stream[i])
    
    # 迭代处理后续的元素
    for i in range(k, len(data_stream)):
        # 生成一个随机整数，范围在 [0, i+1)
        rand = np.random.randint(0, i+1)
        
        # 如果生成的随机整数小于 k，替换蓄水池中的元素
        if rand < k:
            reservoir[rand] = data_stream[i]
    
    return reservoir

# 示例数据流
data_stream = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

# 设置蓄水池大小为 3
reservoir_sample = reservoir_sampling(data_stream, 3)

print("Reservoir Sample:", reservoir_sample)

????????在这个示例中，蓄水池的大小（k）被设置为 3。算法会从数据流中随机选择 3 个元素，保证每个元素被选中的概率相等。在实际应用中，这种随机抽样的方法经常用于模拟从大规模数据流中进行抽样而不需要存储整个数据流。