код для выбора значений N с некоторыми связанными вероятностями

Question

Предположим, что у нас есть набор x из N значений {x_i; i=1,...,N} и набор некоторых связанных вероятностей {w_i; i=1,...,N}.

Мы хотим получить от множества x, новый набор x^ из N значения {x^_i; i=1,...,N} путем выбора каждого значения x_i из множества x в соответствии с вероятностью w_i. Как мы кодируем это (то есть алгоритм псевдокода, который может быть переведен на любой язык).

EDIT: код питона:

def resample(self,x,w): 
    N = len(w) 
    new_x = empty(N) 
    c = cumsum(w) 

    for i in range(N): 
     r = random() 
     for j in range(N): 
      if(j == N-1): 
       new_x[i] = x[j] 
       break 
      else: 
       if((c[j] <= r) and (r < c[j+1])): 
        new_x[i] = x[j+1] 
        break 

    new_w = ones(N,dtype=float)/N 
    return new_x, new_w 

Answer 1

Вы можете вызвать функцию, которая дает вам случайное число между 0 и 1.
Если вероятности w_1 = 0,2, w_2 = 0,5, w_3 = 0,3, вы можете:
Выберите x_1, если вы получили число от 0 до 0,2
Выберите x_2, если у вас есть номер от 0,2 до 0,7
Выберите x_3 в противном случае.

В целом, выбор x_n если w_1 + ... + w_ (п-1) < = случайное число < w_1 + ... + w_ (п-1) + w_n

Это не весь псевдокод , просто объяснение его самой проблематичной части, но я думаю, этого должно быть достаточно, если у вас есть базовое понимание вашей проблемы.

Answer 2

Я думаю, что лучший вариант - это предварительная обработка вероятности, а затем получение случайного значения.

Позвольте мне объяснить, что я имею в виду:

Сначала необходимо создать новый набор, например h_i, в котором вы размещаете накопленную вероятность каждого объекта.

x_i:{A,B,C,D} 
w_i:{0.2,0.3,0.4,0.1} 
h_i:{0.2,0.5,0.9,1} 

Последний элемент, конечно, 1. (но если это не так (у вас есть недостающие случаи) он все еще работает.

Теперь вы генерировать случайные числа 0≤r≤1 и поиска первой элемент, ч больше, чем г.

Например, если вы получите 0,56 вы выбираете C, потому что 0,9 (H_C)> 0,56 и 0,5 (h_B) ≤ 0,56

Эта операция может быть дорогим на массивах, но если вы выбираете двоичное дерево поиска для хранения набора h_i, вы можете получить очень хорошие результаты.

То есть, если вы хотите выбрать множество случайных значений с одинаковой вероятностью. Если набор постоянно меняется, я бы использовал другой подход.

Answer 3

# import the random library 
import random 

# define the input data 
X = ["A","B","C","D"] 
w = [0.2,0.3,0.4,0.1] 

# size of the new sample 
n = 10 

# empy list to store the result 
Xp = [] 

# the actual code 
while len(Xp) < n: 
    random_choice = random.choice(w) 
    if random_choice >= random.random(): 
     Xp.append(X[w.index(random_choice)]) 

# have a look 
Xp 

Из [39]:

[ 'C', 'C', 'C', 'В', 'D', 'B' 'А', 'D' ' A ',' B ']