迭代或惰性水库抽样

Question

我对使用“水库抽样”这种方法还算熟悉，它可以在一次遍历数据的过程中，从一个长度不确定的数据集中抽取样本。不过，我觉得这个方法有一个局限性，就是在返回任何结果之前，还是需要遍历整个数据集。从概念上讲，这样做是有道理的，因为我们需要让整个序列中的每个项目都有机会替换之前遇到的项目，以便得到一个均匀的样本。

有没有办法在还没评估完整个序列之前，就能得到一些随机的结果呢？我在想一种懒惰的方法，这种方法应该和Python的itertools库很搭。也许可以在某个允许的误差范围内做到这一点？如果有人能对这个想法提供反馈，我会很感激！

为了更清楚地说明我的问题，这张图总结了我对不同抽样技术在内存和流式处理之间权衡的理解。我想要的是一种属于流式抽样的技术，也就是说，我们事先并不知道数据集的长度。

显然，在不知道长度的情况下还想得到均匀的样本，这似乎是个矛盾，因为我们很可能会让样本偏向数据集的前面部分。有没有办法量化这种偏差？是否有需要权衡的地方？有没有人有聪明的算法来解决这个问题？

Answer 1

如果你事先知道总人数，那是不是可以直接生成一些随机的“索引”（在数据流中），然后用这些索引来懒惰地获取数据？这样你就不需要读取整个数据流了。

举个例子，如果总人数是100，而你想要的样本数量是3，那你可以从1到100中随机生成几个整数，比如说你得到了10、67和72。

然后你就可以获取数据流中的第10个、第62个和第72个元素，其余的就可以不管了。

我想我不太明白这个问题的意思。

Answer 2

如果你事先知道一个可迭代对象 population 中总共有多少个项目，你就可以在遍历这些项目的时候，逐个获取样本中的项目，而不是等到最后才获取。如果你不知道这个对象的总大小，那就没办法做到这一点，因为你无法计算每个项目被选入样本的概率。

下面是一个简单的生成器，可以实现这个功能：

def sample_given_size(population, population_size, sample_size):
    for item in population:
        if random.random() < sample_size / population_size:
            yield item
            sample_size -= 1
        population_size -= 1

需要注意的是，这个生成器是按照项目在 population 中出现的顺序来获取的，而不是随机顺序（像 random.sample 或大多数水库抽样代码那样），所以样本的切片不会是随机的子样本！