Clés d'échantillonnage en raison de leurs valeurs

Question

J'ai un dictionnaire en python avec key-> value comme str->int. Si je dois choisir une clé en fonction de sa propre valeur, alors que la valeur augmente, la clé a une plus faible possibilité d'être choisie.

Par exemple, si key1=2 et key2->1, l'attitude de key1 devrait être 2:1.

Comment est-ce que je peux faire ceci?

Answer 1

1. dresser une liste CDF comme comme ceci:

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

Cette fonction retourne un tuple, la 1ère valeur est la somme des probabilités et la valeur 2 est le CDF.

2. Construct l'échantillonneur comme ceci:

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] 

Utilisation:

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 

Vous pouvez faire cela en une classe.

Answer 2

Il les valeurs ne sont pas trop grand, vous pouvez le faire de cette façon

>>> 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 3

Si les valeurs sont trop grandes pour l'approche gnibler:

Dressez une liste de tuples (key, index), où index est le somme de toutes les valeurs qui viennent avant la clé dans la liste (ce serait l'indice de la première occurrence de key la liste de gnibler c) Calculez également la somme de toutes les valeurs (n)

Maintenant, générez un nombre aléatoire x entre 0 et n - 1. Trouvez la dernière entrée de la liste avec index < x. Puisque la liste est triée par index, vous pouvez utiliser la recherche binaire pour le faire efficacement.

Mise à jour: Le code de KennyTM en est une implémentation, sauf qu'il utilise une recherche linéaire brute-force au lieu de la recherche binaire; ce sera inefficace si le nombre de clés est important.

Answer 4

Une version rapide et simple de l'algorithme de celle des OEFE et les réponses de 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