Gere números aleatórios com uma determinada distribuição (numérica)

132

Eu tenho um arquivo com algumas probabilidades para valores diferentes, por exemplo:

1 0.1
2 0.05
3 0.05
4 0.2
5 0.4
6 0.2

Eu gostaria de gerar números aleatórios usando essa distribuição. Existe um módulo existente que lida com isso? É bastante simples codificar por conta própria (crie a função de densidade cumulativa, gere um valor aleatório [0,1] e escolha o valor correspondente), mas parece que isso deve ser um problema comum e provavelmente alguém criou uma função / módulo para isto.

Preciso disso porque quero gerar uma lista de aniversários (que não seguem nenhuma distribuição no randommódulo padrão ).

pafcu
fonte
2
Diferente de random.choice()? Você cria a lista mestre com o número adequado de ocorrências e escolhe uma. Esta é uma pergunta duplicada, é claro.
S.Lott
1
possível duplicata aleatória escolha ponderada
S.Lott
2
@ S.Lott não consome muita memória para grandes diferenças na distribuição?
Lucas Moeskops
2
@ S.Lott: Seu método de escolha provavelmente seria bom para um pequeno número de ocorrências, mas prefiro evitar criar listas enormes quando não for necessário.
pafcu
5
@ S.Lott: OK, cerca de 10000 * 365 = 3650000 = 3,6 milhões de elementos. Não tenho certeza sobre o uso de memória no Python, mas é pelo menos 3,6M * 4B = 14,4MB. Não é uma quantidade enorme, mas também não deve ser ignorada quando existe um método igualmente simples que não requer memória extra.
pafcu

Respostas:

118

scipy.stats.rv_discretepode ser o que você quer. Você pode fornecer suas probabilidades através do valuesparâmetro Você pode usar o rvs()método do objeto de distribuição para gerar números aleatórios.

Conforme apontado por Eugene Pakhomov nos comentários, você também pode passar um pparâmetro de palavra - chave para numpy.random.choice(), por exemplo,

numpy.random.choice(numpy.arange(1, 7), p=[0.1, 0.05, 0.05, 0.2, 0.4, 0.2])

Se você estiver usando o Python 3.6 ou superior, poderá usá random.choices()-lo na biblioteca padrão - veja a resposta de Mark Dickinson .

Sven Marnach
fonte
9
Na minha máquina numpy.random.choice()é quase 20 vezes mais rápido.
Eugene Pakhomov
9
faz exatamente o mesmo errado com a pergunta original. Exemplo:numpy.random.choice(numpy.arange(1, 7), p=[0.1, 0.05, 0.05, 0.2, 0.4, 0.2])
Eugene Pakhomov 20/06
1
@EugenePakhomov Isso é legal, eu não sabia disso. Eu posso ver que há uma resposta mencionando isso ainda mais, mas ele não contém nenhum código de exemplo e não possui muitos votos. Vou adicionar um comentário a esta resposta para melhor visibilidade.
Sven Marnach
2
Surpreendentemente, rv_discrete.rvs () funciona em tempo e memória de O (len (p) * tamanho)! Enquanto a opção () parece ser executada no tempo ideal O (len (p) + log (len (p)) * tamanho).
alyaxey
3
Se você estiver usando o Python 3.6 ou mais recente, há outra resposta que não requer nenhum pacote de complemento.
Mark Ransom
113

Desde o Python 3.6, existe uma solução para isso na biblioteca padrão do Python, a saber random.choices.

Exemplo de uso: vamos configurar uma população e pesos correspondentes aos da pergunta do OP:

>>> from random import choices
>>> population = [1, 2, 3, 4, 5, 6]
>>> weights = [0.1, 0.05, 0.05, 0.2, 0.4, 0.2]

Agora choices(population, weights)gera uma única amostra:

>>> choices(population, weights)
4

O argumento opcional somente palavra-chave kpermite solicitar mais de uma amostra de uma vez. Isso é valioso porque há algum trabalho preparatório que random.choicesdeve ser feito toda vez que é chamado, antes da geração de amostras; gerando muitas amostras de uma só vez, só precisamos fazer esse trabalho preparatório uma vez. Aqui, geramos um milhão de amostras e usamos collections.Counterpara verificar se a distribuição que obtemos corresponde aproximadamente aos pesos que fornecemos.

>>> million_samples = choices(population, weights, k=10**6)
>>> from collections import Counter
>>> Counter(million_samples)
Counter({5: 399616, 6: 200387, 4: 200117, 1: 99636, 3: 50219, 2: 50025})
Mark Dickinson
fonte
Existe uma versão do Python 2.7 para isso?
precisa saber é o seguinte
1
@ abbas786: Não integrado, mas as outras respostas a esta pergunta devem funcionar no Python 2.7. Você também pode procurar a fonte Python 3 para random.choices e copiá-la, se assim for.
Mark Dickinson
27

