最近我需要对列表中的元素进行加权随机选择，包括替换和不替换。虽然有一些众所周知且很好的非加权选择算法，还有一些用于不带替换的加权选择（例如对 resevoir 算法的修改），但我找不到任何好的带替换加权选择算法。我还想避免使用 resevoir 方法，因为我选择了列表的很大一部分，它小到足以保存在内存中。
有没有人对这种情况下的最佳方法有任何建议？我有自己的解决方案，但我希望找到更有效、更简单或两者兼而有之的方法。
Arachnid
问问题
31626 次
9 回答
33
使用不变列表中的替换样本制作多个样本的最快方法之一是别名方法。核心直觉是，我们可以为加权列表创建一组大小相等的 bin，可以通过位操作非常有效地对其进行索引，以避免二分查找。事实证明，如果操作正确，我们将只需要从每个 bin 的原始列表中存储两个项目，因此可以用单个百分比表示拆分。
让我们以五个等权重的选择为例，(a:1, b:1, c:1, d:1, e:1)
要创建别名查找：
将权重归一化，使其总和为
1.0。(a:0.2 b:0.2 c:0.2 d:0.2 e:0.2)这是选择每个权重的概率。找到大于或等于变量个数的 2 的最小幂，并创建此分区数，
|p|。每个分区代表一个概率质量1/|p|。在这种情况下，我们创建8分区，每个分区都可以包含0.125.取出剩余重量最少的变量，并将尽可能多的质量放在空分区中。在此示例中，我们看到
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)如果分区未填充，则取权重最大的变量，并用该变量填充分区。
重复步骤 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)有待分配
在运行时：
获取一个
U(0,1)随机数，比如二进制0.001100000移位它
lg2(p)，找到索引分区。因此，我们将它移动3，产生001.1或位置 1，从而划分 2。如果分区被拆分，则使用移位后的随机数的小数部分来决定拆分。在这种情况下，值为
0.5, 并且0.5 < 0.6, 所以 returna。
这是一些代码和另一种解释，但不幸的是它没有使用位移技术，我也没有实际验证它。
于 2008-12-09T17:27:01.697 回答
12
此处未提及的一种简单方法是Efraimidis 和 Spirakis中提出的一种。在 python 中，您可以从 n >= m 加权项目中选择 m 个项目，并将严格正的权重存储在权重中，返回选定的索引，其中：
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)]
这在结构上与 Nick Johnson 提出的第一种方法非常相似。不幸的是，这种方法在选择元素方面存在偏见（请参阅该方法的评论）。Efraimidis 和 Spirakis 在链接的论文中证明了他们的方法等同于无替换的随机抽样。
于 2013-12-12T16:30:12.717 回答
5
这是我提出的无需替换的加权选择：
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:]
这是列表中要从中选择的项目数的 O(m log m)。我相当肯定这将正确地衡量物品，尽管我还没有在任何正式意义上验证它。
这是我提出的带替换加权选择的方法：
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 是输入列表中的项目数，n 是要选择的项目数。
于 2008-12-09T17:06:26.310 回答
4
我建议您首先查看 Donald Knuth 的Seminumerical Algorithms的第 3.4.2 节。
如果您的数组很大，在John Dagpunar的《随机变量生成原理》第 3 章中有更有效的算法。如果您的数组不是特别大，或者您不关心尽可能多地提高效率，那么 Knuth 中更简单的算法可能就可以了。
于 2008-12-09T13:43:46.000 回答
4
以下是对集合（或多集合，如果允许重复）的元素的随机加权选择的描述，无论是否在 O(n) 空间和 O(log n) 时间中进行替换。
它包括实现一个二叉搜索树，按要选择的元素排序，其中树的每个节点包含：
- 元素本身（元素）
- 元素的非标准化权重（elementweight），以及
- 左子节点及其所有子节点的所有未归一化权重的总和（leftbranchweight）。
- 右子节点及其所有子节点的所有未归一化权重的总和（rightbranchweight）。
然后我们从 BST 中随机选择一个元素，沿着树向下下降。下面是对该算法的粗略描述。该算法给出了树的一个节点。然后将节点的leftbranchweight、rightbranchweight和elementweight的值相加，然后将权重除以该和，分别得到leftbranchprobability、 rightbranchprobability和elementprobability的值。然后得到一个介于 0 和 1 之间的随机数（randomnumber）。
- 如果数字小于elementprobability，
- 照常从 BST 中删除元素，更新所有必要节点的leftbranchweight 和rightbranchweight，并返回元素。
- 否则，如果数字小于（elementprobability + leftbranchweight）
- 在leftchild上递归（使用leftchild作为节点运行算法）
- 别的
- 递归右孩子
当我们最终使用这些权重找到要返回的元素时，我们要么简单地返回它（带替换），要么删除它并更新树中的相关权重（不带替换）。
免责声明：该算法是粗糙的，这里没有尝试关于正确实现 BST 的论文；相反，希望这个答案能帮助那些真正需要快速加权选择而不需要替换的人（就像我一样）。
于 2012-03-22T17:07:26.813 回答
4
在 O(N) 时间内首先创建一个额外的 O(N) 大小的数据结构之后，可以在 O(1) 时间内进行加权随机选择和替换。该算法基于Walker 和 Vose 开发的Alias Method ，此处对此进行了很好的描述。
基本思想是直方图中的每个 bin 将由统一的 RNG 以 1/N 的概率选择。因此，我们将遍历它，对于任何会收到过多命中的人口不足的 bin，将多余的 bin 分配给人口过多的 bin。对于每个 bin，我们存储属于它的命中百分比，以及超出部分的合作伙伴 bin。这个版本跟踪大小的箱子，无需额外的堆栈。它使用合作伙伴的索引（存储在 中bucket[1]）作为他们已经被处理的指标。
这是一个最小的python实现，基于这里的C实现
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 = [a-b 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]))
于 2015-04-18T20:07:58.990 回答
1
这是一个老问题，numpy 现在提供了一个简单的解决方案，所以我想我会提到它。numpy 的当前版本是 1.2 版，numpy.random.choice允许在有或没有替换的情况下以及给定的权重下进行采样。
于 2021-03-09T19:34:23.203 回答
0
假设您想用概率从列表 ['white','blue','black','yellow','green'] 中采样 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
于 2016-10-16T15:07:49.500 回答
0
我们面临一个问题，即每个 epoch 按比例随机选择候选人K的验证者一次。N但这给我们带来了以下问题：
想象一下每个候选人的概率：
0.1
0.1
0.8
在 1'000'000 次无替换2选择后，每个候选人的概率变为：3
0.254315
0.256755
0.488930
你应该知道，那些原始的概率是无法实现不替换2的选择的。3
但我们希望初始概率是利润分配概率。否则，它会使小型候选人池更有利可图。所以我们意识到随机选择和替换将帮助我们——随机选择并存储每个验证者的权重以进行奖励分配>K：N
std::vector<int> validators;
std::vector<int> weights(n);
int totalWeights = 0;
for (int j = 0; validators.size() < m; j++) {
int value = rand() % likehoodsSum;
for (int i = 0; i < n; i++) {
if (value < likehoods[i]) {
if (weights[i] == 0) {
validators.push_back(i);
}
weights[i]++;
totalWeights++;
break;
}
value -= likehoods[i];
}
}
它在数百万个样本上给出了几乎原始的奖励分布：
0.101230
0.099113
0.799657
于 2019-08-12T18:23:38.567 回答