我如何生成点相匹配的直方图?
-
05-07-2019 - |
题
我工作的一个模拟系统。我很快就会有实验数据(图),用于现实世界的分布值的几个模拟的投入。
模拟时运行,我想要能够产生随机数值相匹配的测量的分布。我宁愿做到这一点没有储存原来的直方图。什么是一些很好的方式
- 映射图以一组参数表示的分配?
- 生成的价值观,根据这些参数在运行时?
编辑:输入的数据是事件持续时间为几个不同类型的事件。我希望,不同类型将有不同的分配的功能。
解决方案
至少有两个选择:
- 整合的直方图和转化数值。
- 拒绝
数字集成
从 计算在现代物理学 由William R.Gibbs:
人们总是可以用数字整合的[功能]和反[cdf] 但这往往是不十分令人满意,尤其是如果 pdf 是改变 迅速。
你从字面上建立一个表转换的范围 [0-1)
进入适当的范围内在目标的分发。然后把你的通常的(高质量的)养恤金条例》和翻译与表。它是麻烦,但是明确的、可行的和完全一般。
拒绝:
规范化目标的直方图,然后
- 扔骰子选择一个职位(
x
)沿范围。 - 扔一遍,选择这一点上,如果新的随机数量少于归一化的直方图在这站。否则goto(1).
再次,头脑简单但是明确和工作。它可以是缓慢的,用于分发了很多概率非常低(峰值有长长的尾巴).
与这两种方法,你 可以 近似的数据与分段的多项式适合或花键产生平稳的曲线,如果一个步骤功能的直方图是不希望的但离开,对于后来作为它可能为时过早的最优化。
更好的方法可能存在的特殊情况。
所有这一切都是相当标准和应该出现在任何数据分析的教科书,如果我更详细的是需要的。
其他提示
有关此问题的更多信息将非常有用。例如,直方图是什么类型的值?它们是绝对的(例如,颜色,字母)还是连续的(例如,高度,时间)?
如果直方图超出分类数据,我认为除非类别之间存在许多相关性,否则可能难以对分布进行参数化。
如果直方图超过连续数据,您可能会尝试使用高斯混合物拟合分布。也就是说,尝试使用$ \ sum_ {i = 1} ^ n w_i N(m_i,v_i)$拟合直方图,其中m_i和v_i是均值和方差。然后,当你想要生成数据时,首先从1..n中采样i,其概率与权重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的数值积分答案。或者,您可以使用别名,并将点存储在左侧,并在两点之间选择一个统一的数字。
从直方图(原始或缩小)中进行选择, Walker的别名方法 快速而简单。