Eine gewichtete Version von random.choice

Ich musste eine gewichtete Version von random.choice schreiben (jedes Element in der Liste hat eine andere Wahrscheinlichkeit, ausgewählt zu werden). Das ist mir eingefallen:

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

Diese Funktion erscheint mir zu komplex und hässlich. Ich hoffe, dass jeder hier einige Vorschläge zur Verbesserung oder alternative Möglichkeiten machen kann, dies zu tun. Effizienz ist mir nicht so wichtig wie Code-Sauberkeit und Lesbarkeit.

Seit Version 1.7.0 hat NumPy eine choice Funktion, die Wahrscheinlichkeitsverteilungen unterstützt.

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

Beachten Sie, dass probability_distribution ist eine Sequenz in der gleichen Reihenfolge von list_of_candidates. Sie können auch das Schlüsselwort verwenden replace=False um das Verhalten so zu ändern, dass gezeichnete Elemente nicht ersetzt werden.

Seit Python 3.6 gibt es eine Methode choices von dem random Modul.

In [1]: import random

In [2]: random.choices(
...:     population=[['a','b'], ['b','a'], ['c','b']],
...:     weights=[0.2, 0.2, 0.6],
...:     k=10
...: )

Out[2]:
[['c', 'b'],
 ['c', 'b'],
 ['b', 'a'],
 ['c', 'b'],
 ['c', 'b'],
 ['b', 'a'],
 ['c', 'b'],
 ['b', 'a'],
 ['c', 'b'],
 ['c', 'b']]

Beachten Sie, dass random.choices wird Probe mit Ersatzlaut Dokumente:

Rückkehr a k große Liste von Elementen, die aus der Grundgesamtheit mit Ersetzung ausgewählt wurden.

Hinweis zur Vollständigkeit der Antwort:

Wenn eine Stichprobeneinheit aus einer endlichen Grundgesamtheit gezogen und an diese Grundgesamtheit zurückgegeben wird, nachdem ihre Merkmale aufgezeichnet wurden, bevor die nächste Einheit gezogen wird, wird die Stichprobe als “mit Ersatz” bezeichnet. Es bedeutet im Grunde, dass jedes Element mehr als einmal ausgewählt werden kann.

Wenn Sie ersatzlos probieren müssen, können Sie, wie die brillante Antwort von @ronan-paixão feststellt, verwenden numpy.choiceDeren replace Argument kontrolliert ein solches Verhalten.

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"

1. Ordnen Sie die Gewichte in einer kumulativen Verteilung an.
2. Verwenden zufällig.random() um einen zufälligen Float auszuwählen 0.0 <= x < total.
3. Suchen Sie die Distribution mit halbieren.halbieren wie im Beispiel bei gezeigt 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'

Wenn Sie mehr als eine Auswahl treffen müssen, teilen Sie diese in zwei Funktionen auf, eine zum Erstellen der kumulativen Gewichtungen und eine andere zum Halbieren zu einem zufälligen Punkt.

Wenn es Ihnen nichts ausmacht, numpy zu verwenden, können Sie verwenden numpy.random.choice.

Zum Beispiel:

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

Wenn Sie im Voraus wissen, wie viele Auswahlen Sie treffen müssen, können Sie dies ohne eine Schleife wie diese tun:

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

Ab Python v3.6, random.choices könnte verwendet werden, um a zurückzugeben list von Elementen der angegebenen Größe aus der gegebenen Grundgesamtheit mit optionalen Gewichten.

random.choices(population, weights=None, *, cum_weights=None, k=1)

• Population : list mit einzigartigen Beobachtungen. (Wenn leer, wird erhöht IndexError)

• Gewichte : Genauer gesagt relative Gewichtungen, die zum Treffen von Auswahlen erforderlich sind.

• cum_weights : kumulierte Gewichte, die zum Treffen von Auswahlen erforderlich sind.

• k : Größe(len) des list ausgegeben werden. (Standard len()=1)

Einige Vorbehalte:

1) Es wird eine gewichtete Stichprobe mit Ersatz verwendet, damit die gezogenen Gegenstände später ersetzt werden. Die Werte in der Gewichtungssequenz an sich spielen keine Rolle, aber ihr relatives Verhältnis schon.

nicht wie np.random.choice die nur Wahrscheinlichkeiten als Gewichte annehmen können und auch die Summierung einzelner Wahrscheinlichkeiten bis zu 1 Kriterium gewährleisten müssen, gibt es hier keine derartigen Regelungen. Solange sie zu numerischen Typen gehören (int/float/fraction außer Decimal type) , würden diese trotzdem funktionieren.

>>> import random
# weights being integers
>>> random.choices(["white", "green", "red"], [12, 12, 4], k=10)
['green', 'red', 'green', 'white', 'white', 'white', 'green', 'white', 'red', 'white']
# weights being floats
>>> random.choices(["white", "green", "red"], [.12, .12, .04], k=10)
['white', 'white', 'green', 'green', 'red', 'red', 'white', 'green', 'white', 'green']
# weights being fractions
>>> random.choices(["white", "green", "red"], [12/100, 12/100, 4/100], k=10)
['green', 'green', 'white', 'red', 'green', 'red', 'white', 'green', 'green', 'green']

2) Wenn weder Gewichte Noch cum_weights angegeben sind, erfolgt die Auswahl mit gleicher Wahrscheinlichkeit. Wenn ein Gewichte Sequenz geliefert wird, muss sie die gleiche Länge haben wie die Population Reihenfolge.

Beides angeben Gewichte und cum_weights erhebt a TypeError.

>>> random.choices(["white", "green", "red"], k=10)
['white', 'white', 'green', 'red', 'red', 'red', 'white', 'white', 'white', 'green']

3) cum_weights sind in der Regel ein Ergebnis von itertools.accumulate Funktion, die in solchen Situationen wirklich praktisch sind.

_{Aus der verlinkten Dokumentation:}

Intern werden die relativen Gewichtungen in kumulative Gewichtungen konvertiert, bevor eine Auswahl getroffen wird, sodass die Bereitstellung der kumulativen Gewichtungen Arbeit spart.

Also entweder liefern weights=[12, 12, 4] oder cum_weights=[12, 24, 28] denn unser erfundener Fall führt zum gleichen Ergebnis und letzteres scheint schneller / effizienter zu sein.

Grob, aber möglicherweise ausreichend:

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

Funktioniert es?

# 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()

Drucke:

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

Geht davon aus, dass alle Gewichtungen ganze Zahlen sind. Sie müssen sich nicht zu 100 addieren, ich habe das nur gemacht, um die Testergebnisse leichter interpretierbar zu machen. (Wenn Gewichtungen Gleitkommazahlen sind, multiplizieren Sie sie alle wiederholt mit 10, bis alle Gewichtungen >= 1 sind.)

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)