Uma versão ponderada do random.choice

Eu precisava escrever uma versão ponderada do random.choice (cada elemento da lista tem uma probabilidade diferente de ser selecionado). Isto é o que eu vim com:

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

Essa função me parece excessivamente complexa e feia. Espero que todos aqui possam oferecer algumas sugestões para aprimorá-lo ou maneiras alternativas de fazer isso. A eficiência não é tão importante para mim quanto a limpeza e a legibilidade do código.

Desde a versão 1.7.0, o NumPy possui uma choicefunção que suporta distribuições de probabilidade.

from numpy.random import choice
draw = choice(list_of_candidates, number_of_items_to_pick,
              p=probability_distribution)

Observe que probability_distributioné uma sequência na mesma ordem de list_of_candidates. Você também pode usar a palavra replace=False- chave para alterar o comportamento para que os itens desenhados não sejam substituídos.

Desde o Python 3.6, existe um método choicesdo randommódulo.

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

Observe que random.choicesa amostra será substituída de acordo com os documentos :

Retorne uma klista dimensionada de elementos escolhidos da população com substituição.

Se você precisar fazer uma amostra sem substituição, então, como a brilhante resposta de @ ronan-paixão afirma, você pode usar numpy.choice, cujo replaceargumento controla esse comportamento.

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"

1. Organize os pesos em uma distribuição cumulativa.
2. Use random.random () para escolher um flutuador aleatório 0.0 <= x < total.
3. Pesquise a distribuição usando bisect.bisect, como mostra o exemplo em 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'

Se você precisar fazer mais de uma escolha, divida-a em duas funções, uma para criar os pesos cumulativos e outra para dividir em um ponto aleatório.

Se você não se importa em usar numpy, pode usar numpy.random.choice .

Por exemplo:

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

Se você souber quantas seleções precisa fazer com antecedência, poderá fazê-lo sem um loop como este:

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

Bruto, mas pode ser suficiente:

import random
weighted_choice = lambda s : random.choice(sum(([v]*wt for v,wt in s),[]))

Funciona?

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

Impressões:

[('WHITE', 904), ('GREEN', 22), ('RED', 74)]

Assume que todos os pesos são inteiros. Eles não precisam somar 100, apenas fiz isso para facilitar a interpretação dos resultados dos testes. (Se os pesos forem números de ponto flutuante, multiplique todos por 10 repetidamente até todos os pesos> = 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)

Se você possui um dicionário ponderado em vez de uma lista, pode escrever este

items = { "a": 10, "b": 5, "c": 1 } 
random.choice([k for k in items for dummy in range(items[k])])

Observe que [k for k in items for dummy in range(items[k])]produz esta lista['a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'c', 'b', 'b', 'b', 'b', 'b']

No Python v3.6, random.choicespoderia ser usado para retornar um listdos elementos de tamanho especificado da população especificada com pesos opcionais.

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

• população : listcontendo observações únicas. (Se vazio, aumenta IndexError)

• pesos : pesos precisos relativos, mais precisamente necessários para fazer seleções.

• cum_weights : pesos cumulativos necessários para fazer seleções.

• k : tamanho ( len) da listsaída. (Padrão len()=1)

Poucas advertências:

1) Utiliza amostragem ponderada com substituição, para que os itens sorteados sejam substituídos posteriormente. Os valores na sequência de pesos em si não importam, mas a razão relativa deles.

Diferente do np.random.choiceque só pode assumir probabilidades como pesos e também que deve garantir a soma de probabilidades individuais até 1 critério, não existem tais regulamentos aqui. Desde que pertençam a tipos numéricos ( int/float/fractionexceto o Decimaltipo), eles ainda serão executados.

>>> 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) Se não forem especificados pesos nem cum_weights , as seleções serão feitas com igual probabilidade. Se uma sequência de pesos for fornecida, ela deverá ter o mesmo comprimento que o sequência população .

A especificação de pesos e cum_weights aumenta a TypeError.

>>> random.choices(["white", "green", "red"], k=10)
['white', 'white', 'green', 'red', 'red', 'red', 'white', 'white', 'white', 'green']

3) cum_weights normalmente são resultados de itertools.accumulatefunções que são realmente úteis nessas situações.

_{Na documentação vinculada:}

Internamente, os pesos relativos são convertidos em pesos acumulados antes de fazer seleções, portanto, fornecer pesos cumulativos economiza trabalho.

Portanto, fornecer weights=[12, 12, 4]ou cum_weights=[12, 24, 28]para o nosso caso artificial produz o mesmo resultado e o último parece ser mais rápido / eficiente.

Aqui está a versão que está sendo incluída na biblioteca padrão do 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)]

Fonte: https://hg.python.org/cpython/file/tip/Lib/random.py#l340

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

