有和没有replace的加权随机select
最近，我需要从列表中加权随机select元素，无论是否有replace。 虽然有一些众所周知的好的algorithm用于未加权的select，有些用于加权select而没有replace（例如resevoiralgorithm的修改），但我找不到任何用于replace的加权select的好algorithm。 我也想避免使用藏库方法，因为我正在select一个很小的列表中的一小部分，这个列表足够小，可以放在内存中。
在这种情况下有没有人有最好的方法build议？ 我有我自己的解决scheme，但我希望find更有效率，更简单，或两者兼而有之。
使用不变列表replace样本的最快方法之一是别名方法。 核心的直觉是，我们可以为加权列表创build一组相同大小的bin，可以通过位操作非常高效地索引，从而避免二分search。 结果是，如果做得正确的话，我们将只需要从每个分箱的原始列表中存储两个项目，从而可以用单个百分比表示分割。
让我们以五个加权的select为例(a:1, b:1, c:1, d:1, e:1)
要创build别名查找：
-
将权重归一化为
1.0。(a:0.2 b:0.2 c:0.2 d:0.2 e:0.2)这是select每个重量的概率。 -
找出2的最小幂数大于或等于variables个数，并创build这个分区数，
|p|。 每个分区代表1/|p|的概率质量 。 在这种情况下，我们创build了8分区，每个分区可以包含0.125。 -
以剩余重量最小的variables，把尽可能多的质量放在一个空的分区中。 在这个例子中，我们看到
a填满了第一个分区。(p1{a|null,1.0},p2,p3,p4,p5,p6,p7,p8)(a:0.075, b:0.2 c:0.2 d:0.2 e:0.2)(p1{a|null,1.0},p2,p3,p4,p5,p6,p7,p8) -
如果分区没有被填充，取最重的variables，并用该variables填充分区。
重复步骤3和4，直到没有任何来自原始分区的权重需要分配给列表。
例如，如果我们运行另一个3和4的迭代，我们可以看到
(p1{a|null,1.0},p2{a|b,0.6},p3,p4,p5,p6,p7,p8) (a:0, b:0.15 c:0.2 d:0.2 e:0.2) (p1{a|null,1.0},p2{a|b,0.6},p3,p4,p5,p6,p7,p8)留下来分配
在运行时：
-
得到一个
U(0,1)随机数，比如说二进制0.001100000 -
lg2(p)它lg2(p)，find索引分区。 因此，我们将它移动3，产生001.1，或者位置1，从而分割2。 -
如果分区被分割，则使用移位的随机数的小数部分来决定分割。 在这种情况下，值是
0.5，并且0.5 < 0.6，所以返回a。
这里有一些代码和另一个解释 ，但不幸的是，它不使用偏移技术，也没有实际validation它。
我build议你先看一下 Donald Knuth的algorithmalgorithm 3.4.2节。
如果你的数组很大，John Dagpunar 在随机variables生成原理的第3章中有更高效的algorithm。 如果你的arrays不是非常大，或者你不关心尽可能多的效率，Knuth中更简单的algorithm可能是好的。
以下是我想出的无需更换的加权select：
def WeightedSelectionWithoutReplacement(l, n): """Selects without replacement n random elements from a list of (weight, item) tuples.""" l = sorted((random.random() * x[0], x[1]) for x in l) return l[-n:]
这是要从中select的列表中的项目数O（m log m）。 我相当肯定，这将正确地加权项目，虽然我没有任何正式的意义上的validation。
以下是我想出的replace加权select：
def WeightedSelectionWithReplacement(l, n): """Selects with replacement n random elements from a list of (weight, item) tuples.""" cuml = [] total_weight = 0.0 for weight, item in l: total_weight += weight cuml.append((total_weight, item)) return [cuml[bisect.bisect(cuml, random.random()*total_weight)] for x in range(n)]
这是O（m + n log m），其中m是input列表中的项目数量，n是要select的项目数量。
这里没有提到的简单方法是在Efraimidis和Spirakis中提出的方法 。 在python中，你可以从n> = m个加权项目中selectm个项目，权重存储在严格正的权重中，返回选定的索引：
import heapq import math import random def WeightedSelectionWithoutReplacement(weights, m): elt = [(math.log(random.random()) / weights[i], i) for i in range(len(weights))] return [x[1] for x in heapq.nlargest(m, elt)]
这与尼克·约翰逊提出的第一种方法在结构上非常相似。 不幸的是，这种方法在select元素方面存在偏差（请参阅方法的评论）。 Efraimidis和Spirakiscertificate，他们的方法相当于在相关论文中没有replace的随机抽样。
在O（N）时间首先创build一个额外的O（N）大小的数据结构之后，可以用O（1）时间replace来进行加权随机select。 该algorithm基于Walker和Vose开发的Alias方法 ， 这里详细描述。
基本的想法是直方图中的每个bin将被一个统一的RNG以概率1 / N来select。 所以我们将通过它，并为任何可能会收到超额命中的人口过剩的垃圾箱，分配到一个人口过剩的垃圾箱。 对于每个垃圾箱，我们存储属于它的命中的百分比，以及多余的伙伴垃圾箱。 该版本跟踪小型和大型垃圾箱，无需额外的堆栈。 它使用伙伴的索引（存储在bucket[1] ）作为已被处理的指示符。
这里是一个基于C实现的最小的Python实现
def prep(weights): data_sz = len(weights) factor = data_sz/float(sum(weights)) data = [[w*factor, i] for i,w in enumerate(weights)] big=0 while big<data_sz and data[big][0]<=1.0: big+=1 for small,bucket in enumerate(data): if bucket[1] is not small: continue excess = 1.0 - bucket[0] while excess > 0: if big==data_sz: break bucket[1] = big bucket = data[big] bucket[0] -= excess excess = 1.0 - bucket[0] if (excess >= 0): big+=1 while big<data_sz and data[big][0]<=1: big+=1 return data def sample(data): r=random.random()*len(data) idx = int(r) return data[idx][1] if r-idx > data[idx][0] else idx
用法示例：
TRIALS=1000 weights = [20,1.5,9.8,10,15,10,15.5,10,8,.2]; samples = [0]*len(weights) data = prep(weights) for _ in range(int(sum(weights)*TRIALS)): samples[sample(data)]+=1 result = [float(s)/TRIALS for s in samples] err = [ab for a,b in zip(result,weights)] print(result) print([round(e,5) for e in err]) print(sum([e*e for e in err]))
以下是在O（n）空间和O（log n）时间内有或没有replace的集合（或多重集，如果允许重复）的元素的随机加权select的描述。
它包括实现一个二叉search树，按照要select的元素sorting，树的每个节点包含：
- 元素本身（ 元素 ）
- 元素（元素重量）的非标准化权重，以及
- 左子节点及其所有子节点（ 左分支 ）的所有非标准化权重之和。
- 右子节点及其全部子（ 右分支 ）的所有非标准权重的总和。
然后我们通过从树中下降来随机地从BST中select一个元素。 该algorithm的粗略描述如下。 该algorithm被赋予树的节点 。 然后将左分枝 ， 右 分枝和节点 元素的值相加，并将权重除以该和，分别得到左分枝概率 ， 右分枝概率和元素概率 。 然后获得0和1之间的随机数（随机数）。
- 如果该数字小于元素概率 ，
- 正常情况下从BST中删除元素，更新所有必要节点的左分支和右分支 ，并返回元素。
- 否则如果数量小于（ elementprobability + leftbranchweight ）
- 在leftchild上recursion（使用leftchild作为节点运行algorithm）
- 其他
- recursion于右键
当我们最终发现，使用这些权重，要返回哪个元素，我们或者简单地返回它（用replace），或者我们删除它并更新树中的相关权重（没有replace）。
免责声明：该algorithm是粗糙的，并没有尝试在这里正确实施BST的论文; 相反，希望这个答案能帮助那些真正需要快速加权select而不需要replace的人（就像我一样）。
假设你想从列表中抽取3个元素，而不是从列表['白色'，'蓝色'，'黑色'，'黄色'，'绿色] 分布[0.1,0.2,0.4,0.1,0.2]。 使用numpy.random模块就像这样简单：
import numpy.random as rnd sampling_size = 3 domain = ['white','blue','black','yellow','green'] probs = [.1, .2, .4, .1, .2] sample = rnd.choice(domain, size=sampling_size, replace=False, p=probs) # in short: rnd.choice(domain, sampling_size, False, probs) print(sample) # Possible output: ['white' 'black' 'blue']
设置replace标志为True ，你有一个替代抽样。
更多信息在这里： http : //docs.scipy.org/doc/numpy/reference/generated/numpy.random.choice.html#numpy.random.choice
