Eine gewichtete Version von random.choice

245

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

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 dazu machen kann. Effizienz ist für mich nicht so wichtig wie Code-Sauberkeit und Lesbarkeit.

Colin
quelle

Antworten:

297

Seit Version 1.7.0 verfügt NumPy über eine choiceFunktion, 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 dies probability_distributioneine Sequenz in derselben Reihenfolge von ist list_of_candidates. Sie können das Schlüsselwort auch verwenden replace=False, um das Verhalten so zu ändern, dass gezeichnete Elemente nicht ersetzt werden.

Ronan Paixão
quelle
11
Nach meinen Tests ist dies eine Größenordnung langsamer als random.choicesbei einzelnen Anrufen. Wenn Sie viele zufällige Ergebnisse benötigen, ist es wirklich wichtig, alle auf einmal durch Anpassen auszuwählen number_of_items_to_pick. Wenn Sie dies tun, ist es eine Größenordnung schneller.
jpmc26
2
Dies funktioniert nicht mit Tupeln usw. ("ValueError: a muss eindimensional sein"). In diesem Fall kann man numpy bitten, den Index in die Liste aufzunehmen, dh len(list_of_candidates)und dannlist_of_candidates[draw]
xjcl
217

Seit Python 3.6 gibt es eine Methode choicesaus dem randomModul.

Python 3.6.1 (v3.6.1:69c0db5050, Mar 21 2017, 01:21:04)
Type 'copyright', 'credits' or 'license' for more information
IPython 6.0.0 -- An enhanced Interactive Python. Type '?' for help.

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.choicesein Beispiel mit Ersatz gemäß den folgenden Dokumenten erstellt wird :

Gibt eine kgroße Liste von Elementen zurück, die aus der Grundgesamtheit mit Ersetzung ausgewählt wurden.

Wenn Sie ersatzlos probieren müssen, können Sie, wie in der brillanten Antwort von @ ronan-paixão angegeben , verwenden numpy.choice, dessen replaceArgument ein solches Verhalten steuert.

vishes_shell
quelle
4
Das ist so viel schneller als numpy.random.choice. Numpy.random.choice wählte 10.000 Mal aus einer Liste von 8 gewichteten Elementen aus und dauerte 0,3286 Sekunden, während random.choices 0,0416 Sekunden dauerte, was ungefähr 8x schneller war.
Anton Codes
@AntonCodes Dieses Beispiel wurde von Kirschen gepflückt. numpy wird einen zeitlich konstanten Overhead haben, der random.choicesdies nicht tut. Bei einer winzigen Liste mit 8 Elementen ist dies natürlich langsamer. Wenn Sie aus einer solchen Liste 10.000 Mal auswählen, haben Sie Recht. Aber in Fällen, in denen die Liste größer ist (je nachdem, wie Sie testen, sehe ich Unterbrechungspunkte zwischen 100 und 300 Elementen), np.random.choicebeginnt die Outperformance random.choicesdurch eine ziemlich große Lücke. Zum Beispiel, einschließlich des Normalisierungsschritts zusammen mit dem Numpy-Aufruf, erhalte ich eine fast 4-fache Beschleunigung random.choicesfür eine Liste von 10.000 Elementen.
Ggorlen
Dies sollte die neue Antwort sein, die auf der von @AntonCodes gemeldeten Leistungsverbesserung basiert.
Wayne Workman
132
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"
Ned Batchelder
quelle
10
Sie können eine Operation upto +=w; if upto > r
löschen
5
Speichern Sie eine Variable, indem Sie bis zu löschen und r jedes Mal um das Gewicht dekrementieren. Der Vergleich ist dannif r < 0
JnBrymn
@JnBrymn Sie müssen überprüfen r <= 0. Betrachten Sie einen Eingabesatz von 1 Elementen und einen Wurf von 1,0. Die Behauptung wird dann fehlschlagen. Ich habe diesen Fehler in der Antwort korrigiert.
Moooeeeep
1
@ Sardathrion Sie könnten ein Pragma verwenden, um die for-Schleife als partiell zu markieren:# pragma: no branch
Ned Batchelder
1
@ mLstudent33 Ich benutze Udacity nicht.
Anton Codes
70
  1. Ordnen Sie die Gewichte in einer kumulativen Verteilung an.
  2. Verwenden Sie random.random () , um einen zufälligen Float auszuwählen 0.0 <= x < total.
  3. Durchsuchen Sie die Distribution mit bisect.bisect, wie im Beispiel unter http://docs.python.org/dev/library/bisect.html#other-examples gezeigt .
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 Gewichte und eine zum Halbieren auf einen zufälligen Punkt.

