随机加权选择

问题描述：

我有这样的数据：

d = (
  (701, 1, 0.2),
  (701, 2, 0.3),
  (701, 3, 0.5),
  (702, 1, 0.2),
  (702, 2, 0.3),
  (703, 3, 0.5)
)

其中 (701, 1, 0.2) = (id1, id2, priority)

如果我知道 id1，有没有一种使用优先级来选择 id2 的好方法？

Func(701) 应该返回：

  1 - 20% 的情况

  2 - 30%

  3 - 50%

当然百分比会比较粗略

解决方案 1：

为每个 ID1 生成一个累积分布函数，如下所示：

cdfs = defaultdict()
for id1,id2,val in d:
    prevtotal = cdfs[id1][-1][0]
    newtotal = prevtotal + val
    cdfs[id1].append( (newtotal,id2) )

所以你将拥有

cdfs = { 701 : [ (0.2,1), (0.5,2), (1.0,3) ], 
         702 : [ (0.2,1), (0.5,2) ],
         703 : [ (0.5,3) ] }

然后生成一个随机数并在列表中搜索它。

def func(id1):
    max = cdfs[id1][-1][0]
    rand = random.random()*max
    for upper,id2 in cdfs[id1]:
        if upper>rand:
            return id2
    return None

解决方案 2：

意识到我的第一个答案在数学上有很多错误，我产生了一个新的想法。我相信这里的算法与其他几个答案的算法类似，但这个实现似乎符合问题的“漂亮”（如果这等于简单）要求：

def func(id):
    rnd = random()
    sum = 0
    for row in d:
        if row[0] == id:
            sum = sum + row[2]
            if rnd < sum:
                return row[1]

使用来自 OP 的示例数据，情况如下：

• 选取 0 到 1.0 之间的随机数

• 如果数字是，则< 0.2返回第一个元素

• 否则，如果数字是，则< 0.5返回第二个元素

• 否则（如果数字是< 1.0）返回第三个元素

解决方案 3：

使用随机模块中足够数量的值的离散均匀分布，然后对其进行分区：

例如，对于案例 701，使用 10 个值的分布，对于 2 个值返回 1，对于另外 3 个值返回 2，对于其他 5 个值返回 3。

您可以使用足够多的均匀分布来构建任何分布:)

解决方案 4：

如果百分比值不比整数百分比值更精确，请使用随机数生成器生成 0-99 的数字。

然后在您的函数中，使用（程序化的）案例来选择正确的数字。例如（清理一下）：

如果 701
  如果 random_num < 20
    返回 1
  否则，如果随机数<50 //（20 + 30）
    返回 2
  否则，如果随机数<100 //（20 + 30 + 50）
    返回 3
  别的
    // 错误

解决方案 5：

一个非常快速的破解方法：

import random

d = {
    701: [(1,0.2),(2,0.3),(3,0.5)],
    702: [(1,0.2),(2,0.3),(3,0.5)]
}

def func(value):
    possible_values=d[value]
    total=sum(p[-1] for p in possible_values)
    random_value=random.random()
    prob=possible_values[0][-1]/total
    index=1
    while index<len(possible_values) and prob<random_value:
        prob+=possible_values[index][-1]/total
        index+=1
    return possible_values[index-1][0]

if __name__=='__main__':
    testcases=1000
    cnt=[0,0,0]
    for case in xrange(testcases):
        answer=func(701)
        cnt[answer-1]+=1
    for i in xrange(3):
        print "Got %d %f%% of the time"%(i+1,float(cnt[i])/testcases*100)

它并不漂亮，但它是我首先想到的东西，并且看起来按预期工作。

这段代码的作用是获取区间 [0,1) 内的随机值（使用 random.random()）。然后根据随机值是否落在区间 [0,0.2)、[0.2,0.5) 或 [0.5,1) 内来确定返回哪个值。

解决方案 6：

两个想法（为了参数名称的清晰起见，请允许我用分离的选项和比率来说明，如果它们被打包在一个元组中，则可以保存“zip”）：

a) 对权重进行非规范化以获得整数比率，然后将与比率一样多的副本放入列表中并使用random.choice。

def choice_with_ratios(options, ratios):
    tmp = sum([[v]*n for v, n in zip(options, ratios)], [])
    return random.choice(tmp)

b）使用标准化的权重并开始求和，直到达到随机生成的统一值

def choice_with_weights(options, weights):
    s = 0
    r = random.random()
    for v, w in zip(options, weights):
        s += w
        if s >= r: break
    return v

顺便说一句，如果第一个字段用作键，则应该将其放在字典中，例如：

d = {
  701: ((1, 0.2), (2, 0.3), (3, 0.5),
  702: ((1, 0.3), (2, 0.2), (3, 0.5)
}

解决方案 7：

您还可以为每个值创建一个包含 100 个元素的列表，然后让 random.choice 从种子列表中进行选择，该列表的成员按您想要的权重加载：

import random
from collections import defaultdict

d = ( 
  (701, 1, 0.2), 
  (701, 2, 0.3), 
  (701, 3, 0.5), 
  (702, 1, 0.2), 
  (702, 2, 0.3), 
  (702, 3, 0.5) 
) 

class WeightedLookup(object):
    def __init__(self, valueTupleList):
        self.valdict = defaultdict(list)
        for key, val, prob in valueTupleList:
            self.valdict[key] += [val]*(int)(prob*100)

    def __getitem__(self,key):
        return random.choice(self.valdict[key])


lookup = WeightedLookup(d)

# test out our lookup distribution, sample it 100000 times
res = { 1:0, 2:0, 3:0 }
for i in range(100000):
    res[lookup[701]] += 1

# print how many times each value was returned
for k in (1,2,3):
    print k, res[k]

印刷：

1 20059
2 30084
3 49857