가중치 있는 랜덤 버전.선택하다

가중치 있는 랜덤 버전.선택하다

나는 무작위의 가중치를 부여한 버전을 써야 했다.선택(목록의 각 요소는 선택될 확률이 다름)내가 생각해 낸 것은 다음과 같다.

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에는 확률 분포를 지원하는 함수가 있다.

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그려진 항목이 교체되지 않도록 동작을 변경한다.

Python 3.6부터 모듈 방법이 있다.

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

:random.choices문서에 따라 교체 시료 채취:

ak대체 모집단에서 선택한 요소의 크기 목록.

답변의 완전성을 위한 참고 사항:

유한 모집단에서 추출한 표본 단위가 그 특성을 기록한 후 다음 단위를 그리기 전에 표본 단위가 해당 모집단으로 반환되는 경우, 표본 추출은 "대체와 함께"라고 한다.그것은 기본적으로 각 요소가 한 번 이상 선택될 수 있다는 것을 의미한다.

만약 당신이 교체하지 않고 샘플을 채취해야 한다면, @ronan-paixang의 훌륭한 답변이 말한 바와 같이, 당신은 누구의 것을 사용할 수 있다.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()을 사용하여 랜덤 플로트를 선택하십시오.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을 사용할 수 있다.선택 사항

예를 들면 다음과 같다.

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)

Python 은v3.6, 를 반환하는 데 사용할 수 있음list선택적 가중치를 갖는 지정된 모집단에서 지정된 크기의 요소.

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

• 모집단:list고유 관측치를 포함함. (빈 경우 상승IndexError)

• 가중치 : 선택하는데 필요한 보다 정밀하게 상대적인 가중치.

• cum_colume : 선택에 필요한 누적 가중치.

• k : 크기().len의)list출력한다(기본값).len()=1)

---

몇 가지 주의 사항:

1) 도안된 품목을 나중에 교체할 수 있도록 대체 시료와 함께 가중치를 부여한다.가중치 순서의 값 자체는 중요하지 않지만 상대 비율은 중요하다.

와는 달리np.random.choice가중치로서만 확률을 취할 수 있고 또한 최대 1개의 기준까지 개별 확률을 합산해야 하는, 여기에는 그러한 규정이 없다.( (子形 한(자子形)이다.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를 모두 지정하면TypeError.

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

3) cum_properties는 일반적으로 그러한 상황에서 정말로 편리한 기능의 결과물이다.

_{연결된 문서에서:}

내부적으로 상대 가중치를 선택하기 전에 누적 가중치로 변환하므로 누적 가중치를 공급하면 작업이 절약된다.

그럼, 둘 다 공급하거나weights=[12, 12, 4]또는cum_weights=[12, 24, 28]우리의 조작된 케이스는 동일한 결과를 생산하고 후자가 더 빠르고 효율적인 것 같다.

조잡하지만 충분할 수 있음:

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

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

가중 선택을 위한 매우 기본적이고 쉬운 접근방식은 다음과 같다.

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

유용한 것을 기부하기에는 너무 늦었지만, 여기 간단하고, 짧고, 매우 효율적인 작은 조각이 있다.

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]

Python 3이 numpy루프를 직접 쓰거나, 다음 작업을 할 수 있다.

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]

배관 어댑터 봉지로 무엇이든 만들 수 있기 때문이다!하지만...네드의 대답이 조금 더 길긴 하지만 이해하기가 더 쉽다는 것을 인정해야겠다.

뾰족한 다른 나사산을 찾아보니 코딩 스타일의 이 변형이 떠올랐는데, 이것은 집계를 위한 선택 지수를 반환하지만, 문자열 반환은 간단하다(코멘트 반환 대안):

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

여기에 numpy를 사용하는 가중_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 시간을 표본으로 추출한다고 가정합시다.그 다다이, 시스 using 한 시간 복잡도는 다음과 같다.np.random.choice()그때마다O(K(n + log(n)))할 때n분포의 항목 수입니다.

나의 경우 n이 10^6인 10^3의 동일한 분포를 여러 번 표본으로 추출해야 했다.나는 아래 코드를 사용했는데, 이것은 누적 분포를 미리 계산하여 샘플로 추출한 것이다.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]

로보틱스 무료 Udacity 과정 AI에서 세바스티안 Thurn의 강의가 있다.기본적으로 그는 모드 연산자를 사용하여 인덱스된 가중치의 원형 배열을 만든다.%, 변수 베타 값을 0으로 설정하고, 임의로 인덱스를 선택하며, 여기서 N은 인덱스 수이고, for 루프에서는 먼저 공식에 의해 베타 수를 증가시킨다.

베타 = 베타 + {0의 균일한 샘플...2* 중량_max}

그런 다음 아래 루프를 위해 루프에 내포한다.

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

select p[index]

그런 다음 다음 다음 지수로 이동하여 확률(또는 과정에 제시된 사례에서 정규화된 확률)을 기반으로 다시 표본을 추출하십시오.

Udacity find 8과, 그가 입자 필터에 대해 강의하고 있는 로봇공학 인공지능의 21번 비디오.

일반적인 해결책:

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]

이렇게 하는 또 다른 방법은, 요소 배열의 요소와 동일한 색인에 가중치가 있다고 가정하는 것이다.

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

이제, 우리는 한 번의 시험으로 3개의 아이템을 샘플링해야 한다고 가정해보자.중량 배열에 의해 주어진 가중치의 비율에 많은 양의 R,G,B가 있다고 가정할 수 있으며, 다음과 같은 결과가 있을 수 있다.

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

또한 세트 내에서 이항/다항 시행 횟수로 선택할 항목 수를 생각할 수 있다.따라서 위의 예는 여전히 다음과 같이 작동할 수 있다.

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.

한 가지 방법은 모든 가중치의 합계를 랜덤화한 다음 값을 각 변수의 한계점으로 사용하는 것이다.여기에 발전기로서의 조잡한 실행이 있다.

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

나는 내가 마침내 이 템플릿을 만든 아이디어를 찾는 것에서부터 아주 간단한 것과 같은 것을 정말 빨리 할 필요가 있었다.아이디어는 api로부터 json의 형태로 가중치를 부여받는데, 여기서 받아쓰기에 의해 시뮬레이션된다.

그런 다음 각 값이 무게에 비례하여 반복되는 리스트로 번역하고 무작위로 사용한다.목록에서 값을 선택하기 위한 선택

10번, 100번, 1000번 반복해서 실행해 보았다.분포가 꽤 확실한 것 같다.

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)

나는 그것들 중 어떤 구문도 좋아하지 않았다.나는 그저 그 물건들이 무엇이고 각각의 무게는 무엇인지를 분명히 하고 싶었다.내가 할 수 있었다는 걸 깨달았어random.choices대신 나는 아래 수업을 빨리 썼다.

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

임의로 제공하다.사전 예약 목록과 함께 선택:

솔루션 & 테스트:

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)

출력:

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

Numpy 사용

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

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