Raymond Hettinger
quelle
5
Dies ist effizienter als Neds Antwort. Anstatt eine lineare (O (n)) Suche durch die Auswahlmöglichkeiten durchzuführen, führt er im Grunde eine binäre Suche (O (log n)) durch. +1!
NHDaly
Tupel-Index außerhalb des Bereichs, wenn random () zufällig 1.0 zurückgibt
Jon Vaughan
10
Dies läuft O(n)aufgrund der kumulativen Verteilungsberechnung immer noch ein.
Lev Levitsky
6
Diese Lösung ist besser für den Fall, dass mehrere Aufrufe von weighted_choice für dieselbe Auswahl erforderlich sind. In diesem Fall können Sie die kumulative Summe einmal erstellen und bei jedem Aufruf eine binäre Suche durchführen.
Amos
1
@ JonVaughan random() kann 1.0 nicht zurückgeben. Gemäß den Dokumenten wird ein Ergebnis im halboffenen Intervall zurückgegeben [0.0, 1.0), dh, es kann genau 0,0, aber nicht genau 1,0 zurückgeben. Der größte Wert, den es zurückgeben kann, ist 0,99999999999999988897769753748434595763683319091796875 (Python druckt als 0,999999999999999999 und ist der größte 64-Bit-Float kleiner als 1).
Mark Amery
21

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

Beispielsweise:

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 wissen, wie viele Auswahlen Sie im Voraus treffen müssen, können Sie dies ohne eine Schleife wie die folgende tun:

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

Roh, kann aber ausreichen:

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

