51

最近、置換の有無にかかわらず、リストから要素を加重ランダムに選択する必要がありました。重み付けされていない選択にはよく知られた優れたアルゴリズムがあり、置換なしの重み付けされた選択 (resevoir アルゴリズムの変更など) もありますが、置換を使用した重み付けされた選択に適したアルゴリズムは見つかりませんでした。また、メモリに保持するのに十分小さいリストのかなりの部分を選択していたので、resevoir メソッドを避けたかったのです。

この状況での最善のアプローチについて何か提案はありますか? 私には独自の解決策がありますが、より効率的でシンプルなもの、またはその両方を見つけたいと思っています。

4

9 に答える 9

33

変更されていないリストから置換サンプルを使用して多くを作成する最速の方法の 1 つは、エイリアス メソッドです。中核となる直感は、バイナリ検索を回避するために、ビット操作によって非常に効率的にインデックス付けできる加重リスト用の一連の等しいサイズのビンを作成できるということです。正しく行えば、ビンごとに元のリストから 2 つの項目を保存するだけで済み、分割を 1 つのパーセンテージで表すことができることがわかります。

均等に重み付けされた 5 つの選択肢の例を見てみましょう。(a:1, b:1, c:1, d:1, e:1)

エイリアスルックアップを作成するには:

  1. 合計が になるように重みを正規化し1.0ます。 (a:0.2 b:0.2 c:0.2 d:0.2 e:0.2) これは、各重みを選択する確率です。

  2. 変数の数以上の最小の 2 の累乗を見つけ、この数の分割を作成します|p|。各分割は の確率質量を表し1/|p|ます。この場合、8それぞれが を含むことができるパーティションを作成します0.125。

  3. 残りの重みが最も少ない変数を取り、その質量のできるだけ多くを空のパーティションに配置します。aこの例では、最初のパーティションがいっぱいになって いることがわかります。(p1{a|null,1.0},p2,p3,p4,p5,p6,p7,p8)と(a:0.075, b:0.2 c:0.2 d:0.2 e:0.2)

  4. パーティションが満たされていない場合は、重みが最も大きい変数を取得し、その変数でパーティションを埋めます。

元のパーティションの重みをリストに割り当てる必要がなくなるまで、手順 3 と 4 を繰り返します。

たとえば、3 と 4 の別の反復を実行すると、

(p1{a|null,1.0},p2{a|b,0.6},p3,p4,p5,p6,p7,p8)残り(a:0, b:0.15 c:0.2 d:0.2 e:0.2)は割り当てられます

実行時:

  1. U(0,1)バイナリなどの乱数を取得する0.001100000

  2. それをビットシフトしてlg2(p)、インデックスパーティションを見つけます。したがって、3、 yielding 001.1、または位置 1、したがってパーティション 2 だけシフトします。

  3. パーティションが分割されている場合は、シフトされた乱数の小数部分を使用して分割を決定します。この場合、値は0.5、および0.5 < 0.6であるため、 を返しaます。

ここにいくつかのコードと別の説明がありますが、残念ながらビットシフト技術を使用しておらず、実際に検証していません.

于 2008-12-09T17:27:01.697 に答える
5

置換なしの加重選択について私が思いついたのは次のとおりです。

def WeightedSelectionWithoutReplacement(l, n):
  """Selects without replacement n random elements from a list of (weight, item) tuples."""
  l = sorted((random.random() * x[0], x[1]) for x in l)
  return l[-n:]

これは、選択されるリスト内のアイテムの数で O(m log m) です。正式な意味での検証はしていませんが、これがアイテムの重み付けを正しく行うことはかなり確信しています。

置換による加重選択について私が思いついたのは次のとおりです。

def WeightedSelectionWithReplacement(l, n):
  """Selects with replacement n random elements from a list of (weight, item) tuples."""
  cuml = []
  total_weight = 0.0
  for weight, item in l:
    total_weight += weight
    cuml.append((total_weight, item))
  return [cuml[bisect.bisect(cuml, random.random()*total_weight)] for x in range(n)]

これは O(m + n log m) です。ここで、m は入力リスト内のアイテムの数であり、n は選択されるアイテムの数です。

于 2008-12-09T17:06:26.310 に答える
4

以下は、O（n）空間とO（log n）時間での置換がある場合とない場合の両方で、セット（または繰り返しが許可されている場合はマルチセット）の要素のランダムに重み付けされた選択の説明です。

これは、選択する要素でソートされたバイナリ検索ツリーの実装で構成され、ツリーの各ノードには次のものが含まれます。

  1. 要素自体（要素）
  2. 要素の正規化されていない重み（elementweight）、および
  3. 左子ノードとそのすべての子の正規化されていないすべての重みの合計（leftbranchweight）。
  4. 右子ノードとそのすべての子の正規化されていないすべての重みの合計（rightbranchweight）。

