Cách Pythonic để chọn các phần tử danh sách có xác suất khác nhau

Question

import random 
pos = ["A", "B", "C"] 
x = random.choice["A", "B", "C"] 

Mã này cho tôi "A", "B" hoặc "C" có xác suất bằng nhau. Có cách nào tốt đẹp để thể hiện nó khi bạn muốn "A" với 30%, "B" với 40% và "C" với xác suất 30%?

Answer 1

Trọng số xác định hàm phân phối xác suất (pdf). số ngẫu nhiên từ bất kỳ pdf như vậy có thể được tạo ra bởi applying its associated inverse cumulative distribution function đến các số ngẫu nhiên thống nhất giữa 0 và 1.

Xem thêm SO explanation này, hoặc, như được giải thích bởi Wikipedia:

If Y has a U[0,1] distribution then F⁻¹(Y) is distributed as F. This is used in random number generation using the inverse transform sampling-method.

import random 
import bisect 
import collections 

def cdf(weights): 
    total = sum(weights) 
    result = [] 
    cumsum = 0 
    for w in weights: 
     cumsum += w 
     result.append(cumsum/total) 
    return result 

def choice(population, weights): 
    assert len(population) == len(weights) 
    cdf_vals = cdf(weights) 
    x = random.random() 
    idx = bisect.bisect(cdf_vals, x) 
    return population[idx] 

weights=[0.3, 0.4, 0.3] 
population = 'ABC' 
counts = collections.defaultdict(int) 
for i in range(10000): 
    counts[choice(population, weights)] += 1 
print(counts) 

# % test.py 
# defaultdict(<type 'int'>, {'A': 3066, 'C': 2964, 'B': 3970}) 
enter code here 

Các choice chức năng trên sử dụng bisect.bisect, do đó, việc chọn một biến ngẫu nhiên có trọng số được thực hiện trong O(log n) trong đó n là độ dài weights.

---

Lưu ý rằng kể từ phiên bản 1.7.0, NumPy có mã hoá là np.random.choice function. Ví dụ, điều này tạo ra 1000 mẫu từ dân [0,1,2,3] với trọng lượng [0.1, 0.2, 0.3, 0.4]:

import numpy as np 
np.random.choice(4, 1000, p=[0.1, 0.2, 0.3, 0.4]) 

np.random.choice cũng có một tham số replace để lấy mẫu có hoặc không có sự thay thế.

---

Thuật toán tốt hơn về mặt lý thuyết là Alias Method. Nó xây dựng một bảng yêu cầu thời gian O(n), nhưng sau đó, các mẫu có thể được rút ra trong thời gian O(1). Vì vậy, nếu bạn cần rút ra nhiều mẫu, theo lý thuyết thì phương pháp Alias ​​có thể nhanh hơn. Có triển khai Python của Phương thức Walker Alias ​​here và numpy version here.

Answer 2

Không ... rất nhiều ...

pos = ['A'] * 3 + ['B'] * 4 + ['C'] * 3 
print random.choice(pos) 

hoặc

pos = {'A': 3, 'B': 4, 'C': 3} 
print random.choice([x for x in pos for y in range(pos[x])]) 

Answer 3

Dưới đây là một lớp học để phơi bày một loạt các mục có xác suất tương đối, mà không thực sự mở rộng danh sách:

import bisect 
class WeightedTuple(object): 
    """ 
    >>> p = WeightedTuple({'A': 2, 'B': 1, 'C': 3}) 
    >>> len(p) 
    6 
    >>> p[0], p[1], p[2], p[3], p[4], p[5] 
    ('A', 'A', 'B', 'C', 'C', 'C') 
    >>> p[-1], p[-2], p[-3], p[-4], p[-5], p[-6] 
    ('C', 'C', 'C', 'B', 'A', 'A') 
    >>> p[6] 
    Traceback (most recent call last): 
    ... 
    IndexError 
    >>> p[-7] 
    Traceback (most recent call last): 
    ... 
    IndexError 
    """ 
    def __init__(self, items): 
     self.indexes = [] 
     self.items = [] 
     next_index = 0 
     for key in sorted(items.keys()): 
      val = items[key] 
      self.indexes.append(next_index) 
      self.items.append(key) 
      next_index += val 

     self.len = next_index 

    def __getitem__(self, n): 
     if n < 0: 
      n = self.len + n 
     if n < 0 or n >= self.len: 
      raise IndexError 

     idx = bisect.bisect_right(self.indexes, n) 
     return self.items[idx-1] 

    def __len__(self): 
     return self.len 

Bây giờ, chỉ cần nói:

data = WeightedTuple({'A': 30, 'B': 40, 'C': 30}) 
random.choice(data) 

Answer 4

Hãy thử điều này:

import random 
from decimal import Decimal 

pos = {'A': Decimal("0.3"), 'B': Decimal("0.4"), 'C': Decimal("0.3")} 
choice = random.random() 
F_x = 0 
for k, p in pos.iteritems(): 
    F_x += p 
    if choice <= F_x: 
     x = k 
     break 

Answer 5

Bạn cũng có thể tận dụng hình thức này, mà không tạo ra một danh sách tùy tiện lớn (và có thể làm việc với một trong hai xác suất không thể thiếu hoặc số thập phân):

pos = [("A", 30), ("B", 40), ("C", 30)] 


from random import uniform 
def w_choice(seq): 
    total_prob = sum(item[1] for item in seq) 
    chosen = random.uniform(0, total_prob) 
    cumulative = 0 
    for item, probality in seq: 
     cumulative += probality 
     if cumulative > chosen: 
      return item 

Answer 6

Có là một số giải pháp tốt được cung cấp ở đây, nhưng tôi khuyên bạn nên xem xét Eli Bendersky's thorough discussion của vấn đề này, so sánh các thuật toán khác nhau để đạt được điều này (với triển khai bằng Python) trước khi chọn một.