流数据的直方图近似

Question

这个问题稍微延伸了这里回答的问题.我正在努力重新实现本文第2.1节中的直方图近似版本,并且我想在再次开始此过程之前连接所有的鸭子.上次,我用过boost::multi_index,但性能并不是最大的,我想避免插入/发现复杂性的桶数量的对数std::set.由于我正在使用的直方图的数量(随机森林中随机树的每个叶节点每个特征一个),计算复杂度必须尽可能接近常数.

用于实现直方图的标准技术涉及将输入实际值映射到箱号.要做到这一点,一种方法是:

1. 初始化一个大小为N的标准C数组,其中N =二进制数; 和
2. 将输入值(实数)乘以某个因子,并将结果置于C数组中以获得其索引.

这适用于具有统一箱尺寸的直方图,并且非常有效.然而,上面链接的论文的2.1节提供了没有统一的箱尺寸的直方图算法.

另一个问题是,简单地将输入实际值乘以一个因子,并使用得到的产品作为索引,以负数表示失败.为了解决这个问题,我考虑在数组中的某处识别一个'0'bin.这个箱子将以0.0为中心; 它上面/下面的垃圾箱可以使用刚才解释的相同的乘法和平面方法计算,稍作修改,将地板产品加到两个或根据需要减去两个.

然后,这引出了合并的问题:本文中的算法合并了两个最接近的箱,从中心到中心测量.在实践中,这会产生"锯齿状"直方图近似值,因为某些箱子会有非常大的数量,而其他箱子则不会.当然,这是由于不均匀尺寸的箱,并且不会导致任何精度损失.然而,如果我们试图将非均匀尺寸的箱子标准化以制造均匀,则会发生精度损失.这是因为假设m/2样本落在bin中心的左侧和右侧,其中m = bin计数.我们可以将每个bin建模为高斯,但这仍然会导致精度损失(尽管很小)

这就是我现在被困住的地方,导致了这个主要问题:实现直方图接受流数据并将每个样本存储在统一大小的容器中的最佳方法是什么？

Answer 1

保留四个变量.

int N;  // assume for simplicity that N is even
int count[N];
double lower_bound;
double bin_size;

当新样本x到达时,计算double i = floor(x - lower_bound) / bin_size.如果i >= 0 && i < N,然后递增count[i].如果i >= N,那么反复加倍,bin_size直到x - lower_bound < N * bin_size.每增加一倍,调整计数(通过利用多次倍增的稀疏性来优化这一点).

for (int j = 0; j < N / 2; j++) count[j] = count[2 * j] + count[2 * j + 1];
for (int j = N / 2; j < N; j++) count[j] = 0;

这种情况i < 0比较棘手,因为我们需要减少lower_bound和增加bin_size(再次,优化稀疏性或一步调整计数).

while (lower_bound > x) {
    lower_bound -= N * bin_size;
    bin_size += bin_size;
    for (int j = N - 1; j > N / 2 - 1; j--) count[j] = count[2 * j - N] + count[2 * j - N + 1];
    for (int j = 0; j < N / 2; j++) count[j] = 0;
}

特殊情况很昂贵,但在初始箱尺寸的数据范围内仅发生对数次数.

如果以浮点形式实现它,请注意浮点数不是实数,并且语句lower_bound -= N * bin_size可能行为不正确(在这种情况下,如果N * bin_size小于lower_bound).我建议bin_size在任何时候都是基数(通常是两个)的幂.