Eine gewichtete Version von random.choice

Question

Ich musste eine gewichtete Version von random.choice schreiben (jedes Element in der Liste hat eine unterschiedliche Wahrscheinlichkeit ausgewählt zu werden). Das ist, was ich erstellt habe:

def weightedChoice(choices):
    """Wie random.choice, aber jedes Element kann eine andere Chance haben, ausgewählt zu werden.

    choices kann eine beliebige Iterable sein, die Iterable mit zwei Elementen enthält.
    Technisch gesehen können sie mehr als zwei Elemente haben, der Rest wird einfach ignoriert. Das erste Element ist das ausgewählte Element, das zweite Element ist
    sein Gewicht. Die Gewichte können beliebige numerische Werte sein, was zählt sind die
    relativen Unterschiede zwischen ihnen.
    """
    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 scheint mir übermäßig komplex und hässlich zu sein. Ich hoffe, dass alle hier einige Vorschläge zur Verbesserung oder alternative Möglichkeiten bieten können. Effizienz ist für mich nicht so wichtig wie die Leserlichkeit und die Sauberkeit des Codes.

Answer 1

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 eine Sequenz in der gleichen Reihenfolge wie list_of_candidates ist. Sie können auch das Stichwort replace=False verwenden, um das Verhalten zu ändern, sodass gezogene Elemente nicht ersetzt werden.

Answer 2

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

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 gemäß den Dokumenten mit Wiederholung sampelt:

Gibt eine Liste der Größe k mit Elementen aus der Population mit Wiederholung zurück.

Zur Vollständigkeit der Antwort:

Wenn eine Stichprobe aus einer endlichen Population gezogen und nach Aufzeichnung ihrer Merkmale in diese Population zurückgelegt wird, bevor die nächste Einheit gezogen wird, wird die Stichprobe als "mit Wiederholung" bezeichnet. Es bedeutet im Grunde genommen, dass jedes Element mehrmals ausgewählt werden kann.

Wenn Sie ohne Wiederholung sampeln müssen, dann können Sie, wie @ronan-paixão's brillante Antwort besagt, numpy.choice verwenden, dessen Argument replace ein solches Verhalten steuert.

Answer 3

def gewichtete_wahl(wahlen):
    gesamt = sum(w for c, w in wahlen)
    r = random.uniform(0, gesamt)
    bis = 0
    for c, w in wahlen:
        if bis + w >= r:
           return c
        bis += w
    assert False, "Sollte nicht hier landen"

Answer 4

Aktualisierte Antwort

Die Python-Standardbibliothek enthält jetzt random.choices(), das direkt gewichtete Auswahl unterstützt.

Hier ist ein Beispiel aus der Dokumentation:

>>> # Sechs Roulette-Radumdrehungen (gewichtete Stichproben mit Zurücklegen)
>>> choices(['rot', 'schwarz', 'grün'], [18, 18, 2], k=6)
['rot', 'grün', 'schwarz', 'schwarz', 'rot', 'schwarz']

Algorithmusübersicht:

1. Ordnen Sie die Gewichte in eine kumulative Verteilung ein.
2. Verwenden Sie random.random(), um einen zufälligen Float-Wert 0,0 <= x < total auszuwählen.
3. Durchsuchen Sie die Verteilung mithilfe von bisect.bisect() wie im Beispiel unter http://docs.python.org/dev/library/bisect.html#other-examples gezeigt.

Vereinfachter Code:

from random import random
from math import floor as floor
from bisect import bisect as bisect
from itertools import accumulate, repeat

def choices(population, weights=None, *, cum_weights=None, k=1):
    """Gibt eine Liste der Größe k der Elemente der Population zurück, die mit Zurücklegen ausgewählt wurden.

    Wenn die relativen Gewichte oder kumulativen Gewichte nicht angegeben sind,
    werden die Auswahlmöglichkeiten mit gleicher Wahrscheinlichkeit getroffen.

    """
    n = len(population)
    if cum_weights is None:
        if weights is None:
            return [population[floor(random() * n)] for i in repeat(None, k)]
        cum_weights = list(accumulate(weights))
    elif weights is not None:
        raise TypeError('Kann sowohl Gewichte als auch kumulative Gewichte nicht angeben')

    total = cum_weights[-1] + 0.0
    hi = n - 1
    return [population[bisect(cum_weights, random() * total, 0, hi)]
            for i in repeat(None, k)]

Answer 5

Wenn Sie kein Problem haben, numpy zu verwenden, können Sie numpy.random.choice verwenden.

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)  #Hier wird das Element ausgewählt!
    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 Auswahlentscheidungen Sie treffen müssen, können Sie dies auch ohne Schleife tun:

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