一种随机抽样的算法

一种随机抽样的算法

有一个很常见的问题:从N个互不相同的数,随机选取M(M<N)个数字.比如在一组N个样品当中选择其中M个进行破坏性测试。

朴素的想法是,输出M次随机数,在每次输出存于一个表中,每次准备输出时看一下这次要输出的随机数是否以前出现过,若出现过就再生成一个随机数,若没出现过就存入这个表并输出它。这个方法在M远小于N的时候是很灵的,按概率来算一般执行M次就可以获得M个不同的随机数。但是当N与M都很大,并且M和N相差并不很大的时候,比如从整个公司1000人当中挑随机选850人,当已经选出849人之后,只有151/1000的概率能选出一个之前未出现过的随机数,并且每次出现一个随机数要与之前849个数作比较以检查是否之前出现过,这样可能花的时间更长,下面介绍一种仅与总样本数N有关的抽样方法,这是《编程珠玑》上所讨论过的一种算法。在工程上还算实用。

我们从N个样本中选取M个样本,每个样本被选出的概率都是M/N。我们为样本编号为1到N,首先1号样本抽选的概率是M/N,我们可以用if (random(0,N) < M ) then select 1 表示M/N的概率。接下来选择2号样本,如果1号样本被选出了,那么2号样本被选出的概率则应是(M-1)/(N-1)(从剩下N-1个样本中再取M-1个),而如果1号样本没被选出,那么1号样本被选出的概率就是M/(N-1)(从剩下N-1个样本里选M个)。这样2号样本被选出的概率为 (1号被选出)*(在1选出时选2的概率)+(1未被选出)*(1未选时选2的概率)=(M/N)*((M-1)/(N-1))+(1-M/N)*((M)/(N-1)) =M/N。类似地可得出,每个样本被选出的概率都是M/N。

程序设计时,我们可以设定循环次数就是N次,每次循环时做一次随机,判断生成[0,N-i)的随机整数是否小于剩余样本数M,若小于则选择这第i个样本,同时使剩余样本数的变量减去1,否则什么也不做进行下一趟循环,直到进行完所有N趟循环。

from random import randint

N=100
M=25
for i in range(N):
	if randint(0,N-i-1)<M:
		print(i)
		M-=1

这样就可以有序的、随机不重复的从N个样本中选取M个样本

最近写了网页js的音乐播放器。曲库中有很多歌曲,每次听的时候随机选出固定个数的曲目展示在前端界面上
http://lab.malic.xyz/music/ ,这个随机选取就应用了抽样的过程

$N=count($fileList);
$M=18;
$remains=$M;
for($i=0;$i<$N;$i++)
{
	if(rand()%($N-$i)<$remains)
	{
		echo "$fileList[$i]";
		$remains--;
	}
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注