Thuật toán để lấy mẫu mà không cần thay thế?

Question

Tôi đang cố gắng kiểm tra khả năng một nhóm dữ liệu cụ thể đã xảy ra một cách tình cờ. Một cách mạnh mẽ để làm điều này là mô phỏng Monte Carlo, trong đó các kết hợp giữa dữ liệu và nhóm được gán lại một cách ngẫu nhiên một số lần lớn (ví dụ 10.000) và số liệu phân cụm được sử dụng để so sánh dữ liệu thực tế với các mô phỏng để xác định ap giá trị.

Tôi đã thực hiện hầu hết công việc này, với các con trỏ ánh xạ nhóm tới các phần tử dữ liệu, vì vậy tôi có kế hoạch gán ngẫu nhiên con trỏ cho dữ liệu. CÂU HỎI: một cách nhanh chóng để lấy mẫu mà không cần thay thế là gì, để mỗi con trỏ được gán lại ngẫu nhiên trong các tập dữ liệu sao chép?

Ví dụ (những dữ liệu này chỉ là một ví dụ đơn giản):

dữ liệu (n = 12 giá trị) - Nhóm A: 0.1, 0.2, 0.4/Nhóm B: 0,5, 0,6, 0,8/Nhóm C : 0,4, 0,5/Nhóm D: 0,2, 0,2, 0,3, 0,5

Đối với mỗi bộ dữ liệu lặp lại, tôi sẽ có cùng kích thước cụm (A = 3, B = 3, C = 2, D = 4) và các giá trị dữ liệu, nhưng sẽ gán lại các giá trị cho các cụm. Để làm điều này, tôi có thể tạo ra các số ngẫu nhiên trong khoảng 1-12, gán phần tử đầu tiên của nhóm A, sau đó tạo các số ngẫu nhiên trong phạm vi 1-11 và gán phần tử thứ hai trong nhóm A, v.v. . Việc gán lại con trỏ rất nhanh và tôi sẽ phân bổ trước tất cả các cấu trúc dữ liệu, nhưng việc lấy mẫu mà không thay thế có vẻ như là một vấn đề có thể đã được giải quyết nhiều lần trước đây.

Ưu tiên lôgic hoặc mã giả.

Answer 1

Xem câu trả lời của tôi cho câu hỏi này Unique (non-repeating) random numbers in O(1)?. Cùng một logic nên hoàn thành những gì bạn đang tìm kiếm để làm.

Answer 2

Dưới đây là một số mã để lấy mẫu mà không cần thay thế dựa trên Thuật toán 3.4.2S của cuốn sách Thuật toán Seminumeric của Knuth.

void SampleWithoutReplacement 
(
    int populationSize, // size of set sampling from 
    int sampleSize,  // size of each sample 
    vector<int> & samples // output, zero-offset indicies to selected items 
) 
{ 
    // Use Knuth's variable names 
    int& n = sampleSize; 
    int& N = populationSize; 

    int t = 0; // total input records dealt with 
    int m = 0; // number of items selected so far 
    double u; 

    while (m < n) 
    { 
     u = GetUniform(); // call a uniform(0,1) random number generator 

     if ((N - t)*u >= n - m) 
     { 
      t++; 
     } 
     else 
     { 
      samples[m] = t; 
      t++; m++; 
     } 
    } 
} 

Có một phương pháp hiệu quả hơn nhưng phức tạp hơn bởi Jeffrey Scott Vitter trong "Một thuật toán hiệu quả cho tuần tự lấy mẫu ngẫu nhiên," Giao dịch ACM trên Toán học Phần mềm, 13 (1), tháng 3 năm 1987, 58-67.

Answer 3

Một thuật toán khác để lấy mẫu không cần thay thế được mô tả here.

Nó tương tự như mô tả của John D. Cook trong câu trả lời của ông và cũng từ Knuth, nhưng nó có giả thiết khác nhau: Kích thước dân số chưa được biết, nhưng mẫu có thể phù hợp với bộ nhớ. Cái này được gọi là "thuật toán S của Knuth".

Trích dẫn bài viết rosettacode:

