Campionamento chiavi a causa della loro valori

Question

Ho un dizionario in Python con valore a chiave> come str->int. Se devo scegliere una chiave basata su di essa la propria valore, poi come il valore diventa più grande la chiave ha una minore possibilità di essere scelti.

Per esempio, se key1=2 e key2->1, quindi l'atteggiamento di key1 dovrebbe essere 2:1.

Come posso fare questo?

Answer 1

1 Costruire una lista CDF-come in questo modo:.

def build_cdf(distrib):
    cdf = []
    val = 0
    for key, freq in distrib.items():
        val += freq
        cdf.append((val, key))
    return (val, cdf)

Questa funzione restituisce una tupla, il primo valore è la somma delle probabilità, e 2 ° valore è il CDF.

2 Costruire il campionatore in questo modo:.

import random
def sample_from_cdf(val_and_cdf):
    (val, cdf) = val_and_cdf;
    rand = random.uniform(0, val)
    # use bisect.bisect_left to reduce search time from O(n) to O(log n).
    return [key for index, key in cdf if index > rand][0]

Utilizzo:

x = build_cdf({"a":0.2, "b":0.3, "c":0.5});
y = [sample_from_cdf(x) for i in range(0,100000)];
print (len([t for t in y if t == "a"]))   # 19864
print (len([t for t in y if t == "b"]))   # 29760
print (len([t for t in y if t == "c"]))   # 50376

Si consiglia di fare questo in una classe.

Answer 2

Se i valori sono troppo grandi per l'approccio di gnibler:

Crea un elenco di tuple (key, index), dove index è la somma di tutti i valori che vengono prima chiave nell'elenco (questa sarebbe l'indice della prima occorrenza di lista key c di gnibler. Calcola anche la somma di tutti i valori (n ).

Ora, generare un numero casuale xbetween 0 e n - 1. Trova l'ultima voce nella lista con index < x. Dal momento che la lista è ordinata in base all'indice, è possibile utilizzare la ricerca binaria per farlo in modo efficiente.

Aggiornamento: il codice di KennyTM è un'implementazione di questo, se non che utilizza una ricerca lineare forza bruta, invece di ricerca binaria; questo sarà inefficiente se il numero di tasti sono grandi.

Answer 3

i valori non sono troppo grandi, si può fare in questo modo

>>> from random import choice
>>> d={"key1":2,"key2":1}
>>> c=[]
>>> for k,v in d.items():
...  c+=[k]*v
... 
>>> choice(c)
'key1'
>>> sum(1 for x in range(100) if choice(c)=="key1")
63
>>> sum(1 for x in range(100) if choice(c)=="key2")
36

Answer 4

Una versione semplice e veloce dell'algoritmo da oefe di e risposte di KennyTM:

def select_weighted(d):
   offset = random.randint(0, sum(d.itervalues())-1)
   for k, v in d.iteritems():
      if offset < v:
         return k
      offset -= v