Location : Home > Languages > Perl > Package
Title : Algorithm::Numerical::Sample
 		Toolbox Logo

名称

　Algorithm::Numerical::Sample - 集合から標本を抽出

概要

use Algorithm::Numerical::Sample  qw /sample/;

@sample = sample (-set         => [1 .. 10000],
                  -sample_size => 100);

$sampler = Algorithm::Numerical::Sample::Stream -> new;

while (<>) {$sampler -> data ($_)}
$random_line = $sampler -> extract;

説明

　本パッケージは、集合から公平でランダムに標本抽出する２つのメソッドを提供する。全集合が既知の場合に用いる手続き的なインタフェースと、集合の大きさが不明な場合のオブジェクト指向的なインタフェースが用意されている。

A: sample (set => ARRAYREF [,sample_size => EXPR])

　集合と標本数を引数としてとる関数である。
　標本数が省略されると１とみなす。キーワード set 及び sample_size の前には - をつける。関数は標本のリストを返すかまたは文脈にしたがって標本のリストへの参照を返す。

B: Algorithm::Numerical::Sample::Stream

　クラス Algorithm::Numerical::Sample::Stream には以下のようなメソッドがある。

new

　本関数は Algorithm::Numerical::Sample::Stream クラスのオブジェクトを返す。
　引数として sample_size => EXPR を取ることもできる。ただし EXPR は標本数として評価される。引数が省略された場合は１とみなす。キーワード sample_size は前に - をつける。

data (LIST)

　メソッド data は標本抽出をする集合の要素であるパラメータのリストを取る。引数の数はいくらでもよい。

extract

　本メソッドはオブジェクトから標本を抽出し、標本空間の大きさが変わらないように新しい状態に戻す。extract はリストの文脈ではリストを返し、スカラーの文脈では最初の要素を返す。

正当性の証明

Algorithm A

　要素数 N 個の集合から n 個の要素を抽出する時に、既に m 個の要素が抽出された後では (n - m)/(N - t) の確率で t+1 番目の要素が抽出されるという事実が sample アルゴリズムが正しいことを示すのに重要である。k 個しか残っていない状態から k 個の要素を抽出する確率は1であるので（n=mでは確率が０になるので）多すぎる要素も少なすぎる要素も抽出できないからである。標本抽出が不偏であることを確認したければ文献 [3] を参照のこと。 (Section 3.4.2, Exercise 3).

Algorithm B

　２つめのアルゴリズムが正しい要素数を返すことを確認することは容易である。要素数 n の標本に対し、最初の n 個の要素を貯蔵庫（reservoir）に格納しておくと、その大きさは大きくも小さくもならず、要素は置換されるだけである。
　アルゴリズムの正当性の詳細な証明は文献 [3] にある。(Section 3.4.2, Exercise 7).

文献

　双方のアルゴリズムとも Knuth [3] (Section 3.4.2) で議論されている。
　最初のアルゴリズム Selection sampling technique was discovered by Fan, Muller 及び Rezucha [1] が発見し、それとは独立に Jones [2] によって発見された。２つめのアルゴリズム Reservoir sampling Waterman による。

参考文献

  1. C. T. Fan, M. E. Muller and I. Rezucha, J. Amer. Stat. Assoc. 57 (1962), pp 387 - 402.
  2. T. G. Jones, CACM 5 (1962), pp 343.
  3. D. E. Knuth: The Art of Computer Programming, Volume 2, Third edition. Reading: Addison-Wesley, 1997. ISBN: 0-201-89684-2.

履歴

$Date: 1999/08/09 08:01:05 $

$Log: Sample.pm,v $
Revision 1.3  1999/08/09 08:01:05  abigail
Algorithms を Algorithm に変更

Revision 1.2  1999/03/01 21:06:07  abigail
Algorithm::* に変更

Revision 1.1  1998/04/29 03:05:57  abigail
初期バージョン

著者

　本パッケージは Abigail によって作成された。

著作権

　Copyright 1998, 1999 by Abigail.

ライセンス

　本パッケージはフリーかつオープンなソフトウェアである。
　本パッケージを利用・複製・修正・再配布・販売してもよく、以下の条件に触れない限りいかなる修正品を作成してもよい。

　本パッケージは「現状のまま」で、明示であるか暗黙であるかを問わず、何らの保証もなく提供される。ここでいう保証とは、商品性・特定の目的への適合性及び権利非侵害についての保証も含む。

Toolbox Logo
 Updated : 2006/08/29