algorithm - 如何保持动态直方图？

Question

是否有已知的算法+数据结构来维护动态直方图？

假设我有一个数据流 (x_1, w_1) , (x_2, w_2), ... 其中 x_t 是 double ，代表一些测量变量，w_t 是相关权重。

我可以做显而易见的事情(伪 python 代码):

x0,xN = 0, 10
numbins = 100
hist = [(x0 + i * delta , 0) for i in xrange(numbins)]
def updateHistogram(x, w):
    k = lookup(x,  hist)    #find the adequated bin where to put x
    hist[k][1] += 1

但是当我有连续的数据流时，我会遇到一些问题。我手上没有完整的数据集，我必须在数据收集之间检查直方图。我没有期望:

• 理想的垃圾箱尺寸，不会产生大量空垃圾箱，
• 数据范围

所以我想动态定义垃圾箱。我可以做傻事:

 for x in data_stream:
      data.append(x)
      hist = make_histogram(data)

但我想这会很快变慢......

如果所有权重都相等，我认为其中一件事是将数据存储在排序数组中，并以保持数组排序的方式插入新数据。这样我就可以:

data = sortedarray();
for x in data_stream:
     data.insert(x)
     bins = [ data[int(i * data.size()/numbins)] for i in xrange(numbins)]

并且每个 bin 内的计数将等于所有 bin 的 data.size()/numbins。

虽然我想不出一种方法来将权重包括在内……有人有什么建议吗？ (也欢迎了解执行此操作的 C++ 库)。

编辑:(要求澄清)

x_t 是 float 。要计算直方图，我必须将 x 所属的连续范围划分为多个 bin。所以我会有一个数字序列 bin[0]、bin[1] 等...所以我必须确定我做什么 bin[i] < x < bin[i+1]。

当您事先拥有所有数据时，通常就是这样绘制直方图。然后您就会知道 max(x) 和 min(x) 的限制，并且很容易确定足够的 bin。例如，您可以让它们在 min(x) 和 max(x) 之间等距分布。

如果您事先不知道范围，则无法确定 bin。您可能会收到一个不属于任何垃圾箱的 x。或者您可能有很多空箱，因为您选择的范围太大而无法创建箱。

Answer 1

如何确定bin的数量

确定 number of bins 有很多规则在直方图中。对于您的问题，我会选择 Scott 的选择:

bin_width = 3.5*sd*n^{-1/3}

其中 sd 是标准偏差，n 是数据点的数量。至关重要的是，您可以使用 online计算标准偏差的算法。 bin 的数量 k 由下式给出:

k = ceil((max(x) - min(x))/bin_width)

存储数据

假设我们已经观察到 N 个数据点。然后是标准差的置信区间，

Lower limit: sd*sqrt((N-1)/CHIINV((alpha/2), N-1))
Upper limit: sd*sqrt((N-1)/CHIINV(1-(alpha/2), N-1))

其中 CHIINV 是来自卡方分布的值。当 N = 1000 时，sd 的 CI 为:

(0.96*sd, 1.05*sd)

因此，bin 宽度的 95% CI 为:

(3.5*0.96*sd*1000^{-1/3}, 3.5*1.05*sd*1000^{-1/3})
(0.336*sd, 0.3675*sd)

对于 bin 的数量，您可以获得类似的结果。

算法

1. 存储所有数据，直到您对最佳 bin 宽度有一个好的估计，比如当 bin 数量的下限和上限 CI 相等时。
2. 创建 bin 的数量并将数据放入 bin。
3. 所有新的数据点都被放入容器中，然后被丢弃。

评论

1. Freedman–Diaconis 规则更适合选择 bin 的数量，但它涉及到分位数范围，这在网上计算起来有点棘手。
2. 从技术上讲，当数据是连续的时，CI 间隔是不正确的。但是，如果您设置一个合理的最小数据点数来观察，比如 ~100 或 1000，您应该没问题。
3. 这假设数据都遵循相同的分布。
4. bin 的数量取决于 n^{-1/3}。如果您大致知道预期有多少个点，即 10^5、10^6 或 10^7，那么您可以创建更小的 bin 并期望在将来更改 bin 宽度。