大量のデータから一定個数のデータをランダムに採取するReservoirサンプリング
大量の実験データがあるが、馬鹿正直に全部プロット等すると時間がかかりすぎる。実験の初期段階とかで試行錯誤しながら素早く作業をしたい時には、一定個数のデータをランダムに抜き出してプロット等したい事が多い。
そのとき、全体の個数の見当がついていれば、大体の見当で割合を設定して確率的に取得すればよい。例えば、データの全数が約100万個で、とりあえず1000個取り出したいなら、乱数を用いて0.1%の割合でデータを採取すれば良い（ぴったり1000個にはならないだろうがそれは問題ではない）。
全体の個数が不明の場合はそうはいかない。最初に全体の個数を数えてから割合を設定しようとすると、全データを2回走査、つまり2パスの操作が必要になるし、標準入力からデータが流れてくる場合（いわゆるストリーム処理）の場合は、個数を取得するためには全体を保存しておかなければならない。これらの操作は、大規模なデータにおいては非常に高価だ。そもそもデータ自体がメモリに収まるとは限らない。
よって、
- 全体のデータ数が不明でも
- 大量の保存領域を使うこと無く
- 1パスで
- 均一にランダムにデータをサンプリング
というアルゴリズムが必要となる。
その場合に使えるのが、Reservoir sampling [Vitter85] というテクニックだ。これは、全数が不明でも、全体から一定個数の均等なサンプルを取得することができる。Wikipediaのページもある。http://en.wikipedia.org/wiki/Reservoir_sampling
非常に大ざっぱに言えば、i番目のデータは1/iの確率で答えに入ることができるということ。アルゴリズムはこうなる。
- 一定個数 k 個のデータを採取したいとし、答えの配列をRとする。R[1] .. R[k]
- 最初のk個については、無条件に採用する。
- i個目のデータd_i（i > k) については、整数の一様乱数 t (1 <= t <= N)を生成し、もし t <= k なら R[t] = d_i とする。
これによって、長さが不明なデータ列から、1パスでランダムに一定個数のデータを取得することができる。
Vitter85: J.S.Vitter "Random Sampling with a Reservoir" http://www.mathcs.emory.edu/~cheung/papers/StreamDB/RandomSampling/1985-Vitter-Random-sampling-with-reservior.pdf
