Как создать точки, соответствующие гистограмме?

Ответ 1

Как минимум два варианта:

• Интегрируйте гистограмму и инвертируйте ее число.
• Отрицание

Числовое интегрирование

Из вычислений в современной физике Уильяма Р. Гиббса:

Всегда можно численно интегрировать [функцию] и инвертировать [cdf] но это часто не очень удовлетворительно, особенно если PDF меняется быстро.

Вы буквально создаете таблицу, которая переводит диапазон [0-1) в соответствующие диапазоны в целевом дистрибутиве. Затем бросьте свой обычный (высококачественный) PRNG и переведите со столом. Он громоздкий, но ясный, работоспособный и полностью общий.

Отказ:

Нормализовать целевую гистограмму, затем

• Бросьте кости, чтобы выбрать позицию (x) по диапазону случайным образом.
• Бросьте еще раз и выберите эту точку, если новое случайное число меньше, чем нормализованная гистограмма в этом бункере. В противном случае goto (1).

Опять же, простой, но понятный и работающий. Это может быть медленным для распределения с очень низкой вероятностью (пики с длинными хвостами).

При использовании обоих этих методов вы можете аппроксимировать данные кусочно-полиномиальными подгонами или сплайнами, чтобы генерировать гладкую кривую, если гистограмма ступенчатой ​​функции не нужна, но оставьте это для более позднего, поскольку это может быть преждевременная оптимизация.

В особых случаях могут существовать лучшие методы.

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

Ответ 2

Дополнительная информация о проблеме будет полезна. Например, каковы значения гистограмм? Являются ли они категоричными (например, цветами, буквами) или непрерывными (например, высотами, временем)?

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

Если гистограммы превышают непрерывные данные, вы можете попытаться соответствовать распределению, используя смеси гауссиан. То есть попытайтесь установить гистограмму с помощью $\ sum_ {i = 1} ^ n w_i N (m_i, v_i) $, где m_i и v_i - среднее значение и дисперсия. Затем, когда вы хотите генерировать данные, сначала вы выбираете я из 1..n с вероятностью, пропорциональной весам w_i, а затем пробуйте x ~ n (m_i, v_i), как и от любого гауссова.

В любом случае, вы можете больше узнать о моделях смесей.

Ответ 3

Итак, кажется, что я хочу, чтобы генерировать данное распределение вероятности, это Quantile Function, которая является обратной из кумулятивная функция распределения, как говорит @dmckee.

Возникает вопрос: каков наилучший способ генерации и хранения функции квантиля, описывающей заданную непрерывную гистограмму? У меня есть ощущение, что ответ будет сильно зависеть от формы ввода - если он следует любому шаблону, должны быть упрощения в самом общем случае. Я обновляю здесь, пока я ухожу.

Edit:

У меня был разговор на этой неделе, который напомнил мне об этой проблеме. Если я откажусь от описания гистограммы в качестве уравнения и просто сохраню таблицу, могу ли я сделать выбор в течение O (1)? Оказывается, вы можете без какой-либо потери точности за счет времени построения O (N lgN).

Создайте массив из N элементов. Единый случайный выбор в массив найдет элемент с вероятностью 1/N. Для каждого элемента храните часть хитов, для которых этот элемент должен быть выбран, и индекс другого элемента, который будет выбран, если этот элемент не выбран.

Взвешенная случайная выборка, реализация C:

//data structure
typedef struct wrs_data {
  double share; 
  int pair;
  int idx;
} wrs_t;


//sort helper
int wrs_sharecmp(const void* a, const void* b) {
  double delta = ((wrs_t*)a)->share - ((wrs_t*)b)->share;
  return (delta<0) ? -1 : (delta>0);
}


//Initialize the data structure
wrs_t* wrs_create(int* weights, size_t N) {
  wrs_t* data = malloc(sizeof(wrs_t));
  double sum = 0;
  int i;
  for (i=0;i<N;i++) { sum+=weights[i]; }
  for (i=0;i<N;i++) {
    //what percent of the ideal distribution is in this bucket?
    data[i].share = weights[i]/(sum/N); 
    data[i].pair = N;
    data[i].idx = i;
  }
  //sort ascending by size
  qsort(data,N, sizeof(wrs_t),wrs_sharecmp);

  int j=N-1; //the biggest bucket
  for (i=0;i<j;i++) {
    int check = i;
    double excess = 1.0 - data[check].share;
    while (excess>0 && i<j) {
      //If this bucket has less samples than a flat distribution,
      //it will be hit more frequently than it should be.  
      //So send excess hits to a bucket which has too many samples.
      data[check].pair=j; 
      // Account for the fact that the paired bucket will be hit more often,
      data[j].share -= excess;  
      excess = 1.0 - data[j].share;
      // If paired bucket now has excess hits, send to new largest bucket at j-1
      if (excess >= 0) { check=j--;} 
    }
  }
  return data;
}


int wrs_pick(wrs_t* collection, size_t N)
//O(1) weighted random sampling (after preparing the collection).
//Randomly select a bucket, and a percentage.
//If the percentage is greater than that bucket share of hits, 
// use it paired bucket.
{
  int idx = rand_in_range(0,N);
  double pct = rand_percent();
  if (pct > collection[idx].share) { idx = collection[idx].pair; }
  return collection[idx].idx;
} 

Изменить 2: После небольшого исследования я счел возможным сделать конструкцию в O (N) времени. При тщательном отслеживании вам не нужно сортировать массив, чтобы найти большие и маленькие бункеры. Обновлена ​​реализация здесь

Ответ 4

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

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

Ответ 5

Чтобы выбрать гистограмму (исходную или уменьшенную) Метод псевдонима Walker быстро и просто.

Ответ 6

Для нормального распределения может помочь следующее:

http://en.wikipedia.org/wiki/Normal_distribution#Generating_values_for_normal_random_variables