Une version pondérée de random.choice

Question

J'avais besoin d'écrire une version pondérée de random.choice (chaque élément de la liste a une probabilité différente d'être sélectionné). Voici ce que j'ai trouvé :

def weightedChoice(choices):
    """Like random.choice, but each element can have a different chance of
    being selected.

    choices can be any iterable containing iterables with two items each.
    Technically, they can have more than two items, the rest will just be
    ignored.  The first item is the thing being chosen, the second item is
    its weight.  The weights can be any numeric values, what matters is the
    relative differences between them.
    """
    space = {}
    current = 0
    for choice, weight in choices:
        if weight > 0:
            space[current] = choice
            current += weight
    rand = random.uniform(0, current)
    for key in sorted(space.keys() + [current]):
        if rand < key:
            return choice
        choice = space[key]
    return None

Cette fonction me semble excessivement complexe, et laide. J'espère que tout le monde ici pourra faire des suggestions pour l'améliorer ou trouver d'autres façons de la réaliser. L'efficacité n'est pas aussi importante pour moi que la propreté et la lisibilité du code.

Answer 1

Depuis la version 1.7.0, NumPy dispose d'une fonction choice qui prend en charge les distributions de probabilité.

from numpy.random import choice
draw = choice(list_of_candidates, number_of_items_to_pick, p=probability_distribution)

Notez que probability_distribution est une séquence dans le même ordre de list_of_candidates . Vous pouvez également utiliser le mot-clé replace=False pour modifier le comportement afin que les éléments tirés au sort ne soient pas remplacés.

Answer 2

def weighted_choice(choices):
   total = sum(w for c, w in choices)
   r = random.uniform(0, total)
   upto = 0
   for c, w in choices:
      if upto + w > r:
         return c
      upto += w
   assert False, "Shouldn't get here"

Answer 3

1. Classez les poids dans une distribution cumulative.
2. Utilisez random.random() pour choisir un float 0.0 <= x < total .

3. Rechercher la distribution en utilisant bisect.bisect comme comme le montre l'exemple à http://docs.python.org/dev/library/bisect.html#other-examples .

   from random import random from bisect import bisect

   def weighted_choice(choices): values, weights = zip(*choices) total = 0 cum_weights = [] for w in weights: total += w cum_weights.append(total) x = random() * total i = bisect(cum_weights, x) return values[i]

   weighted_choice([("WHITE",90), ("RED",8), ("GREEN",2)]) 'WHITE'

Si vous devez faire plus d'un choix, divisez cette fonction en deux, l'une pour construire les poids cumulés et l'autre pour effectuer une bissectrice vers un point aléatoire.

Answer 4

Si cela ne vous dérange pas d'utiliser numpy, vous pouvez utiliser numpy.random.choice .

Par exemple :

import numpy

items  = [["item1", 0.2], ["item2", 0.3], ["item3", 0.45], ["item4", 0.05]
elems = [i[0] for i in items]
probs = [i[1] for i in items]

trials = 1000
results = [0] * len(items)
for i in range(trials):
    res = numpy.random.choice(items, p=probs)  #This is where the item is selected!
    results[items.index(res)] += 1
results = [r / float(trials) for r in results]
print "item\texpected\tactual"
for i in range(len(probs)):
    print "%s\t%0.4f\t%0.4f" % (items[i], probs[i], results[i])

Si vous savez à l'avance combien de sélections vous devez effectuer, vous pouvez le faire sans boucle comme celle-ci :

numpy.random.choice(items, trials, p=probs)

Answer 5

Brut, mais peut être suffisant :

import random
weighted_choice = lambda s : random.choice(sum(([v]*wt for v,wt in s),[]))

Est-ce que ça marche ?

# define choices and relative weights
choices = [("WHITE",90), ("RED",8), ("GREEN",2)]

# initialize tally dict
tally = dict.fromkeys(choices, 0)

# tally up 1000 weighted choices
for i in xrange(1000):
    tally[weighted_choice(choices)] += 1

print tally.items()

Imprimés :

[('WHITE', 904), ('GREEN', 22), ('RED', 74)]

On suppose que tous les poids sont des entiers. Il n'est pas nécessaire que leur somme soit égale à 100, je l'ai simplement fait pour faciliter l'interprétation des résultats du test. (Si les poids sont des nombres à virgule flottante, multipliez-les tous par 10 de manière répétée jusqu'à ce que tous les poids >= 1).

weights = [.6, .2, .001, .199]
while any(w < 1.0 for w in weights):
    weights = [w*10 for w in weights]
weights = map(int, weights)