1

我需要实施加权水库采样。我参考了这篇博客中提到的论文。我想编写测试用例来对我的实现进行单元测试，并且对如何计算不同元素在水库中的预期概率感到困惑。

我认为它应该与 成比例，但这里(weight_of_element/weight_of_all_elements)提到的测试用例计算它的方式不同。我该怎么做？

4

1 回答 1

0

为了编写测试用例，您确实可以估计选择元素的概率。假设您已经分配了这样的权重：
weights = [1, 5, 8, 2, 5]

现在您正在执行加权水库采样以绘制一个元素。结果中出现元素的概率是多少？它们是(weight_of_element/weight_of_all_elements)：
prob = [0.048, 0.238, 0.381, 0.095, 0.238]

换句话说，如果你重复绘制一个元素 10 6次，你应该有 0.381 * 10 6个第三个元素的实例，0.048 * 10 6个第一个元素的实例，以此类推。大约，当然。

因此，您可以查看第一个元素在 10 6次试验中出现的次数百分比。这应该是大约(weight_of_first_element/weight_of_all_elements). 比较这些值，看看它们是否彼此接近。

所以测试用例可能看起来像这样（伪代码）： 

numTrials = 1000000
histogram = map<int, int>
for i = 1..numTrials:
  element = WeightedReservoir.sample(weights, 1) # draw one element
  histogram[element]++
for i = 1..len(weights):
  real_probability = weights[i] / sum(weights)
  observed_probability = histogram[elements[i]] / numTrials
  assert(abs(real_probability - observed_probability) <= epsilon) # measuring absolute difference, but you can switch to relative difference

有关Java 中的具体实现，请参见此线程。

至于您指出的 Cloudera测试，它遵循不同的逻辑（我在 Python 包numpy测试中也看到了 numpy.random.choice ）：

  1. 抽样例程本质上是概率性的，即非确定性的；
  2. 让我们为随机数生成取一个固定的种子值。将此值嵌入到测试用例中。现在它是完全确定的：多次调用测试用例会产生相同的结果；
  3. 由于结果是确定性的，我们可以手动获得它（对于小输入）。将预期结果嵌入到测试中。

如果您无法控制种子值，则此方法不适合您。

于 2015-09-22T08:43:28.020 回答