Angenommen, alle Gewichte sind ganze Zahlen. Sie müssen nicht 100 addieren, ich habe das nur getan, um die Testergebnisse leichter interpretieren zu können. (Wenn Gewichte Gleitkommazahlen sind, multiplizieren Sie sie alle 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)
PaulMcG
quelle
1
Schön, ich bin mir nicht sicher, ob ich davon ausgehen kann, dass alle Gewichte ganze Zahlen sind.
Colin
1
Scheint, als würden Ihre Objekte in diesem Beispiel dupliziert. Das wäre ineffizient (und ebenso die Funktion zum Konvertieren von Gewichten in ganze Zahlen). Trotzdem ist diese Lösung ein guter Einzeiler, wenn die ganzzahligen Gewichte klein sind.
Wei2912
Grundelemente werden dupliziert, aber Objekte haben nur duplizierte Referenzen, nicht die Objekte selbst. (Aus diesem Grund können Sie keine Liste von Listen erstellen, indem Sie [[]]*10- alle Elemente in der äußeren Liste zeigen auf dieselbe Liste.
PaulMcG
@PaulMcG Nein; nichts als Referenzen werden jemals dupliziert. Pythons Typsystem hat kein Konzept von Grundelementen. Sie können bestätigen, dass Sie auch mit z. B. intimmer noch viele Verweise auf dasselbe Objekt erhalten, indem Sie Folgendes tun [id(x) for x in ([99**99] * 100)]und beobachten, dass idbei jedem Aufruf dieselbe Speicheradresse zurückgegeben wird.
Mark Amery
14

Wenn Sie ein gewichtetes Wörterbuch anstelle einer Liste haben, können Sie dies 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 wird['a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'c', 'b', 'b', 'b', 'b', 'b']

Maxime
quelle
10
Dies funktioniert für kleine Gesamtbevölkerungswerte, jedoch nicht für große Datensätze (z. B. würde die US-Bevölkerung nach Bundesstaaten eine Arbeitsliste mit 300 Millionen Elementen erstellen).
Ryan
@ Ryan in der Tat. Es funktioniert auch nicht für nicht ganzzahlige Gewichte, was ein weiteres realistisches Szenario darstellt (z. B. wenn Sie Ihre Gewichte als Auswahlwahrscheinlichkeiten ausdrücken lassen).
Mark Amery
12

Ab Python v3.6kann random.choicesein listElement mit der angegebenen Größe aus der angegebenen Grundgesamtheit mit optionalen Gewichten zurückgegeben werden.

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

  • Bevölkerung : listenthält einzigartige Beobachtungen. (Wenn leer, erhöht IndexError)

  • Gewichte : Genauer gesagt sind relative Gewichte erforderlich, um eine Auswahl zu treffen.

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

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


Einige Vorsichtsmaßnahmen:

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

Anders np.random.choiceals diejenigen, die nur Wahrscheinlichkeiten als Gewichte annehmen können und auch die Summierung einzelner Wahrscheinlichkeiten bis zu 1 Kriterium sicherstellen müssen, gibt es hier keine derartigen Regelungen. Solange sie zu numerischen Typen gehören ( int/float/fractionaußer DecimalTyp), würden diese weiterhin 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, wird die Auswahl mit gleicher Wahrscheinlichkeit getroffen. Wenn eine Gewichtssequenz angegeben wird, muss sie dieselbe Länge wie die Populationssequenz haben .

Wenn Sie sowohl Gewichte als auch cum_weights angeben, wird a ausgelöstTypeError .

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

3) cum_weights sind normalerweise ein Ergebnis von itertools.accumulateFunktionen, die in solchen Situationen sehr praktisch sind.

Aus der Dokumentation verlinkt:

Intern werden die relativen Gewichte vor der Auswahl in kumulative Gewichte umgewandelt, sodass die Bereitstellung der kumulativen Gewichte Arbeit spart.

Die Lieferung weights=[12, 12, 4]oder cum_weights=[12, 24, 28]für unseren erfundenen Fall führt also zu demselben Ergebnis, und letzteres scheint schneller / effizienter zu sein.

Nickil Maveli
quelle
11

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):
    "Show the code included in the Python 3.6 version of the Random class"

    def choices(self, population, weights=None, *, cum_weights=None, k=1):
        """Return a k sized list of population elements chosen with replacement.

        If the relative weights or cumulative weights are not specified,
        the selections are made with equal probability.

        """
        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('Cannot specify both weights and cumulative weights')
        if len(cum_weights) != len(population):
            raise ValueError('The number of weights does not match the population')
        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

Raymond Hettinger
quelle
2
import numpy as np
w=np.array([ 0.4,  0.8,  1.6,  0.8,  0.4])
np.random.choice(w, p=w/sum(w))
whi
quelle
2

Ich bin wahrscheinlich zu spät, um etwas Nützliches beizutragen, aber hier ist ein einfacher, kurzer und sehr effizienter Ausschnitt:

def choose_index(probabilies):
    cmf = probabilies[0]
    choice = random.random()
    for k in xrange(len(probabilies)):
        if choice <= cmf:
            return k
        else:
            cmf += probabilies[k+1]

Sie müssen Ihre Wahrscheinlichkeiten nicht sortieren oder einen Vektor mit Ihrer cmf erstellen und sie wird beendet, sobald sie ihre Wahl gefunden hat. Speicher: O (1), Zeit: O (N), mit durchschnittlicher Laufzeit ~ N / 2.

Wenn Sie Gewichte haben, fügen Sie einfach eine Zeile hinzu:

def choose_index(weights):
    probabilities = weights / sum(weights)
    cmf = probabilies[0]
    choice = random.random()
    for k in xrange(len(probabilies)):
        if choice <= cmf:
            return k
        else:
            cmf += probabilies[k+1]
ArturJ
quelle
1
Damit sind einige Dinge falsch. Oberflächlich gesehen gibt es einige getippte Variablennamen, und es gibt keine Gründe dafür, dies beispielsweise zu verwenden np.random.choice. Interessanterweise gibt es jedoch einen Fehlermodus, bei dem eine Ausnahme ausgelöst wird. Dies probabilities = weights / sum(weights)garantiert nicht, dass probabilitiessich 1 ergibt . zum Beispiel, wenn weightsist [1,1,1,1,1,1,1]dann probabilitiesnur zu ,9999999999999998 Summe kleiner als der größtmögliche Rückgabewert random.random(die ,9999999999999999 ist). Dann choice <= cmfist man nie zufrieden.
Mark Amery
2

Wenn Ihre Liste der gewichteten Auswahlmöglichkeiten relativ statisch ist und Sie häufige Stichproben wünschen, können Sie einen O (N) -Vorverarbeitungsschritt ausführen und dann die Auswahl in O (1) mithilfe der Funktionen in dieser verwandten Antwort durchführen .

# run only when `choices` changes.
preprocessed_data = prep(weight for _,weight in choices)

# O(1) selection
value = choices[sample(preprocessed_data)][0]
AShelly
quelle
1

Ich habe mir den spitzen anderen Thread angesehen und mir diese Variation in meinem Codierungsstil ausgedacht. Dies gibt den Index der Wahl zum Zweck der Zählung zurück, aber es ist einfach, die Zeichenfolge 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)
    # return index
    return bisect.bisect(cumulative, (r,))
    # return item string
    #return choices[bisect.bisect(cumulative, (r,))][0]

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

tally = [0 for item in choices]

n = 100000
# tally up n weighted choices
for i in range(n):
    tally[weighted_choice(choices)] += 1

print([t/sum(tally)*100 for t in tally])
Tony Veijalainen
quelle
1

Dies hängt davon ab, wie oft Sie die Verteilung testen möchten.

Angenommen, Sie möchten die Verteilung K-mal abtasten. Dann ist die Zeitkomplexität, die np.random.choice()jedes Mal verwendet wird, O(K(n + log(n)))wann ndie Anzahl der Elemente in der Verteilung ist.

In meinem Fall musste ich dieselbe Verteilung mehrmals in der Größenordnung von 10 ^ 3 abtasten, wobei n in der Größenordnung von 10 ^ 6 liegt. Ich habe den folgenden Code verwendet, der die kumulative Verteilung vorberechnet und abtastet O(log(n)). Die Gesamtzeitkomplexität beträgt O(n+K*log(n)).

import numpy as np

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

# Create dummy distribution
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')
    sampled_element = a[idx]
Uppinder Chugh
quelle
0

Eine allgemeine Lösung:

import random
def weighted_choice(choices, weights):
    total = sum(weights)
    treshold = random.uniform(0, total)
    for k, weight in enumerate(weights):
        total -= weight
        if total < treshold:
            return choices[k]
Kennzeichen
quelle
0

Hier ist eine andere Version von weighted_choice, die numpy verwendet. Übergeben Sie den Gewichtungsvektor und es wird ein Array von Nullen zurückgegeben, das eine 1 enthält, die angibt, welcher Behälter ausgewählt wurde. Der Code führt standardmäßig nur eine einzelne Ziehung durch. Sie können jedoch die Anzahl der auszuführenden Ziehungen übergeben, und die Anzahl pro gezogenem Behälter wird zurückgegeben.

Wenn der Gewichtungsvektor nicht 1 ergibt, wird er so normalisiert, dass dies der Fall ist.

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])
murphsp1
quelle
0

Eine andere Möglichkeit, dies zu tun, vorausgesetzt, wir haben Gewichte am gleichen Index wie die Elemente im Elementarray.

