如何从一个非常大的数据集中获取无偏随机样本？

Question

我正在开发一个应用程序，需要从一个非常大的数据集中抽取一小部分值，数量级在60万亿左右（并且还在增长）。

通常，我使用一种技术来判断是否一个均匀随机数r（0..1）小于S/T，其中S是我仍然需要的样本项数，T是我尚未考虑的集合中的项目数。

然而，对于这个新数据，我没有时间为每个值掷骰子；太多了。相反，我想生成一个要“跳过”的条目的随机数量，选择下一个位置的值，然后重复。这样我就可以只掷骰子并访问列表S次。（S是我想要的样本大小。）

我希望有一种简单的方法来实现这一点，并创建一个无偏样本，类似于S/T测试。

- 老实说，近似无偏也可以。 - 这与此人的问题相关（或多或少是一个后续问题）。

https://math.stackexchange.com/questions/350041/simple-random-sample-without-replacement

• 还有一个附带问题...第一个向我展示这个的人称其为“邮递员算法”，但我不确定他是否在开玩笑。这是正确的吗？

- sea-rob

---

一个随机分发信件的邮递员？听起来很糟糕 =P 根据名称，也许他是指“旅行商问题”？无论如何，从0到1中选择S个随机数，并将它们乘以所有项目的数量以获得数据集中的索引。请注意，在选择下一个随机数时留出已选数字是您需要考虑的事情。 - Sean Connolly

这里有一个类似的问题 https://stats.stackexchange.com/questions/141238/how-to-make-an-effective-sampling-from-a-database-of-text-documents，其中有一个给出原则性、精确算法的答案。 - kjetil b halvorsen

Answer 1

这个怎么样：

• 预先计算从0到数据集大小的S个随机数。
• 将数字按低到高的顺序排序。
• 将连续数字之间的差存储为跳过大小。
• 使用上述跳过大小遍历大型数据集。

...假设收集样本的顺序不重要。

- Stanley

Answer 2

所以我考虑了一下，并从http://math.stackexchange.com得到了一些帮助

归结起来就是这样:

• 如果我一次性随机选择n个项目，第一个会落在哪里？也就是说，min({r_1 ... r_n})。数学堆栈交换的一位好心人将其简化为以下方程：

x = 1 - (1 - r) ** (1 / n)

也就是说，分布将是1减去(1 - r)的n次方。然后解出x。非常容易。

• 如果我生成一个均匀分布的随机数，并将其代入r，这个分布与min({r_1 ... r_n})相同--就像最低项会掉落的方式一样。瞧！我刚刚模拟了挑选第一项，就好像我已经随机选择了所有n。

• 所以我跳过列表中那么多项，选择那一项，然后...

• 重复直到n为0

这样，如果我有一个大型数据库（比如Mongo），我可以跳过，找到一个，跳过，找到一个，等等，直到我获得所有我需要的项目。

唯一的问题是我的实现偏爱列表中的第一个和最后一个元素。但我可以接受这一点。

在Python 2.7中，我的实现看起来像：

def skip(n):
    """
    Produce a random number with the same distribution as
    min({r_0, ... r_n}) to see where the next smallest one is
    """
    r = numpy.random.uniform()
    return 1.0 - (1.0 - r) ** (1.0 / n)


def sample(T, n):
    """
    Take n items from a list of size T
    """
    t = T
    i = 0
    while t > 0 and n > 0:
        s = skip(n) * (t - n + 1)
        i += s
        yield int(i) % T
        i += 1
        t -= s + 1
        n -= 1

if __name__ == '__main__':

    t = [0] * 100
    for c in xrange(10000):
        for i in sample(len(t), 10):
            t[i] += 1  # this is where we would read value i

    pprint.pprint(t)

- sea-rob