我正在寻找一种优雅且高效的方式来表示和存储由显式抽样构建的任意概率分布。
该分布应具有以下特性：
[-4000; 4000]a、b，|a - b| < 40通常的表示方法——直方图数组——并不理想，主要是因为量化/分辨率和空间之间的权衡。我想象中必须有一种表示方法，根据局部“复杂性”自适应地变化bin大小。
空间是一个问题，因为更高级别的类似网格的数据结构将包含成千上万个单元格，每个单元格至少包含一个这样的概率表示。易于磁盘或网络传输的序列化是可取的，但效率不是优先考虑的因素。
任何帮助都将不胜感激。
struct Distribution
{
virtual ~Distribution() {};
virtual double integrate(std::function<double(double)>) = 0;
};
struct SampledDistribution
{
double integrate(std::function<double(double)> f)
{
double acc = 0;
for (double x: samples) acc += f(samples);
return acc / samples.size();
}
std::deque<double> samples;
};
integrate来生成系数，并将其序列化。如果积分估计器产生的方差很高，则可以丢弃系数。Distribution对象，其integrate方法针对小波执行积分。可以使用您喜欢的数值积分方法进行积分。我在这里故意保持模糊，因为实际实现取决于您选择的小波族（平滑、紧支撑、正交或非正交等）。无论如何，您都需要深入研究文献以获取详细信息。我强烈建议您查看SciPy中提供的所有分布模型。它们与这个问题密切相关，而且任何我想出来的旨在解决分辨率粒度问题的特定算法都是他们至少间接考虑过的。
正如此处所提到的，对于多重分辨率数据，八叉树似乎是您所需的正确数据结构表示。您的目标不是包含数据限制在固定区间内的平坦直方图，而是在不同级别的固定粒度下存储扰动数据集。这最类似于JPEG压缩所使用的算法，但还希望从某个粒度和复杂度水平的分布中提取样本。
如果要创建一个分类算法或二分器来填充数据结构，我强烈建议查看像JPEG 2000这样的分解算法，以确定数据中扰动的形状和复杂性。其他方法（例如ID3和C4.5）也可能适用，但我认为简单的向量化分解可能适合您的目的。
另外，如果您在该领域找到更适用的算法，我会非常感兴趣。我直接与对数据中多尺度关系感兴趣的研究人员合作，因此如果您发现更有效的算法，请务必告诉我们！
存储n个分位数。它们将自适应地聚集在众数周围。
假设n是2的幂次方，则可以通过递归地将分位数存储为中位数和“子中位数”的二叉树，将密度（和累积概率）查找限制为O（log（n））。
这样怎么样：
我假设我们从等价于直方图的数据开始，即一个区间列表，其中包含与之关联的样本数。
现在让我们通过从一个包含所有样本的简单直方图开始来构建它的近似值。
对于近似中的所有桶，请考虑将其分成两个桶的中间部分，但只实际分割将产生最佳改进的桶。
重复此过程，直到达到所需的近似值或获得可接受的最大桶数为止。
因此，您需要一种识别最佳拆分桶的方法。我认为新桶与原始桶的一半相比的最大偏差可能有效。
您还需要一些标准来确定何时停止。
我认为这实际上与1D Octree非常相似。您可以在那里寻找高效的实现。
要实际存储近似值，您可以仅使用一个数组存储桶边界和另一个数组存储每个桶的内容。或者使用大小为两倍的一个数组，其中交替存储桶边界和内容值。