Как мне сгенерировать точки, соответствующие гистограмме?
https://stackoverflow.com/questions/423006
-
05-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianВопрос
Я работаю над системой моделирования.Вскоре у меня будут экспериментальные данные (гистограммы) для реального распределения значений для нескольких входных данных моделирования.
Когда моделирование будет запущено, я хотел бы иметь возможность выдавать случайные значения, соответствующие измеренному распределению.Я бы предпочел сделать это без сохранения исходных гистограмм.Каковы некоторые хорошие способы
- Сопоставление гистограммы с набором параметров, представляющих распределение?
- Генерирование значений, основанных на этих параметрах во время выполнения?
Редактировать:Входными данными являются длительности событий для нескольких различных типов событий.Я ожидаю, что разные типы будут иметь разные функции распределения.
Решение
Как минимум два варианта:
<Ол>Числовая интеграция
Из Вычисления в современной физике Уильяма Р. Гиббса:
Всегда можно численно интегрировать [функцию] и инвертировать [ cdf ] но это часто не очень удовлетворительно, особенно если меняется pdf быстро.
Вы буквально строите таблицу, которая переводит диапазон [0-1) в соответствующие диапазоны в целевом распределении. Затем бросьте свой обычный (качественный) PRNG и переводите со стола. Это громоздко, но понятно, выполнимо и совершенно общее.
Отказ:
нормализуйте целевую гистограмму, затем
<Ол> x ) вдоль диапазона. Опять же, простой, но понятный и работающий. Распространение может быть медленным с очень малой вероятностью (пики с длинными хвостами).
<Ч>Используя оба этих метода, вы можете аппроксимировать данные кусочно-полиномиальными подгонками или сплайнами, чтобы получить гладкую кривую, если гистограмма пошаговой функции нежелательна, но оставить ее на потом, как это может быть преждевременная оптимизация. <Ч>
Лучшие методы могут существовать для особых случаев.
Все это довольно стандартно и должно появиться в любом учебнике по числовому анализу, если мне потребуется больше подробностей.
Другие советы
Было бы полезно получить дополнительную информацию о проблеме. Например, над какими значениями находятся гистограммы? Они категоричны (например, цвета, буквы) или непрерывны (например, высота, время)?
Если гистограммы превышают категориальные данные, я думаю, что может быть сложно параметризовать распределения, если между категориями нет большого количества корреляций.
Если гистограммы превышают непрерывные данные, вы можете попытаться согласовать распределение, используя смеси гауссианов. То есть попробуйте подогнать гистограмму, используя $ \ sum_ {i = 1} ^ n w_i N (m_i, v_i) $, где m_i и v_i - среднее значение и дисперсия. Затем, когда вы хотите сгенерировать данные, вы сначала выбираете a i из 1..n с вероятностью, пропорциональной весам w_i, а затем выбираете x ~ n (m_i, v_i), как если бы вы использовали любой гауссиан.
В любом случае, вы можете захотеть узнать больше о моделях смесей .
Итак, кажется, что то, что я хочу для генерации заданного распределения вероятности, - это Квантильная функция, что является обратным по отношению к кумулятивная функция распределения, как говорит @dmckee.
Возникает вопрос:Каков наилучший способ сгенерировать и сохранить квантильную функцию, описывающую данную непрерывную гистограмму?У меня такое чувство, что ответ будет сильно зависеть от формы входных данных - если он следует какому-либо шаблону, то в самом общем случае должны быть упрощения.Я буду обновлять информацию здесь по ходу дела.
Редактировать:
На этой неделе у меня был разговор, который напомнил мне об этой проблеме.Если я откажусь от описания гистограммы в виде уравнения и просто сохраню таблицу, смогу ли я выполнить выборку за 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's share of hits,
// use it's 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) времени.При тщательном отслеживании вам не нужно сортировать массив, чтобы найти большие и маленькие ячейки. Обновленная реализация здесь
Если вам нужно получить большое количество выборок с взвешенным распределением дискретных точек, посмотрите на ответ на аналогичный вопрос .
Однако, если вам нужно аппроксимировать некоторую непрерывную случайную функцию с помощью гистограммы, тогда, вероятно, лучшим вариантом будет числовой интеграционный ответ dmckee. Кроме того, вы можете использовать псевдонимы и сохранить точку слева и выбрать одинаковое число между двумя точками.
Чтобы выбрать из гистограммы (оригинал или уменьшенная), метод псевдонима Уокера это быстро и просто.
Для нормального распространения может помочь следующее:
http://en.wikipedia.org/wiki/Normal_distribution#Generating_values_var>var
