Python: numpy.random.choice () без Numpy [дубликат]

gcc по умолчанию не строит никаких функций при компиляции без оптимизации. Я не знаю о visual studio - deft_code

Я проверил это для Visual Studio 9 (15.00.30729.01), компилировав / FAcs и посмотрев на код сборки: компилятор произвел вызовы функции-члены без оптимизации включены в режиме отладки. Даже если функция отмечена __forceinline, не создается встроенный код времени выполнения.

154
задан Ben 26 January 2013 в 14:31
поделиться

18 ответов

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

184
ответ дан Zim 23 August 2018 в 23:34
поделиться

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

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]
1
ответ дан ArturJ 23 August 2018 в 23:34
поделиться

Если ваш список взвешенных вариантов относительно статичен и вам нужна частая выборка, вы можете сделать один шаг предварительной обработки O (N), а затем сделать выбор в O (1), используя функции в , связанные с этим answer .

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

# O(1) selection
value = choices[sample(preprocessed_data)][0]
1
ответ дан Community 23 August 2018 в 23:34
поделиться
  1. Упорядочить веса в кумулятивное распределение.
  2. Использовать random.random () для выбора случайного поплавка 0.0 <= x < total.
  3. Найдите распределение, используя bisect.bisect, как показано в примере в 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'

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

67
ответ дан Lev Levitsky 23 August 2018 в 23:34
поделиться

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

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]
1
ответ дан Mark 23 August 2018 в 23:34
поделиться

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

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

15
ответ дан Maxime 23 August 2018 в 23:34
поделиться
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"
127
ответ дан moooeeeep 23 August 2018 в 23:34
поделиться

Вот еще одна версия 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])
0
ответ дан murphsp1 23 August 2018 в 23:34
поделиться

Начиная с 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), они все равно будут выполняться.

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

8
ответ дан Nickil Maveli 23 August 2018 в 23:34
поделиться

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

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)
15
ответ дан PaulMcG 23 August 2018 в 23:34
поделиться

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

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
0
ответ дан Perennial 23 August 2018 в 23:34
поделиться

Я бы потребовал сумму выборов 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')
3
ответ дан phihag 23 August 2018 в 23:34
поделиться

Если вы не против использования 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)
18
ответ дан pweitzman 23 August 2018 в 23:34
поделиться

Вот версия, которая включена в стандартную библиотеку для 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

8
ответ дан Raymond Hettinger 23 August 2018 в 23:34
поделиться

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

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])
0
ответ дан Tony Veijalainen 23 August 2018 в 23:34
поделиться

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

Предположим, вы хотите пробовать распределение 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]
1
ответ дан Uppinder Chugh 23 August 2018 в 23:34
поделиться

Поскольку 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: As @roganjosh , random.choices не может возвращать значения без замены, как упоминалось в docs :

Вернуть a k (g15)

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

90
ответ дан vishes_shell 23 August 2018 в 23:34
поделиться
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))
1
ответ дан whi 23 August 2018 в 23:34
поделиться
Другие вопросы по тегам:

Похожие вопросы: