Ważona wersja random.choice

Musiałem napisać ważoną wersję random.choice (każdy element na liście ma inne prawdopodobieństwo wyboru). Oto co wymyśliłem:

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

Ta funkcja wydaje mi się zbyt skomplikowana i brzydka. Mam nadzieję, że wszyscy tutaj będą mogli zaproponować kilka ulepszeń lub alternatywne sposoby na zrobienie tego. Wydajność nie jest dla mnie tak ważna, jak czystość i czytelność kodu.

Od wersji 1.7.0 NumPy ma choicefunkcję, która obsługuje rozkłady prawdopodobieństwa.

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

Zauważ, że probability_distributionjest to sekwencja w tej samej kolejności co list_of_candidates. Możesz także użyć słowa kluczowego, replace=Falseaby zmienić zachowanie, aby narysowane elementy nie zostały zastąpione.

Od wersji Python 3.6 istnieje metoda choicesz randommodułu.

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

Pamiętaj, że random.choicesbędzie próbkować z zamiennikiem , według dokumentów :

Zwraca kuporządkowaną listę elementów wybranych z populacji wraz z zamiennikiem.

Jeśli musisz próbkować bez zamiany, wówczas jako genialną odpowiedź @ ronan-paixão można użyć numpy.choice, którego replaceargument kontroluje takie zachowanie.

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. Ułóż wagi w skumulowanym rozkładzie.
2. Użyj random.random (), aby wybrać losową liczbę zmiennoprzecinkową 0.0 <= x < total.
3. Przeszukaj dystrybucję za pomocą bisect.bisect, jak pokazano w przykładzie na stronie 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'

Jeśli musisz dokonać więcej niż jednego wyboru, podziel to na dwie funkcje, jedną do zbudowania skumulowanych wag, a drugą do podzielenia na losowe punkty.

Jeśli nie masz nic przeciwko użyciu numpy, możesz użyć numpy.random.choice .

Na przykład:

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

Jeśli wiesz, ile wyborów musisz zrobić z góry, możesz to zrobić bez takiej pętli:

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

Surowy, ale może być wystarczający:

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

Czy to działa?

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

Wydruki:

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

Zakłada, że ​​wszystkie wagi są liczbami całkowitymi. Nie muszą sumować się do 100, właśnie to zrobiłem, aby wyniki testu były łatwiejsze do interpretacji. (Jeśli wagi są liczbami zmiennoprzecinkowymi, należy pomnożyć je wszystkie przez 10 razy, aż wszystkie wagi> = 1.)

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)

Jeśli masz ważoną słownik zamiast listy, możesz to napisać

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

Zauważ, że [k for k in items for dummy in range(items[k])]tworzy tę listę['a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'c', 'b', 'b', 'b', 'b', 'b']

Począwszy od Pythona v3.6, random.choicesmożna go użyć do zwrócenia listelementów o określonym rozmiarze z danej populacji z opcjonalnymi wagami.

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

• populacja : listzawierająca unikalne obserwacje. (Jeśli pusty, podnosi IndexError)

• wagi : Aby dokonać selekcji, wymagane są bardziej dokładne wagi względne.

• cum_weights : skumulowane wagi wymagane do dokonania selekcji.

• k : rozmiar ( len), listktóry ma być wyprowadzony. (Domyślnie len()=1)

Kilka ostrzeżeń:

1) Wykorzystuje ważenie próbkowania z wymianą, aby narysowane elementy zostały później zastąpione. Wartości w sekwencji wag same w sobie nie mają znaczenia, ale ich względny stosunek ma znaczenie.

W przeciwieństwie do tego, np.random.choicektóry może przyjmować jedynie prawdopodobieństwa jako wagi, a także który musi zapewniać sumowanie indywidualnych prawdopodobieństw do 1 kryteriów, nie ma tutaj takich przepisów. Tak długo, jak należą do typów numerycznych ( int/float/fractionoprócz Decimaltypu), będą one nadal działać.

>>> 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) Jeśli nie podano ani wag, ani cum_weights , wyborów dokonuje się z jednakowym prawdopodobieństwem. Jeśli podano sekwencję wag , musi ona być tej samej długości co sekwencja populacji .

Określenie zarówno wag, jak i cum_weights podnosi a TypeError.

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

3) Cum_wagi są zazwyczaj wynikiem itertools.accumulatefunkcji, które są naprawdę przydatne w takich sytuacjach.

_{Z powiązanej dokumentacji:}

Wewnętrznie wagi względne są konwertowane na wagi skumulowane przed dokonaniem selekcji, więc podanie skumulowanych wag oszczędza pracę.

Zatem dostarczanie weights=[12, 12, 4]lub cum_weights=[12, 24, 28]w naszym przemyślanym przypadku daje ten sam rezultat, a ten drugi wydaje się być szybszy / bardziej wydajny.

Oto wersja, która jest zawarta w standardowej bibliotece Python 3.6:

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

Źródło: https://hg.python.org/cpython/file/tip/Lib/random.py#l340

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

Prawdopodobnie spóźniłem się, by przekazać coś przydatnego, ale oto prosty, krótki i bardzo skuteczny fragment:

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]

