抽樣直方圖，使樣品上的總和是統一的

我有一個項目的列表，我想從中隨機抽樣一個子集，但每個項目都與一個直方圖配對在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

抽樣直方圖，使樣品上的總和是統一的

回答

相關問題