带或不带替换的加权随机选择

最近我需要从列表中加权随机选择元素,无论是否有替换.虽然有未知加权选择的众所周知和良好的算法,有些用于无替换的加权选择(例如修改算法),我找不到任何好的算法用于替换加权选择.我也想避免使用resevoir方法,因为我选择了列表中的一小部分,这个小部分足够小以容纳在内存中.

有没有人对这种情况下的最佳方法有任何建议？我有自己的解决方案,但我希望找到更高效,更简单或两者兼而有之的方法.

1> John with wa..：

---

使用不变列表替换样本的最快方法之一是别名方法.核心直觉是我们可以为加权列表创建一组大小相等的二进制位,可以通过位操作非常有效地索引,以避免二进制搜索.结果表明,正确完成后,我们只需要从每个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

bitshift它lg2(p),找到索引分区.因此,我们将其移位3,屈服001.1或定位1,从而将分区2 移位.

如果拆分分区,请使用移位的随机数的小数部分来确定拆分.在这种情况下,值是0.5,然后0.5 < 0.6返回a.

这是一些代码和另一种解释,但不幸的是它没有使用位移技术,也没有我实际验证它.

2> josliber..：

---

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证明了他们的方法等同于随机抽样，而无需替换链接的论文。

3> Nick Johnson..：

---

这是我想出的无需替换的加权选择:

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是要选择的项目数.

---

第一个功能是辉煌的,但唉它没有正确加重项目.考虑`WeightedSelectionWithoutReplacement([(1,'A'),(2,'B')],1)`.它将选择A的概率为1/4,而不是1/3.很难解决.