Распределение вероятностей в Python

У меня есть куча ключей, у каждой из которых есть переменная с недопустимостью. Я хочу случайным образом выбрать один из этих ключей, но я хочу, чтобы он был маловероятным для маловероятного (ключ, значения), который будет выбран, чем менее вероятный (более вероятный) объект. Мне интересно, есть ли у вас какие-либо предложения, желательно существующий модуль python, который я мог бы использовать, иначе мне нужно будет сделать это самостоятельно.

Я проверил случайный модуль; это не похоже на это.

Я должен сделать такой выбор много миллионов раз для 1000 различных наборов объектов, каждый из которых содержит 2 455 объектов. Каждый набор будет обмениваться объектами друг с другом, поэтому произвольный выборщик должен быть динамическим. С 1000 наборами из 2433 объектов, что составляет 2433 миллиона объектов; Низкое потребление памяти имеет решающее значение. И поскольку этот выбор не является основной частью алгоритма, мне нужно, чтобы этот процесс был довольно быстрым; Время CPU ограничено.

Спасибо

Обновить:

Хорошо, я старался правильно рассмотреть ваши предложения, но время настолько ограничено …

Я посмотрел на подход двоичного поиска, и он кажется слишком рискованным (сложным и сложным). Другие предложения напоминают рецепт 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 

Я надеюсь получить выигрыш в эффективности от динамического поддержания суммы уверенности и максимальной уверенности. Любые дополнительные предложения приветствуются. Вы, ребята, экономит мне столько времени и сил, увеличивая мою эффективность, это безумие. Спасибо! Спасибо! Спасибо!

Update2:

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

 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) 

Я еще не пробовал. Если у вас есть какие-либо комментарии / предложения, пожалуйста, не стесняйтесь. Спасибо!

Update3:

Я работаю весь день на заданной вами задаче Rex Logan. Вместо 2 массивов объектов и весов это фактически специальный класс словаря; что делает вещи довольно сложными, так как код Рекса генерирует случайный индекс … Я также закодировал тестовый пример, похожий на то, что произойдет в моем алгоритме (но я не могу знать, пока не попытаюсь!). Основной принцип заключается в следующем: чем больше ключ генерируется случайным образом, тем более маловероятно, что он будет сгенерирован снова:

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

Любые комментарии по-прежнему приветствуются. @Darius: ваши бинарные деревья слишком сложны и сложны для меня; и я не думаю, что его листья могут быть удалены эффективно … Thx all

12 Solutions collect form web for “Распределение вероятностей в Python”

Этот рецепт 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 . Else вычитают вероятность левого ребенка из 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 () дает вам случайный float от 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, а второе вычитание сделает выбор второго объекта.

Вы хотите дать каждому объекту вес. Чем больше вес, тем вероятнее это произойдет. Точнее probx = weight / 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 

… vs:

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

EDIT : Я просто подумал о том, насколько медленным будет мой код с очень большими наборами (это 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; } 
Python - лучший язык программирования в мире.