Uma vantagem de gerar a lista usando o CDF é que você pode usar a pesquisa binária. Enquanto você precisa de O (n) tempo e espaço para pré-processamento, é possível obter k números em O (k log n). Como as listas Python normais são ineficientes, você pode usar o arraymódulo

Se você insiste em espaço constante, pode fazer o seguinte; O (n) tempo, O (1) espaço.

def random_distr(l):
    r = random.uniform(0, 1)
    s = 0
    for item, prob in l:
        s += prob
        if s >= r:
            return item
    return item  # Might occur because of floating point inaccuracies
sdcvvc
fonte
A ordem dos pares (item, prob) na lista é importante na sua implementação, certo?
stackoverflowuser2010
1
@ stackoverflowuser2010: Ele não deve importar (erros modulo em ponto flutuante)
sdcvvc
Agradável. Eu achei que era 30% mais rápido que scipy.stats.rv_discrete.
Aspen
1
Muitas vezes, essa função lançará um KeyError porque a última linha.
imrek
@DrunkenMaster: Eu não entendo. Você sabe que l[-1]retorna o último elemento da lista?
Sdcvvc 9/09/15
15

Talvez seja tarde demais. Mas você pode usar numpy.random.choice(), passando o pparâmetro:

val = numpy.random.choice(numpy.arange(1, 7), p=[0.1, 0.05, 0.05, 0.2, 0.4, 0.2])
Ramon Martinez
fonte
1
O OP não quer usar random.choice()- veja os comentários.
Pobrelkey
5
numpy.random.choice()é completamente diferente random.choice()e suporta distribuição de probabilidade.
Eugene Pakhomov
14

(OK, eu sei que você está pedindo um termo-encolhimento, mas talvez essas soluções domésticas não tenham sido sucintas o suficiente para você gostar. :-)

pdf = [(1, 0.1), (2, 0.05), (3, 0.05), (4, 0.2), (5, 0.4), (6, 0.2)]
cdf = [(i, sum(p for j,p in pdf if j < i)) for i,_ in pdf]
R = max(i for r in [random.random()] for i,c in cdf if c <= r)

Eu pseudo-confirmei que isso funciona através dos olhos da saída desta expressão:

sorted(max(i for r in [random.random()] for i,c in cdf if c <= r)
       for _ in range(1000))
