0

このリンク「http://had00b.blogspot.com/2013/07/random-subset-in-mapreduce.html」では、マップ削減フレームワークを使用して貯水池サンプリングを実装する方法について説明しています。彼らの解決策は複雑で、次のより単純なアプローチがうまくいくと思います。

問題: 非常に多数のサンプルが与えられた場合、各サンプルがセット内に存在する確率が等しくなるように、サイズ k のセットを生成します。

提案された解決策:

  1. マップ操作: 各入力番号 n に対して、(i, n) を出力します。ここで、i は 0 から k-1 の範囲でランダムに選択されます。
  2. リデュース操作: 同じキーを持つすべての数字の中から、ランダムに 1 つを選択します。

主張: k サイズのセットに任意の数が含まれる確率は k/n (n はサンプルの総数)

直観の証明:

マップ操作では、各入力サンプルがバケット番号 i (0 <= i <= k-1) にランダムに割り当てられるため、各バケットのサイズは n/k になります。ここで、各数値は 1 つのバケットにのみ存在します。バケット i とします。バケット i の削減操作で選択される確率は、1/(n/k) = k/n です。

それが正しいように見えるかどうかにかかわらず、私の解決策について考え直していただければ幸いです。

4

1 に答える 1

3

あなたの主張には小さな欠陥があります。アルゴリズムがサイズ k のサンプルを返さない場合があります。これは、どの要素も特定のキーにマップされないことがあるからです。極端な場合 (可能性が低い場合でも)、すべての入力要素が 1 つのキーのみにマップされる可能性があります。この場合、アルゴリズムは 1 つの要素のみを返します。

特定のキーが「見つからない」というイベントには、確率 ((k-1)/k)^n = (1-1/k)^n があり、これは (テイラー近似を使用して) e^{-n/k} とほぼ同じです。k が n よりもはるかに小さい場合、これは無視できますが、k が n に比例する場合、たとえば k=n/2 の場合、この悪いイベントは実際には一定の確率で発生します。

于 2013-08-11T00:24:15.037 に答える