如何保持动态直方图？

Question

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

想象一下,我有一个数据流(x_1,w_1),(x_2,w_2),...其中x_t是双精度数,代表一些测量变量,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是浮点数.要计算直方图,我必须将x所属的连续范围除以多个区间.所以我将有一个数字序列bin [0],bin [1]等...所以我必须确定我做什么bin [i] <x <bin [i + 1].

这是您在预先获得所有数据时通常进行直方图的方法.然后,您将知道极限(x)和min(x)的极限,并且很容易确定足够的箱.例如,你可以让它们在min(x)和max(x)之间等间隔.

如果您事先不知道范围,则无法确定容器.你可以收到一个不属于任何垃圾箱的x.或者你可以使用许多空箱,因为你选择了太大的范围来制作垃圾箱.

Answer 1

如何确定垃圾箱的数量

确定直方图中的箱数有许多规则.对于你的问题,我会选择Scott的选择:

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

其中sd是标准偏差,n是数据点的数量.至关重要的是,您可以使用在线算法来计算标准偏差.箱数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)

您可以获得类似垃圾箱的数量.

算法

1. 存储所有数据,直到您对最佳箱宽有一个很好的估计,比如当箱数的下限和上限相等时.
2. 创建箱数并将数据放入箱中.
3. 所有新数据点都放入箱中,然后丢弃.

评论

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

Answer 2

听起来好像您要实现以下抽象数据类型。

insert(x, w): add item x to the collection with weight x
select(p): return the item greater than a p weighted fraction of the items

例如，select(0)返回最小值，select(0.5)返回加权中位数，然后select(1)返回最大值。

我将以两种方式之一实现此ADT。如果很少进行选择，则将数据放入数组中，并使用线性时间选择算法进行O（1）次插入和O（n）次选择。如果选择频繁，我将使用二进制搜索树，其中每个节点将总权重存储在其子树中。例如，之后

insert(2, 10)
insert(1, 5)
insert(3, 100)
insert(4, 20)

那棵树可能看起来像

   2 (135)
  / \
 /   \
1 (5) 4 (120)
     /
    /
   3 (100)

现在，找到加权中值，乘以135通过0.5并获得67.5如所期望的“指标”。从根开始2，我们发现5小于67.5，因此该项不在左子树中，我们减去5以获得62.5树的其余部分的索引。由于135 - 120 = 15小于62.5，中位数不是2。我们15从中减去62.5得到47.5并下降到4。在4，我们发现100大于47.5，3中位数也是如此。

假设树是平衡的，则insert和的运行时间select为O(log n)。如果我是从头开始实现的，那么我可能会选择一个八卦树。