Генерация случайных чисел с заданным (числовым) распределением

134

У меня есть файл с некоторыми вероятностями для разных значений, например:

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

Я хотел бы генерировать случайные числа, используя это распределение. Существует ли существующий модуль, который этим занимается? Довольно просто написать код самостоятельно (построить кумулятивную функцию плотности, сгенерировать случайное значение [0,1] и выбрать соответствующее значение), но похоже, что это должна быть общая проблема, и, возможно, кто-то создал функцию / модуль для Это.

Мне это нужно, потому что я хочу сгенерировать список дней рождения (который не соответствует никакому распределению в стандартном randomмодуле).

pafcu
источник
2
Кроме random.choice()? Вы составляете главный список с нужным количеством вхождений и выбираете одно. Это, конечно, повторяющийся вопрос.
S.Lott
1
возможный дубликат случайного взвешенного выбора
S.Lott
2
@ S.Lott разве не так много памяти из-за больших различий в распределении?
Лукас Моэскопс,
2
@ S.Lott: Ваш метод выбора, вероятно, подходит для небольшого количества случаев, но я бы предпочел избегать создания огромных списков, когда в этом нет необходимости.
pafcu
5
@ S.Lott: Окей, примерно 10000 * 365 = 3650000 = 3,6 миллиона элементов. Я не уверен в использовании памяти в Python, но это не менее 3,6 МБ * 4Б = 14,4 МБ. Не очень много, но не то, что вы также должны игнорировать, когда есть такой же простой метод, который не требует дополнительной памяти.
pafcu

Ответы:

120

scipy.stats.rv_discreteможет быть то, что вы хотите. Вы можете указать свои вероятности с помощью valuesпараметра. Затем вы можете использовать rvs()метод объекта распределения для генерации случайных чисел.

Как отметил Евгений Пахомов в комментариях, вы также можете передать pпараметр ключевого слова numpy.random.choice(), например

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

Если вы используете Python 3.6 или выше, вы можете использовать random.choices()стандартную библиотеку - см. Ответ Марка Дикинсона .

Свен Марнах
источник
9
На моей машине numpy.random.choice()почти в 20 раз быстрее.
Евгений Пахомов
9
он делает то же самое по отношению к исходному вопросу. Например:numpy.random.choice(numpy.arange(1, 7), p=[0.1, 0.05, 0.05, 0.2, 0.4, 0.2])
Евгений Пахомов
1
@EugenePakhomov Замечательно, я этого не знал. Я вижу, что есть ответ, в котором говорится об этом далее, но он не содержит примеров кода и не имеет большого количества голосов. Я добавлю комментарий к этому ответу для большей наглядности.
Sven Marnach
2
Удивительно, но rv_discrete.rvs () работает за O (len (p) * size) времени и памяти! В то время как choice (), похоже, выполняется за оптимальное время O (len (p) + log (len (p)) * size).
alyaxey
3
Если вы используете Python 3.6 или новее, есть еще один ответ , который не требует дополнительных пакетов.
Марк Рэнсом
114

Начиная с Python 3.6, в стандартной библиотеке Python есть решение, а именно random.choices.

Пример использования: давайте настроим совокупность и веса, соответствующие значениям в вопросе 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]

Теперь choices(population, weights)генерирует один образец:

>>> choices(population, weights)
4

Необязательный аргумент, содержащий только ключевое слово, kпозволяет запросить более одного образца одновременно. Это ценно, потому что есть некоторая подготовительная работа, random.choicesкоторую нужно проделывать каждый раз, когда он вызывается, перед генерацией любых семплов; Создавая множество образцов одновременно, нам нужно сделать эту подготовительную работу только один раз. Здесь мы генерируем миллион выборок и используем их collections.Counterдля проверки того, что полученное нами распределение примерно соответствует заданным нами весам.

>>> 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})
Марк Дикинсон
источник
Есть ли для этого версия Python 2.7?
abbas786 05
1
@ abbas786: не встроен, но все остальные ответы на этот вопрос должны работать на Python 2.7. Вы также можете найти исходный код Python 3 для random.choices и скопировать его, если хотите.
Марк Дикинсон
27

Преимущество создания списка с использованием CDF состоит в том, что вы можете использовать двоичный поиск. Хотя вам нужно O (n) времени и места для предварительной обработки, вы можете получить k чисел за O (k log n). Поскольку обычные списки Python неэффективны, вы можете использовать arraymodule.

Если вы настаиваете на постоянном пространстве, вы можете сделать следующее; O (n) время, O (1) пространство.

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
источник
Порядок пар (элемент, проблема) в списке имеет значение в вашей реализации, верно?
stackoverflowuser2010
1
@ stackoverflowuser2010: Это не имеет значения (ошибки по модулю в
числах с
Ницца. Я обнаружил, что это на 30% быстрее, чем scipy.stats.rv_discrete.
Аспен
1
Довольно часто эта функция выдает ошибку KeyError, потому что последняя строка.
imrek
@DrunkenMaster: Я не понимаю. Знаете ли вы, что l[-1]возвращает последний элемент списка?
sdcvvc 09
15

Может, уже поздно. Но вы можете использовать numpy.random.choice(), передав pпараметр:

val = numpy.random.choice(numpy.arange(1, 7), p=[0.1, 0.05, 0.05, 0.2, 0.4, 0.2])
Рамон Мартинес
источник
1
OP не хочет использовать random.choice()- см. Комментарии.
побрелкей 01
5
numpy.random.choice()полностью отличается от random.choice()распределения вероятностей и поддерживает его.
Евгений Пахомов
14

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

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)

