random.choice 的加权版本
- 2024-11-22 08:47:00
- admin 原创
- 177
问题描述：
我需要编写一个加权版本的 random.choice（列表中的每个元素被选中的概率不同）。这就是我想到的：
def weightedChoice(choices):
"""Like random.choice, but each element can have a different chance of
being selected.
choices can be any iterable containing iterables with two items each.
Technically, they can have more than two items, the rest will just be
ignored. The first item is the thing being chosen, the second item is
its weight. The weights can be any numeric values, what matters is the
relative differences between them.
"""
space = {}
current = 0
for choice, weight in choices:
if weight > 0:
space[current] = choice
current += weight
rand = random.uniform(0, current)
for key in sorted(space.keys() + [current]):
if rand < key:
return choice
choice = space[key]
return None
我觉得这个函数过于复杂，而且很丑。我希望这里的每个人都能提出一些改进建议或其他方法。对我来说，效率不如代码整洁和可读性重要。
解决方案 1：
从 1.7.0 版本开始，NumPy 具有choice支持概率分布的函数。
from numpy.random import choice
draw = choice(list_of_candidates, number_of_items_to_pick,
p=probability_distribution)
请注意probability_distribution是与 顺序相同的序列list_of_candidates。您还可以使用关键字replace=False来更改行为，以便绘制的项目不会被替换。
解决方案 2：
choices从 Python 3.6 开始，模块中有一个方法random。
In [1]: import random
In [2]: random.choices(
...: population=[['a','b'], ['b','a'], ['c','b']],
...: weights=[0.2, 0.2, 0.6],
...: k=10
...: )
Out[2]:
[['c', 'b'],
['c', 'b'],
['b', 'a'],
['c', 'b'],
['c', 'b'],
['b', 'a'],
['c', 'b'],
['b', 'a'],
['c', 'b'],
['c', 'b']]
请注意，根据文档random.choices，将进行替换采样：
返回
k从总体中按一定大小选择的元素列表。
为了保证答案的完整性，请注意：
当从有限总体中抽取一个抽样单元，并在记录其特征后、抽取下一个单元之前将其放回该总体时，这种抽样被称为“有放回”抽样。这基本上意味着每个元素可能被选择多次。
如果您需要进行无放回采样，那么正如@ronan-paixão 的精彩回答所述，您可以使用numpy.choice，其replace参数控制这种行为。
解决方案 3：
def weighted_choice(choices):
total = sum(w for c, w in choices)
r = random.uniform(0, total)
upto = 0
for c, w in choices:
if upto + w >= r:
return c
upto += w
assert False, "Shouldn't get here"
解决方案 4：
更新答案
Python 标准库现在具有random.choices()，它直接支持加权选择。
以下是来自文档的一个例子：
>>> # Six roulette wheel spins (weighted sampling with replacement)
>>> choices(['red', 'black', 'green'], [18, 18, 2], k=6)
['red', 'green', 'black', 'black', 'red', 'black']
算法概述：
将权重排列成累积分布。
用于
random.random()挑选一个随机浮点数0.0 <= x < total。使用http://docs.python.org/dev/library/bisect.html#other-examples
bisect.bisect()中的示例所示搜索分布。
简化代码：
from random import random
from math import floor as floor
from bisect import bisect as bisect
from itertools import accumulate, repeat
def choices(population, weights=None, *, cum_weights=None, k=1):
"""Return a k sized list of population elements chosen with replacement.
If the relative weights or cumulative weights are not specified,
the selections are made with equal probability.
"""
n = len(population)
if cum_weights is None:
if weights is None:
return [population[floor(random() * n)] for i in repeat(None, k)]
cum_weights = list(accumulate(weights))
elif weights is not None:
raise TypeError('Cannot specify both weights and cumulative weights')
total = cum_weights[-1] + 0.0
hi = n - 1
return [population[bisect(cum_weights, random() * total, 0, hi)]
for i in repeat(None, k)]
解决方案 5：
如果您不介意使用 numpy，则可以使用numpy.random.choice。
例如：
import numpy
items = [["item1", 0.2], ["item2", 0.3], ["item3", 0.45], ["item4", 0.05]
elems = [i[0] for i in items]
probs = [i[1] for i in items]
trials = 1000
results = [0] * len(items)
for i in range(trials):
res = numpy.random.choice(items, p=probs) #This is where the item is selected!
results[items.index(res)] += 1
results = [r / float(trials) for r in results]
print "item expected actual"
for i in range(len(probs)):
print "%s %0.4f %0.4f" % (items[i], probs[i], results[i])
如果您提前知道需要进行多少次选择，则可以不使用循环来执行此操作，如下所示：
numpy.random.choice(items, trials, p=probs)
解决方案 6：
从 Python 开始v3.6，random.choices可用于从list给定总体中返回具有可选权重的指定大小的元素。
random.choices(population, weights=None, *, cum_weights=None, k=1)
人口：
list包含独特的观察结果。（如果为空，则引发IndexError）权重：更准确地说是进行选择所需的相对权重。
cum_weights：进行选择所需的累积权重。
k：要输出
len的大小（）list。（默认值len()=1）
几点注意事项：
1) 它利用了带替换的加权抽样，因此抽取的项目稍后会被替换。权重序列中的值本身并不重要，但它们的相对比率很重要。
与np.random.choice只能以概率为权重，并且必须确保单个概率相加达到 1 个标准不同，这里没有这样的规定。只要它们属于数字类型（类型int/float/fraction除外Decimal），它们仍然可以执行。
>>> import random
# weights being integers
>>> random.choices(["white", "green", "red"], [12, 12, 4], k=10)
['green', 'red', 'green', 'white', 'white', 'white', 'green', 'white', 'red', 'white']
# weights being floats
>>> random.choices(["white", "green", "red"], [.12, .12, .04], k=10)
['white', 'white', 'green', 'green', 'red', 'red', 'white', 'green', 'white', 'green']
# weights being fractions
>>> random.choices(["white", "green", "red"], [12/100, 12/100, 4/100], k=10)
['green', 'green', 'white', 'red', 'green', 'red', 'white', 'green', 'green', 'green']
2) 如果未指定权重或cum_weights，则选择将以相等的概率进行。如果提供了权重序列，则其长度必须与种群序列相同。
同时指定权重和cum_weights会引发TypeError。
>>> random.choices(["white", "green", "red"], k=10)
['white', 'white', 'green', 'red', 'red', 'red', 'white', 'white', 'white', 'green']
3) cum_weights通常是函数的结果itertools.accumulate，在这种情况下非常方便。
来自链接的文档：
在内部，相对权重在做出选择之前会转换为累积权重，因此提供累积权重可以节省工作量。
因此，对于我们所设计的案例，无论是供应weights=[12, 12, 4]还是提供cum_weights=[12, 24, 28]都会产生相同的结果，并且后者似乎更快/更有效。
解决方案 7：
粗糙，但可能足够了：
import random
weighted_choice = lambda s : random.choice(sum(([v]*wt for v,wt in s),[]))
它有用吗？
# define choices and relative weights
choices = [("WHITE",90), ("RED",8), ("GREEN",2)]
# initialize tally dict
tally = dict.fromkeys(choices, 0)
# tally up 1000 weighted choices
for i in xrange(1000):
tally[weighted_choice(choices)] += 1
print tally.items()
印刷：
[('WHITE', 904), ('GREEN', 22), ('RED', 74)]
假设所有权重都是整数。它们的总和不必等于 100，我这样做只是为了使测试结果更容易解释。（如果权重是浮点数，则将它们全部反复乘以 10，直到所有权重 >= 1。）
weights = [.6, .2, .001, .199]
while any(w < 1.0 for w in weights):
weights = [w*10 for w in weights]
weights = map(int, weights)
解决方案 8：
如果你有一个加权字典而不是列表，你可以这样写
items = { "a": 10, "b": 5, "c": 1 }
random.choice([k for k in items for dummy in range(items[k])])
请注意[k for k in items for dummy in range(items[k])]生成此列表['a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'c', 'b', 'b', 'b', 'b', 'b']
解决方案 9：
这是包含在 Python 3.6 标准库中的版本：
import itertools as _itertools
import bisect as _bisect
class Random36(random.Random):
"Show the code included in the Python 3.6 version of the Random class"
def choices(self, population, weights=None, *, cum_weights=None, k=1):
"""Return a k sized list of population elements chosen with replacement.
If the relative weights or cumulative weights are not specified,
the selections are made with equal probability.
"""
random = self.random
if cum_weights is None:
if weights is None:
_int = int
total = len(population)
return [population[_int(random() * total)] for i in range(k)]
cum_weights = list(_itertools.accumulate(weights))
elif weights is not None:
raise TypeError('Cannot specify both weights and cumulative weights')
if len(cum_weights) != len(population):
raise ValueError('The number of weights does not match the population')
bisect = _bisect.bisect
total = cum_weights[-1]
return [population[bisect(cum_weights, random() * total)] for i in range(k)]
来源： https ://hg.python.org/cpython/file/tip/Lib/random.py#l340
解决方案 10：
加权选择的一个非常基本且简单的方法如下：
np.random.choice(['A', 'B', 'C'], p=[0.3, 0.4, 0.3])
解决方案 11：
import numpy as np
w=np.array([ 0.4, 0.8, 1.6, 0.8, 0.4])
np.random.choice(w, p=w/sum(w))
解决方案 12：
我可能已经太晚了，无法贡献任何有用的东西，但这里有一个简单、简短且非常有效的代码片段：
def choose_index(probabilies):
cmf = probabilies[0]
choice = random.random()
for k in xrange(len(probabilies)):
if choice <= cmf:
return k
else:
cmf += probabilies[k+1]
无需对概率进行排序或使用 cmf 创建向量，一旦找到选择，它就会终止。内存：O(1)，时间：O(N)，平均运行时间 ~ N/2。
如果有权重，只需添加一行：
def choose_index(weights):
probabilities = weights / sum(weights)
cmf = probabilies[0]
choice = random.random()
for k in xrange(len(probabilies)):
if choice <= cmf:
return k
else:
cmf += probabilies[k+1]
解决方案 13：
如果您的加权选择列表相对静态，并且您想要频繁采样，则可以执行一个 O（N）预处理步骤，然后使用相关答案中的函数在 O（1）中进行选择。
# run only when `choices` changes.
preprocessed_data = prep(weight for _,weight in choices)
# O(1) selection
value = choices[sample(preprocessed_data)][0]
解决方案 14：
如果你恰好有 Python 3，并且害怕安装numpy或编写自己的循环，你可以这样做：
import itertools, bisect, random
def weighted_choice(choices):
weights = list(zip(*choices))[1]
return choices[bisect.bisect(list(itertools.accumulate(weights)),
random.uniform(0, sum(weights)))][0]
因为你可以用一袋管道接头制作任何东西！虽然……我必须承认，Ned 的回答虽然稍长一些，但却更容易理解。
解决方案 15：
我查看了指出的其他线程并想出了我的编码风格的这种变化，它返回了用于计数的选择索引，但返回字符串很简单（注释掉返回替代方案）：
import random
import bisect
try:
range = xrange
except:
pass
def weighted_choice(choices):
total, cumulative = 0, []
for c,w in choices:
total += w
cumulative.append((total, c))
r = random.uniform(0, total)
# return index
return bisect.bisect(cumulative, (r,))
# return item string
#return choices[bisect.bisect(cumulative, (r,))][0]
# define choices and relative weights
choices = [("WHITE",90), ("RED",8), ("GREEN",2)]
tally = [0 for item in choices]
n = 100000
# tally up n weighted choices
for i in range(n):
tally[weighted_choice(choices)] += 1
print([t/sum(tally)*100 for t in tally])
解决方案 16：
通用解决方案：
import random
def weighted_choice(choices, weights):
total = sum(weights)
treshold = random.uniform(0, total)
for k, weight in enumerate(weights):
total -= weight
if total < treshold:
return choices[k]
解决方案 17：
这是使用 numpy 的另一个版本的 weighted_choice。传入权重向量，它将返回一个包含 0 的数组，其中包含一个 1，表示选择了哪个 bin。代码默认只进行一次抽取，但您可以传入要进行的抽取次数，然后会返回每个 bin 的计数。
如果权重向量的总和不为 1，则对其进行标准化。
import numpy as np
def weighted_choice(weights, n=1):
if np.sum(weights)!=1:
weights = weights/np.sum(weights)
draws = np.random.random_sample(size=n)
weights = np.cumsum(weights)
weights = np.insert(weights,0,0.0)
counts = np.histogram(draws, bins=weights)
return(counts[0])
解决方案 18：
Sebastien Thurn 在 Udacity 的免费课程 AI for Robotics 中讲过这个。基本上，他使用 mod 运算符创建一个索引权重的循环数组%，将变量 beta 设置为 0，随机选择一个索引，循环遍历 N，其中 N 是索引的数量，在 for 循环中首先按以下公式增加 beta：
beta = beta + 来自 {0...2* Weight_max} 的均匀样本
然后在 for 循环中嵌套一个 while 循环，如下所示：
while w[index] < beta:
beta = beta - w[index]
index = index + 1
select p[index]
然后根据概率（或课程中介绍的案例中的标准化概率）对下一个索引进行重新采样。
在 Udacity 上找到《机器人人工智能》第 8 课第 21 个视频，他正在其中讲授粒子过滤器。
解决方案 19：
这取决于您想要对分布进行抽样的次数。
假设你想对分布进行 K 次采样。那么，当分布中的项目数为时，np.random.choice()每次采样的时间复杂度为。O(K(n + log(n)))`n`
在我的例子中，我需要对相同的分布进行多次采样，采样次数为 10^3 的数量级，其中 n 的数量级为 10^6。我使用了下面的代码，它预先计算了累积分布并对其进行了采样O(log(n))。总体时间复杂度为O(n+K*log(n))。
import numpy as np
n,k = 10**6,10**3
# Create dummy distribution
a = np.array([i+1 for i in range(n)])
p = np.array([1.0/n]*n)
cfd = p.cumsum()
for _ in range(k):
x = np.random.uniform()
idx = cfd.searchsorted(x, side='right')
sampled_element = a[idx]
解决方案 20：
另一种方法是，假设我们的权重与元素数组中的元素位于相同的索引处。
import numpy as np
weights = [0.1, 0.3, 0.5] #weights for the item at index 0,1,2
# sum of weights should be <=1, you can also divide each weight by sum of all weights to standardise it to <=1 constraint.
trials = 1 #number of trials
num_item = 1 #number of items that can be picked in each trial
selected_item_arr = np.random.multinomial(num_item, weights, trials)
# gives number of times an item was selected at a particular index
# this assumes selection with replacement
# one possible output
# selected_item_arr
# array([[0, 0, 1]])
# say if trials = 5, the the possible output could be
# selected_item_arr
# array([[1, 0, 0],
# [0, 0, 1],
# [0, 0, 1],
# [0, 1, 0],
# [0, 0, 1]])
现在让我们假设，我们必须在 1 次试验中抽取 3 个项目。您可以假设有三个球 R、G、B 按照权重数组给出的权重比大量存在，以下可能是可能的结果：
num_item = 3
trials = 1
selected_item_arr = np.random.multinomial(num_item, weights, trials)
# selected_item_arr can give output like :
# array([[1, 0, 2]])
你也可以将要选择的项目数视为一组中的二项式/多项式试验次数。因此，上述示例仍然可以用作
num_binomial_trial = 5
weights = [0.1,0.9] #say an unfair coin weights for H/T
num_experiment_set = 1
selected_item_arr = np.random.multinomial(num_binomial_trial, weights, num_experiment_set)
# possible output
# selected_item_arr
# array([[1, 4]])
# i.e H came 1 time and T came 4 times in 5 binomial trials. And one set contains 5 binomial trails.
解决方案 21：
假设你有
items = [11, 23, 43, 91]
probability = [0.2, 0.3, 0.4, 0.1]
并且你有一个函数可以生成 [0, 1) 之间的随机数（我们可以在这里使用 random.random()）。所以现在取概率的前缀和
prefix_probability=[0.2,0.5,0.9,1]
现在我们可以在 0-1 之间取一个随机数，然后使用二分搜索来找到该数字在 prefix_probability 中的位置。该索引就是你的答案
代码将会像这样
return items[bisect.bisect(prefix_probability,random.random())]
解决方案 22：
一种方法是对所有权重的总和进行随机化，然后使用这些值作为每个变量的极限点。这是一个粗略的生成器实现。
def rand_weighted(weights):
"""
Generator which uses the weights to generate a
weighted random values
"""
sum_weights = sum(weights.values())
cum_weights = {}
current_weight = 0
for key, value in sorted(weights.iteritems()):
current_weight += value
cum_weights[key] = current_weight
while True:
sel = int(random.uniform(0, 1) * sum_weights)
for key, value in sorted(cum_weights.iteritems()):
if sel < value:
break
yield key
解决方案 23：
使用 numpy
def choice(items, weights):
return items[np.argmin((np.cumsum(weights) / sum(weights)) < np.random.rand())]
解决方案 24：
我需要快速、简单地完成类似的事情，通过搜索想法，我最终创建了这个模板。想法是从 api 以 json 形式接收加权值，这里通过 dict 进行模拟。
然后将其转换成一个列表，其中每个值按其权重比例重复，然后使用 random.choice 从列表中选择一个值。
我尝试运行 10、100 和 1000 次迭代。分布似乎相当稳定。
def weighted_choice(weighted_dict):
"""Input example: dict(apples=60, oranges=30, pineapples=10)"""
weight_list = []
for key in weighted_dict.keys():
weight_list += [key] * weighted_dict[key]
return random.choice(weight_list)
解决方案 25：
我不喜欢其中任何一种语法。我真的只想指定项目是什么以及每个项目的权重是多少。我意识到我可以使用，random.choices但我很快在下面编写了类。
import random, string
from numpy import cumsum
class randomChoiceWithProportions:
'''
Accepts a dictionary of choices as keys and weights as values. Example if you want a unfair dice:
choiceWeightDic = {"1":0.16666666666666666, "2": 0.16666666666666666, "3": 0.16666666666666666
, "4": 0.16666666666666666, "5": .06666666666666666, "6": 0.26666666666666666}
dice = randomChoiceWithProportions(choiceWeightDic)
samples = []
for i in range(100000):
samples.append(dice.sample())
# Should be close to .26666
samples.count("6")/len(samples)
# Should be close to .16666
samples.count("1")/len(samples)
'''
def __init__(self, choiceWeightDic):
self.choiceWeightDic = choiceWeightDic
weightSum = sum(self.choiceWeightDic.values())
assert weightSum == 1, 'Weights sum to ' + str(weightSum) + ', not 1.'
self.valWeightDict = self._compute_valWeights()
def _compute_valWeights(self):
valWeights = list(cumsum(list(self.choiceWeightDic.values())))
valWeightDict = dict(zip(list(self.choiceWeightDic.keys()), valWeights))
return valWeightDict
def sample(self):
num = random.uniform(0,1)
for key, val in self.valWeightDict.items():
if val >= num:
return key
解决方案 26：
为 random.choice() 提供预先加权的列表：
解决方案和测试：
import random
options = ['a', 'b', 'c', 'd']
weights = [1, 2, 5, 2]
weighted_options = [[opt]*wgt for opt, wgt in zip(options, weights)]
weighted_options = [opt for sublist in weighted_options for opt in sublist]
print(weighted_options)
# test
counts = {c: 0 for c in options}
for x in range(10000):
counts[random.choice(weighted_options)] += 1
for opt, wgt in zip(options, weights):
wgt_r = counts[opt] / 10000 * sum(weights)
print(opt, counts[opt], wgt, wgt_r)
输出：
['a', 'b', 'b', 'c', 'c', 'c', 'c', 'c', 'd', 'd']
a 1025 1 1.025
b 1948 2 1.948
c 5019 5 5.019
d 2008 2 2.008
解决方案 27：
如果您没有提前定义要选择的项目数（因此，您不会执行类似操作k=10），而只有概率，则可以执行以下操作。请注意，您的概率不需要加起来等于 1，它们可以彼此独立：
soup_items = ['pepper', 'onion', 'tomato', 'celery']
items_probability = [0.2, 0.3, 0.9, 0.1]
selected_items = [item for item,p in zip(soup_items,items_probability) if random.random()<p]
print(selected_items)
>>>['pepper','tomato']
解决方案 28：
在机器学习中，我不仅需要从数组中随机选择一个项目，而且还要确保该项目在整个回合中被选择稳定的次数。
其思想是，根据每个索引的出现概率，将其复制 N 次。最小概率为 0.001，因此，如果某个项目的概率为 0.001，则概率为 1.0 的索引将被复制 1000 次。
所以我创建了一个 Choiceer 类。它还支持嵌套 Choiceer。
from __future__ import annotations
from typing import Any, Sequence
import numpy as np
class Choicer:
def __init__(self, items : Sequence[ Any|Choicer ],
probs : Sequence[int|float]|np.ndarray ):
""" probs [ 0.001 .. 1.0 ] """
self._items = items
self._probs = probs = np.array(probs, np.float32).clip(0.001, 1.0)
if len(probs) != len(items):
raise ValueError('must len(probs) == len(items)')
# how often each item will occur
rates = (probs/probs.min()).astype(np.int32)
# base idx sequence, for example Choicer(['a', 'b', 'c'], [1,1,0.5]) , idxs_base == [0,0,1,1,2]
self._idxs_base = np.concatenate([np.full( (x,), i, dtype=np.uint32) for i,x in enumerate(rates)], 0)
self._idxs = None
self._idx_counter = 0
@property
def items(self) -> Sequence[ Any|Choicer ]: return self._items
@property
def probs(self) -> np.ndarray: return self._probs
def pick(self, count : int) -> Sequence[Any]:
"""pick `count` items"""
out = []
if len(self._items) != 0:
while len(out) < count:
if self._idx_counter == 0:
self._idxs = self._idxs_base.copy()
np.random.shuffle(self._idxs)
self._idx_counter = len(self._idxs)
self._idx_counter -= 1
idx = self._idxs[self._idx_counter]
item = self._items[idx]
if isinstance(item, Choicer):
item = item.pick(1)[0]
out.append(item)
return out
例子：
c = Choicer(['a', 'b', 'c'], [1,1,0.5])
print( c.pick(5) ) # ['c', 'a', 'b', 'a', 'b']
print( c.pick(5) ) # ['a', 'a', 'b', 'b', 'c']
print( c.pick(5) ) # ['a', 'c', 'a', 'b', 'b']
嵌套选择器的示例：
c = Choicer(['a',
'b',
Choicer(['c0','c1','c2'], [1,1,1]),
],
[1,1,0.5])
print( c.pick(15) )
# ['b', 'a', 'b', 'c0', 'a', 'b', 'a', 'b', 'c1', 'a', 'b', 'c2', 'a', 'a', 'b']
解决方案 29：
步骤 1：F生成你感兴趣的CDF
步骤 2：生成 urvu
步骤 3：评估z=F^{-1}(u)
这种建模是在概率论或随机过程的过程中描述的。这很适用，因为你有简单的 CDF。
