Ważona wersja random.wybór

Od Pythona 3.6 istnieje metoda choices z random Moduł.

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

Zauważ, że random.choices będzie próbkować z zamiennikiem , zgodnie z docs :

Zwraca k listę elementów wybranych z populacji z wymianą.

Uwaga dla kompletności odpowiedzi:

Gdy jednostka pobierania próbek jest pobierana ze skończonej populacji i jest zwracana do tej populacji, po jej charakterystyce(cechach) były nagrane, przed pobraniem kolejnej jednostki, pobieranie próbek mówi się, że "z wymiana". Zasadniczo oznacza, że każdy element może być wybrany więcej niż raz.

Jeśli potrzebujesz próbki bez wymiany, to jak stwierdza @ronan-paixão genialna odpowiedź , możesz użyć numpy.choice, którego argument replace 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łóż ciężarki w Dystrybucja skumulowana.
2. Użyj losowo.random () {[7] } to pick a random float 0.0 <= x < total.
3. Search the Dystrybucja za pomocą bisect.bisect as pokazane w przykładzie na 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 budowania masy kumulacyjnej, a drugą do przebijania do losowego punktu.

Jeśli nie masz nic przeciwko użyciu numpy, możesz użyć numpy.przypadkowe.wybór .

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 selekcji musisz zrobić z góry, możesz to zrobić bez pętli takiej jak Ta:

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

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

Druki:

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

Zakłada, że wszystkie wagi są liczbami całkowitymi. Nie muszą dodawać do 100, zrobiłem to, aby ułatwić interpretację wyników testu. (Jeśli wagi są liczbami zmiennoprzecinkowymi, pomnóż je wszystkie przez 10 wielokrotnie, 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 słownik ważony zamiast listy, możesz napisać to

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

Od Pythona v3.6, random.choices może być użyty do zwrócenia list elementów o określonej wielkości z danej populacji z opcjonalnymi wagami.

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

• ludność : list zawierające unikalne obserwacje. (Jeśli jest pusty, podnosi IndexError)

• wagi : dokładniej względne wagi wymagane do dokonania selekcji.

• cum_weights : skumulowane ciężary wymagane do wykonania wybór.

• k : Rozmiar (len) z list do wyprowadzenia. (Domyślnie len()=1)

Kilka Zastrzeżeń:

1) wykorzystuje ważone pobieranie próbek z wymianą, więc pobrane elementy zostaną później zastąpione. Wartości w sekwencji wag same w sobie nie mają znaczenia, ale ich stosunek względny ma znaczenie.

W przeciwieństwie do np.random.choice, które mogą przyjmować tylko prawdopodobieństwa jako wagi, a także które muszą zapewnić sumowanie Indywidualne Prawdopodobieństwo do 1 kryteriów, nie ma takich przepisów tutaj. Tak długo, jak należą do typów liczbowych (int/float/fraction z wyjątkiem typu Decimal), 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 anicum_weights , selekcje są dokonywane z równym prawdopodobieństwem. Jeśli dostarczona jest sekwencja wag , musi ona mieć taką samą długość jak Sekwencja populacji.

Określanie zarówno wag i cum_weights podnosi TypeError.

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

3) cum_weights są zazwyczaj wynikiem itertools.accumulate funkcji, które są naprawdę przydatne w takich sytuacjach.

_{z załączonej dokumentacji:}

Wewnętrznie względne wagi są konwertowane na wagi skumulowane przed dokonaniem wyboru, więc dostarczanie skumulowanych wag oszczędza praca.

Więc albo dostarczając weights=[12, 12, 4] albo cum_weights=[12, 24, 28] dla naszej zmyślonej sprawy daje ten sam wynik, a ten drugi wydaje się być szybszy / bardziej wydajny.

Oto wersja, która jest dołączana do standardowej biblioteki Pythona 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

Bardzo proste i proste podejście do ważonego wyboru jest następujące:

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

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 jestem za późno, aby wnieść coś użytecznego, 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 ma potrzeby sortowania prawdopodobieństwa lub tworzenia wektora z cmf, a kończy się, gdy znajdzie swój wybór. Pamięć: O(1), Czas: O(N), przy średnim czasie pracy ~ N/2.

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

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ęstego próbkowania, możesz wykonać jeden etap wstępnego przetwarzania O (N), A następnie dokonać wyboru W O(1), używając funkcji w tej powiązanej 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 inny wątek i wymyśliłem tę odmianę w moim stylu kodowania, to zwraca wybrany indeks w celu obliczenia, ale łatwo jest zwrócić ciąg (commented return alternative):

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 wypróbować dystrybucję.

Załóżmy, że chcesz wypróbować rozkład K razy. Wtedy złożoność czasowa np.random.choice() za każdym razem wynosi O(K(n + log(n))), Gdy n jest liczbą elementów w dystrybucji.

W moim przypadku, musiałem spróbować tego samego rozkładu 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 pobiera go w O(log(n)). Całkowity czas złożoność jest 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 przypadkiem masz Pythona 3 i boisz się zainstalować numpy lub napisać własne pętle, możesz to zrobić:

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]

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. Przechodzi w wektor wagi i zwróci tablicę 0 zawierającą 1 wskazującą, który bin został wybrany. Kod domyślnie tylko do jednego losowania, ale można przekazać w liczbie losowań, które mają być wykonane i liczniki na kosz losowane zostaną zwrócone.

Jeśli wektor wagi nie będzie sumował się do 1, będzie znormalizowany tak, że tak się stanie.

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

Inny sposób na to, zakładając, że mamy wagi w 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]])

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ż myśleć o liczbie elementów, które mają być wybrane jako liczba dwumianowych / wielomianowych prób w zestawie. Tak więc powyższe 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.

Jest na ten temat wykład Sebastiena Thurna w Darmowym kursie Udacity AI for Robotics. Zasadniczo tworzy okrągłą tablicę indeksowanych wag używając operatora mod %, ustawia zmienną beta na 0, losowo wybiera indeks, pętla for przez N, gdzie N jest liczbą indeksów, a w pętli for pierwsze przyrosty beta według wzoru:

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

A następnie zagnieżdżona w pętli for, pętla while per poniżej:

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

select p[index]

Następnie przejdź do następnego indeksu, aby dokonać ponownej próby na podstawie prawdopodobieństwa (lub znormalizowanego prawdopodobieństwa w przypadku przedstawionym w kursie).

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

Jestem zalogowany do Udacity z mojego szkolnego konta, więc jeśli link nie działa, to jest lekcja 8, wideo numer 21 sztucznej inteligencji dla robotyki, gdzie wykłada na temat filtrów cząstek.

Jednym ze sposobów jest randomizacja na sumie wszystkich wag, a następnie użycie wartości jako punktów granicznych dla każdego var. 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

Using numpy

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

Musiałem zrobić coś takiego naprawdę szybko, naprawdę prosto, od poszukiwania pomysłów w końcu zbudowałem ten szablon. Ideą jest otrzymanie wartości ważonych w postaci json z api, które tutaj jest symulowane przez dict.

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

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 określić, jakie były przedmioty i jaka była waga każdego z nich. Zdaję sobie sprawę, że mogłem użyć random.choices, ale 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 losowo.choice() z wstępnie ważoną listą:

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

Wyjście:

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