3

对于我正在处理的应用程序，我需要从一个非常大的数据集中抽取一小组值，从大约 60 万亿（并且还在增长）中抽取大约几百个值。

通常我使用查看均匀随机数 r (0..1) 是否小于 S/T 的技术，其中 S 是我仍然需要的样本项目数，T 是我在集合中的项目数还没考虑。

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

我希望有一种简单的方法可以做到这一点，并按照 S/T 测试的方式创建一个公正的样本。

  • 老实说，大致不偏不倚就可以了。

  • 这与此人的问题有关（或多或少是后续问题）：

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

  • 还有一个问题……第一个展示给我看的人称它为“邮递员算法”，但我不确定他是否在拉我的腿。是对的吗？
4

2 回答 2

2

这个怎么样：

  • 预先计算从 0 到数据集大小的 S 个随机数。
  • 订购您的号码，从低到高
  • 将连续数字之间的差异存储为跳过大小
  • 使用上面的跳过大小迭代大型数据集。

...假设您收集样本的顺序无关紧要

于 2013-04-03T21:52:48.810 回答
1

所以我想了想，得到了一些帮助http://math.stackexchange.com

归结为：

  • 如果我一次随机选择n 个项目，第一个会落在哪里？也就是说，min({r_1 ... r_n})。math.stackexchange 的一位乐于助人的人将其归结为以下等式：

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

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

  • 如果我生成一个统一的随机数并将其插入r，它的分布与min({r_1 ... r_n})相同 - 与最低项目下降的方式相同。瞧！我刚刚模拟了选择第一项，就好像我随机选择了所有n一样。

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

  • 重复直到n为 0

这样，如果我有一个大数据库（如 Mongo），我可以跳过、find_one、skip、find_one 等。直到我拥有我需要的所有项目。

我遇到的唯一问题是我的实现有利于列表中的第一个和最后一个元素。但我可以忍受。

在 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)
于 2013-04-10T06:39:42.080 回答