3

サブセットをランダムにサンプリングするアイテムのリストがありますが、各アイテムは 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])

合計されたヒストグラムの絶対値は重要ではなく、正確に均一である必要もありません。ほぼ均一である必要があります。また、返されたサンプル サイズが指定されたサンプル サイズと正確に一致しないかどうかは気にしません。サンプリングは交換なしで行う必要があります。

4

2 に答える 2

2

@Ilmari Karonenのソリューションを拡張するには、各ヒストグラムの重みを計算し、それらの重みに従ってサンプリングします。あなたの目標を考えると、これを行う最も効率的な方法は線形計画法を使用することだと私には思えます。

D_ijを、i番目のアイテムのヒストグラムのj番目のビンの重みとします。次に、各アイテムが重みw_iで重み付けされている場合、「合計ヒストグラム」は重みsum（i in items）w_iD_ijになります。「ほぼ一様」な分布を得る1つの方法は、ビン間の最大差を最小化することです。そのため、次の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 >=すべての重み付けされたビンのペア間の差の絶対値を示しています。numpyにはLPソルバーが含まれていないため、このLPを解決するには別のパッケージが必要になります。を使用した解決策についてはこの要点を、を使用した解決策についてはこの要点を参照してください。これらのソリューションと同様に、重みにいくつかの制約を設定する必要があることに注意してください（たとえば、各重みは0以上です）。GLPK（GNU線形計画法キット）用の他のPythonバインディングは、http：//en.wikibooks.org/wiki/GLPK/Pythonにあります。cplexcvxpy

i最後に、重みを使用してヒストグラムからサンプリングしますw_i。これは、@ Ilmari Karonenを使用して、ルーレットの選択を調整することで実行できます。この要点を参照cumsumしてください。searchsorted

結果の重み付き分布を「可能な限り均一」にしたい場合は、重みに関する同様の問題を解決しますが、ビンの重み付き合計全体で重み付きエントロピーを最大化します。この問題は非線形に見えますが、BFGSや勾配ベースの方法などの非線形ソルバーをいくつでも使用できます。これはおそらくLP方式よりも少し遅いでしょうが、アプリケーションで何が必要かによって異なります。LP法は、ヒストグラムが多数ある場合、一様分布に到達しやすいため、非線形法を非常に厳密に近似します。

LPソリューションを使用する場合、制約の数が少ないため、ヒストグラムの重みの束が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]
于 2013-02-11T18:01:49.290 に答える