1. Chọn các mục n đầu tiên làm mẫu khi họ trở nên có sẵn;
2. Đối với mặt hàng thứ i, trong đó i> n, có cơ hội ngẫu nhiên không giữ. Nếu không có cơ hội này, mẫu vẫn giữ nguyên. Nếu không, hãy chọn ngẫu nhiên (1/n) thay thế một trong các mục n đã chọn trước đó của mẫu.
3. Lặp lại # 2 cho bất kỳ mục tiếp theo nào.

Answer 4

Mã hoạt động C++ dựa trên answer by John D. Cook.

#include <random> 
#include <vector> 

double GetUniform() 
{ 
    static std::default_random_engine re; 
    static std::uniform_real_distribution<double> Dist(0,1); 
    return Dist(re); 
} 

// John D. Cook, https://stackoverflow.com/a/311716/15485 
void SampleWithoutReplacement 
(
    int populationSize, // size of set sampling from 
    int sampleSize,  // size of each sample 
    std::vector<int> & samples // output, zero-offset indicies to selected items 
) 
{ 
    // Use Knuth's variable names 
    int& n = sampleSize; 
    int& N = populationSize; 

    int t = 0; // total input records dealt with 
    int m = 0; // number of items selected so far 
    double u; 

    while (m < n) 
    { 
     u = GetUniform(); // call a uniform(0,1) random number generator 

     if ((N - t)*u >= n - m) 
     { 
      t++; 
     } 
     else 
     { 
      samples[m] = t; 
      t++; m++; 
     } 
    } 
} 

#include <iostream> 
int main(int,char**) 
{ 
    const size_t sz = 10; 
    std::vector<int> samples(sz); 
    SampleWithoutReplacement(10*sz,sz,samples); 
    for (size_t i = 0; i < sz; i++) { 
    std::cout << samples[i] << "\t"; 
    } 

    return 0; 
} 

Answer 5

Lấy cảm hứng từ @John D. Cook's answer, tôi đã viết một triển khai trong Nim. Lúc đầu, tôi đã gặp khó khăn trong việc hiểu cách nó hoạt động, vì vậy tôi đã nhận xét rộng rãi cũng bao gồm một ví dụ. Có lẽ nó giúp hiểu ý tưởng. Ngoài ra, tôi đã thay đổi tên biến một chút.

iterator uniqueRandomValuesBelow*(N, M: int) = 
    ## Returns a total of M unique random values i with 0 <= i < N 
    ## These indices can be used to construct e.g. a random sample without replacement 
    assert(M <= N) 

    var t = 0 # total input records dealt with 
    var m = 0 # number of items selected so far 

    while (m < M): 
    let u = random(1.0) # call a uniform(0,1) random number generator 

    # meaning of the following terms: 
    # (N - t) is the total number of remaining draws left (initially just N) 
    # (M - m) is the number how many of these remaining draw must be positive (initially just M) 
    # => Probability for next draw = (M-m)/(N-t) 
    # i.e.: (required positive draws left)/(total draw left) 
    # 
    # This is implemented by the inequality expression below: 
    # - the larger (M-m), the larger the probability of a positive draw 
    # - for (N-t) == (M-m), the term on the left is always smaller => we will draw 100% 
    # - for (N-t) >> (M-m), we must get a very small u 
    # 
    # example: (N-t) = 7, (M-m) = 5 
    # => we draw the next with prob 5/7 
    # lets assume the draw fails 
    # => t += 1 => (N-t) = 6 
    # => we draw the next with prob 5/6 
    # lets assume the draw succeeds 
    # => t += 1, m += 1 => (N-t) = 5, (M-m) = 4 
    # => we draw the next with prob 4/5 
    # lets assume the draw fails 
    # => t += 1 => (N-t) = 4 
    # => we draw the next with prob 4/4, i.e., 
    # we will draw with certainty from now on 
    # (in the next steps we get prob 3/3, 2/2, ...) 
    if (N - t)*u >= (M - m).toFloat: # this is essentially a draw with P = (M-m)/(N-t) 
     # no draw -- happens mainly for (N-t) >> (M-m) and/or high u 
     t += 1 
    else: 
     # draw t -- happens when (M-m) gets large and/or low u 
     yield t # this is where we output an index, can be used to sample 
     t += 1 
     m += 1 