Nie musisz sortować swoich prawdopodobieństw ani tworzyć wektora za pomocą cmf, i kończy się, gdy znajdzie swój wybór. Pamięć: O (1), czas: O (N), ze średnim czasem pracy ~ N / 2.

Jeśli masz wagi, po prostu dodaj jedną linię:

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]

Jeśli twoja lista ważonych wyborów jest względnie statyczna i chcesz często próbkować, możesz wykonać jeden etap wstępnego przetwarzania O (N), a następnie dokonać wyboru w O (1), korzystając z funkcji w tej pokrewnej odpowiedzi .

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

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

Spojrzałem na wskazany drugi wątek i wymyśliłem tę odmianę w moim stylu kodowania, to zwraca indeks wyboru do celów liczenia, ale łatwo jest zwrócić ciąg (skomentowana opcja powrotu):

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

To zależy od tego, ile razy chcesz próbkować rozkład.

Załóżmy, że chcesz próbkować rozkład K razy. Następnie złożonością czasową używaną za np.random.choice()każdym razem jest, O(K(n + log(n)))kiedy njest liczba elementów w rozkładzie.

W moim przypadku musiałem próbować ten sam rozkład wiele razy rzędu 10 ^ 3, gdzie n jest rzędu 10 ^ 6. Użyłem poniższego kodu, który wstępnie oblicza skumulowany rozkład i próbkuje go O(log(n)). Ogólna złożoność czasu wynosi 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]

Jeśli masz Python 3 i boisz się instalować numpylub pisać własne pętle, możesz:

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]

Ponieważ możesz zbudować wszystko z torby adapterów hydraulicznych! Chociaż ... Muszę przyznać, że odpowiedź Neda, choć nieco dłuższa, jest łatwiejsza do zrozumienia.

Ogólne rozwiązanie:

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]

Oto kolejna wersja weighted_choice, która używa numpy. Przekaż wektor wag, a zwróci tablicę zer zawierającą 1 wskazującą, który bin został wybrany. Kod domyślnie wykonuje tylko jedno losowanie, ale możesz przekazać liczbę losowań, które mają zostać wykonane, a liczba losowanych bin zostanie zwrócona.

Jeśli wektor wag nie sumuje się do 1, zostanie znormalizowany, a więc tak.

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

Innym sposobem jest założenie, że mamy wagi o tym samym indeksie co elementy w tablicy elementów.

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

Załóżmy teraz, że musimy wypróbować 3 elementy w 1 próbie. Można założyć, że występują trzy kule R, G, B w dużych ilościach w stosunku ich ciężarów podanych w układzie wagowym, może być możliwy następujący wynik:

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

możesz również pomyśleć o liczbie elementów do wyboru jako liczbie prób dwumianowych / wielomianowych w zestawie. Tak więc powyższy przykład może nadal działać jako

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.

Wykład na ten temat przeprowadził Sebastien Thurn w bezpłatnym kursie Udacity AI for Robotics. Zasadniczo tworzy tablicę kołową indeksowanych wag za pomocą operatora mod %, ustawia zmienną beta na 0, losowo wybiera indeks, dla pętli przez N, gdzie N jest liczbą indeksów, aw pętli for najpierw zwiększa beta według wzoru:

beta = beta + jednolita próbka z {0 ... 2 * Weight_max}

a następnie zagnieżdżone w pętli for, pętla while na poniżej:

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

select p[index]

Następnie przejdź do następnego indeksu do ponownego próbkowania w oparciu o prawdopodobieństwa (lub znormalizowane prawdopodobieństwo w przypadku przedstawionym w trakcie).

Link do wykładu: https://classroom.udacity.com/courses/cs373/lessons/48704330/concepts/487480820923

Jestem zalogowany do konta Udacity na moim szkolnym koncie, więc jeśli link nie działa, to lekcja 8, numer wideo 21 sztucznej inteligencji dla robotyki, gdzie wykłada filtry cząstek stałych.

Jednym ze sposobów jest randomizacja sumy wszystkich wag, a następnie wykorzystanie wartości jako punktów granicznych dla każdej zmiennej. Oto prymitywna implementacja jako 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

Korzystanie z numpy

def choice(items, weights):
    return items[np.argmin((np.cumsum(weights) / sum(weights)) < np.random.rand())]

Musiałem zrobić coś takiego bardzo szybko, naprawdę prosto, od szukania pomysłów w końcu zbudowałem ten szablon. Chodzi o to, aby otrzymać ważone wartości w postaci json z interfejsu API, który tutaj jest symulowany przez dyktando.

Następnie przetłumacz go na listę, w której każda wartość powtarza się proporcjonalnie do swojej wagi, i po prostu użyj random.choice, aby wybrać wartość z listy.

Próbowałem go uruchomić z 10, 100 i 1000 iteracjami. Rozkład wydaje się dość solidny.

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)

Nie podobała mi się składnia żadnego z nich. Naprawdę chciałem tylko sprecyzować, jakie były przedmioty i jaka była waga każdego z nich. Zdaję sobie sprawę, że mogłem skorzystać, random.choicesale zamiast tego szybko napisałem klasę poniżej.

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

Podaj random.choice () z wstępnie ważoną listą:

Rozwiązanie i 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)

Wynik:

['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