水塘抽樣

维基百科,自由的百科全书
跳转至: 导航搜索

水塘抽樣是一系列的隨機算法,其目的在於從包含n個項目的集合S中選取k個樣本,其中n為一很大或未知的數量,尤其適用於不能把所有n個項目都存放到主記憶體的情況。最常見例子為Jeffrey Vitter在其論文[1]中所提及的算法R

參照Dictionary of Algorithms and Data Structures[2]所載的O(n)算法,包含以下步驟(假設陣列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,以P_n表示。如果檔案共有N行,任意第n行被抽取的機率為

\begin{align}
&P_n\prod_{k=n+1}^N(1-P_k)\\
=&\frac{1}{n}\prod_{k=n+1}^N(1-\frac{1}{k})\\
=&\frac{1}{n}\prod_{k=n+1}^N\frac{k-1}{k}\\
=&\frac{1}{n}\frac{n}{n+1}\frac{n+1}{n+2}\cdots\frac{N-1}{N}\\
=&\frac{1}{N}
\end{align}

故此,各行被抽取的機率均相同。

由於上述算法不需要先把整個檔案掃描以判定總行數再作抽樣,此算法是一線上算法

以上問題可擴展為

可否在一未知大小的集合中,隨機取出k個元素?

亦即是說,如果檔案共有N \ge k行,則每一行被抽取的機率為\frac{k}{N},則算法為

$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,以P_n表示。如果檔案共有N行,任意第n行被抽取的機率為

\begin{align}
&P_n\prod_{j=n+1}^N(1-\frac{P_j}{k})\\
=&\frac{k}{n}\prod_{j=n+1}^N(1-\frac{k}{kj})\\
=&\frac{k}{n}\prod_{j=n+1}^N\frac{j-1}{j}\\
=&\frac{k}{n}\frac{n}{n+1}\frac{n+1}{n+2}\cdots\frac{N-1}{N}\\
=&\frac{k}{N}
\end{align}

因此,各行被抽取的機率均相同。同理,此算法亦是線上算法。

在水塘算法的定義中,並沒有要求每一項目被抽取的機率相同,然而相同機率的情況較常用。

參考文獻[编辑]