random.choice의 가중치 버전

random.choice의 가중치 버전

---

random.choice의 가중치 버전을 작성해야했습니다 (목록의 각 요소는 선택 될 확률이 다릅니다). 이것이 내가 생각해 낸 것입니다.

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

이 기능은 나에게 지나치게 복잡해 보이고 추악합니다. 나는 여기의 모든 사람들이 그것을 개선하거나 다른 방법으로 제안 할 수 있기를 바랍니다. 효율성은 코드 청결도와 가독성만큼 중요하지 않습니다.

---

버전 1.7.0부터 NumPy에는 choice확률 분포를 지원 하는 기능이 있습니다.

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

참고 probability_distribution동일한 순서 시퀀스이다 list_of_candidates. 또한 키워드 replace=False를 사용하여 그려진 항목이 교체되지 않도록 동작을 변경할 수 있습니다 .

---

이후 Python3.6 방법이있다 choices에서 random모듈.

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

또한 사람들은 numpy.random.choice가중치를 지원 하지만 2d 배열을 지원하지 않는 등의 방법을 언급 했습니다.

따라서 기본적으로 3.6.x Python 이 있으면 기본적으로 원하는 것을 얻을 수 있습니다 ( 업데이트 참조 ) .random.choices

업데이트 : @roganjosh가 친절하게 언급했듯이 docsrandom.choices 에서 언급했듯이 대체없이 값을 반환 할 수 없습니다 .

대체로k 모집단에서 선택한 크기가 지정된 요소 목록을 반환합니다 .

그리고 @ 로난-paixão 의 화려한 응답 상태 numpy.choice가 replace인수를, 그 컨트롤 그런 행동.

---

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. 가중치를 누적 분포로 배열합니다.
2. random.random () 을 사용 하여 임의의 float을 선택하십시오 0.0 <= x < total.
3. http://docs.python.org/dev/library/bisect.html#other-examples 의 예제에 표시된대로 bisect.bisect 를 사용하여 배포를 검색 하십시오 .

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'

하나 이상의 선택을해야하는 경우, 이것을 두 가지 기능으로 나누십시오. 하나는 누적 가중치를 만들고 다른 하나는 임의의 점으로 이등분합니다.

---

numpy를 사용하지 않는다면 numpy.random.choice 를 사용할 수 있습니다 .

예를 들면 다음과 같습니다.

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

얼마나 많은 선택을해야하는지 알고 있다면 다음과 같이 반복하지 않아도됩니다.

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

---

조잡하지만 충분할 수 있습니다.

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

인쇄물:

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

모든 가중치가 정수라고 가정합니다. 그들은 100을 더할 필요가 없으며 테스트 결과를 더 쉽게 해석하기 위해 그렇게했습니다. 가중치가 부동 소수점 숫자 인 경우 모든 가중치가 1보다 크거나 같을 때까지 반복적으로 10을 곱합니다.

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)

---

목록 대신 가중 사전이 있다면 이것을 쓸 수 있습니다.

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

[k for k in items for dummy in range(items[k])]이 목록 을 생성합니다['a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'c', 'b', 'b', 'b', 'b', 'b']

---

파이썬으로 v3.6, random.choices반환하는 데 사용할 수있는 list옵션 가중치 주어진 인구에서 지정된 크기의 요소를.

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

• 인구 : list고유 한 관측치 포함. (비어 있으면 IndexError)

• 가중치 : 선택에 필요한보다 정확한 상대 가중치.

• cum_weights : 선택에 필요한 누적 가중치입니다.

• k : 출력 할 크기 ( len) list. (기본 len()=1)

---

몇 가지주의 사항 :

1) 추첨 된 품목을 나중에 교체 할 수 있도록 가중 샘플링을 교체와 함께 사용합니다. 가중치 시퀀스 자체의 값 자체는 중요하지 않지만 상대적 비율은 중요합니다.

np.random.choice확률을 가중치로만 취할 수 있고 개별 확률을 1 기준까지 합산해야하는 것과는 달리 , 여기에는 그러한 규정이 없습니다. 숫자 유형 ( type int/float/fraction제외 Decimal) 에 속하는 한 여전히 수행됩니다.

>>> 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) 가중치 또는 cum_weights 를 지정 하지 않으면 동일한 확률로 선택됩니다. 경우 무게 시퀀스가 공급되고,이 같은 길이이어야 인구 순서.

