75

重みなし (等確率) の選択については、ここで美しく説明されています。

このアプローチを加重アプローチに変換する方法があるかどうか疑問に思っていました。

他のアプローチにも興味があります。

更新:置換なしのサンプリング

4

14 に答える 14

44

サンプリングに置換を使用する場合は、ルーレット ホイール選択手法を使用します (遺伝的アルゴリズムでよく使用されます)。

  1. ウェイトを並べ替える
  2. 累積重みを計算する
  3. で乱数を選ぶ[0,1]*totalWeight
  4. この数が入る間隔を見つけます
  5. 対応する間隔で要素を選択します
  6. 繰り返しk回数

代替テキスト

サンプリングが置換なしの場合、各繰り返しの後に選択した要素をリストから削除し、合計が 1 になるように重みを再正規化することにより、上記の手法を適応させることができます (有効な確率分布関数)。

于 2010-01-28T02:24:34.820 に答える
31

私はこれが非常に古い質問であることを知っていますが、少し数学を適用すると、O(n) 時間でこれを行うための巧妙なトリックがあると思います!

指数分布には、非常に役立つ 2 つの特性があります。

  1. 異なるレート パラメータを持つ異なる指数分布からの n 個のサンプルが与えられた場合、特定のサンプルが最小である確率は、そのレート パラメータをすべてのレート パラメータの合計で割った値に等しくなります。

  2. 「無記憶」です。したがって、最小値が既にわかっている場合、残りの要素のいずれかが 2 番目から最小である確率は、真の最小値が削除された (そして生成されなかった) 場合にその要素が新しいものであった確率と同じです。分。これは明らかなように思えますが、条件付き確率の問題があるため、他の分布には当てはまらない可能性があると思います。

事実 1 を使用すると、単一の要素を選択するには、これらの指数分布サンプルを重みに等しいレート パラメータで生成し、最小値を持つものを選択することで実行できることがわかります。

事実 2 を使用すると、指数サンプルを再生成する必要がないことがわかります。代わりに、要素ごとに 1 つ生成し、サンプル数が最も少ない k 個の要素を取得します。

最小の k を見つけることは、O(n) で行うことができます。Quickselectアルゴリズムを使用して k 番目の要素を見つけ、すべての要素をもう一度パスして、k 番目よりも低いすべての要素を出力します。

有用なメモ: 指数分布サンプルを生成するライブラリにすぐにアクセスできない場合は、次の方法で簡単に実行できます。-ln(rand())/weight

于 2015-05-13T23:35:07.377 に答える
3

私はRubyでこれをやった

https://github.com/fl00r/pickup

require 'pickup'
pond = {
  "selmon"  => 1,
  "carp" => 4,
  "crucian"  => 3,
  "herring" => 6,
  "sturgeon" => 8,
  "gudgeon" => 10,
  "minnow" => 20
}
pickup = Pickup.new(pond, uniq: true)
pickup.pick(3)
#=> [ "gudgeon", "herring", "minnow" ]
pickup.pick
#=> "herring"
pickup.pick
#=> "gudgeon"
pickup.pick
#=> "sturgeon"
于 2012-06-01T18:07:28.697 に答える
1

geodnsからの Go 実装は次のとおりです。

package foo

import (
    "log"
    "math/rand"
)

type server struct {
    Weight int
    data   interface{}
}

func foo(servers []server) {
    // servers list is already sorted by the Weight attribute

    // number of items to pick
    max := 4

    result := make([]server, max)

    sum := 0
    for _, r := range servers {
        sum += r.Weight
    }

    for si := 0; si < max; si++ {
        n := rand.Intn(sum + 1)
        s := 0

        for i := range servers {
            s += int(servers[i].Weight)
            if s >= n {
                log.Println("Picked record", i, servers[i])
                sum -= servers[i].Weight
                result[si] = servers[i]

                // remove the server from the list
                servers = append(servers[:i], servers[i+1:]...)
                break
            }
        }
    }

    return result
}
于 2012-08-26T07:55:43.493 に答える
1

replacement を使用してランダムな整数の大きな配列を生成する場合は、区分的線形補間を使用できます。たとえば、NumPy/SciPy を使用する場合:

import numpy
import scipy.interpolate

def weighted_randint(weights, size=None):
    """Given an n-element vector of weights, randomly sample
    integers up to n with probabilities proportional to weights"""
    n = weights.size
    # normalize so that the weights sum to unity
    weights = weights / numpy.linalg.norm(weights, 1)
    # cumulative sum of weights
    cumulative_weights = weights.cumsum()
    # piecewise-linear interpolating function whose domain is
    # the unit interval and whose range is the integers up to n
    f = scipy.interpolate.interp1d(
            numpy.hstack((0.0, weights)),
            numpy.arange(n + 1), kind='linear')
    return f(numpy.random.random(size=size)).astype(int)

置換せずにサンプリングしたい場合、これは効果的ではありません。

于 2011-05-10T00:15:01.393 に答える
0

これはまさにそれを O(n) で行い、余分なメモリを使用しません。これは、どの言語にも簡単に移植できる巧妙で効率的なソリューションだと思います。最初の 2 行は、Drupal にサンプル データを入力するためのものです。

function getNrandomGuysWithWeight($numitems){
  $q = db_query('SELECT id, weight FROM theTableWithTheData');
  $q = $q->fetchAll();

  $accum = 0;
  foreach($q as $r){
    $accum += $r->weight;
    $r->weight = $accum;
  }

  $out = array();

  while(count($out) < $numitems && count($q)){
    $n = rand(0,$accum);
    $lessaccum = NULL;
    $prevaccum = 0;
    $idxrm = 0;
    foreach($q as $i=>$r){
      if(($lessaccum == NULL) && ($n <= $r->weight)){
        $out[] = $r->id;
        $lessaccum = $r->weight- $prevaccum;
        $accum -= $lessaccum;
        $idxrm = $i;
      }else if($lessaccum){
        $r->weight -= $lessaccum;
      }
      $prevaccum = $r->weight;
    }
    unset($q[$idxrm]);
  }
  return $out;
}
于 2013-08-14T22:28:23.383 に答える
0

あなたがリンクした質問では、カイルの解決策は些細な一般化で機能します。リストをスキャンして、合計重量を合計します。次に、要素を選択する確率は次のようになります。

1 - (1 - (#needed/(残りの重量)))/(n での重量)。ノードを訪問した後、合計からその重みを引きます。また、n が必要で n が残っている場合は、明示的に停止する必要があります。

すべての重みが 1 であることを確認できます。これにより、カイルのソリューションが単純化されます。

編集：（2倍の可能性が意味することを再考する必要がありました）

于 2010-01-26T16:51:22.420 に答える
0

ここでは、1 つのアイテムを選択するための簡単なソリューションを示します。k 個のアイテムに簡単に拡張できます (Java スタイル)。

double random = Math.random();
double sum = 0;
for (int i = 0; i < items.length; i++) {
    val = items[i];
    sum += val.getValue();
    if (sum > random) {
        selected = val;
        break;
    }
}
于 2014-01-29T16:13:13.653 に答える
-2

連想マップ (ウェイト、オブジェクト) を使用しました。例えば：

{
(10,"low"),
(100,"mid"),
(10000,"large")
}

total=10110

0 から 'total' までの乱数をピークし、この数が指定された範囲に収まるまでキーを反復処理します。

于 2010-01-26T16:36:57.787 に答える