0

次の単純なアルゴリズムでは、テストif Ri > T:を使用すると、L で 30 個の要素、U で 70 個の要素が得られます。T の値が 0.7 に設定されているため、これは問題ありません。

ここで、次のような制約を追加したい場合: L に配置される要素 i は、Ri > T であるという事実に加えて、L に B=20 を超えるものが含まれていないことも必要です (つまり、最後に、i=n の場合、L のサイズは多かれ少なかれ B=20 になります)。

しかし問題は、テストを で置き換えると、if Ri > T:Lif Ri > T and len(L) < B:に配置される要素は、ブラウズする最初の要素 i に含まれる可能性が高くなるということです (つまり、要素 i = 87 にはチャンスがありません)。 Lにある）。しかし、i = 1 から n までのすべての要素が L に含まれる可能性が等しいことを望みます (最初の要素だけを有利にするのではありません)。

注：Ri > T要素をLに配置するための条件は、コードから削除しないでください。これは私にとって重要です。時間 i で $Ri$ が T よりも高かった要素のみが L に存在することが許可されます。len(L) は B を超えてはなりません (多かれ少なかれ)。

import random

T = 0.7 # or any value T in ]0,1[
n = 100 # or any value n > B
B = 20 # or any value B < n

L = []
U = []

for i in range(1,n+1):
   xi = input("please give a new data x")
   Ri = 1. - random.random() # normally it is Ri = 1. - Proba(xi) depending on xi, but lets simplify using random() ...
   if Ri > T:
      Pay 1 euro and buy yi the label of xi
      L.append((xi, yi))
   else:
      U.append(xi)


print len(L), L
print
print len(U), U
4

2 に答える 2

1

私は、これが可能な限り明確に指定されていないことを示唆するコメントに同意する傾向があります。ただし、私が正しく読んでいれば、一種のリザーバーサンプリングを使用できます。

def some_accept(value_stream, p, max_num_to_accept):
    accepted = []
    passed = (v for v in value_stream if random.random() < p)
    for i, value in enumerate(passed):
        if len(accepted) < max_num_to_accept:
            accepted.append(value)
        else:
            replace_i = random.randint(0, i)
            if replace_i < max_num_to_accept:
                accepted[replace_i] = value
    return accepted

を与える

>>> some_accept(range(100), 0.7, 10)
[34, 26, 30, 16, 22, 38, 32, 86, 33, 12]
>>> some_accept(range(100), 0.05, 10)
[16, 17, 83, 95]

これは、10 を超える要素を「追加」する可能性があるという点で、に関する「コスト」条件に違反する可能性がありますLが、要素を置き換えるたびに、コインを返さなければならないと主張します。

頻度分布の簡単な健全性チェックは問題ないように見えます (偏りの原因となる off-by-one エラーを起こすのは非常に簡単です):

import matplotlib.pyplot as plt

fig = plt.figure()
ax = fig.add_subplot(111)
for i in range(100):
    s = sum((Counter(some_accept(range(10), 0.25, 4)) for i in range(10**3)), Counter())
    x, y = zip(*sorted(s.items()))
    ax.plot(x,y)

plt.savefig("test.png")

与える

ここに画像の説明を入力

于 2013-04-14T00:46:48.867 に答える
0

最も簡単な解決策は、乱数を選択してそれを B/n と比較することにより、要素を追加するリストを最初に把握することです。次に、問題のリストの範囲内にあるランダムな値でアイテムを作成します。

for i in range(n):
  rt = random.randint(1,n)
  if (rt <= B):
    r1 = random.uniform(T, 1)
    # add x1 with r1 to L
  else:
    r1 = random.uniform(0, T)
    # add x1 with r1 to U

ちなみに、[0, 1)1 から範囲内の乱数を引いても確率は反転しません。である可能性はまだ 30% あり> 0.70ます。(範囲が に変更されますが(0, 1]、ほとんどの場合、それは重要ではありません。) それはあなたが望んでいたものではないと思いますが、知るのは難しいです。とにかく、値の 70% が の範囲に入るように変更しましたL。必要に応じて上記を調整します。

于 2013-04-14T00:40:41.627 に答える