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:替换if Ri > T and len(L) < B:为在 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]

现在，这可能违反了关于 的“成本”条件L，因为我们确实可能“添加”了 10 多个元素，但我认为每次我替换一个元素时，你都必须返还一个硬币。

频率分布的快速健全性检查看起来不错（很容易产生一个错误导致偏差）：

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 回答