随机选择频率项的高效算法

这听起来像轮盘赌,主要用于遗传/进化算法中的选择过程。

看 Roulette Selection in Genetic Algorithms

您可以创建目标数组,然后通过单词循环确定它应该被选取的概率,并根据随机数替换数组中的单词。

第一个词的概率是f。 _零 /m _零 (M) _n = f _零 +++f _n ,即100%,因此目标阵列中的所有位置都将填充w _零 .

对于下面的单词,概率下降,当您到达最后一个单词时,目标数组将填充随机选取的符合频率的单词。

C中的示例代码:

public class WordFrequency {

    public string Word { get; private set; }
    public int Frequency { get; private set; }

    public WordFrequency(string word, int frequency) {
        Word = word;
        Frequency = frequency;
    }

}

WordFrequency[] words = new WordFrequency[] {
    new WordFrequency("Hero", 80),
    new WordFrequency("Monkey", 4),
    new WordFrequency("Shoe", 13),
    new WordFrequency("Highway", 3),
};

int p = 7;
string[] result = new string[p];
int sum = 0;
Random rnd = new Random();
foreach (WordFrequency wf in words) {
    sum += wf.Frequency;
    for (int i = 0; i < p; i++) {
        if (rnd.Next(sum) < wf.Frequency) {
            result[i] = wf.Word;
        }
    }
}

好的,我找到了另一个算法: the alias method (也提到) in this answer )基本上,它创建了概率空间的一个划分,这样:

• 有 n 相同宽度的隔墙 r S.T. nr = m .
• 每个分区以一定的比例包含两个单词(与分区一起存储)。
• 每个词 w i , f i = ∑ partitions t s.t w i ∈ t r × ratio(t,w i )

因为所有分区的大小都相同,所以选择可以在恒定工作中完成的分区(从 0...n-1 然后,可以使用分区的比率来选择在常量工作中使用的单词(将带引号的数字与两个单词之间的比率进行比较)。所以这意味着 p 选择可以在 O(p) 工作,给这样一个分区。

这种分区存在的原因是存在一个词 W 我 S.T. f i < r ,如果且仅当存在一个词时 w i' S.T. f i' > r ,因为r是频率的平均值。

给这样一对 W 我 和 W 我 我们可以用一个伪词来代替它们 w' i 频率的 f' i = r (代表 W 我 有概率的 f i /r 和 W 我 有概率的 1 - f i /r )还有一个新词 w' i' 调整频率 f' i' = f i' - (r - f i ) 分别。所有单词的平均频率仍然是r,并且上一段的规则仍然适用。由于伪词具有频率r,由频率≠r的两个词组成,我们知道如果我们迭代这个过程,我们将永远不会从伪词中生成一个伪词,这样的迭代必须以N个伪词序列结束,这是所需的分区。

在中构造此分区 O(n) 时间,

• 将单词列表浏览一次,构建两个列表:
  • 频率≤r的单词之一
  • 频率为>r的单词之一
• 然后从第一个列表中抽出一个词
  • 如果其频率=r,则将其划分为一个元素分区
  • 否则,从另一个列表中拉出一个单词,并使用它来填充两个单词的分区。然后根据调整后的频率将第二个单词放回第一个或第二个列表中。

如果分区数为 q > n (你只需要用不同的方式证明)。如果你想确定r是积分的,你不容易找到一个因子 q 属于 m S.T. Q&GN ,您可以将所有频率加上一个系数 n 如此 f' i = nf i 更新 m' = mn 集 r' = m 什么时候? q = n .

在任何情况下,该算法只需要 O(n + p) 工作,我认为这是最好的。

红宝石:

def weighted_sample_with_replacement(input, p)
  n = input.size
  m = input.inject(0) { |sum,(word,freq)| sum + freq }

  # find the words with frequency lesser and greater than average
  lessers, greaters = input.map do |word,freq| 
                        # pad the frequency so we can keep it integral
                        # when subdivided
                        [ word, freq*n ] 
                      end.partition do |word,adj_freq| 
                        adj_freq <= m 
                      end

  partitions = Array.new(n) do
    word, adj_freq = lessers.shift

    other_word = if adj_freq < m
                   # use part of another word's frequency to pad
                   # out the partition
                   other_word, other_adj_freq = greaters.shift
                   other_adj_freq -= (m - adj_freq)
                   (other_adj_freq <= m ? lessers : greaters) << [ other_word, other_adj_freq ]
                   other_word
                 end

    [ word, other_word , adj_freq ]
  end

  (0...p).map do 
    # pick a partition at random
    word, other_word, adj_freq = partitions[ rand(n) ]
    # select the first word in the partition with appropriate
    # probability
    if rand(m) < adj_freq
      word
    else
      other_word
    end
  end
end