从元素具有权重的列表中选择k个随机元素

Question

这里精美地描述了没有任何权重(相等概率)的选择.

我想知道是否有办法将这种方法转换为加权方法.

我也对其他方法感兴趣.

更新:无需更换的采样

Answer 1

如果采样是替换的,您可以使用此算法(在Python中实现):

import random

items = [(10, "low"),
         (100, "mid"),
         (890, "large")]

def weighted_sample(items, n):
    total = float(sum(w for w, v in items))
    i = 0
    w, v = items[0]
    while n:
        x = total * (1 - random.random() ** (1.0 / n))
        total -= x
        while x > w:
            x -= w
            i += 1
            w, v = items[i]
        w -= x
        yield v
        n -= 1

这是O(n + m),其中m是项目数.

为什么这样做？它基于以下算法:

def n_random_numbers_decreasing(v, n):
    """Like reversed(sorted(v * random() for i in range(n))),
    but faster because we avoid sorting."""
    while n:
        v *= random.random() ** (1.0 / n)
        yield v
        n -= 1

该功能weighted_sample就是这个算法与items列表的步行融合,以挑选出那些随机数所选择的项目.

这又起作用,因为n个随机数0 ... v将全部碰巧小于z的概率是P =(z/v)ⁿ.求解z,得到z = vP ^1/n.用随机数代替P选择正确分布的最大数; 我们可以重复这个过程来选择所有其他数字.

如果采样没有替换,您可以将所有项目放入二进制堆中,其中每个节点缓存该子堆中所有项目的权重总和.构建堆是O(m).从堆中选择一个关于权重的随机项是O(log m).删除该项目并更新缓存的总计也是O(log m).所以你可以在O(m + n log m)时间内选择n项.

(注意:"权重"在这里意味着每次选择一个元素时,剩余的可能性都会按其权重成比例选择.这并不意味着元素出现在输出中,其可能性与其权重成比例.)

这是一个实现,充分评论:

import random

class Node:
    # Each node in the heap has a weight, value, and total weight.
    # The total weight, self.tw, is self.w plus the weight of any children.
    __slots__ = ['w', 'v', 'tw']
    def __init__(self, w, v, tw):
        self.w, self.v, self.tw = w, v, tw

def rws_heap(items):
    # h is the heap. It's like a binary tree that lives in an array.
    # It has a Node for each pair in `items`. h[1] is the root. Each
    # other Node h[i] has a parent at h[i>>1]. Each node has up to 2
    # children, h[i<<1] and h[(i<<1)+1].  To get this nice simple
    # arithmetic, we have to leave h[0] vacant.
    h = [None]                          # leave h[0] vacant
    for w, v in items:
        h.append(Node(w, v, w))
    for i in range(len(h) - 1, 1, -1):  # total up the tws
        h[i>>1].tw += h[i].tw           # add h[i]'s total to its parent
    return h

def rws_heap_pop(h):
    gas = h[1].tw * random.random()     # start with a random amount of gas

    i = 1                     # start driving at the root
    while gas >= h[i].w:      # while we have enough gas to get past node i:
        gas -= h[i].w         #   drive past node i
        i <<= 1               #   move to first child
        if gas >= h[i].tw:    #   if we have enough gas:
            gas -= h[i].tw    #     drive past first child and descendants
            i += 1            #     move to second child
    w = h[i].w                # out of gas! h[i] is the selected node.
    v = h[i].v

    h[i].w = 0                # make sure this node isn't chosen again
    while i:                  # fix up total weights
        h[i].tw -= w
        i >>= 1
    return v

def random_weighted_sample_no_replacement(items, n):
    heap = rws_heap(items)              # just make a heap...
    for i in range(n):
        yield rws_heap_pop(heap)        # and pop n items off it.

Answer 2

如果采样是替换,请使用轮盘选择技术(通常用于遗传算法):

1. 对权重进行排序
2. 计算累积权重
3. 选择一个随机数 [0,1]*totalWeight
4. 找到此数字落入的时间间隔
5. 选择具有相应间隔的元素
6. 重复k次数

如果采样没有替换,您可以通过在每次迭代后从列表中删除所选元素来调整上述技术,然后重新标准化权重,使其总和为1(有效概率分布函数)

Answer 3

我知道这是一个非常古老的问题,但是如果你应用一点数学,我认为在O(n)时间有一个巧妙的技巧!

该指数分布有两个非常有用的特性.

1. 给定来自具有不同速率参数的不同指数分布的n个样本,给定样本的最小概率等于其速率参数除以所有速率参数的总和.

2. 它是"无记忆的".因此,如果您已经知道最小值,那么任何剩余元素是第二个到最小值的概率与如果真正的最小值被移除(并且从未生成)的概率相同,那个元素将是新的分钟.这看起来很明显,但我认为由于某些条件概率问题,其他分布可能不是这样.

使用事实1,我们知道选择单个元素可以通过生成速率参数等于权重的指数分布样本,然后选择具有最小值的指数分布样本来完成.

使用事实2,我们知道我们不必重新生成指数样本.相反,只需为每个元素生成一个元素,并使用最低样本的k元素.

找到最低k可以在O(n)中完成.使用Quickselect算法查找第k个元素,然后简单地再次通过所有元素并输出低于第k个的所有元素.

一个有用的说明:如果您无法立即访问库以生成指数分布样本,则可以通过以下方式轻松完成: -ln(rand())/weight