Marcelo Cantos
fonte
Isso parece impressionante. Apenas para colocar as coisas em contexto, eis os resultados de 3 execuções consecutivas do código acima: ['Contagem de 1 com prob: 0,1 é: 113', 'Contagem de 2 com prob: 0,05 é: 55', 'Contagem de 3 com prob: 0,05 é: 50 ',' Contagem de 4 com prob: 0,2 é: 201 ',' Contagem de 5 com prob: 0,4 é: 388 ',' Contagem de 6 com prob: 0,2 é: 193 ']. ............. ['Contagem de 1 com prob: 0,1 é: 77', 'Contagem de 2 com prob: 0,05 é: 60', 'Contagem de 3 com prob: 0,05 é: 51 ',' Contagem de 4 com prob: 0,2 é: 193 ',' Contagem de 5 com prob: 0,4 é: 438 ',' Contagem de 6 com prob: 0,2 é: 181 '] ........ ..... e
Vaibhav
['Contagem de 1 com prob: 0,1 é: 84', 'Contagem de 2 com prob: 0,05 é: 52', 'Contagem de 3 com prob: 0,05 é: 53', 'Contagem de 4 com prob: 0,2 é: 210 ',' Contagem de 5 com prob: 0,4 é: 405 ',' Contagem de 6 com prob: 0,2 é: 196 ']
Vaibhav
Uma pergunta, como faço para retornar max (i ..., se 'i' é um objeto? ''
Vaibhav
@Vaibhav inão é um objeto.
Marcelo Cantos
6

Eu escrevi uma solução para tirar amostras aleatórias de uma distribuição contínua personalizada .

Eu precisava disso para um caso de uso semelhante ao seu (por exemplo, gerar datas aleatórias com uma determinada distribuição de probabilidade).

Você só precisa da função random_custDiste da linha samples=random_custDist(x0,x1,custDist=custDist,size=1000). O resto é decoração ^^.

import numpy as np

#funtion
def random_custDist(x0,x1,custDist,size=None, nControl=10**6):
    #genearte a list of size random samples, obeying the distribution custDist
    #suggests random samples between x0 and x1 and accepts the suggestion with probability custDist(x)
    #custDist noes not need to be normalized. Add this condition to increase performance. 
    #Best performance for max_{x in [x0,x1]} custDist(x) = 1
    samples=[]
    nLoop=0
    while len(samples)<size and nLoop<nControl:
        x=np.random.uniform(low=x0,high=x1)
        prop=custDist(x)
        assert prop>=0 and prop<=1
        if np.random.uniform(low=0,high=1) <=prop:
            samples += [x]
        nLoop+=1
    return samples

#call
x0=2007
x1=2019
def custDist(x):
    if x<2010:
        return .3
    else:
        return (np.exp(x-2008)-1)/(np.exp(2019-2007)-1)
samples=random_custDist(x0,x1,custDist=custDist,size=1000)
print(samples)

#plot
import matplotlib.pyplot as plt
#hist
bins=np.linspace(x0,x1,int(x1-x0+1))
hist=np.histogram(samples, bins )[0]
hist=hist/np.sum(hist)
plt.bar( (bins[:-1]+bins[1:])/2, hist, width=.96, label='sample distribution')
#dist
grid=np.linspace(x0,x1,100)
discCustDist=np.array([custDist(x) for x in grid]) #distrete version
discCustDist*=1/(grid[1]-grid[0])/np.sum(discCustDist)
plt.plot(grid,discCustDist,label='custom distribustion (custDist)', color='C1', linewidth=4)
#decoration
plt.legend(loc=3,bbox_to_anchor=(1,0))
plt.show()

Distribuição personalizada contínua e distribuição discreta de amostras

O desempenho desta solução é improvável, com certeza, mas eu prefiro a legibilidade.

Markus Dutschke
fonte
1

Faça uma lista de itens, com base em weights:

items = [1, 2, 3, 4, 5, 6]
probabilities= [0.1, 0.05, 0.05, 0.2, 0.4, 0.2]
# if the list of probs is normalized (sum(probs) == 1), omit this part
prob = sum(probabilities) # find sum of probs, to normalize them
c = (1.0)/prob # a multiplier to make a list of normalized probs
probabilities = map(lambda x: c*x, probabilities)
print probabilities

ml = max(probabilities, key=lambda x: len(str(x)) - str(x).find('.'))
ml = len(str(ml)) - str(ml).find('.') -1
amounts = [ int(x*(10**ml)) for x in probabilities]
itemsList = list()
for i in range(0, len(items)): # iterate through original items
  itemsList += items[i:i+1]*amounts[i]

# choose from itemsList randomly
print itemsList

Uma otimização pode ser normalizar valores pelo maior divisor comum, para diminuir a lista de destinos.

Além disso, isso pode ser interessante.

khachik
fonte
Se a lista de itens for grande, isso poderá consumir muita memória extra.
pafcu
@pafcu Concordou. Apenas uma solução, a segunda que me veio à mente (a primeira foi procurar algo como "python de probabilidade de peso" :)).
Khachik
1

Outra resposta, provavelmente mais rápida :)

distribution = [(1, 0.2), (2, 0.3), (3, 0.5)]  
# init distribution  
dlist = []  
sumchance = 0  
for value, chance in distribution:  
    sumchance += chance  
    dlist.append((value, sumchance))  
assert sumchance == 1.0 # not good assert because of float equality  

# get random value  
r = random.random()  
# for small distributions use lineair search  
if len(distribution) < 64: # don't know exact speed limit  
    for value, sumchance in dlist:  
        if r < sumchance:  
            return value  
else:  
    # else (not implemented) binary search algorithm  
Lucas Moeskops
fonte
1
from __future__ import division
import random
from collections import Counter


def num_gen(num_probs):
    # calculate minimum probability to normalize
    min_prob = min(prob for num, prob in num_probs)
    lst = []
    for num, prob in num_probs:
        # keep appending num to lst, proportional to its probability in the distribution
        for _ in range(int(prob/min_prob)):
            lst.append(num)
    # all elems in lst occur proportional to their distribution probablities
    while True:
        # pick a random index from lst
        ind = random.randint(0, len(lst)-1)
        yield lst[ind]

Verificação:

gen = num_gen([(1, 0.1),
               (2, 0.05),
               (3, 0.05),
               (4, 0.2),
               (5, 0.4),
               (6, 0.2)])
lst = []
times = 10000
for _ in range(times):
    lst.append(next(gen))
# Verify the created distribution:
for item, count in Counter(lst).iteritems():
    print '%d has %f probability' % (item, count/times)

1 has 0.099737 probability
2 has 0.050022 probability
3 has 0.049996 probability 
4 has 0.200154 probability
5 has 0.399791 probability
6 has 0.200300 probability
Saksham Varma
fonte
1

com base em outras soluções, você gera distribuição acumulativa (como número inteiro ou flutua o que quiser) e, em seguida, pode usar o bisset para torná-lo mais rápido

