Взвешенная версия random.choice

Question

Мне нужно было написать взвешенную версию 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

Эта функция кажется мне слишком сложной и безобразной. Я надеюсь, что все здесь могут предложить некоторые предложения по улучшению или альтернативные способы сделать это. Эффективность не так важна для меня, как чистота кода и удобочитаемость.

Answer 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 изменить поведение, чтобы нарисованные элементы не заменялись.

Answer 2

Начиная с Python3.6 есть метод choices от random модуль.

Python 3.6.1 (v3.6.1:69c0db5050, Mar 21 2017, 01:21:04)
Type 'copyright', 'credits' or 'license' for more information
IPython 6.0.0 -- An enhanced Interactive Python. Type '?' for help.

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']]

И люди также упоминали, что есть numpy.random.choice которые поддерживают веса, НО не поддерживают 2-мерные массивы и так далее.

Таким образом, в принципе вы можете получить все, что вам нравится (см. Обновление) с помощью встроенного random.choices если у вас 3.6.x Python.

ОБНОВЛЕНИЕ: Как любезно упомянуто @roganjosh, random.choices не может возвращать значения без замены, как указано в документации:

Вернуть k размерный список элементов, выбранных из популяции с заменой.

И блестящий ответ @ronan-paixão гласит, что numpy.choice имеет replace аргумент, который контролирует такое поведение.

Answer 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"

Answer 4

1. Расставьте веса в накопительное распределение.
2. Используйте random.random(), чтобы выбрать случайное число 0.0 <= x < total,
3. Выполните поиск по распределению, используя bisect.bisect, как показано в примере по адресу http://docs.python.org/dev/library/bisect.html.

from random import random
from bisect import bisect

def weighted_choice(choices):
    values, weights = zip(*choices)
    total = 0
    cum_weights = []
    for w in weights:
        total += w
        cum_weights.append(total)
    x = random() * total
    i = bisect(cum_weights, x)
    return values[i]

>>> weighted_choice([("WHITE",90), ("RED",8), ("GREEN",2)])
'WHITE'

Если вам нужно сделать более одного выбора, разделите его на две функции: одну для построения совокупных весов, а другую для деления пополам на случайную точку.

Answer 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\texpected\tactual"
for i in range(len(probs)):
    print "%s\t%0.4f\t%0.4f" % (items[i], probs[i], results[i])

Если вы знаете, сколько выборов нужно сделать заранее, вы можете сделать это без цикла, подобного следующему:

numpy.random.choice(items, trials, p=probs)

Answer 6

Начиная с Python v3.6, random.choices может быть использован для возврата list элементов указанного размера из данной совокупности с необязательными весами.

random.choices(population, weights=None, *, cum_weights=None, k=1)

• население: list содержащие уникальные наблюдения. (Если пусто, поднимает IndexError)

• веса: точнее, относительные веса, необходимые для выбора.

• cum_weights: совокупные веса, необходимые для выбора.

• к: размер (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] для нашего надуманного случая результат тот же, а последний кажется более быстрым / эффективным.

Answer 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)

Answer 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']

Answer 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

Answer 10

Вот очень простой и простой подход к взвешенному выбору:

np.random.choice(['A', 'B', 'C'], p=[0.3, 0.4, 0.3])

Answer 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))

Answer 12

Я бы потребовал, чтобы сумма вариантов была равна 1, но это все равно работает

def weightedChoice(choices):
    # Safety check, you can remove it
    for c,w in choices:
        assert w >= 0


    tmp = random.uniform(0, sum(c for c,w in choices))
    for choice,weight in choices:
        if tmp < weight:
            return choice
        else:
            tmp -= weight
     raise ValueError('Negative values in input')

Answer 13

Я, вероятно, слишком поздно, чтобы внести что-то полезное, но вот простой, короткий и очень эффективный фрагмент:

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]

Answer 14

Если ваш список взвешенных вариантов относительно статичен, и вы хотите частую выборку, вы можете сделать один 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]

Answer 15

Если у вас установлен 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]

Потому что из пакета сантехнических адаптеров можно собрать что угодно! Хотя... Я должен признать, что ответ Неда, хоть и немного длиннее, но для понимания легче.

Answer 16

Вот еще одна версия weighted_choice, которая использует numpy. Передайте вектор весов, и он вернет массив из 0, содержащий 1, указывающий, какой лот был выбран. В коде по умолчанию используется только одна раздача, но вы можете указать количество разыгранных розыгрышей, и будет возвращено количество разыгранных бинов.

Если вектор весовых коэффициентов не равен 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])

Answer 17

Это зависит от того, сколько раз вы хотите попробовать дистрибутив.

Предположим, вы хотите попробовать распределение 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]

Answer 18

Общее решение:

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]

Answer 19

Об этом есть лекция Себастьяна Турна в бесплатном курсе Udacity AI для робототехники. В основном он создает круговой массив индексированных весов, используя оператор 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]

Затем перейдите к следующему индексу для повторной выборки на основе вероятностей (или нормализованной вероятности в случае, представленном в курсе).

Ссылка на лекцию: https://classroom.udacity.com/courses/cs373/lessons/48704330/concepts/487480820923

Я вошел в Udacity со своей школьной учетной записью, поэтому, если ссылка не работает, это Урок 8, видео номер 21 Искусственного интеллекта для робототехники, где он читает лекции по фильтрам частиц.

Answer 20

Я посмотрел указанную другую нить и нашел этот вариант в своем стиле кодирования, он возвращает индекс выбора для подсчета, но просто вернуть строку (закомментированная альтернатива возврата):

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])

Answer 21

Другой способ сделать это, предполагая, что у нас есть веса с тем же индексом, что и у элементов в массиве элементов.

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]])

Теперь предположим, что нам нужно выбрать 3 элемента в 1 испытании. Вы можете предположить, что есть три шара 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.

Answer 22

скажем, у вас есть

      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())]

Answer 23

Если вы не определили заранее, сколько предметов вы хотите выбрать (поэтому вы не делаете что-то вроде ) и у вас просто есть вероятности, вы можете сделать следующее. Обратите внимание, что ваши вероятности не должны в сумме равняться 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']

Answer 24

Используя NumPy

def choice(items, weights):
    return items[np.argmin((np.cumsum(weights) / sum(weights)) < np.random.rand())]

Answer 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

Answer 26

Одним из способов является рандомизация по сумме всех весов, а затем использование значений в качестве предельных точек для каждой переменной. Вот грубая реализация в качестве генератора.

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

Answer 27

Мне нужно было сделать что-то вроде этого очень быстро, очень просто, от поиска идей я наконец-то создал этот шаблон. Идея состоит в том, чтобы получить взвешенные значения в виде json от API, который здесь моделируется диктом.

Затем переведите его в список, в котором каждое значение повторяется пропорционально его весу, и просто используйте 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)

Answer 28

Предоставьте 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

Answer 29

Шаг 1: Создайте CDF Fв котором ты интересен

Шаг 2. Создайте URL -адресu

Шаг 3: Оцените z=F^{-1}(u)

Это моделирование описывается в курсе теории вероятностей или случайных процессов. Это применимо только потому, что у вас есть легкий CDF.