4

我正在尝试实现 A-Chao 版本的加权水库采样，如https://en.wikipedia.org/wiki/Reservoir_sampling#Algorithm_A-Chao所示

但是我发现wiki中描述的伪代码似乎是错误的，尤其是在初始化部分。我读了这篇论文，它提到我们需要处理权重过大的数据点，但我仍然不知道如何正确初始化。

据我了解，在初始化步骤中，我们要确保选择的所有初始数据点都应该具有相同的概率*权重。但是，我不明白超重点与此有何关系。

我根据wiki实现的代码，但结果显示它是不正确的。

const reservoirSampling = <T>(dataList: T[], k: number, getWeight: (point: T) => number): T[] => {
  const sampledList = dataList.slice(0, k);
  let currentWeightSum: number = sampledList.reduce((sum, item) => sum + getWeight(item), 0);
  for (let i = k; i < dataList.length; i++) {
    const currentItem = dataList[i];
    currentWeightSum += getWeight(currentItem);
    const probOfChoosingCurrentItem = getWeight(currentItem) / currentWeightSum;
    const rand = Math.random();
    if (rand <= probOfChoosingCurrentItem) {
      sampledList[getRandomInt(0, k - 1)] = currentItem;
    }
  }
  return sampledList;
};
4

1 回答 1

1

获得 Chao 算法产生的分布的最佳方法是在Cohen 等人介绍 VarOpt k采样的论文中标记为算法 1 的伪代码中实现 VarOpt k采样。

这是一个 arXiv 链接，因此非常稳定，但总而言之，这个想法是将项目分为“重”（重量足够高以保证包含在样本中）和“轻”（其他）。将较重的项目保留在优先队列中，以便轻松移除最轻的项目。当一个新物品进来时，我们必须确定它是重还是轻，哪些重的物品变轻了（如果有的话）。然后有一个抽样程序，用于丢弃一个项目，该项目专门使用加权抽样处理重→轻项目，然后回退到选择一个均匀的随机轻项目（如 Chao 算法的简单案例）。

伪代码的一个技巧是，如果你使用浮点运算，你必须小心“不可能”的情况。在 Code Review 上发布您完成的代码，如果您需要反馈，请在此处联系我。

于 2019-10-20T14:29:06.583 回答