# example use 
for i in uniqueRandomValuesBelow(100, 5): 
    echo i 

Answer 6

Khi quy mô dân số lớn hơn nhiều so với kích thước mẫu, các thuật toán trên trở nên không hiệu quả, vì chúng có độ phức tạp O (n), n là quy mô dân số.

Khi tôi còn là một sinh viên, tôi đã viết một số thuật toán để lấy mẫu thống nhất mà không cần thay thế, trong đó có độ phức tạp trung bình O (s log s), nơi s là kích thước mẫu. Dưới đây là mã cho các thuật toán cây nhị phân, với độ phức tạp trung bình O (s log s), R:

# The Tree growing algorithm for uniform sampling without replacement 
# by Pavel Ruzankin 
quicksample = function (n,size) 
# n - the number of items to choose from 
# size - the sample size 
{ 
    s=as.integer(size) 
    if (s>n) { 
    stop("Sample size is greater than the number of items to choose from") 
    } 
    # upv=integer(s) #level up edge is pointing to 
    leftv=integer(s) #left edge is poiting to; must be filled with zeros 
    rightv=integer(s) #right edge is pointig to; must be filled with zeros 
    samp=integer(s) #the sample 
    ordn=integer(s) #relative ordinal number 

    ordn[1L]=1L #initial value for the root vertex 
    samp[1L]=sample(n,1L) 
    if (s > 1L) for (j in 2L:s) { 
    curn=sample(n-j+1L,1L) #current number sampled 
    curordn=0L #currend ordinal number 
    v=1L #current vertice 
    from=1L #how have come here: 0 - by left edge, 1 - by right edge 
    repeat { 
     curordn=curordn+ordn[v] 
     if (curn+curordn>samp[v]) { #going down by the right edge 
     if (from == 0L) { 
      ordn[v]=ordn[v]-1L 
     } 
     if (rightv[v]!=0L) { 
      v=rightv[v] 
      from=1L 
     } else { #creating a new vertex 
      samp[j]=curn+curordn 
      ordn[j]=1L 
      # upv[j]=v 
      rightv[v]=j 
      break 
     } 
     } else { #going down by the left edge 
     if (from==1L) { 
      ordn[v]=ordn[v]+1L 
     } 
     if (leftv[v]!=0L) { 
      v=leftv[v] 
      from=0L 
     } else { #creating a new vertex 
      samp[j]=curn+curordn-1L 
      ordn[j]=-1L 
      # upv[j]=v 
      leftv[v]=j 
      break 
     } 
     } 
    } 
    } 
    return(samp) 
} 

Sự phức tạp của thuật toán này được thảo luận trong: Rouzankin, P. S .; Voytishek, A. V. Trên chi phí của các thuật toán để lựa chọn ngẫu nhiên. Phương pháp Monte Carlo Appl. 5 (1999), không. 1, 39-54. http://dx.doi.org/10.1515/mcma.1999.5.1.39

Nếu bạn tìm thấy thuật toán hữu ích, vui lòng tham khảo.

Xem thêm: P. Gupta, G. P. Bhattacharjee. (1984) Một thuật toán hiệu quả để lấy mẫu ngẫu nhiên mà không cần thay thế. Tạp chí Quốc tế về Toán học Máy tính 16: 4, trang 201-209. DOI: 10.1080/00207168408803438

Teuhola, J. và Nevalainen, O. 1982. Hai thuật toán hiệu quả để lấy mẫu ngẫu nhiên mà không cần thay thế./IJCM /, 11 (2): 127–140. DOI: 10,1080/00207168208803304

Trong giấy cuối cùng các tác giả sử dụng bảng băm và tuyên bố rằng các thuật toán của họ có O (s) phức tạp. Có một thuật toán bảng băm nhanh hơn, sẽ sớm được triển khai trong pqR (khá nhanh R): https://stat.ethz.ch/pipermail/r-devel/2017-October/075012.html