均匀取样直方图的样本总和

Question

我有一份物品列表，我想从中随机抽取一部分，但每个物品都有一个直方图，直方图分成D个区间。我希望抽取这些物品的方式能让所有物品的直方图加起来后，尽量均匀。

所以，它应该像下面这个抽样函数那样工作：

>>> import numpy
>>> #The histograms from which to sample (each having 5 bins):
>>> data = numpy.random.randint(100, size=(10000,5))
>>> #The function which I'm trying to program:
>>> samples = sample(data,500)
>>> samples.shape
(500,5)
>>> summed_histogram = samples.sum(axis=0)
>>> #Each bin should have approximately equal value
>>> summed_histogram / float(summed_histogram.sum())
array([ 0.2,  0.2,  0.2,  0.2,  0.2])

加起来的直方图的绝对值并不重要，也不需要完全均匀，只要大致均匀就可以了。另外，我不在乎返回的样本数量是否和我指定的样本数量完全一致。抽样时要确保不重复。

Answer 1

你能随机抽取一些完整的样本（比如500个），然后选出其中最均匀的一个吗？也就是说，选择那个标准差最低的样本（用sample.sum(axis=0).std()来计算）。这样可以避免在逐步抽样时出现奇怪的偏差。

Answer 2

为了更好地理解@Ilmari Karonen的解决方案，你需要为每个直方图计算权重，然后根据这些权重进行抽样。根据你的目标，我觉得最有效的方法是使用线性规划。

设D_ij为第i个项目中第j个箱子的权重。如果每个项目都有一个权重w_i，那么“汇总直方图”的权重就是所有项目的权重w_i乘以D_ij的总和。要获得“尽可能均匀”的分布，可以通过最小化各个箱子之间的最大差异来实现，因此我们需要解决以下线性规划问题：

minimize z
subject to (for all j, k) 
    z >= (sum i in items) w_i D_ij - (sum i in items) w_i D_ik
    z >= (sum i in items) w_i D_ik - (sum i in items) w_i D_ij

上面的意思是z >=所有加权箱子对之间差异的绝对值。要解决这个线性规划问题，你需要一个单独的工具包，因为numpy本身没有线性规划求解器。可以参考这个链接，它提供了使用cplex的解决方案，或者这个链接，它提供了使用cvxpy的解决方案。请注意，你需要对权重设置一些限制（例如，每个权重必须大于或等于0），这些解决方案都有这样的设置。其他GLPK（GNU线性规划工具包）的Python绑定可以在这里找到：http://en.wikibooks.org/wiki/GLPK/Python。

最后，你只需根据权重w_i从直方图i中进行抽样。这可以通过使用cumsum和searchsorted的轮盘选择方法来实现，具体可以参考@Ilmari Karonen的建议，查看这个链接。

如果你希望得到的加权分布“尽可能均匀”，我会解决一个类似的权重问题，但要最大化加权箱子总和的加权熵。这个问题看起来是非线性的，不过你可以使用许多非线性求解器，比如BFGS或基于梯度的方法。这个方法可能会比线性规划慢一些，但具体取决于你的应用需求。如果你有很多直方图，线性规划方法会非常接近非线性方法，因为达到均匀分布会比较容易。

在使用线性规划解决方案时，由于约束条件较少，很多直方图的权重可能会变为0，但如果箱子的数量不小，这不会成为问题，因为约束的数量是O(n^2)。

以下是50个直方图和10个箱子的示例权重：

[0.006123642775837011, 0.08591660144140816, 0.0, 0.0, 0.0, 0.0, 0.03407525280610657, 0.0, 0.0, 0.0, 0.07092537493489116, 0.0, 0.0, 0.023926802333318554, 0.0, 0.03941537854267549, 0.0, 0.0, 0.0, 0.0, 0.10937063438351756, 0.08715770469631079, 0.0, 0.05841899435928017, 0.016328676622408153, 0.002218517959171183, 0.0, 0.0, 0.0, 0.08186919626269101, 0.03173286609277701, 0.08737065271898292, 0.0, 0.0, 0.041505225727435785, 0.05033635148761689, 0.0, 0.09172214842175723, 0.027548495513552738, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0259929997624099, 0.0, 0.0, 0.028044483157851748, 0.0, 0.0, 0.0]

对于每个有50个箱子的50个直方图，现在几乎没有零值：

[0.0219136051655165, 0.0, 0.028325808078797768, 0.0, 0.040889043180965624, 0.04372501089775975, 0.0, 0.031032870504105477, 0.020745831040881676, 0.04794861828714149, 0.0, 0.03763592540998652, 0.0029093177405377577, 0.0034239051136138398, 0.0, 0.03079554151573207, 0.0, 0.04676278554085836, 0.0461258666541918, 9.639105313353352e-05, 0.0, 0.013649362063473166, 0.059168272186891635, 0.06703936360466661, 0.0, 0.0, 0.03175895249795131, 0.0, 0.0, 0.04376133487616099, 0.02406633433758186, 0.009724226721798858, 0.05058252335384487, 0.0, 0.0393763638188805, 0.05287112817101315, 0.0, 0.0, 0.06365320629437914, 0.0, 0.024978299494456246, 0.023531082497830605, 0.033406648550332804, 0.012693750980220679, 0.00274892002684083, 0.0, 0.0, 0.0, 0.0, 0.04465971034045478, 4.888224154453002]