从给定每个项目概率的列表中选择随机项目
Selecting Random Item from List given probability of each item
抱歉标题措辞不当....
我有一个 object 叫做 NGram
class NGram
{
//other properties
double Probability {get; set;} //Value between 1 and 0
}
现在假设我有这些 object 的列表,这样...
List<NGrams> grams = GetNGrams();
Debug.Assert(grams.Sum(x => x.Probability) == 1);
我如何 select 从这个列表中随机选择一个项目,同时考虑概率分布。
例如,假设 grams[0].Probability == 0.5
那么应该有 50% 的机会 selecting grams[0]
我想我可能需要类似 rand.NextDouble()
的东西,但我不知所措。
对列表进行排序,按概率升序排列。
对列表中所有元素的概率字段求和。我们称这个和为 P.
得到一个介于[0,P]之间的随机数,我们称它为r
迭代列表,同时将概率总和的累加值保留到您正在迭代的当前元素 (pe)。当找到第一个 pe >= r
的元素时结束搜索
数组中所有元素求和1的情况现在只是一个特例:)
这是一种更通用的方法(意味着您不需要需要断言概率加起来为 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;
}
在伪代码中
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 的尺子投掷飞镖,所有概率都沿着尺子叠加。一个项目被击中的概率与其大小成正比(即它的分配概率)。
试试这个:
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 });
它给了我这样的结果:
抱歉标题措辞不当....
我有一个 object 叫做 NGram
class NGram
{
//other properties
double Probability {get; set;} //Value between 1 and 0
}
现在假设我有这些 object 的列表,这样...
List<NGrams> grams = GetNGrams();
Debug.Assert(grams.Sum(x => x.Probability) == 1);
我如何 select 从这个列表中随机选择一个项目,同时考虑概率分布。
例如,假设 grams[0].Probability == 0.5
那么应该有 50% 的机会 selecting grams[0]
我想我可能需要类似 rand.NextDouble()
的东西,但我不知所措。
对列表进行排序,按概率升序排列。
对列表中所有元素的概率字段求和。我们称这个和为 P.
得到一个介于[0,P]之间的随机数,我们称它为r
迭代列表,同时将概率总和的累加值保留到您正在迭代的当前元素 (pe)。当找到第一个 pe >= r
的元素时结束搜索数组中所有元素求和1的情况现在只是一个特例:)
这是一种更通用的方法(意味着您不需要需要断言概率加起来为 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;
}
在伪代码中
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 的尺子投掷飞镖,所有概率都沿着尺子叠加。一个项目被击中的概率与其大小成正比(即它的分配概率)。
试试这个:
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 });
它给了我这样的结果: