database - 从无限流中选择 10% 的随机数

Question

一串数字传来。在任何时候，我都可能需要 10% 的随机数。我显然不想存储整个流。

更大的问题是我正在考虑上述算法。我有很多数据（基于时间戳）进入数据库。现在我还想构建一个示例表，其中包含主数据库表中 10% 的记录，但是是随机的，这样如果想要快速查询并且我可以几乎不准确，我可以快速查询。我批量收到消息（数字）说有时说 100 ，有时说 20 有时 5 等等。

我在想我会在流式传输时这样做，这表明有问题的问题。有人可以为此提出一个好的算法吗？有没有更好的办法 ？

Answer 1

简单的解决方案是只保存每 10 个传入的数据点，但这可能会导致结果有偏差，具体取决于数据的随机程度。

如果您想在输入流上模拟真正随机的 10% 样本，您可以使用平均值为 9 的泊松分布来决定在记录下一个条目之前要跳过多少条目。不过，设置上限可能是个好主意，这样您就不会在数据中遇到罕见但可预见的巨大差距。

Answer 2

公式

以下是我将如何制定问题。让你的（可能是无限的）序列中的项目是i=1,2,...。假设您想0 < z < 1从序列中获取大约的项目，以生成更稀疏的序列。让我们x(i)表示我们是否在我们生成的稀疏序列中包含项目i。

对于任何n连续项目的窗口（您选择n >= 1），您希望项目的预期数量为z*n，但可能与该预期有一些差异。为此，您可以使用（截断的）二项式分布（链接），具有均值z*n和标准差d（您选择的位置d > 0）。n（它在右边被截断，因为当你只需要考虑时，你不可能选择比项目更多的东西n！你也可以在左边截断它说“我总是想要至少 m每个项目中的项目n，哪里m少得多比z*n，但我假设你跳过那个。）

i现在，您可以根据是否包含n-1前面的每个项目来确定您应该在生成的稀疏序列中包含该项目的概率i-1,i-2,...,i-(n-1)：

A = P( x(i) = 1 | x(i - j), 1 <= j < n )

这是什么意思呢？

公式化的方式，你选择三个数字：

• 0 < z < 1
  • 在您的问题中，您已指定z为 10% - 即，z = 0.1
• n >= 1和d > 0
  • 将n其视为窗口大小
  • 将d其视为从常规采样到更嘈杂的采样模式的偏差量
  • n = 1i表示“以概率包含每个项目，而与z其他项目是否包含在稀疏序列中无关
  • n = 100, d = 0.0001意思是“除了在极少数情况下，包括稀疏序列中10的每个连续100项目”
    • 如果你做d的非常小，你基本上是在说“1/z以常规模式选择每一个项目”
  • n = 100, d = 5表示“在稀疏序列中5大致包含15每个连续项目”100

Answer 3

以你在评论中的例子：

• 数据之间没有相关性。
• 您想要在一天中的特定时间获得样品。

在这种情况下，您可以跟踪在每个时间间隔内通过的数据总数 - 例如，餐厅每半小时营业一次。（或者甚至只是一个 0 到 9 的计数器，当你达到 10 时它会重置为零。）

抓住每个时间间隔内看到的第一个，让九个掉在地板上。

冲洗并重复，您应该为每个时间间隔建立良好的 10% 采样。