Как выбрать ключи из словаря python на основе взвешенной вероятности?

Question

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

d = {'a': 0.0625, 'c': 0.625, 'b': 0.3125} 
# Note that sum([v for k,v in d.iteritems()]) == 1 for all `d` 

Учитывая это соотношение элементов к весам, как я могу выбрать ключ от d таких, что 6,25% времени, результат является «а», 32,25% времени результата «б ', а 62,5% результата -' c '?

Answer 1

def weighted_random_by_dct(dct): 
    rand_val = random.random() 
    total = 0 
    for k, v in dct.items(): 
     total += v 
     if rand_val <= total: 
      return k 
    assert False, 'unreachable' 

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

Answer 2

Что я понял: вам нужна простая случайная функция, которая будет генерировать случайное число равномерно между 0 и 1. Если значение находится между словами 0 to 0.0625, вы выберете ключ a, если он находится между 0.0625 and (0.0625 + 0.625), тогда вы выберете ключ c и т. д. Это то, что на самом деле указано в этом answer.

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

Answer 3

Если вы можете использовать NumPy, вы можете использовать функцию numpy.random.choice, например, так:

import numpy as np 

d = {'a': 0.0625, 'c': 0.625, 'b': 0.3125} 

def pick_by_weight(d): 
    d_choices = [] 
    d_probs = [] 
    for k,v in d.iteritems(): 
     d_choices.append(k) 
     d_probs.append(v) 
    return np.random.choice(d_choices, 1, p=d_probs)[0] 


d = {'a': 0.0625, 'c': 0.625, 'b': 0.3125} 
choice = pick_by_weight(d) 

Answer 4

Если вы планируете сделать это много, можно использовать numpy, чтобы выбрать ваши ключи от список с взвешенными вероятностями с использованием np.random.choice(). Ниже приведен пример ваших ключей 10 000 раз с взвешенными вероятностями.

import numpy as np 

probs = [0.0625, 0.625, 0.3125] 
keys = ['a', 'c', 'b'] 

choice_list = np.random.choice(keys, 10000, replace=True, p=probs) 

Answer 5

Это может быть полезно, чтобы держать «перевернутый» словарь, где ключи являются весовыми значениями, а значения представляют собой списки ключей вы можете получить. Таким образом, это легче распределить его в случае, если несколько ключей имеют одинаковый вес:

from collections import defaultdict 
import random 

dict = {'a': 0.0625, 'd': 0.0625, 'c': 0.625, 'b': 0.3125} 

inverted_dict = defaultdict(list) 

for k, v in dict.items(): 
    inverted_dict[v].append(k) 

# Here first you get a random value between 0 and 1, which is your weigth 
# Then, you choose a random value from the list of keys that have the same weight 
print(random.choice(inverted_dict[random.choice(inverted_dict.keys())])) 

Answer 6

Не уверен, что ваш случай использования, но вы можете проверить классы распределения частотного распределения/вероятности в пакете NLTK, который обрабатывать все детали nitty.

FreqDist - это расширение счетчика, которое может быть передано на интерфейс ProbDistI. Интерфейс ProbDistI предоставляет метод «generate()», который может использоваться для выборки дистрибутива, а также метод «prob (sample)», который может использоваться для получения вероятности заданного ключа.

Для вашего случая вы хотите использовать оценку максимального правдоподобия, поэтому MLEProbDist. Если вы хотите сгладить распространение, вы можете попробовать LaplaceProbDist или SimpleGoodTuringProbDist.

Например:

from nltk.probability import FreqDist, MLEProbDist 

d = {'a': 6.25, 'c': 62.5, 'b': 31.25} 
freq_dist = FreqDist(d) 
prob_dist = MLEProbDist(freq_dist) 

print prob_dist.prob('a') 
print prob_dist.prob('b') 
print prob_dist.prob('c') 
print prob_dist.prob('d') 

будет печатать "0,0625 0,3125 0,625 0.0".

Для создания нового образца, вы можете использовать:

prob_dist.generate()