我如何生成点相匹配的直方图?
https://stackoverflow.com/questions/423006
-
05-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russian题
我工作的一个模拟系统。我很快就会有实验数据(图)，用于现实世界的分布值的几个模拟的投入。
模拟时运行，我想要能够产生随机数值相匹配的测量的分布。我宁愿做到这一点没有储存原来的直方图。什么是一些很好的方式
- 映射图以一组参数表示的分配？
- 生成的价值观，根据这些参数在运行时?
编辑：输入的数据是事件持续时间为几个不同类型的事件。我希望，不同类型将有不同的分配的功能。
解决方案
至少有两个选择：
- 整合的直方图和转化数值。
- 拒绝
数字集成
从 计算在现代物理学 由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的别名方法 快速而简单。
