【原】ダムサンプリングの詳細
2889 ワード
この古典的なアルゴリズムはTAOCPに収録されているが、おじいさんはアルゴリズムのステップだけを与えて証明していない.ここでは詳細に定義して証明する.
定義:
N個のレコードからn個のレコードをランダムに選択したが,最初はNがどれだけあるか分からなかった.
アルゴリズム:
1.サンプリングアルゴリズムを選択する:
N個のレコードを順次スキャンし、t+1個目のレコードに対して確率(n-m)/(N-t)で選択(mは選択したレコード数)することができるが、これは、Nのサイズを得るために事前にファイルを順次スキャンしなければならない.
2.ダムサンプリングアルゴリズム:
2.1記録が十分大きい場合
ファイルを1回目にスキャンすると、m>=n個の元の記録の「ダム」とn個のインデックスがあるテーブルが得られ、m個の記録のうちどのn個が抽出されたかが記録され、m個の記録のダムを順次スキャンするとn個のサンプリングが得られる.
t+1番目のレコードを入力し、t>=nとすると、n個のインデックスのテーブルには、ダム内の要素に対応するサンプルとして、ダム内のt個のレコードから選択したレコードが記録される.入力がいつ終わるか分からないので、n/(t+1)の確率で新しいレコードを新しいサンプリングに含め(終了時に各レコードが同じ選択確率を持つように)、以前のサンプリングのランダム要素を1つ取り除くべきである.
アルゴリズムは、以下のR 1->R 6:n>0が与えられ、正確なサイズは未知であるが>=nのファイルでランダムにn個のレコードが選択される.「ダム」という補助文書には、最後のサンプリング候補者としてm個のすべての記録が格納されている.n個のインデックスを持つテーブル,I[j],1<=j<=nであり,各インデックスはダム内の記録に対応する.
R 1:[初期化]入力ヘッダn個のレコードをダムにコピーし、1<=j<=n,I[j]=jに対してt=m=n(サンプリングされたファイルがn個未満の場合はアルゴリズムを中断してエラーを報告する必要がある)
R 2:[ファイル終了?]入力できるレコードがない場合は=>R 6
R 3:[生成し検証]tは1増加し、[1,t]間のランダム整数Mを生成する.M>nであれば=>R 5(すなわち選択確率はn/(t+1))
R 4:[ダムに追加]次のレコードをダムにコピーし、mは1増加し、I[M]=m(以前はI[M]が指していたレコードがこれによって新しいレコードに置き換えられた)後=>R 2
R 5:[ジャンプ]次のレコードをスキップ(ダムに入れない)し、=>R 2
R 6:[第2走査ダム]IテーブルをI[1]
2.2記録が十分に小さい場合:
現在サンプリングされたn個の記録をメモリに入れることができる場合、もちろん「ダム」を構築する必要は全くなく、R 6、変数mとダムを削除し、Iテーブルの代わりに1個の記録テーブルpoolを用いてR 1の頭n個の記録に初期化し、I[M]を新記録とする.
ファイルの前のn項目のデータをpoolに入れてから、後のi番目の要素に対してpoolのある要素をn/iの確率で置き換えます.
アルゴリズムの疑似コード:
この方法で選択すると,すべての要素などの確率が選択されることを実証する必要がある.帰納法の証明は以下の通りである.[初期状態]まだ選択されていない場合、poolに現れるn個の要素の確率は同じであり、いずれも1である.n+1番目の元素がn/(n+1)の確率で選択すると、poolにおける前のn個の元素の確率はn/(n+1)であり、すなわち新旧元素が選択される確率は同じであることを証明する: .
任意の要素が置換される確率は、(n/(n+1)*(1/n)=1/(n+1)である.
従って、前のn個の要素が選択(置換されていない)される確率は、1−1/(n+1)=n/(n+1)である.
また、前のn個の要素が選択される前のpoolにおける確率は1であるため、2つの確率が乗算される:1*(n/(n+1)=n/(n+1)であり、結論に合致する.[仮定]i番目の要素がn/iの確率で選択された場合、前のi−1要素が選択された確率もn/iである. [証明]i+1番目の要素の場合:前のi要素が選択された確率は2つの部分からなる: a.i+1回目の選択の前に、このi要素はpoolにあります.
仮定から,前のi要素が選択される確率はn/i,すなわちpoolにおける確率である.
b.i+1回目の選択で現在のpoolの要素が置換されていません:
任意の要素が置換される確率を先に計算する:(n/(i+1)*(1/n)=1/(i+1)
したがって置換されない確率は、1−1/(i+1)=i/(i+1)である.
aとbを乗算すると、前のi要素が選択される確率:(n/i)*(i/(i+1)=n/(i+1)が得られ、仮定に合致する.
定義:
N個のレコードからn個のレコードをランダムに選択したが,最初はNがどれだけあるか分からなかった.
アルゴリズム:
1.サンプリングアルゴリズムを選択する:
N個のレコードを順次スキャンし、t+1個目のレコードに対して確率(n-m)/(N-t)で選択(mは選択したレコード数)することができるが、これは、Nのサイズを得るために事前にファイルを順次スキャンしなければならない.
2.ダムサンプリングアルゴリズム:
2.1記録が十分大きい場合
ファイルを1回目にスキャンすると、m>=n個の元の記録の「ダム」とn個のインデックスがあるテーブルが得られ、m個の記録のうちどのn個が抽出されたかが記録され、m個の記録のダムを順次スキャンするとn個のサンプリングが得られる.
t+1番目のレコードを入力し、t>=nとすると、n個のインデックスのテーブルには、ダム内の要素に対応するサンプルとして、ダム内のt個のレコードから選択したレコードが記録される.入力がいつ終わるか分からないので、n/(t+1)の確率で新しいレコードを新しいサンプリングに含め(終了時に各レコードが同じ選択確率を持つように)、以前のサンプリングのランダム要素を1つ取り除くべきである.
アルゴリズムは、以下のR 1->R 6:n>0が与えられ、正確なサイズは未知であるが>=nのファイルでランダムにn個のレコードが選択される.「ダム」という補助文書には、最後のサンプリング候補者としてm個のすべての記録が格納されている.n個のインデックスを持つテーブル,I[j],1<=j<=nであり,各インデックスはダム内の記録に対応する.
R 1:[初期化]入力ヘッダn個のレコードをダムにコピーし、1<=j<=n,I[j]=jに対してt=m=n(サンプリングされたファイルがn個未満の場合はアルゴリズムを中断してエラーを報告する必要がある)
R 2:[ファイル終了?]入力できるレコードがない場合は=>R 6
R 3:[生成し検証]tは1増加し、[1,t]間のランダム整数Mを生成する.M>nであれば=>R 5(すなわち選択確率はn/(t+1))
R 4:[ダムに追加]次のレコードをダムにコピーし、mは1増加し、I[M]=m(以前はI[M]が指していたレコードがこれによって新しいレコードに置き換えられた)後=>R 2
R 5:[ジャンプ]次のレコードをスキップ(ダムに入れない)し、=>R 2
R 6:[第2走査ダム]IテーブルをI[1]
2.2記録が十分に小さい場合:
現在サンプリングされたn個の記録をメモリに入れることができる場合、もちろん「ダム」を構築する必要は全くなく、R 6、変数mとダムを削除し、Iテーブルの代わりに1個の記録テーブルpoolを用いてR 1の頭n個の記録に初期化し、I[M]を新記録とする.
ファイルの前のn項目のデータをpoolに入れてから、後のi番目の要素に対してpoolのある要素をn/iの確率で置き換えます.
アルゴリズムの疑似コード:
1: for i in [n+1,N] 2: M = rand(1,i); 3: if (M <= n) 4: swap the ith and Mth dataこの方法で選択すると,すべての要素などの確率が選択されることを実証する必要がある.帰納法の証明は以下の通りである.
任意の要素が置換される確率は、(n/(n+1)*(1/n)=1/(n+1)である.
従って、前のn個の要素が選択(置換されていない)される確率は、1−1/(n+1)=n/(n+1)である.
また、前のn個の要素が選択される前のpoolにおける確率は1であるため、2つの確率が乗算される:1*(n/(n+1)=n/(n+1)であり、結論に合致する.
仮定から,前のi要素が選択される確率はn/i,すなわちpoolにおける確率である.
b.i+1回目の選択で現在のpoolの要素が置換されていません:
任意の要素が置換される確率を先に計算する:(n/(i+1)*(1/n)=1/(i+1)
したがって置換されない確率は、1−1/(i+1)=i/(i+1)である.
aとbを乗算すると、前のi要素が選択される確率:(n/i)*(i/(i+1)=n/(i+1)が得られ、仮定に合致する.