迭代或惰性储层采样

Question

我非常熟悉使用Reservoir Sampling在一次通过数据的过程中从一组未确定的长度中采样.在我看来,这种方法的一个限制是它仍然需要在返回任何结果之前传递整个数据集.从概念上讲,这是有道理的,因为必须允许整个序列中的项目有机会替换先前遇到的项目以获得统一的样本.

有没有办法在整个序列评估之前能够产生一些随机结果？我正在考虑那种适合python的伟大的itertools库的懒惰方法.也许这可以在一些给定的容错范围内完成？我很感激有关这个想法的任何反馈!

为了澄清这个问题,这个图总结了我对不同采样技术的内存与流媒体权衡的理解.我想要的是属于Stream Sampling的类别,我们事先并不知道人口的长度.

显然,由于我们很可能将样本偏向人口的开头,因此不知道先验长度并且仍然得到统一样本存在看似矛盾.有没有办法量化这种偏见？是否需要权衡利弊？有没有人有一个聪明的算法来解决这个问题？

Answer 1

如果您事先知道可迭代产生的项目总数population,则可以在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

请注意,生成器按照它们在总体中出现的顺序生成项目(不是按随机顺序,如random.sample大多数储层采样代码),因此样本的切片将不是随机子样本!