خوارزمية أخذ العينات دون استبدال؟

Question

أحاول اختبار احتمال حدوث مجموعة معينة من البيانات عن طريق الصدفة.إحدى الطرق القوية للقيام بذلك هي محاكاة مونت كارلو، حيث يتم إعادة تعيين الارتباطات بين البيانات والمجموعات بشكل عشوائي لعدد كبير من المرات (على سبيل المثال.10000)، ويتم استخدام مقياس التجميع لمقارنة البيانات الفعلية مع عمليات المحاكاة لتحديد قيمة p.

لقد قمت بمعظم هذا العمل، حيث تقوم المؤشرات بتعيين التجميع لعناصر البيانات، لذلك أخطط لإعادة تعيين المؤشرات عشوائيًا للبيانات.السؤال:ما هي الطريقة السريعة لأخذ العينات دون استبدال، بحيث يتم إعادة تعيين كل مؤشر بشكل عشوائي في مجموعات البيانات المتماثلة؟

على سبيل المثال (هذه البيانات مجرد مثال مبسط):

البيانات (ن = 12 قيمة) - المجموعة أ:0.1، 0.2، 0.4 / المجموعة ب:0.5، 0.6، 0.8 / المجموعة ج:0.4، 0.5 / المجموعة د:0.2، 0.2، 0.3، 0.5

بالنسبة لكل مجموعة بيانات متكررة، سيكون لدي نفس أحجام المجموعة (A = 3، B = 3، C = 2، D = 4) وقيم البيانات، ولكن سأعيد تعيين القيم إلى المجموعات.

للقيام بذلك، يمكنني إنشاء أرقام عشوائية في النطاق من 1 إلى 12، وتعيين العنصر الأول في المجموعة أ، ثم إنشاء أرقام عشوائية في النطاق من 1 إلى 11، وتعيين العنصر الثاني في المجموعة أ، وهكذا.تتم إعادة تعيين المؤشر بسرعة، وسأكون قد قمت بتخصيص جميع هياكل البيانات مسبقًا، ولكن يبدو أن أخذ العينات بدون استبدال يمثل مشكلة ربما تم حلها عدة مرات من قبل.

يفضل المنطق أو الكود الكاذب.

Answer 1

وانظر جوابي على هذا السؤال فريد (غير مكرر) أرقام عشوائية في O ( 1)؟ . نفس المنطق يجب أن تنجز ما كنت تبحث القيام به.

Answer 2

وفيما يلي بعض التعليمات البرمجية لأخذ العينات من دون استبدال بناء على خوارزمية 3.4.2S من كتاب نث Seminumeric الخوارزميات.

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++;
        }
    }
}

وهناك طريقة أكثر كفاءة ولكن أكثر تعقيدا جيفري سكوت فيتر في "خوارزمية فعالة لمتسلسل أخذ العينات عشوائية،" المعاملات ACM على البرامج الرياضية، و 13 (1)، مارس 1987، 58-67.

Answer 3

وA C ++ كود عمل استنادا على الاجابة التي كتبها جون D. كوك .

#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 4

John D. كوك الجواب ، كتبت التنفيذ في نيم. في البداية كان لي صعوبات في فهم كيف يعمل، لذلك أنا علق على نطاق واسع أيضا بما في ذلك على سبيل المثال. ربما أنها تساعد على فهم هذه الفكرة. أيضا، لقد تغيرت أسماء المتغيرات قليلا.

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 5

عندما يكون حجم السكان أكبر بكثير من حجم العينة، تصبح الخوارزميات المذكورة أعلاه غير فعالة، لأنها معقدة يا(ن), ن كونه حجم السكان.

عندما كنت طالبًا، كتبت بعض الخوارزميات لأخذ العينات الموحدة دون استبدال، والتي كانت متوسطة التعقيد يا(س سجل س)، أين س هو حجم العينة.إليك رمز خوارزمية الشجرة الثنائية، بتعقيد متوسط يا(س سجل س) ، في ر:

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

تمت مناقشة تعقيد هذه الخوارزمية في:روزانكين، P.س.؛فويتيشيك، أ.الخامس.على تكلفة خوارزميات الاختيار العشوائي.تطبيق طرق مونت كارلو.5 (1999)، لا.1، 39-54.http://dx.doi.org/10.1515/mcma.1999.5.1.39

إذا وجدت الخوارزمية مفيدة، يرجى الإشارة إليها.

أنظر أيضا:ص.غوبتا، G.ص.بهاتاشارجي.(1984) خوارزمية فعالة لأخذ العينات العشوائية بدون استبدال.المجلة الدولية لرياضيات الكمبيوتر 16:4، الصفحات 201-209.معرف الهوية الرقمي:10.1080/00207168408803438

تيهولا، ج.و نيفالاينن، O.1982.خوارزميتان فعالتان لأخذ العينات العشوائية دون استبدال./IJCM/, 11(2):127-140.معرف الهوية الرقمي:10.1080/00207168208803304

في الورقة الأخيرة، استخدم المؤلفون جداول التجزئة وادعوا أن خوارزمياتهم تمتلكها يا(س) تعقيد.هناك خوارزمية أخرى لجدول التجزئة السريع، والتي سيتم تنفيذها قريبًا في pqR (R سريع جدًا):https://stat.ethz.ch/pipermail/r-devel/2017-October/075012.html

Answer 6

تم وصف خوارزمية أخرى لأخذ العينات بدون استبدال هنا.

وهو مشابه لما وصفه جون د.كوك في إجابته وأيضا من كنوث، ولكن لها فرضية مختلفة:حجم السكان غير معروف، ولكن يمكن احتواء العينة في الذاكرة.هذا يسمى "خوارزمية Knuth S".

نقلا عن مقالة Rosettacode :

1. حدد العناصر n الأولى كعينة عندما تصبح متاحة؛
2. بالنسبة للعنصر i حيث i > n، لديك فرصة عشوائية لـ n/i للاحتفاظ به.إذا فشلت هذه الفرصة، تظل العينة كما هي.إذا لم يكن الأمر كذلك ، اطلب من ذلك بشكل عشوائي (1/n) استبدال أحد العناصر n المحددة مسبقًا من العينة.
3. كرر رقم 2 لأية عناصر لاحقة.