python - 如何生成预算受限的加权随机样本，其中项目具有不同的概率和权重？

Question

假设我想从一组三条记录中选择两条记录，其中三条记录的概率分别为 0.1、0.5 和 0.4。每this SO answer ，numpy.random.choice 将起作用:

import pandas as pd
from numpy import random

df = pd.DataFrame({'prob': [0.1, 0.5, 0.4]})

random.seed(0)
random.choice(df.index, p=df.prob, size=2, replace=False)
# array([1, 2])

现在假设每个项目也有一个重量，我不想选择两个项目，而是选择一个最大重量。因此，如果这些商品的权重为 4、5 和 6，而我的预算为 10，则可以选择 {0, 1} 或 {0, 2}。包含的每个项目的相对概率仍然受概率控制(尽管在实践中我认为算法会更频繁地返回项目 1，因为它的权重较低可以充当填充物)。

有没有办法适应random.choice来实现这一点，或者有其他方法来产生这个结果？

Answer 1

您可以做的是使用 np.random.choice 与您所做的一样，但对于数据的完整大小。然后使用从 np.random.choice 获得的新订单重新索引 df。使用cumsum列权重，最后仅返回索引，直到达到您想要的值。

def weighted_budgeted_random_sample_all(df, budget):
   random_index_order = np.random.choice( df.index, size = len(df), 
                                          p = df.prob, replace = False)
   s = df.reindex(random_index_order).weight.cumsum()
   return s[s <= budget].index.values

现在这个方法的问题是，如果问题中的 df 和 budget 为 10，那么某些解决方案只有索引 1 或 2，因为如果 random_index_order 等于 [2,1,0] 或 [1,2,0] 则 cumsum 在第二行高于 10。

查看 Counter ，使用tuple和np.sort只是为了让Counter工作并且更容易看到结果:

from collections import Counter
print (Counter([ tuple(np.sort(weighted_budgeted_random_sample_all(df,10))) 
                 for i in range(1000)]))
# Counter({(0, 1): 167, (0, 2): 111, (1,): 390, (2,): 332})

正如您所看到的，有些抽签的顺序是前 2 个值是 2 和 3，但结果只有 2 或 3，因为它们的权重之和为 11。

但实际上，如果您以 11 的预算尝试同样的事情，那么您会得到预期的输出:

print (Counter([ tuple(np.sort(weighted_budgeted_random_sample_all(df,11))) 
                 for i in range(1000)]))
# Counter({(0, 1): 169, (0, 2): 111, (1, 2): 720})

在这里您可以找到三个可能的集合，并且更频繁地获得集合{1,2}这一事实是有意义的。

我看到您在发表评论后修改了您的问题，您将采用一次处理一项的方法。我相信这样做会对整体概率产生影响，但我对概率的了解不足以说明原因。如果您真的愿意，那么我认为您可以将您的方法和我的方法结合起来以获得一些时间:

def weighted_budgeted_random_sample_mixed(df, budget):
    ids = []
    total = 0
    dftemp = df.copy()
    while total < budget:
        remaining = budget - total
        dftemp = dftemp[dftemp.weight <= remaining]
        # Stop if there are no records with small enough weight.
        if dftemp.shape[0] == 0:
            break
        # New order
        new_index = np.random.choice( dftemp.index, size = len(dftemp), 
                                      p = (dftemp.prob/dftemp.prob.sum()), 
                                      replace = False)
        s = dftemp.reindex(new_index).weight.cumsum()
        #select only the necessary rows
        s = s[s <= remaining] 
        total += s.max() #last value in s which is less than remaining
        dftemp.drop(s.index, inplace=True)
        ids += s.index.tolist()
    return ids

现在与您的方法在结果方面进行比较:

#your approach
print (Counter([ tuple(np.sort(weighted_budgeted_random_sample(df,10))) 
                 for i in range(1000)]))
#Counter({(0, 1): 546, (0, 2): 454})

#mixed approach
print (Counter([ tuple(np.sort(weighted_budgeted_random_sample_mixed(df,10))) 
                 for i in range(1000)])
#Counter({(0, 1): 554, (0, 2): 446})

如您所见，结果非常相似，并且混合方法在较大的数据帧上应该更快，因为它最大限度地减少了 while 中的循环