1

我在一次采访中遇到了一个问题。

Q - 想象一下，给你一个非常大的数据元素流（5 月份的谷歌搜索查询、圣诞节期间在沃尔玛购买的产品、电话簿中的姓名等等）。您的目标是有效地返回从原始流中均匀分布的 1,000 个元素的随机样本。你会怎么做？

我在寻找 -

  1. 数据集的随机抽样是什么意思？（我的意思是，如果结果为 1，我可以简单地掷硬币并从输入中选择一个字符串，然后这样做直到我有 1000 个样本......）
  2. 这样做时我需要考虑哪些事项？例如..采用连续的字符串可能比采用非连续的字符串更好..重新措辞-如果我随机选择连续的1000个字符串会更好..还是像抛硬币一样一次选择一个字符串更好..

这可能是一个模糊的问题。我试图用谷歌搜索“随机样本数据集”，但没有找到任何相关结果。

4

3 回答 3

3

二进制样本/不样本可能不是正确的答案..假设您要采样 1000 个字符串，并且通过抛硬币来进行..这意味着大约在访问 2000 个字符串之后..您将完成.. 那怎么样其余的字符串？

我读了这篇文章 - http://gregable.com/2007/10/reservoir-sampling.html

这很清楚地回答了这个问题..

让我把摘要放在这里-

简单的解决方案

为您在流中看到的每个元素分配一个随机数，然后始终保留前 1,000 个编号的元素。

油藏取样

创建一个包含 1,000 个元素的容器（数组），并用流中的前 1,000 个元素填充它。从 i = 1,001 开始。在第 1001 步之后，元素 1,001（或与此相关的任何元素）应该在 1,000 个元素的集合中的概率是多少？答案很简单：1,000/1,001。因此，生成一个介于 0 和 1 之间的随机数，如果它小于 1,000/1,001，则应取元素 1,001。如果您选择添加它，则替换随机选择的水库中的任何元素（例如元素 #2）。元素#2 在第 1,000 步时肯定在水库中，它被移除的概率是元素 1,001 被选中的概率乘以 #2 被随机选为替换候选者的概率。该概率为 1,000/1,001 * 1/1,000 = 1/1,001。所以，

这可以扩展到第 i 轮 - 以 1,000/i 的概率保留第 i 个元素，如果您选择保留它，请从水库中替换一个随机元素。此步骤之前的任何元素在储层中的概率为 1,000/(i-1)。它们被移除的概率是 1,000/i * 1/1,000 = 1/i。考虑到它们已经在水库中，每个元素保留的概率是 (i-1)/i，因此在 i 轮后元素在水库中的总体概率是 1,000/(i-1) * (i- 1)/i = 1,000/i。

于 2013-09-09T04:27:28.020 回答
1

我认为你使用了无限这个词有点松散，抽样的前提是每个元素都有平等的机会进入样本，只有当你至少遍历每个元素时才有可能。因此，我将无限翻译为表示您需要单遍解决方案而不是多遍的大量数字。

尽管@abipc 的分析似乎朝着正确的方向，但并不完全正确，但水库采样是一种方法。

如果我们首先清楚我们想要什么，那就更容易了。假设你有 N 个元素（N 个未知），你需要选择 1000 个元素。这意味着我们需要设计一个采样方案，其中任何元素在样本中的概率恰好是 1000/N ，因此每个元素在样本中的概率相同（根据其在原始元素上的位置不偏好任何元素列表）。@abipc 提到的方案工作正常，概率计算是这样的 -

在第一步之后，您有 1001 个元素，因此我们需要以 1000/1001 的概率选择每个元素。我们以该概率选择第 1001 个元素，这样就可以了。现在我们还需要证明每个其他元素也有相同的概率出现在样本中。

p（样品中剩余的任何其他元素）= [ 1 - p（从样品中移除的元素）]

    =  [ 1 - p(1001st element is selected) * p(the element is picked to be removed)
    =  [ 1 - (1000/1001) * (1/1000)] =  1000/1001

太好了，所以现在我们已经证明每个元素都有 1000/1001 的概率出现在样本中。这个精确的论证可以使用归纳法扩展到第 i 步。

于 2013-09-09T16:56:04.327 回答
1

据我所知，这类算法称为水库采样算法。

我从 DataMining 知道其中之一，但不知道它的名称：

  1. 收集存储中的前 S 个元素，其中 max.size 等于 S。
  2. 假设流的下一个元素的编号为 N。
  3. 以概率 S/N 捕获新元素，否则丢弃它
  4. 如果你抓住了元素 N，然后替换同一个 S 中的元素之一，统一挑选它。
  5. N=N+1，获取下一个元素，跳转到 1

理论上可以证明，在这种流处理的任何步骤中，大小为 S 的存储包含具有相等概率 S/N_you_have_seen 的元素。

所以例如 S=10;

N_you_have_seen=10^6

S——有限数；N_you_have_seen - 可以是无限数；

于 2014-04-20T17:00:59.713 回答