Вопросы Теги

Эффективный алгоритм для случайного выбора объектов с частотой

Я создаю каталог журналов в / usr / local / hadoop и предоставляю разрешение моей учетной записи hadoop. 

/usr/local/hadoop$ sudo mkdir logs
/usr/local/hadoop$ sudo chown -R hadoop logs
10
задан kcwu 18 May 2009 в 03:47
поделиться

3 ответа

Хорошо, я нашел другой алгоритм: метод псевдонима (также упоминается в этом ответе ). По сути, он создает такое разделение вероятностного пространства, что:

  • Есть n разделов, все одинаковой ширины r st nr = m .
  • каждый раздел содержит два слова в некотором соотношении (которое сохраняется вместе с разделом).
  • для каждого слова w i , f i = ∑ разделы t st w i ∈ t r × ratio (t, w i )

Поскольку все разделы имеют одинаковый размер, выбор разделение может выполняться в постоянной работе (выберите случайным образом индекс из 0 ... n-1 ), а затем можно использовать коэффициент раздела, чтобы выбрать, какое слово будет использоваться в постоянной работе (сравните значение pRNGed число с соотношением между двумя словами). Таким образом, это означает, что выбор p может быть выполнен в O (p) работе с таким разделом.

Причина, по которой такое разделение существует, состоит в том, что существует слово w i st f i , тогда и только тогда, когда существует слово w i ' st f i' > r , поскольку r - это среднее значение частот.

Для такой пары w i и w i ' мы можем заменить их псевдословом w' i частоты f ' i = r (что представляет w i с вероятностью f i / r и w i ' с вероятностью 1 - f i / r ) и новое слово w' i ' настроенной частоты f' i ' = f i' - (r - f i ) соответственно. Средняя частота всех слов по-прежнему будет r, и по-прежнему действует правило из предыдущего абзаца.

  • одно из слов с частотой ≤ r
  • одно из слов с частотой> r
  • затем вытащить слово из первого списка
    • , если его частота = r, то превратить его в одноэлементный раздел
    • в противном случае, извлечь слово из другого списка и использовать его для заполнения двухсловного раздела. Затем поместите второе слово обратно в первый или второй список в соответствии с его настроенной частотой.

    • Это действительно работает, если количество разделов q> n (вам просто нужно доказать это по-другому). Если вы хотите убедиться, что r является целым, и вы не можете легко найти множитель q из m st q> n , вы можете заполнить все частоты в 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
    1
    ответ дан 4 December 2019 в 01:57
    поделиться

    This sounds like roulette wheel selection, mainly used for the selection process in genetic/evolutionary algorithms.

    Look at Roulette Selection in Genetic Algorithms

    6
    ответ дан 4 December 2019 в 01:57
    поделиться

    You could create the target array, then loop through the words determining the probability that it should be picked, and replace the words in the array according to a random number.

    For the first word the probability would be f0/m0 (where mn=f0+..+fn), i.e. 100%, so all positions in the target array would be filled with w0.

    For the following words the probability falls, and when you reach the last word the target array is filled with randomly picked words accoding to the frequency.

    Example code in 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;
        }
    }
}
    2
    ответ дан 4 December 2019 в 01:57
    поделиться