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

Question

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

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

Comment puis-je faire?

Answer 1

1 Construire 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 Construire 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

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

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

Maintenant, générer un nombre aléatoire xbetween 0 et n - 1. Trouvez la dernière entrée dans la liste avec index < x. Étant donné que la liste est triée par index, vous pouvez utiliser la recherche binaire pour le faire efficacement.

Mise à jour: Code de KennyTM est une application de la présente, sauf qu'il utilise une force brute recherche linéaire au lieu de recherche binaire; ce sera inefficace si le nombre de touches sont grandes.

Answer 3

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