Взвешенная версия 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 - последовательность в том же порядке1008 *.Вы также можете использовать ключевое слово 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, которые поддерживают веса, НО он не поддерживает 2d массивы и так далее.

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

UPDATE : Как любезно сказано @ 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 () , чтобы выбрать случайный float 0.0 <= x < total.
3. Поиск распространение с использованием bisect.bisect as показано в примере на http://docs.python.org/dev/library/bisect.html#other-examples.

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

Сырой, но может быть достаточно:

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 7

Если у вас есть взвешенный словарь вместо списка, вы можете написать это

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 8

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

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

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

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

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

• k : размер (len) list для вывода. (По умолчанию len()=1)

---

Несколько предостережений:

1) Используется взвешенная выборка с заменой, чтобы вытянутые элементы были позже заменены. Значения в последовательности весов сами по себе не имеют значения, но их относительное отношение имеет значение.

В отличие от np.random.choice, который может принимать только вероятности в качестве весов, а также который должен обеспечивать суммирование индивидуальных вероятностей до 1 критерия, здесь нет таких правил. Пока они принадлежат числовым типам (int/float/fraction кроме Decimal type), они все равно будут работать.

>>> 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 , выбор выполняется с равной вероятностью. Если указана последовательность weights , она должна быть такой же длины, что и последовательность population .

Указание весов и 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 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#l340

Answer 10

Я бы потребовал, чтобы сумма вариантов составляла 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')