次に、ツリーを下に移動して、BSTから要素をランダムに選択します。アルゴリズムの大まかな説明は次のとおりです。アルゴリズムにはツリーのノードが与えられます。次に、ノードのleftbranchweight、rightbranchweight、およびelementweightの値が合計され、重みがこの合計で除算されて、それぞれ、 leftbranchprobability、 rightbranchprobability、およびelementprobabilityの値になります。次に、0から1までの乱数（乱数）が取得されます。

  • 数が要素確率よりも小さい場合、
    • 通常どおりBSTから要素を削除し、必要なすべてのノードのleftbranchweight とrightbranchweightを更新して、要素を返します。
  • それ以外の場合、数が（ elementprobability + leftbranchweight） 未満の場合
    • 左子で再帰（左子をノードとして使用してアルゴリズムを実行します）
  • そうしないと
    • 右子に再帰

最終的に、返される要素であるこれらの重みを使用して、それを返す（置換あり）か、削除してツリー内の関連する重みを更新する（置換なし）かのいずれかを最終的に見つけます。

免責事項：アルゴリズムは大まかなものであり、BSTの適切な実装に関する論文はここでは試みられていません。むしろ、この回答が、（私のように）置き換えなしで高速加重選択を本当に必要とする人々に役立つことが期待されています。

于 2012-03-22T17:07:26.813 に答える
4

Donald Knuth のSeminumerical Algorithmsのセクション 3.4.2 を見ることから始めることをお勧めします。

配列が大きい場合は、John Dagpunar によるPrinciples of Random Variate Generation の第 3 章に、より効率的なアルゴリズムがあります。配列がそれほど大きくない場合、またはできるだけ多くの効率を絞り出すことに関心がない場合は、Knuth のより単純なアルゴリズムでおそらく問題ありません。

于 2008-12-09T13:43:46.000 に答える
4

最初に O(N) 時間で追加の O(N) サイズのデータ​​構造を作成した後、O(1) 時間で置換を伴う加重ランダム選択を行うことができます。このアルゴリズムは、Walker と Vose によって開発されたAlias Methodに基づいています。これについては、こちらで詳しく説明しています。

本質的な考え方は、ヒストグラムの各ビンが一様な RNG によって確率 1/N で選択されるということです。そのため、それを詳しく説明し、過剰なヒットを受け取る人口の少ないビンについては、過剰なヒットを人口の多いビンに割り当てます。ビンごとに、それに属するヒットのパーセンテージと、超過分のパートナー ビンを保存します。このバージョンは、大小のビンを所定の位置で追跡し、追加のスタックの必要性を取り除きます。パートナーのインデックス ( に格納されてbucket[1]いる) を、パートナーが既に処理されていることを示す指標として使用します。

これは、C 実装 hereに基づいた、最小限の Python 実装です。

def prep(weights):
    data_sz = len(weights)
    factor = data_sz/float(sum(weights))
    data = [[w*factor, i] for i,w in enumerate(weights)]
    big=0
    while big<data_sz and data[big][0]<=1.0: big+=1
    for small,bucket in enumerate(data):
        if bucket[1] is not small: continue
        excess = 1.0 - bucket[0]
        while excess > 0:
            if big==data_sz: break
            bucket[1] = big
            bucket = data[big]
            bucket[0] -= excess
            excess = 1.0 - bucket[0]
            if (excess >= 0):
                big+=1
                while big<data_sz and data[big][0]<=1: big+=1
    return data

def sample(data):
    r=random.random()*len(data)
    idx = int(r)
    return data[idx][1] if r-idx > data[idx][0] else idx

使用例:

TRIALS=1000
weights = [20,1.5,9.8,10,15,10,15.5,10,8,.2];
samples = [0]*len(weights)
data = prep(weights)

for _ in range(int(sum(weights)*TRIALS)):
    samples[sample(data)]+=1

result = [float(s)/TRIALS for s in samples]
err = [a-b for a,b in zip(result,weights)]
print(result)
print([round(e,5) for e in err])
print(sum([e*e for e in err]))
于 2015-04-18T20:07:58.990 に答える
0

リスト ['white','blue','black','yellow','green'] から置換なしで 3 つの要素を prob でサンプリングしたいとします。分布 [0.1、0.2、0.4、0.1、0.2]。numpy.random モジュールを使用すると、次のように簡単になります。

    import numpy.random as rnd

    sampling_size = 3
    domain = ['white','blue','black','yellow','green']
    probs = [.1, .2, .4, .1, .2]
    sample = rnd.choice(domain, size=sampling_size, replace=False, p=probs)
    # in short: rnd.choice(domain, sampling_size, False, probs)
    print(sample)
    # Possible output: ['white' 'black' 'blue']

replaceフラグをに設定するTrueと、置換ありのサンプリングが行われます。

詳細はこちら: http://docs.scipy.org/doc/numpy/reference/generated/numpy.random.choice.html#numpy.random.choice

于 2016-10-16T15:07:49.500 に答える