Распределение вероятностей в Python
https://stackoverflow.com/questions/526255
-
22-08-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianВопрос
У меня есть связка ключей, каждый из которых имеет переменную маловероятности.Я хочу случайным образом выбрать один из этих ключей, но я хочу, чтобы выбор маловероятного (ключа, значений) был более маловероятным, чем менее маловероятный (более вероятный) объект.Мне интересно, есть ли у вас какие-либо предложения, предпочтительно существующий модуль python, который я мог бы использовать, иначе мне нужно будет создать его самому.
Я проверил случайный модуль;похоже, он этого не обеспечивает.
Мне приходится делать такой выбор много миллионов раз для 1000 различных наборов объектов, каждый из которых содержит 2455 объектов.Каждый набор будет обмениваться объектами друг с другом, поэтому случайный выбор должен быть динамичным.С 1000 наборами из 2,433 объектов, то есть 2,433 миллиона объектов;низкое потребление памяти имеет решающее значение.И поскольку эти варианты не являются основной частью алгоритма, мне нужно, чтобы этот процесс был довольно быстрым;Процессорное время ограничено.
Спасибо
Обновить:
Хорошо, я постарался обдумать ваши предложения с умом, но время так ограничено...
Я посмотрел на подход к бинарному дереву поиска, и он кажется слишком рискованным (сложным и запутанным).Все остальные предложения напоминают рецепт ActiveState.Я взял его и немного изменил в надежде сделать более эффективным:
def windex(dict, sum, max):
'''an attempt to make a random.choose() function that makes
weighted choices accepts a dictionary with the item_key and
certainty_value as a pair like:
>>> x = [('one', 20), ('two', 2), ('three', 50)], the
maximum certainty value (max) and the sum of all certainties.'''
n = random.uniform(0, 1)
sum = max*len(list)-sum
for key, certainty in dict.iteritems():
weight = float(max-certainty)/sum
if n < weight:
break
n = n - weight
return key
Я надеюсь получить прирост эффективности от динамического поддержания суммы определенностей и максимальной определенности.Любые дальнейшие предложения приветствуются.Вы, ребята, экономите мне столько времени и усилий, одновременно повышая мою эффективность, это безумие.Спасибо!Спасибо!Спасибо!
Обновление 2:
Я решил сделать его более эффективным, позволив ему выбирать больше вариантов одновременно.Это приведет к приемлемой потере точности в моем алгоритме, поскольку он динамичен по своей природе.В любом случае, вот что у меня есть сейчас:
def weightedChoices(dict, sum, max, choices=10):
'''an attempt to make a random.choose() function that makes
weighted choices accepts a dictionary with the item_key and
certainty_value as a pair like:
>>> x = [('one', 20), ('two', 2), ('three', 50)], the
maximum certainty value (max) and the sum of all certainties.'''
list = [random.uniform(0, 1) for i in range(choices)]
(n, list) = relavate(list.sort())
keys = []
sum = max*len(list)-sum
for key, certainty in dict.iteritems():
weight = float(max-certainty)/sum
if n < weight:
keys.append(key)
if list: (n, list) = relavate(list)
else: break
n = n - weight
return keys
def relavate(list):
min = list[0]
new = [l - min for l in list[1:]]
return (min, new)
Я еще не пробовал это делать.Если у вас есть какие-либо комментарии / предложения, пожалуйста, не стесняйтесь.Спасибо!
Обновление 3:
Я весь день работал над адаптированной к задаче версией ответа Рекса Логана.Вместо двух массивов объектов и весов, это фактически специальный класс dictionary;что делает вещи довольно сложными, поскольку код Rex генерирует случайный индекс...Я также закодировал тестовый пример, который отчасти напоминает то, что произойдет в моем алгоритме (но я не могу точно знать, пока не попробую!).Основным принципом является:чем чаще ключ генерируется случайным образом, тем более маловероятно, что он будет сгенерирован снова:
import random, time
import psyco
psyco.full()
class ProbDict():
"""
Modified version of Rex Logans RandomObject class. The more a key is randomly
chosen, the more unlikely it will further be randomly chosen.
"""
def __init__(self,keys_weights_values={}):
self._kw=keys_weights_values
self._keys=self._kw.keys()
self._len=len(self._keys)
self._findSeniors()
self._effort = 0.15
self._fails = 0
def __iter__(self):
return self.next()
def __getitem__(self, key):
return self._kw[key]
def __setitem__(self, key, value):
self.append(key, value)
def __len__(self):
return self._len
def next(self):
key=self._key()
while key:
yield key
key = self._key()
def __contains__(self, key):
return key in self._kw
def items(self):
return self._kw.items()
def pop(self, key):
try:
(w, value) = self._kw.pop(key)
self._len -=1
if w == self._seniorW:
self._seniors -= 1
if not self._seniors:
#costly but unlikely:
self._findSeniors()
return [w, value]
except KeyError:
return None
def popitem(self):
return self.pop(self._key())
def values(self):
values = []
for key in self._keys:
try:
values.append(self._kw[key][1])
except KeyError:
pass
return values
def weights(self):
weights = []
for key in self._keys:
try:
weights.append(self._kw[key][0])
except KeyError:
pass
return weights
def keys(self, imperfect=False):
if imperfect: return self._keys
return self._kw.keys()
def append(self, key, value=None):
if key not in self._kw:
self._len +=1
self._kw[key] = [0, value]
self._keys.append(key)
else:
self._kw[key][1]=value
def _key(self):
for i in range(int(self._effort*self._len)):
ri=random.randint(0,self._len-1) #choose a random object
rx=random.uniform(0,self._seniorW)
rkey = self._keys[ri]
try:
w = self._kw[rkey][0]
if rx >= w: # test to see if that is the value we want
w += 1
self._warnSeniors(w)
self._kw[rkey][0] = w
return rkey
except KeyError:
self._keys.pop(ri)
# if you do not find one after 100 tries then just get a random one
self._fails += 1 #for confirming effectiveness only
for key in self._keys:
if key in self._kw:
w = self._kw[key][0] + 1
self._warnSeniors(w)
self._kw[key][0] = w
return key
return None
def _findSeniors(self):
'''this function finds the seniors, counts them and assess their age. It
is costly but unlikely.'''
seniorW = 0
seniors = 0
for w in self._kw.itervalues():
if w >= seniorW:
if w == seniorW:
seniors += 1
else:
seniorsW = w
seniors = 1
self._seniors = seniors
self._seniorW = seniorW
def _warnSeniors(self, w):
#a weight can only be incremented...good
if w >= self._seniorW:
if w == self._seniorW:
self._seniors+=1
else:
self._seniors = 1
self._seniorW = w
def test():
#test code
iterations = 200000
size = 2500
nextkey = size
pd = ProbDict(dict([(i,[0,i]) for i in xrange(size)]))
start = time.clock()
for i in xrange(iterations):
key=pd._key()
w=pd[key][0]
if random.randint(0,1+pd._seniorW-w):
#the heavier the object, the more unlikely it will be removed
pd.pop(key)
probAppend = float(500+(size-len(pd)))/1000
if random.uniform(0,1) < probAppend:
nextkey+=1
pd.append(nextkey)
print (time.clock()-start)*1000/iterations, "msecs / iteration with", pd._fails, "failures /", iterations, "iterations"
weights = pd.weights()
weights.sort()
print "avg weight:", float(sum(weights))/pd._len, max(weights), pd._seniorW, pd._seniors, len(pd), len(weights)
print weights
test()
Любые комментарии по-прежнему приветствуются.@Дариус:ваши бинарные деревья слишком сложны для меня;и я не думаю, что его листья можно эффективно удалить...Спасибо всем
Решение
Этот рецепт activestate предоставляет простой в использовании подход, в частности версию в комментариях, которая не требует от вас предварительной нормализации ваших весов:
import random
def weighted_choice(items):
"""items is a list of tuples in the form (item, weight)"""
weight_total = sum((item[1] for item in items))
n = random.uniform(0, weight_total)
for item, weight in items:
if n < weight:
return item
n = n - weight
return item
Это будет происходить медленно, если у вас большой список элементов.Бинарный поиск, вероятно, был бы лучше в этом случае...но также было бы сложнее написать, что привело бы к небольшому выигрышу, если у вас небольшой размер выборки. Вот пример подхода к бинарному поиску в python если вы хотите следовать этим маршрутом.
(Я бы рекомендовал провести быстрое тестирование производительности обоих методов в вашем наборе данных.Производительность различных подходов к такого рода алгоритмам часто немного неинтуитивна.)
Редактировать: Я последовал своему собственному совету, поскольку мне было любопытно, и провел несколько тестов.
Я сравнил четыре подхода:
Приведенная выше функция weighted_choice.
Функция выбора двоичного поиска, подобная такой:
def weighted_choice_bisect(items):
added_weights = []
last_sum = 0
for item, weight in items:
last_sum += weight
added_weights.append(last_sum)
return items[bisect.bisect(added_weights, random.random() * last_sum)][0]
Компиляционная версия 1:
def weighted_choice_compile(items):
"""returns a function that fetches a random item from items
items is a list of tuples in the form (item, weight)"""
weight_total = sum((item[1] for item in items))
def choice(uniform = random.uniform):
n = uniform(0, weight_total)
for item, weight in items:
if n < weight:
return item
n = n - weight
return item
return choice
Компилирующая версия 2:
def weighted_choice_bisect_compile(items):
"""Returns a function that makes a weighted random choice from items."""
added_weights = []
last_sum = 0
for item, weight in items:
last_sum += weight
added_weights.append(last_sum)
def choice(rnd=random.random, bis=bisect.bisect):
return items[bis(added_weights, rnd() * last_sum)][0]
return choice
Затем я составил большой список вариантов, вот так:
choices = [(random.choice("abcdefg"), random.uniform(0,50)) for i in xrange(2500)]
И чрезмерно простая функция профилирования:
def profiler(f, n, *args, **kwargs):
start = time.time()
for i in xrange(n):
f(*args, **kwargs)
return time.time() - start
Результаты:
(Секунды, потраченные на 1000 вызовов функции.)
- Простой некомпилированный:0.918624162674
- Двоичный файл без компиляции:1.01497793198
- Простой скомпилированный:0.287325024605
- Скомпилированный двоичный файл:0.00327413797379
"Скомпилированные" результаты включают среднее время, затраченное на однократную компиляцию функции выбора.(Я рассчитал время 1000 компиляций, затем разделил это время на 1000 и добавил результат ко времени функции выбора.)
Итак:если у вас есть список элементов + веса, которые меняются очень редко, двоичный скомпилированный метод является безусловно самый быстрый.
Другие советы
В комментариях к оригинальному сообщению Николас Леонард предполагает, что и обмен, и выборка должны быть быстрыми.Вот идея на этот случай;Я еще не пробовал этого.
Если бы только выборка должна была быть быстрой, мы могли бы использовать массив значений вместе с текущей суммой их вероятностей и выполнить двоичный поиск по текущей сумме (с ключом, являющимся однородным случайным числом) - операция O (log (n)).Но обмен потребовал бы обновления всех значений текущей суммы, появляющихся после обмена записями - операция O (n).(Не могли бы вы обменять только товары, указанные в конце их списков?Я предполагаю, что нет.)
Итак, давайте стремиться к O(log(n)) в обеих операциях.Вместо массива сохраните двоичное дерево для каждого набора для выборки.Лист содержит выборочное значение и его (ненормализованную) вероятность.Узел ветви содержит общую вероятность появления его дочерних элементов.
Для выборки сгенерируйте однородное случайное число x между 0 и общей вероятностью корня, и спускайтесь по дереву.В каждой ветви выберите левый дочерний элемент, если левый дочерний элемент имеет общую вероятность <= x.Иначе вычтите вероятность левого дочернего элемента из x и идите направо.Верните конечное значение, которого вы достигнете.
Чтобы обменять, удалите лист из его дерева и отрегулируйте ветви, которые ведут к нему (уменьшая их общую вероятность и вырезая все узлы ветви с одним дочерним элементом).Вставьте лист в дерево назначения:у вас есть выбор, куда его положить, так что соблюдайте баланс.Выбор случайного ребенка на каждом уровне, вероятно, достаточно хорош - вот с чего я бы начал.Увеличьте вероятность каждого родительского узла, возвращаясь к корню.
Теперь и выборка, и обмен в среднем равны O (log (n)).(Если вам нужен гарантированный баланс, простой способ - добавить еще одно поле к узлам ветви, содержащее количество листьев во всем поддереве.Добавляя лист, на каждом уровне выбирайте дочерний элемент с меньшим количеством листьев.Это оставляет возможность того, что дерево выйдет из равновесия исключительно из-за удалений;это не может быть проблемой, если трафик между наборами достаточно равномерный, но если это так, то выберите повороты во время удаления, используя информацию о количестве листьев на каждом узле в вашем обходе.)
Обновить: По запросу, вот базовая реализация.Я вообще его не настраивал.Использование:
>>> t1 = build_tree([('one', 20), ('two', 2), ('three', 50)])
>>> t1
Branch(Leaf(20, 'one'), Branch(Leaf(2, 'two'), Leaf(50, 'three')))
>>> t1.sample()
Leaf(50, 'three')
>>> t1.sample()
Leaf(20, 'one')
>>> t2 = build_tree([('four', 10), ('five', 30)])
>>> t1a, t2a = transfer(t1, t2)
>>> t1a
Branch(Leaf(20, 'one'), Leaf(2, 'two'))
>>> t2a
Branch(Leaf(10, 'four'), Branch(Leaf(30, 'five'), Leaf(50, 'three')))
Код:
import random
def build_tree(pairs):
tree = Empty()
for value, weight in pairs:
tree = tree.add(Leaf(weight, value))
return tree
def transfer(from_tree, to_tree):
"""Given a nonempty tree and a target, move a leaf from the former to
the latter. Return the two updated trees."""
leaf, from_tree1 = from_tree.extract()
return from_tree1, to_tree.add(leaf)
class Tree:
def add(self, leaf):
"Return a new tree holding my leaves plus the given leaf."
abstract
def sample(self):
"Pick one of my leaves at random in proportion to its weight."
return self.sampling(random.uniform(0, self.weight))
def extract(self):
"""Pick one of my leaves and return it along with a new tree
holding my leaves minus that one leaf."""
return self.extracting(random.uniform(0, self.weight))
class Empty(Tree):
weight = 0
def __repr__(self):
return 'Empty()'
def add(self, leaf):
return leaf
def sampling(self, weight):
raise Exception("You can't sample an empty tree")
def extracting(self, weight):
raise Exception("You can't extract from an empty tree")
class Leaf(Tree):
def __init__(self, weight, value):
self.weight = weight
self.value = value
def __repr__(self):
return 'Leaf(%r, %r)' % (self.weight, self.value)
def add(self, leaf):
return Branch(self, leaf)
def sampling(self, weight):
return self
def extracting(self, weight):
return self, Empty()
def combine(left, right):
if isinstance(left, Empty): return right
if isinstance(right, Empty): return left
return Branch(left, right)
class Branch(Tree):
def __init__(self, left, right):
self.weight = left.weight + right.weight
self.left = left
self.right = right
def __repr__(self):
return 'Branch(%r, %r)' % (self.left, self.right)
def add(self, leaf):
# Adding to a random branch as a clumsy way to keep an
# approximately balanced tree.
if random.random() < 0.5:
return combine(self.left.add(leaf), self.right)
return combine(self.left, self.right.add(leaf))
def sampling(self, weight):
if weight < self.left.weight:
return self.left.sampling(weight)
return self.right.sampling(weight - self.left.weight)
def extracting(self, weight):
if weight < self.left.weight:
leaf, left1 = self.left.extracting(weight)
return leaf, combine(left1, self.right)
leaf, right1 = self.right.extracting(weight - self.left.weight)
return leaf, combine(self.left, right1)
Обновление 2: В решение другой проблемы, Джейсон Орендорф указывает, что двоичные деревья можно поддерживать идеально сбалансированными, представляя их в виде массива точно так же, как классическую структуру кучи.(Это также экономит место, затрачиваемое на указатели.) Смотрите мои комментарии к этому ответу о том, как адаптировать его код к этой проблеме.
Я предлагаю вам портвейн эта PHP-реализация взвешенного случайного к Python.В частности, второй алгоритм, основанный на двоичном поиске, помогает решить ваши проблемы со скоростью.
Я бы использовал это рецепт .Вам нужно будет добавить вес к вашим объектам, но это всего лишь простое соотношение и поместить их в список кортежей (объект, убежденность / (сумма обвинительных приговоров)).Это должно быть легко сделать, используя понимание списка.
Вот классический способ сделать это в псевдокоде, где random.random() выдает вам случайное значение с плавающей точкой от 0 до 1.
let z = sum of all the convictions
let choice = random.random() * z
iterate through your objects:
choice = choice - the current object's conviction
if choice <= 0, return this object
return the last object
Для примера:представьте, что у вас есть два объекта, один с весом 2, другой с весом 4.Вы генерируете число от 0 до 6.Если choice находится между 0 и 2, что произойдет с вероятностью 2/6 = 1/3, затем оно будет вычитаться на 2 и будет выбран первый объект.Если выбор находится между 2 и 6, что произойдет с вероятностью 4/6 = 2/3, то при первом вычитании выбор все равно будет равен > 0, а при втором вычитании будет выбран 2-й объект.
Вы хотите присвоить каждому объекту определенный вес.Чем больше вес, тем больше вероятность, что это произойдет.Точнее, probx =вес/sum_all_weights.
Затем сгенерируйте случайное число в диапазоне от 0 до sum_all_weights и сопоставьте его каждому объекту.
Этот код позволяет вам сгенерировать случайный индекс, и он сопоставляется при создании объекта для повышения скорости.Если все ваши наборы объектов имеют одинаковое распределение, то вы можете обойтись только одним объектом randomIndex.
import random
class RandomIndex:
def __init__(self, wlist):
self._wi=[]
self._rsize=sum(wlist)-1
self._m={}
i=0
s=wlist[i]
for n in range(self._rsize+1):
if n == s:
i+=1
s+=wlist[i]
self._m[n]=i
def i(self):
rn=random.randint(0,self._rsize)
return self._m[rn]
sx=[1,2,3,4]
wx=[1,10,100,1000] #weight list
ri=RandomIndex(wx)
cnt=[0,0,0,0]
for i in range(1000):
cnt[ri.i()] +=1 #keep track of number of times each index was generated
print(cnt)
Примерно 3 года спустя...
Если вы используете numpy, возможно, самым простым вариантом является использование np.random.choice, который принимает список возможных значений и необязательную последовательность вероятностей, связанных с каждым значением:
import numpy as np
values = ('A', 'B', 'C', 'D')
weights = (0.5, 0.1, 0.2, 0.2)
print ''.join(np.random.choice(values, size=60, replace=True, p=weights))
# ACCADAACCDACDBACCADCAAAAAAADACCDCAADDDADAAACCAAACBAAADCADABA
Самое простое, что можно сделать, это использовать random.choice (который использует равномерное распределение) и изменять частоту появления объекта в исходной коллекции.
>>> random.choice([1, 2, 3, 4])
4
...против:
>>> random.choice([1, 1, 1, 1, 2, 2, 2, 3, 3, 4])
2
Таким образом, ваши объекты могут иметь базовую частоту встречаемости (n), и от 1 до n объектов добавляются в исходную коллекцию в зависимости от частоты убежденности.Этот метод действительно прост;однако это может привести к значительным накладным расходам, если количество отдельных объектов велико или уровень убежденности должен быть очень мелкозернистым.
В качестве альтернативы, если вы генерируете более одного случайного числа, используя равномерное распределение, и суммируете их, числа, встречающиеся вблизи среднего значения, более вероятны, чем числа, встречающиеся вблизи крайних значений (подумайте о броске двух кубиков и вероятности выпадения 7 против 12 или 2).Затем вы можете упорядочить объекты по показателю убежденности и сгенерировать число, используя несколько бросков кубика, которые вы используете для вычисления и индексирования объектов.Используйте числа, близкие к среднему значению, для индексации объектов с низкой судимостью и числа, близкие к крайним значениям, для индексации объектов с высокой судимостью.Вы можете варьировать точную вероятность того, что данный объект будет выбран, изменяя "количество сторон" и количество ваших "кубиков" (возможно, проще разложить объекты по корзинам и использовать кубики с небольшим количеством сторон, а не пытаться связать каждый объект с определенным результатом):
>>> die = lambda sides : random.randint(1, sides)
>>> die(6)
3
>>> die(6) + die(6) + die(6)
10
Очень простой способ сделать это - установить веса для каждого из значений, и это не потребует много памяти.
Вероятно, вы могли бы использовать хэш / словарь для этого.
Что вы захотите сделать, так это получить случайное число, x, умножьте и суммируйте по всему набору объектов, которые вы хотите выбрать, и разделите этот результат на количество объектов в вашем наборе.
Псевдокод:
objectSet = [(object1, weight1), ..., (objectN, weightN)]
sum = 0
rand = random()
for obj, weight in objectSet
sum = sum+weight*rand
choice = objectSet[floor(sum/objectSet.size())]
Редактировать:Я просто подумал о том, насколько медленным был бы мой код с очень большими наборами (это O (n)).Следующий псевдокод имеет значение O(log(n)) и в основном использует двоичный поиск.
objectSet = [(object1, weight1), ..., (objectN, weightN)]
sort objectSet from less to greater according to weights
choice = random() * N # where N is the number of objects in objectSet
do a binary search until you have just one answer
В Python существуют реализации двоичного поиска по всей сети, поэтому здесь нет необходимости повторяться.
Вот лучший ответ для специального распределения вероятностей, тот Ответ Рекса Логана кажется, на это ориентированы.Распределение выглядит следующим образом:каждый объект имеет целочисленный вес от 0 до 100, и его вероятность пропорциональна его весу.Поскольку это общепринятый в настоящее время ответ, я думаю, об этом стоит подумать.
Так что храните массив из 101 ячейки.Каждая ячейка содержит список всех объектов с определенным весом.Каждая ячейка также знает итого вес всех его объектов.
Для пробы:выберите контейнер случайным образом пропорционально его общему весу.(Используйте для этого один из стандартных рецептов - линейный или двоичный поиск.) Затем выберите объект из ячейки равномерно случайным образом.
Для передачи объекта:удалите его из его ячейки, поместите в его ячейку в целевом объекте и обновите веса обеих ячеек.(Если вы используете двоичный поиск для выборки, вы также должны обновить текущие суммы, которые использует.Это все еще достаточно быстро, поскольку ячеек не так много.)
(Год спустя) Метод псевдонимов Уолкера для случайных объектов с разной вероятностью это очень быстро и очень просто
Я был нужен в более быстрых функциях, для не очень больших чисел.Итак, вот оно, в Visual C ++:
#undef _DEBUG // disable linking with python25_d.dll
#include <Python.h>
#include <malloc.h>
#include <stdlib.h>
static PyObject* dieroll(PyObject *, PyObject *args)
{
PyObject *list;
if (!PyArg_ParseTuple(args, "O:decompress", &list))
return NULL;
if (!PyList_Check(list))
return PyErr_Format(PyExc_TypeError, "list of numbers expected ('%s' given)", list->ob_type->tp_name), NULL;
int size = PyList_Size(list);
if (size < 1)
return PyErr_Format(PyExc_TypeError, "got empty list"), NULL;
long *array = (long*)alloca(size*sizeof(long));
long sum = 0;
for (int i = 0; i < size; i++) {
PyObject *o = PyList_GetItem(list, i);
if (!PyInt_Check(o))
return PyErr_Format(PyExc_TypeError, "list of ints expected ('%s' found)", o->ob_type->tp_name), NULL;
long n = PyInt_AsLong(o);
if (n == -1 && PyErr_Occurred())
return NULL;
if (n < 0)
return PyErr_Format(PyExc_TypeError, "list of positive ints expected (negative found)"), NULL;
sum += n; //NOTE: integer overflow
array[i] = sum;
}
if (sum <= 0)
return PyErr_Format(PyExc_TypeError, "sum of numbers is not positive"), NULL;
int r = rand() * (sum-1) / RAND_MAX; //NOTE: rand() may be too small (0x7fff). rand() * sum may result in integer overlow.
assert(array[size-1] == sum);
assert(r < sum && r < array[size-1]);
for (int i = 0; i < size; ++i)
{
if (r < array[i])
return PyInt_FromLong(i);
}
return PyErr_Format(PyExc_TypeError, "internal error."), NULL;
}
static PyMethodDef module_methods[] =
{
{"dieroll", (PyCFunction)dieroll, METH_VARARGS, "random index, beased on weights" },
{NULL} /* Sentinel */
};
PyMODINIT_FUNC initdieroll(void)
{
PyObject *module = Py_InitModule3("dieroll", module_methods, "dieroll");
if (module == NULL)
return;
}
