抽样直方图，使样品上的总和是统一的

我有一个项目的列表，我想从中随机抽样一个子集，但每个项目都与一个直方图配对在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])

的总和直方图的绝对值并不重要，也不需要是完全一致的，它只是需要大致均匀。另外，我不在乎返回的样本大小是否不完全是指定的样本大小。取样应该没有更换。

来源

2013-02-09 CvW

顺便说一句，我想的项目样本是图像块，直方图是手动分割图像的标签直方图。 – CvW 2013-02-09 21:44:30

你可以做的是首先选择你的物品的重量，以使加权总和（大致）一致，然后对这些物品进行加权抽样。第一部分是多变量优化问题，第二部分是相对直接的，例如，使用'cumsum（）'来计算CDF和'searchsorted（）'来对它进行采样。 – 2013-02-11 14:30:42

要扩展@Ilmari Karonen的解决方案，您要做的是计算每个直方图的权重，然后根据这些权重进行采样。在我看来，考虑到您的目标，最有效的方法是使用linear program。

设D_ij为第i项直方图中第j个bin的权重。那么如果每个项目都用权重w_i进行加权，则“总和直方图”将具有权重总和（项目中的i）w_i D_ij。一个办法让你“近似均匀”分布将最大限度地降低箱的最大差异，所以我们将解决以下LP：

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 >=绝对值的箱子。要解决这个LP，你将需要一个单独的包，因为numpy不包含LP解算器。有关使用cplex或this gist的解决方案，请参阅this gist以了解使用cvxpy的解决方案。请注意，您将需要对权重设置一些限制（例如，每个权重大于或等于0），正如这些解决方案所做的那样。其他用于GLPK的Python绑定（GNU线性编程工具包）可以在这里找到：http://en.wikibooks.org/wiki/GLPK/Python。

最后你只是从直方图i采样，重量w_i。这可以通过使用cumsum和searchsorted来适应轮盘赌选择，如由@Ilmari Karonen所建议的，参见this gist。

如果你想要得到的加权分布“尽可能的一致”，我会解决一个类似的权重问题，但是最大化加权和的加权总和。虽然可以使用任何数量的非线性求解器（如BFGS或基于梯度的方法），但这个问题似乎是非线性的。这可能会比LP方法慢一点，但这取决于您在应用程序中需要什么。如果有大量直方图，LP方法会非常接近非线性方法，因为它很容易达到均匀分布。

当使用LP解决方案时，一束直方图权重可能绑定到0，因为约束的数量很小，但这对于非平凡的bin数不会有问题，因为约束的数量是为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]

来源

2013-02-11 18:01:49

这似乎是要走的路。在接受它作为答案之前，我会尝试一下。 – CvW 2013-02-12 14:08:33

太棒了，让我知道如果我可以帮助任何事情。我使用Java的LP和非线性求解器来处理许多应用程序。 – 2013-02-12 16:23:29

我必须添加约束条件，即所有'w> = 0'，之后，我得到它的工作，看到这个问题'cvxpy'的要点：https://gist.github.com/cvanweelden/4961033 – CvW 2013-02-15 17:09:34

您可以绘制一些完整的随机样本（500），然后选择最均匀的样本（即最低sample.sum(axis=0).std()）？这可避免绘制增量样本时出现奇怪偏差。

来源

2013-02-11 17:35:06 noio

与此相关的问题是，这些样本中具有与数据集分布非常不同的分布的任何一个样本的概率非常小。为了有机会绘制大致均匀的样本，我必须绘制的样本数量太大。 – CvW 2013-02-12 09:40:33

抽样直方图，使样品上的总和是统一的

回答

相关问题