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

Ab Python v3.6 konnte random.choices verwendet werden, um eine Liste von Elementen der angegebenen Größe aus der gegebenen Population mit optionalen Gewichten zurückzugeben.

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

• population : Liste mit eindeutigen Beobachtungen. (Wenn leer, wirft es IndexError)

• weights : Genauere relative Gewichte, die für die Auswahl erforderlich sind.

• cum_weights : Kumulative Gewichte, die für die Auswahl erforderlich sind.

• k : Größe(len) der auszugebenden Liste. (Standard len()=1)

---

Einige Einschränkungen:

1) Es wird eine gewichtete Stichprobe mit Wiederholung verwendet, sodass die gezogenen Elemente später ersetzt werden. Die Werte in der Gewichtssequenz selbst sind nicht wichtig, aber ihr relatives Verhältnis.

Im Gegensatz zu np.random.choice, das nur Wahrscheinlichkeiten als Gewichtungen annehmen kann und auch sicherstellen muss, dass die Summierungen der einzelnen Wahrscheinlichkeiten bis zu 1 erfolgen, gibt es hier keine solchen Bestimmungen. Solange sie zu numerischen Typen gehören (int/float/fraction außer vom Typ Decimal), funktionieren sie dennoch.

>>> import random
# Gewichte als ganze Zahlen
>>> random.choices(["weiß", "grün", "rot"], [12, 12, 4], k=10)
['grün', 'rot', 'grün', 'weiß', 'weiß', 'weiß', 'grün', 'weiß', 'rot', 'weiß']
# Gewichte als Gleitkommazahlen
>>> random.choices(["weiß", "grün", "rot"], [.12, .12, .04], k=10)
['weiß', 'weiß', 'grün', 'grün', 'rot', 'rot', 'weiß', 'grün', 'weiß', 'grün']
# Gewichte als Brüche
>>> random.choices(["weiß", "grün", "rot"], [12/100, 12/100, 4/100], k=10)
['grün', 'grün', 'weiß', 'rot', 'grün', 'rot', 'weiß', 'grün', 'grün', 'grün']

2) Wenn weder weights noch cum_weights angegeben sind, werden die Auswahlen mit gleicher Wahrscheinlichkeit getroffen. Wenn eine Gewichtungssequenz bereitgestellt wird, muss sie die gleiche Länge wie die Populationssequenz haben.

Das Angeben sowohl von weights als auch von cum_weights führt zu einem TypeError.

>>> random.choices(["weiß", "grün", "rot"], k=10)
['weiß', 'weiß', 'grün', 'rot', 'rot', 'rot', 'weiß', 'weiß', 'weiß', 'grün']

3) cum_weights sind typischerweise das Ergebnis der itertools.accumulate-Funktion, die in solchen Situationen wirklich nützlich sind.

_{Aus der verlinkten Dokumentation:}

Intern werden die relativen Gewichte in kumulative Gewichte umgewandelt, bevor Auswahl getroffen wird, daher spart das Bereitstellen der kumulativen Gewichte Arbeit.

Also produzieren entweder die Bereitstellung von Gewichte=[12, 12, 4] oder cum_weights=[12, 24, 28] für unseren konstruierten Fall das gleiche Ergebnis und Letzteres scheint schneller / effizienter zu sein.

Answer 2

Roh, aber möglicherweise ausreichend:

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

Funktioniert es?

# definiere Auswahlmöglichkeiten und relative Gewichte
choices = [("WEISS",90), ("ROT",8), ("GRÜN",2)]

# initialisiere Zähldikt
tally = dict.fromkeys(choices, 0)

# zähle 1000 gewichtete Auswahlmöglichkeiten
for i in xrange(1000):
    tally[weighted_choice(choices)] += 1

print tally.items()

Druckt:

[('WEISS', 904), ('GRÜN', 22), ('ROT', 74)]

Vorausgesetzt, alle Gewichte sind Ganzzahlen. Sie müssen nicht auf 100 addieren, ich habe das nur gemacht, um die Testergebnisse einfacher zu interpretieren. (Wenn die Gewichte Gleitkommazahlen sind, multiplizieren Sie sie wiederholt mit 10, bis alle Gewichte >= 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)

Answer 3

Wenn Sie ein gewichtetes Wörterbuch anstelle einer Liste haben, können Sie Folgendes schreiben

items = { "a": 10, "b": 5, "c": 1 } 
random.choice([k for k in items for dummy in range(items[k])])

Beachten Sie, dass [k for k in items for dummy in range(items[k])] diese Liste erstellt ['a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'c', 'b', 'b', 'b', 'b', 'b']

Answer 4

Hier ist die Version, die in der Standardbibliothek für Python 3.6 enthalten ist:

import itertools as _itertools
import bisect as _bisect

class Random36(random.Random):
    "Zeigen Sie den in der Python 3.6-Version der Random-Klasse enthaltenen Code"

    def choices(self, population, weights=None, *, cum_weights=None, k=1):
        """Geben Sie eine Liste mit k Elementen der Bevölkerung zurück, die mit Ersatz ausgewählt wurden.

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

        """
        random = self.random
        if cum_weights is None:
            if weights is None:
                _int = int
                total = len(population)
                return [population[_int(random() * total)] for i in range(k)]
            cum_weights = list(_itertools.accumulate(weights))
        elif weights is not None:
            raise TypeError('Kann sowohl Gewichte als auch kumulative Gewichte nicht angeben')
        if len(cum_weights) != len(population):
            raise ValueError('Die Anzahl der Gewichte stimmt nicht mit der Bevölkerung überein')
        bisect = _bisect.bisect
        total = cum_weights[-1]
        return [population[bisect(cum_weights, random() * total)] for i in range(k)]

Quelle: https://hg.python.org/cpython/file/tip/Lib/random.py#l340

Answer 5

Ein sehr einfacher und einfacher Ansatz für eine gewichtete Auswahl ist der folgende:

np.random.choice(['A', 'B', 'C'], p=[0.3, 0.4, 0.3])