根据每个项的概率从列表中选择随机项

Question

根据每个项的概率从列表中选择随机项

3

抱歉标题表述不太清楚...... 我有一个名为NGram的对象。

class NGram
{
     //other properties
     double Probability {get; set;} //Value between 1 and 0 
}

现在假设我有一个这些对象的列表，例如...

List<NGrams> grams = GetNGrams();
Debug.Assert(grams.Sum(x => x.Probability) == 1);

如何在考虑概率分布的情况下从列表中选择一个随机项。

例如，假设grams [0] .Probability == 0.5，则选择grams [0]的概率应为50％。

我想我可能需要像rand.NextDouble()这样的东西，但我不知道该怎么做。

- William

你想根据它们的概率值进行选择吗？ - Arthur Putnam

4个回答

2

按概率升序排序列表。

对列表中所有元素的概率字段求和。将其称为总和 P。

获取介于 [0，P] 之间的随机数，称其为 r。

在迭代列表时，保持 Probability 累加值（pe）到当前正在迭代的元素。当找到第一个满足 pe >= r 的元素时，结束搜索。

现在，数组中所有元素都相加为1的情况只是一种特殊情况 :)

- Ricardo Amores

2

谢谢。我按照您说的实现了，但是我注意到了这个问题：假设我生成了一个0.955的随机数。列表中没有任何一个项目的概率为0.955，因此在这种情况下Probability value >= r永远不会成立。 - William

忘了说，在迭代时应累积概率，让我重新审查一下。 - Ricardo Amores

1

好的，已经使用正确的算法进行了编辑。当使用累积概率检查随机值时，您不会遇到您指出的问题。 - Ricardo Amores

不需要排序 https://dotnetfiddle.net/GANFnq - Kelly Elton

1

在伪代码中

r = Get a random number between 0 and 1
sum = 0
i = 0
Loop  
    sum = sum + grams[i].Probability  
    If sum >= r Then  
        Exit Loop
    End
    i = i + 1  
End
i is the index of the random item in the list

这个想法是将项目的概率相加，直到总和大于或等于一个随机数。由于概率总和为1且随机数在0..1范围内，因此无论如何都会找到一个项目。概率较大的项目更有可能被选择。

∑P= 0 0.08     0.3 0.43 0.53          0.88  1
    +--+--------+----+---+-------------+----+
    |  |        |    |   |             |    |
    +--+--------+----+---+-------------+----+ 
i =  0      1      2   3       4         5

您可以将每个项目想象成其分配概率相等的长度。该算法就像是在长度为1的标尺上随机投掷飞镖，所有概率都沿着标尺堆叠。被命中的项目的概率与其大小（即其分配概率）成比例。

- Olivier Jacot-Descombes

1

假设您有这样的数据{0.7，0.15，0.15}，这个算法是否有效？ - Fatih Türker

@FatihTürker 是的，它确实可以。 - Kelly Elton

@FatihTürker：该算法不需要按任何方式对概率进行排序。您可以将其想象为一个目标。您从远处随机方向射击。特定矩形被命中的概率与其面积成比例，我们使这些区域与给定的概率成比例。 - Olivier Jacot-Descombes

1

试试这个：

List<NGram> grams = new List<NGram>()
{
    new NGram() { Probability = 0.5 },
    new NGram() { Probability = 0.35 },
    new NGram() { Probability = 0.15 }
};

var rnd = new Random();

var result =
    grams
        .Aggregate(
            new { sum = 0.0, target = rnd.NextDouble(), gram = (NGram)null },
            (a, g) =>
                a.gram == null && a.sum + g.Probability >= a.target
                    ? new { sum = a.sum + g.Probability, a.target, gram = g }
                    : new { sum = a.sum + g.Probability, a.target, a.gram });

它给我这样的结果：

- Enigmativity

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- D Stanley · Accepted Answer

这里有一种更通用的方法（意味着您不需要断言概率总和为1）：

static Random rand = new Random();

public NGram GetRandom(IEnumerable<NGram> pool)
{
     // get universal probability 
     double u = pool.Sum (p => p.Probability);

     // pick a random number between 0 and u
     double r = rand.NextDouble() * u;

     double sum = 0;
     foreach(NGram n in pool)
     {
         // loop until the random number is less than our cumulative probability
         if(r <= (sum = sum + n.Probability))
         {
            return n;
         }
     }
     // should never get here
     return null;
}