加重リザーバサンプリングのアルゴリズムはありますか

データストリーム内のポイントに関連するウェイトがある場合、リザーバサンプリングを実行するアルゴリズムはありますか？加重リザーバサンプリングのアルゴリズムはありますか

2013-06-14 Budhapest

も広すぎますか？私は質問が非常に特殊なアルゴリズムを求めていると思う。 –

完全に@ JuanA.Navarroに同意します - この質問はストリームや並列処理には非常に便利で、再オープンする必要があります（彼の答えも非常に良いです）。 –

アルゴリズムは、まさにこの問題を解決します。完全な校正を行った原著論文は、2006年情報処理学会レターに「貯留層を用いた無作為抽出サンプリング」というタイトルで出版されていますが、簡単な要約hereがあります。

アルゴリズムは次のように動作します。重み付けされていないリザーバのサンプリングを解決する別の方法は、各要素に0と1の間のランダムなID Rを割り当て、インクリメンタルに（ヒープを使用して）上位k個のIDを追跡することです。今度は加重バージョンを見て、i番目の要素に重みw_iがあるとしましょう。次に、i番目の要素のidをR ^（1/w_i）とすることでアルゴリズムを修正する。ここでRは（0,1）に一様に分布する。

このアルゴリズムに関するもう1つの記事は、Clouderaの人々によってthis oneです。

出典

2013-08-16 21:30:22 had00b

そして、1行のpythonの実装： 'heapq.nlargest（k、items、key = lambda item：math.pow（random.random（）、1/weight（item）））' –

これを置き換えることで可能ですか？？ – eleanora

@eleanoraエイリアスメソッドが存在するので、O（n）時間後に各選択がO（1）であるテーブルを最初に作成する必要があるため、置換でこれを行うことには意味がありません。ただし、エイリアスを使用しない限り、エイリアスは実行時の複雑さを選択しません。 – snb

this paper of S. EfraimidisからA-ESアルゴリズムを試すことができます。コード化が非常に簡単で効率的です。このことができます

希望、Pavlos EfraimidisとポールSpirakisによって

ブノワ

出典

2013-07-18 13:09:22 bmat06

加重リザーバサンプリングのアルゴリズムはありますか

答えて

関連する問題