15

我有一系列事件流过我的服务器。存储所有这些对我来说是不可行的，但我希望能够定期汇总处理其中一些。所以，我想保留一个流的子集，它是我所看到的所有内容的随机采样，但限制为最大大小。

因此，对于每个新项目，我需要一个算法来决定是否应该将其添加到存储的集合中，或者是否应该丢弃它。如果我添加它，并且我已经达到了我的极限，我需要一个算法来驱逐一个旧项目。

显然，只要我低于我的限制（只需保存所有内容），这很容易。但是，一旦超过该限制，我如何才能保持良好的随机抽样而不偏向旧项目或新项目？

谢谢，

4

6 回答 6

6

这称为随机抽样。资料来源：http ://en.wikipedia.org/wiki/Reservoir_sampling

array R[k];    // result
integer i, j;

// fill the reservoir array
for each i in 1 to k do
    R[i] := S[i]
done;

// replace elements with gradually decreasing probability
for each i in k+1 to length(S) do
    j := random(1, i);   // important: inclusive range
    if j <= k then
        R[j] := S[i]
    fi
done

一个体面的解释/证明： http: //propersubset.com/2010/04/choosing-random-elements.html

于 2014-01-30T21:22:28.653 回答
6

这是一个常见的面试问题。

一种简单的方法是以概率 k/n（或 1，以较小者为准）保存第 n 个元素。如果您需要删除一个元素来保存新样本，请逐出一个随机元素。

这为您提供了 n 个元素的均匀随机子集。如果你不知道n，你可以估计它并得到一个近似一致的子集。

于 2010-12-02T22:27:19.537 回答
1

虽然这篇论文并不是您正在寻找的内容，但它可能是您搜索的一个很好的起点。

于 2010-12-02T22:04:19.557 回答
1

将样本存储在先进先出 (FIFO) 队列中。

设置样本之间如此多事件的采样率，或将其随机化 - 取决于您的事件模式。

保存每第 n 个事件，或者只要您的费率告诉您保存，然后将其放在队列的末尾。

如果尺寸太大，从顶部弹出一个。

于 2010-12-02T22:04:33.800 回答
1

这是假设您不知道将收到的事件总数，并且您不需要子集中的最少元素数。

arr = arr[MAX_SIZE] //Create a new array that will store the events. Assuming first index 1.
counter = 1 //Initialize a counter.

while(receiving event){
  random = //Generate a random number between 1 and counter
  if( counter == random ){
     if( counter <= MAX_SIZE ){
        arr[counter] = event
     }
     else{
        tmpRandom = //Generate a random number between 1 and MAX_SIZE
        arr[tmpRandom] = event
     }
  }
  counter =+ 1

}
于 2010-12-02T22:13:57.210 回答
0

分配记录每个事件的概率并将事件存储在可索引的数据结构中。当结构的大小达到阈值时，删除随机元素并添加新元素。在 Ruby 中，您可以这样做：

@storage = []
prob = 0.002

while ( message = getnextMessage) do
    @storage.delete((rand() * @storage.length).floor) if @storage.length > MAX_LEN
    @storage << message if (rand() < prob) 
end

这解决了您的最大尺寸和您对事件发生时间的无偏见。您还可以通过将存储的元素划分到存储桶中，然后从具有多个元素的任何存储桶中删除一个元素来选择删除哪个元素。例如，bucket 方法允许您每小时保留一个。

您还应该知道抽样理论是大数学。如果您需要的不仅仅是外行的想法，您应该咨询您所在地区的合格数学家。

于 2010-12-02T22:13:22.393 回答