가중치 와 cum_weights를 모두 지정 하면 a가 발생합니다 TypeError.

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

3) cum_weights 는 일반적으로 itertools.accumulate그러한 상황에서 실제로 유용한 기능 의 결과입니다 .

_{링크 된 문서에서 :}

내부적으로 상대 가중치는 선택하기 전에 누적 가중치로 변환되므로 누적 가중치를 제공하면 작업이 줄어 듭니다.

따라서 우리의 사례를 제공 weights=[12, 12, 4]하거나 cum_weights=[12, 24, 28]우리의 사례에 대해 동일한 결과를 산출하고 후자는 더 빠르고 효율적으로 보입니다.

---

다음은 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)]

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

---

선택의 합계는 1이 필요하지만 이것은 어쨌든 작동합니다.

def weightedChoice(choices):
    # Safety check, you can remove it
    for c,w in choices:
        assert w >= 0


    tmp = random.uniform(0, sum(c for c,w in choices))
    for choice,weight in choices:
        if tmp < weight:
            return choice
        else:
            tmp -= weight
     raise ValueError('Negative values in input')

---

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

---

유용한 정보를 제공하기에는 너무 늦었을지 모르지만 다음은 간단하고 짧으며 매우 효율적인 스 니펫입니다.

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]

확률을 정렬하거나 cmf로 벡터를 만들 필요가 없으며 선택을 찾으면 종료됩니다. 메모리 : O (1), 시간 : O (N), 평균 실행 시간 ~ N / 2.

가중치가있는 경우 한 줄만 추가하면됩니다.

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]

---

가중 선택 목록이 상대적으로 정적이고 샘플링을 자주 원할 경우 O (N) 전처리 단계를 한 번 수행 한 다음 이 관련 답변 의 함수를 사용하여 O (1)에서 선택을 수행 할 수 있습니다.

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

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

---

나는 지적 된 다른 스레드를 보았고 코딩 스타일 에서이 변형을 생각해 냈습니다. 이것은 키를 높이기 위해 선택한 인덱스를 반환하지만 문자열을 반환하는 것은 간단합니다 (댓글 대체 옵션).

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

---

일반적인 해결책 :

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]

---

다음은 numpy를 사용하는 다른 버전의 weighted_choice입니다. 가중치 벡터를 전달하면 선택한 빈을 나타내는 1을 포함하는 0의 배열을 반환합니다. 코드는 기본적으로 하나의 그리기를 수행하지만 그리기 수를 전달할 수 있으며 빈당 카운트가 반환됩니다.

가중치 벡터의 합이 1이 아닌 경우 정규화되어 정규화됩니다.

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

---

분포를 샘플링하려는 횟수에 따라 다릅니다.

분포 K 배를 샘플링한다고 가정합니다. 그런 다음 np.random.choice()각 시간을 사용하는 시간 복잡성 은 O(K(n + log(n)))언제 n분포의 항목 수입니까?

제 경우에는 10 ^ 3 차수의 동일한 분포를 여러 번 샘플링해야했습니다. 여기서 n은 10 ^ 6 차수입니다. 아래 코드를 사용하여 누적 분포를 미리 계산하고로 샘플링합니다 O(log(n)). 전반적인 시간 복잡도는 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]

---

한 가지 방법은 모든 가중치의 총계를 랜덤 화 한 다음 각 변수의 한계점으로 값을 사용하는 것입니다. 다음은 발전기로서의 조잡한 구현입니다.

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

---

numpy 사용

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

---

I needed to do something like this really fast really simple, from searching for ideas i finally built this template. The idea is receive the weighted values in a form of a json from the api, which here is simulated by the dict.

Then translate it into a list in which each value repeats proportionally to it's weight, and just use random.choice to select a value from the list.

I tried it running with 10, 100 and 1000 iterations. The distribution seems pretty solid.

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)

---

I didn't love the syntax of any of those. I really wanted to just specify what the items were and what the weighting of each was. I realize I could have used random.choices but instead I quickly wrote the class below.

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

---

Provide random.choice() with a pre-weighted list:

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

Output:

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

참고URL : https://stackoverflow.com/questions/3679694/a-weighted-version-of-random-choice