Я псевдо-подтвердил, что это работает, глядя на вывод этого выражения:

sorted(max(i for r in [random.random()] for i,c in cdf if c <= r)
       for _ in range(1000))
Марсело Кантос
источник
Выглядит впечатляюще. Чтобы представить вещи в контексте, вот результаты 3 последовательных выполнений приведенного выше кода: ['Число 1 с проблемой: 0,1 равно: 113', 'Счетчик 2 с проблемой: 0,05 равно: 55', 'Количество 3 с вероятностью: 0,05 составляет: 50 ', «Число 4 с пробой: 0,2 равно: 201», «Число 5 с пробой: 0,4 равно: 388», «Число 6 с пробой: 0,2 составляет: 193»]. ............. ['Счетчик 1 с проблемой: 0,1 равен: 77', 'Счетчик 2 с проблемой: 0,05 равен: 60', 'Счетчик 3 с проблемой: 0,05 равен: 51 ',' Счетчик 4 с проблемой: 0,2 равен: 193 ',' Счетчик 5 с проблемой: 0,4 равен: 438 ',' Счетчик 6 с проблемой: 0,2 равен: 181 '] ........ ..... и
Вайбхав
['Счетчик 1 с вероятностью: 0,1 равен: 84', 'Счетчик 2 с проблемой: 0,05 равен: 52', 'Счетчик 3 с проблемой: 0,05 равен: 53', 210 ',' Счет из 5 с вероятностью: 0,4 составляет: 405 ',' Счет из 6 с проблемой: 0,2 составляет: 196 ']
Вайбхав
Вопрос, как мне вернуть max (я ..., если 'i' - это объект?
Вайбхав
@Vaibhav iне является объектом.
Марсело Кантос
6

Я написал решение для рисования случайных выборок из пользовательского непрерывного распределения .

Мне это нужно для аналогичного варианта использования (например, для генерации случайных дат с заданным распределением вероятностей).

Вам просто нужны функции random_custDistи линия samples=random_custDist(x0,x1,custDist=custDist,size=1000). Остальное украшение ^^.

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

Непрерывное индивидуальное распределение и дискретное распределение выборок

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

Маркус Дучке
источник
1

Составьте список предметов на основе их 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

Оптимизация может заключаться в нормализации сумм по наибольшему общему делителю для уменьшения целевого списка.

Также это может быть интересно.

Хачик
источник
Если список элементов большой, это может потребовать много дополнительной памяти.
pafcu
@pafcu Согласен. Как раз решение, второе пришло мне в голову (первое было искать что-то вроде "питона вероятности веса" :)).
хачик
1

Другой ответ, наверное, быстрее :)

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  
Лукас Моэскопс
источник
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]

Проверка:

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
Сакшам Варма
источник
1

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

это простой пример (здесь я использовал целые числа)

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

get_cdfфункция будет преобразовать его с 20, 60, 10, 10 в 20, 20 + 60, 20 + 60 + 10, 20 + 60 + 10 + 10

теперь мы выбираем случайное число до 20 + 60 + 10 + 10, используя random.randintзатем мы используем биссектрису, чтобы быстро получить фактическое значение

Муайяд Альсади
источник
0

вы можете взглянуть на распределения выборки NumPy Random

Мануэль Сальвадорес
источник
3
Функции numpy также, похоже, поддерживают только ограниченное количество дистрибутивов без поддержки указания ваших собственных.
pafcu
0

Ни один из этих ответов не является особенно ясным или простым.

Вот простой и понятный метод, который гарантированно работает.

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

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

Урожайность:

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

Почему это работает

На этапе накопления каждый символ превращается в интервал между ним и вероятностью или частотой предыдущих символов (или 0 в случае первого символа). Эти интервалы можно использовать для выбора (и, таким образом, выборки предоставленного распределения), просто переходя по списку, пока случайное число в интервале 0,0 -> 1,0 (подготовленное ранее) не станет меньше или равно конечной точке интервала текущего символа.

Нормализация освобождает нас от необходимости убедиться , что все суммы до некоторого значения. После нормализации "вектор" вероятностей суммируется до 1.0.

Остальная часть кода для выбора и генерации произвольной длины образца от распределения ниже:

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

Использование :

>>> 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
Крис Стрингфеллоу
источник
-1

Вот более эффективный способ сделать это:

Просто вызовите следующую функцию со своим массивом «weights» (при условии, что индексы являются соответствующими элементами) и значением no. необходимых образцов. Эту функцию можно легко изменить для обработки упорядоченной пары.

Возвращает индексы (или элементы), отобранные / выбранные (с заменой), используя их соответствующие вероятности:

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

Краткое замечание о концепции, используемой в цикле while. Мы уменьшаем вес текущего элемента из кумулятивного бета, который представляет собой кумулятивное значение, построенное равномерно случайным образом, и увеличиваем текущий индекс, чтобы найти элемент, вес которого соответствует значению бета.

Vaibhav
источник