Инициализация выборки взвешенных коллекторов (реализация A-Chao) - PullRequest
Новая
       2

Инициализация выборки взвешенных коллекторов (реализация A-Chao)

4 голосов
/ 09 октября 2019

Я пытаюсь реализовать A-Chao-версию взвешенной выборки из коллектора, как показано в https://en.wikipedia.org/wiki/Reservoir_sampling#Algorithm_A-Chao

Но я обнаружил, что псевдокод, описанный в вики, кажется неправильным, особенно в части инициализации. Я прочитал документ , в котором упоминается, что нам нужно обрабатывать слишком взвешенные точки данных, но я все еще не могу понять, как правильно инициализировать.

В моем понимании на этапе инициализации мыхотите убедиться, что все выбранные исходные точки данных должны иметь одинаковую вероятность * вес, который будет выбран. Однако я не понимаю, как с этим связаны переоцененные баллы.

Код, который я реализовал в соответствии с вики, но результаты показывают, что он неверен. 

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;
};

1 Ответ

1 голос
/ 20 октября 2019

Лучший способ получить распределение, которое производит алгоритм Чао, - реализовать выборку VarOpt k , как в псевдокоде с меткой Алгоритм 1 из бумаги, в которой была представлена ​​выборка VarOpt k от Cohen и др.

Это ссылка arXiv и, следовательно, очень стабильная, но в итоге идея состоит в том, чтобы разделить элементы на «тяжелые» (достаточно высокие, чтобы гарантировать включение в выборку до сих пор). ) и "свет" (остальные). Храните тяжелые предметы в очереди с приоритетами, где легко удалить самые легкие из них. Когда приходит новый предмет, мы должны определить, тяжелый он или легкий, и какие тяжелые предметы стали легкими (если есть). Затем есть процедура выборки для отбрасывания элемента, который обрабатывает тяжелые → легкие элементы, особенно с использованием взвешенной выборки, а затем возвращается к выбору равномерного случайного легкого элемента (как в простом случае алгоритма Чао).

ОдинУловка с псевдокодом состоит в том, что, если вы используете арифметику с плавающей точкой, вы должны быть немного осторожны с «невозможными» случаями. Разместите свой готовый код в Code Review и отправьте мне пинг, если хотите получить обратную связь.

...