este é um exemplo simples (usei números inteiros aqui)

l=[(20, 'foo'), (60, 'banana'), (10, 'monkey'), (10, 'monkey2')]
def get_cdf(l):
    ret=[]
    c=0
    for i in l: c+=i[0]; ret.append((c, i[1]))
    return ret

def get_random_item(cdf):
    return cdf[bisect.bisect_left(cdf, (random.randint(0, cdf[-1][0]),))][1]

cdf=get_cdf(l)
for i in range(100): print get_random_item(cdf),

a get_cdffunção converteria de 20, 60, 10, 10 para 20, 20 + 60, 20 + 60 + 10, 20 + 60 + 10 + 10

agora escolhemos um número aleatório de até 20 + 60 + 10 + 10 usando random.randinte usamos bisect para obter o valor real de maneira rápida

Muayyad Alsadi
fonte
0

Nenhuma dessas respostas é particularmente clara ou simples.

Aqui está um método claro e simples que é garantido para o trabalho.

acumulate_normalize_probabilities usa um dicionário pque mapeia símbolos para probabilidades OU frequências. Ele gera uma lista utilizável de tuplas das quais fazer a seleção.

def accumulate_normalize_values(p):
        pi = p.items() if isinstance(p,dict) else p
        accum_pi = []
        accum = 0
        for i in pi:
                accum_pi.append((i[0],i[1]+accum))
                accum += i[1]
        if accum == 0:
                raise Exception( "You are about to explode the universe. Continue ? Y/N " )
        normed_a = []
        for a in accum_pi:
                normed_a.append((a[0],a[1]*1.0/accum))
        return normed_a

Rendimentos:

>>> accumulate_normalize_values( { 'a': 100, 'b' : 300, 'c' : 400, 'd' : 200  } )
[('a', 0.1), ('c', 0.5), ('b', 0.8), ('d', 1.0)]

Por que funciona

A acumulação etapa de transforma cada símbolo em um intervalo entre si e a probabilidade ou frequência dos símbolos anteriores (ou 0 no caso do primeiro símbolo). Esses intervalos podem ser usados ​​para selecionar (e, assim, amostrar a distribuição fornecida), basta percorrer a lista até que o número aleatório no intervalo 0,0 -> 1,0 (preparado anteriormente) seja menor ou igual ao ponto final do intervalo do símbolo atual.

A normalização nos liberta da necessidade de garantir que tudo seja de algum valor. Após a normalização, o "vetor" de probabilidades é 1.0.

O restante do código para seleção e geração de uma amostra arbitrariamente longa da distribuição está abaixo:

def select(symbol_intervals,random):
        print symbol_intervals,random
        i = 0
        while random > symbol_intervals[i][1]:
                i += 1
                if i >= len(symbol_intervals):
                        raise Exception( "What did you DO to that poor list?" )
        return symbol_intervals[i][0]


def gen_random(alphabet,length,probabilities=None):
        from random import random
        from itertools import repeat
        if probabilities is None:
                probabilities = dict(zip(alphabet,repeat(1.0)))
        elif len(probabilities) > 0 and isinstance(probabilities[0],(int,long,float)):
                probabilities = dict(zip(alphabet,probabilities)) #ordered
        usable_probabilities = accumulate_normalize_values(probabilities)
        gen = []
        while len(gen) < length:
                gen.append(select(usable_probabilities,random()))
        return gen

Uso:

>>> gen_random (['a','b','c','d'],10,[100,300,400,200])
['d', 'b', 'b', 'a', 'c', 'c', 'b', 'c', 'c', 'c']   #<--- some of the time
Cris Stringfellow
fonte
-1

Aqui está uma maneira mais eficaz de fazer isso:

Basta chamar a seguinte função com sua matriz 'pesos' (assumindo os índices como os itens correspondentes) e o não. de amostras necessárias. Esta função pode ser facilmente modificada para lidar com pares ordenados.

Retorna índices (ou itens) amostrados / selecionados (com substituição) usando suas respectivas probabilidades:

def resample(weights, n):
    beta = 0

    # Caveat: Assign max weight to max*2 for best results
    max_w = max(weights)*2

    # Pick an item uniformly at random, to start with
    current_item = random.randint(0,n-1)
    result = []

    for i in range(n):
        beta += random.uniform(0,max_w)

        while weights[current_item] < beta:
            beta -= weights[current_item]
            current_item = (current_item + 1) % n   # cyclic
        else:
            result.append(current_item)
    return result

Uma breve nota sobre o conceito usado no loop while. Reduzimos o peso do item atual do beta cumulativo, que é um valor acumulado construído uniformemente de forma aleatória, e incrementamos o índice atual para encontrar o item, cujo peso corresponde ao valor do beta.

Vaibhav
fonte