Provavelmente estou muito atrasado para contribuir com algo útil, mas aqui está um trecho simples, curto e muito eficiente:

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]

Não há necessidade de classificar suas probabilidades ou criar um vetor com seu cmf, e ele termina assim que encontrar sua escolha. Memória: O (1), tempo: O (N), com tempo médio de execução ~ N / 2.

Se você tiver pesos, basta adicionar uma linha:

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]

Se sua lista de opções ponderadas for relativamente estática e você desejar amostragem frequente, poderá executar uma etapa de pré-processamento de O (N) e, em seguida, fazer a seleção em O (1), usando as funções nesta resposta relacionada .

# run only when `choices` changes.
preprocessed_data = prep(weight for _,weight in choices)

# O(1) selection
value = choices[sample(preprocessed_data)][0]

Eu olhei o outro thread apontado e surgiu com essa variação no meu estilo de codificação, isso retorna o índice de escolha para fins de cálculo, mas é simples retornar a string (alternativa de retorno comentada):

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

Depende de quantas vezes você deseja provar a distribuição.

Suponha que você queira provar a distribuição K vezes. Em seguida, a complexidade do tempo que utiliza np.random.choice()cada momento é O(K(n + log(n)))quando né o número de itens na distribuição.

No meu caso, eu precisava amostrar a mesma distribuição várias vezes da ordem de 10 ^ 3, em que n é da ordem de 10 ^ 6. Usei o código abaixo, que pré-calcula a distribuição cumulativa e a amostra O(log(n)). A complexidade geral do tempo é 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]

Se você possui o Python 3 e tem medo de instalar numpyou gravar seus próprios loops, você pode:

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]

Porque você pode construir qualquer coisa com uma bolsa de adaptadores de encanamento! Embora ... Devo admitir que a resposta de Ned, embora um pouco mais longa, seja mais fácil de entender.

Uma solução geral:

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]

Aqui está outra versão do weighted_choice que usa numpy. Passe o vetor de pesos e ele retornará uma matriz de 0 contendo um 1 indicando qual bin foi escolhida. O código padrão é apenas fazer um único sorteio, mas você pode passar o número de sorteios a serem feitos e as contagens por posição sorteada serão retornadas.

Se o vetor de pesos não somar 1, ele será normalizado.

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

Outra maneira de fazer isso, assumindo que temos pesos no mesmo índice que os elementos na matriz de elementos.

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

Agora, vamos supor que precisamos provar 3 itens em um teste. Você pode supor que há três bolas R, G, B presentes em grande quantidade na proporção de seus pesos dados pela matriz de pesos; o seguinte resultado pode ser possível:

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

você também pode pensar no número de itens a serem selecionados como número de testes binomiais / multinomiais em um conjunto. Portanto, o exemplo acima ainda pode funcionar como

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.

Há uma palestra sobre Sebastien Thurn no curso gratuito Udacity AI for Robotics. Basicamente, ele faz uma matriz circular dos pesos indexados usando o operador mod% , define uma variável beta como 0, escolhe aleatoriamente um índice, para loops através de N onde N é o número de índices e no loop for incrementa primeiro beta pela fórmula:

beta = beta + amostra uniforme de {0 ... 2 * Weight_max}

e depois aninhado no loop for, um loop while abaixo:

while w[index] < beta:
    beta = beta - w[index]
    index = index + 1

select p[index]

Em seguida, passe para o próximo índice para reamostrar com base nas probabilidades (ou probabilidade normalizada no caso apresentado no curso).

O link da palestra: https://classroom.udacity.com/courses/cs373/lessons/48704330/concepts/487480820923

Estou logado no Udacity com a conta da minha escola. Se o link não funcionar, é na Lição 8, vídeo número 21 da Inteligência Artificial para Robótica, onde ele está dando palestras sobre filtros de partículas.

Uma maneira é aleatorizar o total de todos os pesos e, em seguida, usar os valores como pontos limite para cada var. Aqui está uma implementação bruta como um gerador.

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

Usando numpy

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

Eu precisava fazer algo assim muito rápido, muito simples, desde a busca de idéias que finalmente construí este modelo. A idéia é receber os valores ponderados na forma de um json da API, que aqui é simulada pelo ditado.

Em seguida, traduza-o em uma lista na qual cada valor se repita proporcionalmente ao seu peso e use apenas random.choice para selecionar um valor da lista.

Eu tentei rodando com 10, 100 e 1000 iterações. A distribuição parece bastante sólida.

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)

Eu não amei a sintaxe de nenhuma delas. Eu realmente queria apenas especificar quais eram os itens e qual era o peso de cada um. Sei que poderia ter usado, random.choicesmas, em vez disso, escrevi rapidamente a aula abaixo.

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

Forneça a random.choice () uma lista pré-ponderada:

Solução e teste:

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)

Resultado:

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