水塘抽样
![本页使用了标题或全文手工转换](http://images.weserv.nl/?url=//upload.wikimedia.org/wikipedia/commons/thumb/c/cd/Zh_conversion_icon_m.svg/35px-Zh_conversion_icon_m.svg.png)
水塘抽样(英语:Reservoir sampling)是一系列的随机算法,其目的在于从包含n个项目的集合S中选取k个样本,其中n为一很大或未知的数量,尤其适用于不能把所有n个项目都存放到内存的情况。最常见例子为Jeffrey Vitter在其论文[1]中所提及的算法R。
参照Dictionary of Algorithms and Data Structures[2]所载的算法,包含以下步骤(假设数组S以0开始标示):
從S中抽取首k項放入「水塘」中 對於每一個S[j]項(j ≥ k): 隨機產生一個範圍從0到j的整數r 若 r < k 則把水塘中的第r項換成S[j]項
实例
- 可否在一未知大小的集合中,随机取出一元素?
例如在一很大,但未知确实行数的文字档中抽取任意一行。如果要确保每一行抽取的机率相等,即是说如果最后发现文字档共有N行,则每一行被抽取的机率均为1/N,则有如下算法(以Perl表示)
$line;
$n = 0;
srand;
while(<>) {
$n++;
$line = $_ if (rand < (1/$n));
}
以下Perl程序为上述程序之精简写法:
srand;
rand($.) < 1 && ($line = $_) while <>;
上例中,在回圈内第n行被抽取的机率为1/n,以表示。如果档案共有N行,任意第n行被抽取的机率为
故此,各行被抽取的机率均相同。
由于上述算法不需要先把整个档案扫描以判定总行数再作抽样,此算法是一线上算法。
以上问题可扩展为
- 可否在一未知大小的集合中,随机取出k个元素?
亦即是说,如果档案共有行,则每一行被抽取的机率为,则算法为
$k = 輸出數量;
@lines;
$n = 0;
srand;
while(<>) {
$n++;
if ($n <= $k) {
push(@lines, $_);
} else {
$r = int(rand($n));
if ($r < $k) {
$lines[$r] = $_;
}
}
}
上例中,在回圈内第n行被抽取的机率为k/n,以表示。如果档案共有N行,任意第n行被抽取的机率为
因此,各行被抽取的机率均相同。同理,此算法亦是线上算法。
在水塘算法的定义中,并没有要求每一项目被抽取的机率相同,然而相同机率的情况较常用。
参考文献
- ^ Jeffrey Scott Vitter. Random Sampling with a Reservoir (PDF). [2020-02-09]. (原始内容存档 (PDF)于2020-02-28) (英语).
- ^ reservoir sampling. [2020-02-09]. (原始内容存档于2018-10-13) (英语).