import numpy as np
weights = [0.1, 0.3, 0.5] #weights for the item at index 0,1,2
# sum of weights should be <=1, you can also divide each weight by sum of all weights to standardise it to <=1 constraint.
trials = 1 #number of trials
num_item = 1 #number of items that can be picked in each trial
selected_item_arr = np.random.multinomial(num_item, weights, trials)
# gives number of times an item was selected at a particular index
# this assumes selection with replacement
# one possible output
# selected_item_arr
# array([[0, 0, 1]])
# say if trials = 5, the the possible output could be 
# selected_item_arr
# array([[1, 0, 0],
#   [0, 0, 1],
#   [0, 0, 1],
#   [0, 1, 0],
#   [0, 0, 1]])

Nehmen wir nun an, wir müssen 3 Elemente in einem Versuch ausprobieren. Sie können davon ausgehen, dass drei Kugeln R, G, B in großer Menge im Verhältnis ihrer Gewichte vorhanden sind, die durch die Gewichtsanordnung angegeben werden. Folgendes könnte möglich sein:

num_item = 3
trials = 1
selected_item_arr = np.random.multinomial(num_item, weights, trials)
# selected_item_arr can give output like :
# array([[1, 0, 2]])

Sie können sich auch vorstellen, wie viele Elemente als Anzahl von Binomial- / Multinomialversuchen innerhalb eines Satzes ausgewählt werden sollen. Das obige Beispiel kann also immer noch als funktionieren

num_binomial_trial = 5
weights = [0.1,0.9] #say an unfair coin weights for H/T
num_experiment_set = 1
selected_item_arr = np.random.multinomial(num_binomial_trial, weights, num_experiment_set)
# possible output
# selected_item_arr
# array([[1, 4]])
# i.e H came 1 time and T came 4 times in 5 binomial trials. And one set contains 5 binomial trails.
Nsquare
quelle
0

Es gibt einen Vortrag von Sebastien Thurn im kostenlosen Udacity-Kurs AI for Robotics. Grundsätzlich erstellt er mit dem Mod-Operator ein kreisförmiges Array der indizierten Gewichte %, setzt eine Variable Beta auf 0, wählt zufällig einen Index für Schleifen durch N, wobei N die Anzahl der Indizes ist, und erhöht in der for-Schleife zunächst Beta durch die Formel:

Beta = Beta + einheitliche Stichprobe aus {0 ... 2 * Weight_max}

und dann in der for-Schleife verschachtelt, eine while-Schleife wie folgt:

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

select p[index]

Fahren Sie dann mit dem nächsten Index fort, der basierend auf den Wahrscheinlichkeiten (oder der normalisierten Wahrscheinlichkeit in dem im Kurs dargestellten Fall) erneut abgetastet werden soll.

Der Link zur Vorlesung: https://classroom.udacity.com/courses/cs373/lessons/48704330/concepts/487480820923

Ich bin mit meinem Schulkonto bei Udacity angemeldet. Wenn der Link nicht funktioniert, ist es Lektion 8, Video Nummer 21 der Künstlichen Intelligenz für Robotik, in der er Vorlesungen über Partikelfilter hält.

mLstudent33
quelle
0

Wenn Sie Python 3 haben und Angst haben, numpyeigene Loops zu installieren oder zu schreiben, können Sie Folgendes tun:

import itertools, bisect, random

def weighted_choice(choices):
   weights = list(zip(*choices))[1]
   return choices[bisect.bisect(list(itertools.accumulate(weights)),
                                random.uniform(0, sum(weights)))][0]

Weil Sie alles aus einer Tüte mit Sanitäradaptern bauen können ! Obwohl ... ich muss zugeben, dass Neds Antwort, obwohl sie etwas länger ist, leichter zu verstehen ist.

personal_cloud
quelle
-1

Eine Möglichkeit besteht darin, die Summe aller Gewichte nach dem Zufallsprinzip zu sortieren und dann die Werte als Grenzpunkte für jede Variable zu verwenden. Hier ist eine grobe Implementierung als Generator.

def rand_weighted(weights):
    """
    Generator which uses the weights to generate a
    weighted random values
    """
    sum_weights = sum(weights.values())
    cum_weights = {}
    current_weight = 0
    for key, value in sorted(weights.iteritems()):
        current_weight += value
        cum_weights[key] = current_weight
    while True:
        sel = int(random.uniform(0, 1) * sum_weights)
        for key, value in sorted(cum_weights.iteritems()):
            if sel < value:
                break
        yield key
