используя вероятности для построения диапазона (python)? [Дубликат]

Если у кого-то возникают проблемы с INNODB / Utf-8, пытаясь поместить индекс UNIQUE в поле VARCHAR (256) , переключите его на VARCHAR ( 255) . Кажется, 255 является ограничением.

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

183
ответ дан Zim 17 August 2018 в 09:47
поделиться
  • 1
    Дорогой СО, с 2014 года это правильный ответ ... Хотелось бы, чтобы официальный официальный способ обновлять вопросы в таких случаях. – n1000 9 February 2016 в 21:20
  • 2
    Это действительно хороший ответ, но я по-прежнему ценю альтернативы без numpy. – Josep Valls 4 May 2016 в 22:17
  • 3
    Кажется, немного жестко установить numpy только для этой функции ... – Sardathrion 28 April 2017 в 11:48
  • 4
    Посмотрите на правильный ответ 2017+, используя Python 3.6 – StefanJCollier 28 January 2018 в 03:17
  • 5
    По моему тестированию это на порядок медленнее, чем random.choices для отдельных вызовов. Если вам нужно много случайных результатов, очень важно выбрать их сразу, отрегулировав number_of_items_to_pick. Если вы это сделаете, это на порядок быстрее. – jpmc26 6 April 2018 в 23:27

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

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 17 August 2018 в 09:47
поделиться
1
ответ дан Community 17 August 2018 в 09:47
поделиться
  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 17 August 2018 в 09:47
поделиться
  • 1
  • 2
    индекс кортежа выходит за пределы диапазона, если random () происходит с возвратом 1.0 – Jon Vaughan 17 July 2014 в 20:54
  • 3
    Это все еще работает в O(n) из-за вычисления кумулятивного распределения. – Lev Levitsky 16 November 2014 в 11:43
  • 4
    Мне нравится это решение лучше. Чище и понятнее код. – Homunculus Reticulli 7 January 2016 в 19:33
  • 5
    Это решение лучше в случае, когда для одного и того же набора вариантов требуется несколько вызовов для weighted_choice. В этом случае вы можете создать кумулятивную сумму один раз и выполнить двоичный поиск по каждому вызову. – Amos 2 May 2016 в 13:53

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

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 17 August 2018 в 09:47
поделиться

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

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 17 August 2018 в 09:47
поделиться
  • 1
    Это работает для небольших общих значений населения, но не для больших наборов данных (например, население США штатом в конечном итоге создаст рабочий список с 300 миллионами предметов в нем). – Ryan 13 July 2012 в 01:31
  • 2
    Работает ли, Kudos – nehemiah 1 June 2016 в 00:53
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 17 August 2018 в 09:47
поделиться
  • 1
    Вы можете удалить операцию и сохранить временную шкалу времени, изменив выражения внутри цикла for: upto +=w; if upto > r – knite 31 July 2013 в 09:31
  • 2
    @knite, Пожалуйста, не предлагайте это. Вы даже это испытали? Это полностью нарушает распределение. Запуск weighted_choice([('a',1.0),('b',2.0),('c',3.0)]) с вашей модификацией приводит к тому, что b никогда не выбирается ... – Cerin 21 December 2013 в 00:25
  • 3
    @rsk, ты прав, хотя это очень редкое явление. Изменение > r на >= r устраняет эту проблему для меня. – Cerin 21 December 2013 в 00:27
  • 4
    сохраняйте переменную, удаляя upto и просто уменьшая r по весу каждый раз. Тогда сравнение if r < 0 – JnBrymn 31 March 2014 в 04:33
  • 5
    вы могли бы построить for ... else вместо вашего ложного утверждения – maxbellec 5 October 2016 в 15:50

Вот еще одна версия 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 17 August 2018 в 09:47
поделиться

Начиная с 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 17 August 2018 в 09:47
поделиться

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

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 17 August 2018 в 09:47
поделиться
  • 1
  • 2
    Похоже, ваши объекты будут дублированы в этом примере. Это было бы неэффективно (и, следовательно, функция преобразования весов в целые числа). Тем не менее, это решение является хорошим однострочным, если целочисленные веса малы. – wei2912 22 December 2013 в 09:36
  • 3
    Примитивы будут дублироваться, но объекты будут иметь только дубликаты ссылок, а не сами объекты. (поэтому вы не можете создать список списков с помощью [[]]*10 - все элементы во внешнем списке указывают на тот же список. – PaulMcG 20 July 2015 в 21:31

Один из способов - рандомизировать по сумме всех весов, а затем использовать значения в качестве предельных точек для каждого 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 17 August 2018 в 09:47
поделиться

Я бы потребовал сумму выборов 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 17 August 2018 в 09:47
поделиться
  • 1
    Из любопытства, есть ли причина, по которой вы предпочитаете random.random () * total вместо random.uniform (0, total)? – Colin 9 September 2010 в 20:23
  • 2
    @Colin Нет, совсем нет. Обновлено. – phihag 9 September 2010 в 20:27
  • 3
    Вы пересекаете три раза по итерируемым. Это может не поддерживаться итерируемым. – liori 9 September 2010 в 20:30
  • 4
    Я думаю, что это действительно возможно. utopia.duth.gr/~pefraimi/research/data/2007EncOfAlg.pdf Это на самом деле довольно просто ... Но кто заботится ... – liori 9 September 2010 в 21:56
  • 5
    @liori Мне все равно, и вы правы: weightedChoice может вычисляться только с одним итератором. Однако для этого, похоже, требуется более одного вызова псевдослучайного генератора. – phihag 10 September 2010 в 15:04
18
ответ дан pweitzman 17 August 2018 в 09:47
поделиться

Вот версия, которая включена в стандартную библиотеку для 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 17 August 2018 в 09:47
поделиться

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

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 17 August 2018 в 09:47
поделиться
1
ответ дан Uppinder Chugh 17 August 2018 в 09:47
поделиться

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

89
ответ дан vishes_shell 17 August 2018 в 09:47
поделиться
  • 1
    Это хороший актуальный ответ, python 3.6 действительно имеет взвешенную функцию choices. Отлично. – EmlynC 25 November 2016 в 14:31
  • 2
    должен быть принят ответ, я думаю. – Ilya V. Schurov 1 March 2018 в 08:56
  • 3
    Отличный выбор (каламбур). – jpmc26 6 April 2018 в 00:59
  • 4
    Это можно выбрать с помощью весов, но, похоже, он не может остановить замещение, которое может выполнять np.random.choice. – roganjosh 14 July 2018 в 09:02
  • 5
    @roganjosh true, спасибо, я упомянул об этом в обновленном ответе. – vishes_shell 14 July 2018 в 10:09
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 17 August 2018 в 09:47
поделиться
Другие вопросы по тегам:

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