直播数据的直方图近似

Question

此问题是answered here的稍微延伸。我正在重新实现在this paper的第2.1节中找到的直方图近似的一个版本，并且我想在再次开始此过程之前将所有的鸭子都连成一排。上次我使用boost::multi_index，但是性能并不是最好的，我想避免在桶的数量上插入对数/发现std::set的复杂性。由于我使用的直方图的数量（随机森林中随机树的每个叶节点的每个特征每个特征一个），计算复杂性必须尽可能接近常数。

用于实现直方图的标准技术涉及将输入实际值映射到箱号。为此，一种方法是：

1. 初始化大小为N的标准C数组，其中N =箱的数量;和
2. 将输入值（实数）乘以某个因子并将结果发送到底以获得C数组中的索引。

这适用于具有均匀分档大小的直方图，效率很高。然而，上述链接文件的第2.1节提供了一个没有统一的容器大小的直方图算法。

另一个问题是，简单地将输入实数值乘以一个因子，并将结果乘积作为索引失败，结果为负数。为了解决这个问题，我考虑在数组中的某个地方标识一个'0'。这个bin将会以0.0为中心;在它之上/之下的箱可以使用刚刚解释的相同的乘法和底板方法来计算，其中稍微修改的是将地板产品添加到两个或根据需要从两个中减去。

这就引发了合并的问题：本文中的算法将两个最接近的二进制数据库合并，如从中心到中心所测量的那样。实际上，这会产生一个“锯齿状”的直方图近似值，因为一些箱子会有非常大的数量，而其他箱子则不会。当然，这是由于非均匀大小的分箱，并且不会导致任何精度损失。但是，如果我们试图规范不均匀大小的箱子来制造制服，会发生精度损失。这是因为假定m/2个样本落在箱中心的左侧和右侧，其中m =箱数。我们可以将每个垃圾桶建模为高斯，但这仍然会导致精度损失（尽管最小）

所以这就是我现在卡住的地方，导致这个主要问题：实施的最佳方式是什么接收流式数据并将每个样本存储在统一大小的分箱中的直方图？

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; 
} 

例外情况很贵，但在数据范围内仅在初始bin大小范围内发生对数次数。

如果实施该浮点，当心，浮点数并不是实数，并且像lower_bound -= N * bin_size语句可能无法正常运作（在这种情况下，如果N * bin_size比lower_bound小得多）。我建议bin_size在任何时候都是基数的权力（通常是两个）。