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

Ich habe den anderen Thread betrachtet und bin zu dieser Variation in meinem Codierungsstil gekommen, das gibt den Index der Auswahl zurück, um zu zählen, aber es ist einfach, den String zurückzugeben (kommentierte Rückgabealternative):

import random
import bisect

try:
    range = xrange
except:
    pass

def weighted_choice(choices):
    total, cumulative = 0, []
    for c,w in choices:
        total += w
        cumulative.append((total, c))
    r = random.uniform(0, total)
    # Index zurückgeben
    return bisect.bisect(cumulative, (r,))
    # String zurückgeben
    #return choices[bisect.bisect(cumulative, (r,))][0]

# Auswahl und relative Gewichte festlegen
choices = [("WHITE",90), ("RED",8), ("GREEN",2)]

tally = [0 for item in choices]

n = 100000
# Zähle n gewichtete Entscheidungen zusammen
for i in range(n):
    tally[weighted_choice(choices)] += 1

print([t/sum(tally)*100 for t in tally])

Answer 2

Hier ist eine weitere Version von weighted_choice, die numpy verwendet. Übergeben Sie den Gewichtsvektor und es wird ein Array von 0en zurückgegeben, das eine 1 enthält, die angibt, welches Bin gewählt wurde. Der Code wird standardmäßig nur eine Ziehung machen, aber Sie können die Anzahl der zu machenden Ziehungen übergeben und die Zählungen pro gezogenem Bin werden zurückgegeben.

Wenn der Gewichtsvektor nicht auf 1 summiert, wird er normalisiert, so dass er dies tut.

import numpy as np

def weighted_choice(weights, n=1):
    if np.sum(weights)!=1:
        weights = weights/np.sum(weights)

    draws = np.random.random_sample(size=n)

    weights = np.cumsum(weights)
    weights = np.insert(weights,0,0.0)

    counts = np.histogram(draws, bins=weights)
    return(counts[0])

Answer 3

Es gibt eine Vorlesung dazu von Sebastien Thurn im kostenlosen Udacity-Kurs KI für Robotik. Grundsätzlich erstellt er ein kreisförmiges Array der indexierten Gewichte unter Verwendung des Modulo-Operators %, setzt eine Variable beta auf 0, wählt zufällig einen Index aus, durchläuft eine Schleife für N, wobei N die Anzahl der Indizes ist, und inkrementiert in der Schleife zunächst beta nach folgender Formel:

beta = beta + gleichverteilte Zufallsstichprobe aus {0...2* Weight_max}

und dann verschachtelt in der Schleife eine while-Schleife wie unten dargestellt:

while w[index] < beta:
    beta = beta - w[index]
    index = index + 1

select p[index]

Dann geht es zum nächsten Index, um basierend auf den Wahrscheinlichkeiten (oder normalisierten Wahrscheinlichkeiten im im Kurs präsentierten Fall) neu zu sampeln.

Auf Udacity finden Sie Lektion 8, Video Nummer 21 zur Künstlichen Intelligenz für Robotik, in der er über Partikelfilter referiert.

Answer 4

Je nachdem, wie oft Sie die Verteilung abtasten möchten.

Angenommen, Sie möchten die Verteilung K Mal abtasten. Dann beträgt die Zeitkomplexität bei jeder Verwendung von np.random.choice() O(K(n + log(n))), wobei n die Anzahl der Elemente in der Verteilung ist.

In meinem Fall musste ich die gleiche Verteilung mehrmals im Bereich von 10^3 abtasten, wobei n im Bereich von 10^6 liegt. Ich habe den folgenden Code verwendet, der die kumulative Verteilung vorbereitet und diese in O(log(n)) abtastet. Die Gesamtzeitkomplexität beträgt O(n+K*log(n)).

import numpy as np

n, k = 10**6, 10**3

# Erstellen einer Dummy-Verteilung
a = np.array([i+1 for i in range(n)])
p = np.array([1.0/n]*n)

cfd = p.cumsum()
for _ in range(k):
    x = np.random.uniform()
    idx = cfd.searchsorted(x, side='right')
    abgetastetes_element = a[idx]

Answer 5

Sagen wir, du hast

items = [11, 23, 43, 91] 
probability = [0.2, 0.3, 0.4, 0.1]

und du hast eine Funktion, die eine Zufallszahl zwischen [0, 1) generiert (hier können wir random.random() verwenden). also berechne jetzt die Präfixsumme der Wahrscheinlichkeiten

prefix_probability=[0.2,0.5,0.9,1]

jetzt können wir einfach eine Zufallszahl zwischen 0 und 1 nehmen und eine Binärsuche verwenden, um zu finden, wo diese Zahl in der Präfixsumme der Wahrscheinlichkeiten liegt. Dieser Index wird deine Antwort sein

Der Code wird ungefähr so aussehen

return items[bisect.bisect(prefix_probability,random.random())]