Staude
quelle
-1

Mit numpy

def choice(items, weights):
    return items[np.argmin((np.cumsum(weights) / sum(weights)) < np.random.rand())]
blue_note
quelle
NumPy hat bereits np.random.choice, wie in der akzeptierten Antwort erwähnt, die seit 2014 hier ist. Was bringt es , wenn Sie Ihre eigenen rollen?
Mark Amery
-1

Ich musste so etwas wirklich schnell und einfach machen, von der Suche nach Ideen habe ich endlich diese Vorlage erstellt. Die Idee ist, die gewichteten Werte in Form eines JSON von der API zu erhalten, was hier durch das Diktat simuliert wird.

Übersetzen Sie es dann in eine Liste, in der sich jeder Wert proportional zu seinem Gewicht wiederholt, und verwenden Sie einfach random.choice, um einen Wert aus der Liste auszuwählen.

Ich habe es mit 10, 100 und 1000 Iterationen versucht. Die Verteilung scheint ziemlich solide zu sein.

def weighted_choice(weighted_dict):
    """Input example: dict(apples=60, oranges=30, pineapples=10)"""
    weight_list = []
    for key in weighted_dict.keys():
        weight_list += [key] * weighted_dict[key]
    return random.choice(weight_list)
Stas Baskin
quelle
-1

Ich habe die Syntax von keinem von denen geliebt. Ich wollte wirklich nur angeben, was die Gegenstände waren und wie sie jeweils gewichtet waren. Mir ist klar, dass ich es hätte verwenden können, random.choicesaber stattdessen habe ich schnell die folgende Klasse geschrieben.

import random, string
from numpy import cumsum

class randomChoiceWithProportions:
    '''
    Accepts a dictionary of choices as keys and weights as values. Example if you want a unfair dice:


    choiceWeightDic = {"1":0.16666666666666666, "2": 0.16666666666666666, "3": 0.16666666666666666
    , "4": 0.16666666666666666, "5": .06666666666666666, "6": 0.26666666666666666}
    dice = randomChoiceWithProportions(choiceWeightDic)

    samples = []
    for i in range(100000):
        samples.append(dice.sample())

    # Should be close to .26666
    samples.count("6")/len(samples)

    # Should be close to .16666
    samples.count("1")/len(samples)
    '''
    def __init__(self, choiceWeightDic):
        self.choiceWeightDic = choiceWeightDic
        weightSum = sum(self.choiceWeightDic.values())
        assert weightSum == 1, 'Weights sum to ' + str(weightSum) + ', not 1.'
        self.valWeightDict = self._compute_valWeights()

    def _compute_valWeights(self):
        valWeights = list(cumsum(list(self.choiceWeightDic.values())))
        valWeightDict = dict(zip(list(self.choiceWeightDic.keys()), valWeights))
        return valWeightDict

    def sample(self):
        num = random.uniform(0,1)
        for key, val in self.valWeightDict.items():
            if val >= num:
                return key
ML_Dev
quelle
-1

Stellen Sie random.choice () eine vorgewichtete Liste zur Verfügung:

Lösung & Test:

import random

options = ['a', 'b', 'c', 'd']
weights = [1, 2, 5, 2]

weighted_options = [[opt]*wgt for opt, wgt in zip(options, weights)]
weighted_options = [opt for sublist in weighted_options for opt in sublist]
print(weighted_options)

# test

counts = {c: 0 for c in options}
for x in range(10000):
    counts[random.choice(weighted_options)] += 1

for opt, wgt in zip(options, weights):
    wgt_r = counts[opt] / 10000 * sum(weights)
    print(opt, counts[opt], wgt, wgt_r)

Ausgabe:

['a', 'b', 'b', 'c', 'c', 'c', 'c', 'c', 'd', 'd']
a 1025 1 1.025
b 1948 2 1.948
c 5019 5 5.019
d 2008 2 2.008
DocOc
quelle