1

インタビューの1つで尋ねられたQに出くわしました..

Q - 非常に大量のデータ要素 (5 月の Google 検索でのクエリ、クリスマス シーズンにウォルマートで購入した製品、電話帳の名前など) が与えられたと想像してください。目標は、元のストリームから均等に分散された 1,000 要素のランダム サンプルを効率的に返すことです。どのようにしますか？

を探しています -

  1. データ セットのランダム サンプリングとはどういう意味ですか? (つまり、結果が 1 の場合、単純にコイントスを実行して入力から文字列を選択し、1000 個のサンプルが得られるまでこれを実行できます..)
  2. その際、何を考慮する必要がありますか? たとえば..連続していない文字列よりも、連続した文字列を取得する方が良い場合があります..言い換えると、連続する1000個の文字列をランダムに選択した方が良いですか..または、コイントスのように一度に1つの文字列を選択する方が良いですか..

これは漠然とした質問かもしれません..「ランダムにサンプルデータセット」をグーグルで検索しようとしましたが、関連する結果が見つかりませんでした.

4

3 に答える 3

1

私が知っているように、そのようなアルゴリズムのクラスは、貯水池サンプリング アルゴリズムと呼ばれます。

私はDataMiningからそれの1つを知っていますが、その名前は知りません:

  1. max.size が S に等しいストレージ内の最初の S 要素を収集します。
  2. ストリームの次の要素の番号が N であるとします。
  3. 確率 S/N で新しい要素をキャッチし、そうでない場合は破棄します
  4. 要素 N をキャッチした場合は、sameple S 内の要素の 1 つを置き換えて、それを均一に選択します。
  5. N=N+1、次の要素を取得、1 に移動

このようなストリーム処理の任意のステップで、サイズ S のストレージに S/N_you_have_seen の確率が等しい要素が含まれていることを理論的に証明できます。

たとえば、S=10;

N_you_have_seen=10^6

S - 有限数です。N_you_have_seen - 無限の可能性があります。

于 2014-04-20T17:00:59.713 に答える