問題タブ [reservoir-sampling]

サイズが未定の配列からk 個の乱数を取得するには、リザーバー サンプリングと呼ばれる手法を使用します。サンプルコードでそれがどのように起こるかを簡単に強調できますか?

このMSDNの記事は、 ReservoirSamplingアルゴリズムの正しさを次

1. 基本ケースは簡単です。k + 1番目のケースでは、位置<=kの特定の要素iがRにある確率はs/kです。

2. iが置き換えられる確率は、k + 1番目の要素が選択される確率にiが置き換えられるように選択されることを掛けたものです。つまり、s /（k + 1）* 1 / s = 1 /（k + 1）であり、i置き換えられないのはk/k+1です。

3. したがって、k + 1ラウンド後に続く任意の要素の確率は次のとおりです。（kステップで選択され、kステップで削除されない）= s / k * k /（k + 1）、つまりs /（k + 1）。

4. したがって、k + 1 = nの場合、任意の要素が確率s/nで存在します。

ステップ3について：

• 何がk+1 rounds言及されていますか？

• 何chosen in k steps, and not removed in k stepsですか？

• R最初のsステップの後にすでに含まれている要素についてのみこの確率を計算するのはなぜですか？

最近別の質問に関連して尋ねられました:未知の長さのリストが与えられた場合、1回だけスキャンしてその中のランダムなアイテムを返します

すべきではないことはわかっていますが、そうすべきではない理由の標準的な説明に指を置くことはできません.

サンプルコードを見てください：

アイテムごとに新しい乱数を生成する適切なリザーバー サンプリングの選択肢は、次のように適切に均等に分散されます。

一方、すべてのアイテムに同じ乱数を再利用すると、非常に低い数値に偏った分布が得られます。

ここの数学は何ですか？同じ乱数を再利用できないのはなぜですか?

与えられたS個の要素のセットからk<=Sとなるk個の要素を選択するリザーバーサンプリングアルゴリズムを理解したいと思います。

ウィキで与えられたアルゴリズムでは：

これを正しく理解していれば、最初にセットからk個の要素を選択し、次にSのi個の要素を連続的に解析し、1からiの範囲のランダムなno jを生成し、要素jをS[i]に置き換えます。

サンプリングされるセットKが非常に大きい場合は問題ないように見えますが、無限サイズ（少なくとも未知のサイズ）のリンクリストから1つの要素だけをランダムに選択したい場合は、このアルゴリズムでどのように行いますか... ？

私は Reservoir Sampling アルゴリズムに精通しており、合計サイズNが与えられたらどうなるか考えています。この状況下で私たちはどのような利益を得ることができますか？その結果、アルゴリズムは次のようになります。

一見正しいように見えますが、証明するのは難しいと感じました。このアルゴリズムを正式な方法で証明するのを手伝ってくれる人はいますか?

私はデータ マイニング クラスのプロジェクトを持っています。このプロジェクトでは、ファイルのリザーバー サンプリング アルゴリズムをコーディングする必要があります。このプログラムは、数値 k、入力ファイルの名前、および作成する出力ファイルの名前を入力として受け取ります。出力ファイルには、入力からの k 個のランダムな行が含まれている必要があります。いくつか試してみましたが、出力が間違っています。

これは私が使用するコードです：

このプログラムがやろうとしているのは、ファイルから最初の k 行を読み取り、それを (k,256) サイズの 2 次元文字列配列に格納することです。次に、次の行ごとに乱数 j を生成し、その数が k より小さい場合、buffer[j] をファイルから取得した最新の行に置き換えます。

}ただし、出力は、入力の最後の文字であるの k 行で構成されています。このように (例: k=5):

バッファを印刷してその内容を確認すると、正しく表示されます。しかし、ファイルに書き込むと、間違った出力が書き込まれます。

どんな助けでも大歓迎です！前もって感謝します！

Weighted Reservoir Sampling を実装する必要があります。このブログで言及されている論文を参照しました。実装を単体テストするためのテストケースを書きたいのですが、貯水池にあるさまざまな要素の期待確率を計算する方法について混乱しています。

に比例するはずだと思っていましたが、ここで(weight_of_element/weight_of_all_elements)言及されているテストケースでは計算が異なります。どうすればいいですか？

Java を使用してリザーバー サンプリング アルゴリズムを実装しようとしています。サイズが不明な N 個のデータ ストリーム (シンク ノードに到着するセンサーからの読み取り値) があります。簡単にするために、未知のサイズのストリームが 1 つあると仮定します。

したがって、リザーバー サンプリング アルゴリズムの 1 つが示唆するのは、サイズのリザーバーを作成することです。5 としましょう。取得した最初の 5 つの測定値をリザーバーに保存します。Ok。より多くの読み取り値を取得すると、読み取り値ごとに 0 から読み取り番号までの乱数が生成され、その乱数がリザーバー サイズよりも小さい場合は、読み取り値がリザーバー [randomNumber] に格納されます。

たとえば、reservoirSize = 5 で、10 回目の測定値を取得したとします。0 から 10 までの乱数を生成し、その数が 5 より小さい場合は、乱数が指す場所に読み取り値を保存します。乱数が 3 であるとしましょう。したがって、読み取り番号 10 をリザーバー [3] に保存します。

このコードの問題は、streamIndex が十分に大きくなると (たとえば 4.000 を超える)、読み取り値をほとんどサンプリングしないことです。5 より小さい 0 から 4000 までの乱数を生成する確率は、5 より小さい 0 から 100 までの乱数を生成する確率よりも大幅に小さいため、これは理にかなっています。

また、Vitters の論文から AlgorthmR を実装し、ここで説明する別の方法を実装しました:
Gregable ReservoirSampling

しかし、すべての実装には同じ問題があります。ストリームが大きくなるほど、サンプリング周波数は小さくなります。したがって、0.5 秒のサンプリング レートの場合、サンプリングを開始してから 1 時間後 (つまり、約 7000 の読み取り値がシンク ノードに転送されたことを意味します)、測定量の変化は、さらに 30 分ほど検出されません。変更がリザーバーから破棄されることを示します。

アルゴリズムの実装

グレガブル実装

それはアルゴリズムの通常の動作ですか、それともここで何か不足していますか? それが通常の動作である場合、それをより「正確に」機能させる方法はありますか?

明確にするために、次の質問があります。

不確定な長さの入力ストリームが与えられた場合、一定数以上の入力を格納することは許可されておらず、通過することしかできない場合、そのストリームのランダムなメンバーを (それぞれの確率で) どのように返すのですか?入力を一度

この問題の解決策は Reservoir Sampling であると思われ、以下に記載されています。「最初に、1,000 要素のリザーバー (配列) を作成し、ストリーム内の最初の 1,000 要素で埋めます。そうすれば、正確に 1,000 要素がある場合、アルゴリズムは機能します。これが基本ケースです。

次に、i 番目の要素 (i = 1,001 から開始) を処理して、そのステップの処理の最後に、リザーバー内の 1,000 要素が、これまでに見た i 要素の中からランダムにサンプリングされるようにします。どうすればこれを行うことができますか？i = 1,001 から始めます。1001 番目のステップの後、要素 1,001 (またはその要素) が 1,000 個の要素のセットに含まれる確率はどれくらいですか? 答えは簡単です。1,000/1,001 です。」

最後の文「答えは簡単です: 1,000/1,001」が理解できません。1001 要素の配列で 1 つの要素を見つける確率は、1000/1001 ではなく 1/1001 であってはなりませんか? Sample space は 1001 に等しく、結果の好ましい数は 1 に等しくありませんか?