algorithme efficace pour sélectionner de façon aléatoire les articles avec la fréquence

Question

Etant donné un ensemble de paires mot-n fréquence:

[ (w0, f0), (w1, f1), ..., (wn-1, fn-1) ]

où wi est un mot, fi est un frequencey entier, et la somme des fréquences ∑fi = m,

Je veux utiliser un générateur de nombres pseudo-aléatoires (PRNG) pour sélectionner les mots p tels que wj0, wj1, ..., wjp-1 la probabilité de sélectionner l'un quelconque mot est proportionnelle à sa fréquence:

P(wi = wjk) = P(i = jk) = fi / m

(Remarque, c'est la sélection avec le remplacement, donc le même mot peut choisir à chaque fois).

Je suis venu avec trois algorithmes à ce jour:

1. Créer un tableau de taille m, et le remplir de sorte que les premières entrées sont f0 w0, les entrées suivantes sont f1 w1, et ainsi de suite, de sorte que le dernier <= > entrées sont fp-1.

   [ w0, ..., w0, w1,..., w1, ..., wp-1, ..., wp-1 ]

   Utilisez ensuite le PRNG pour sélectionner les indices dans la wp-1 gamme 0...m-1, et signaler les mots stockés à ces indices.
   Cela prend travail O(n + m + p), ce qui est grand, car peut être beaucoup mi beaucoup plus grande que n.

2. Etape par l'intermédiaire du réseau d'entrée une fois, calcul

   mi = ∑h≤ifh = mi-1 + fi

   et après le calcul xk, utiliser le PRNG pour générer un nombre dans la gamme 0...mi-1 k pour chaque 0...p-1 dans wjk et sélectionner xk < fi pour O(n + np) (éventuellement le remplacement de la valeur actuelle de i) si mi-fi ≤ xk < mi.
   Cela nécessite le travail O(n + p log n).

3. Compute <=> comme dans l'algorithme 2, et générer le tableau suivant sur n-mot-fréquence-somme partielle triple:

   [ (w0, f0, m0), (w1, f1, m1), ..., (wn-1, fn-1, mn-1) ]

   puis, pour chaque k dans <=>, utilisez le PRNG pour générer un nombre dans la gamme <=> puis faire la recherche <=> binaire sur le tableau de triplets pour trouver le S.T. <=> <=> et sélectionnez pour <=> <=>.
   Cela nécessite le travail <=>.

Ma question est : Y at-il un algorithme plus efficace que je peux utiliser pour cela, ou sont ceux-ci aussi bon qu'il obtient

Answer 1

Ok, j'ai trouvé un autre algorithme: la méthode alias ( dans cette réponse ). Fondamentalement, il crée une partition de l'espace de probabilité telle que:

• Il y a des partitions n, toutes de la même largeur S.T. r nr = m.
• chaque partition contient deux mots dans un certain rapport (qui est stocké avec la partition).
• pour chaque mot wi, fi = ∑partitions t s.t wi ∈ t r × ratio(t,wi)

Étant donné que toutes les partitions sont de la même taille, la sélection la partition peut être fait dans le travail constant (choisir un indice de 0...n-1 au hasard), et le ratio de la partition peut alors être utilisé pour sélectionner quel mot est utilisé dans constante travailler (comparer un nombre pRNGed avec le rapport entre les deux mots). Donc, cela signifie que les sélections peuvent être p faire dans le travail O(p), étant donné une telle partition.

La raison existe qu'une telle séparation est qu'il existe un mot S.T. fi < r wi', si et seulement s'il existe un mot S.T. fi' > r w'i, puisque r est la moyenne des fréquences.

Avec une telle paire et f'i = r nous pouvons les fi/r remplacer par un pseudo-mot de la fréquence 1 - fi/r w'i' (qui représente avec une probabilité f'i' = fi' - (r - fi) et O(n) avec une probabilité q > n <= >) et un nouveau mot de fréquence ajustée q respectivement m. La fréquence moyenne de tous les mots sera toujours r, et la règle du paragraphe précédent s'applique encore. Étant donné que le pseudo-mot a une fréquence r et est composé de deux mots avec de la fréquence r, nous savons que si nous parcourons ce processus, nous ne ferons jamais un pseudo-mot d'un pseudo-mot, et cette itération doit se terminer par un séquence de n pseudo-mots qui sont la partition souhaitée.

Pour construire cette partition en temps f'i = nfi,

• passer par la liste des mots une fois, la construction de deux listes:
  • un des mots de fréquence ≤ r
  • l'un des mots avec une fréquence> r
• puis tirer un mot de la première liste
  • si sa fréquence = r, puis en faire une seule partition de l'élément
  • sinon, tirer un mot de l'autre liste, et l'utiliser pour remplir une partition en deux mots. Ensuite, placez le deuxième mot nouveau dans la première ou la deuxième liste en fonction de sa fréquence ajustée.

Cette réalité fonctionne toujours si le nombre de partitions m' = mn (il vous suffit de le prouver différemment). Si vous voulez vous assurer que r est partie intégrante, et vous ne pouvez pas trouver facilement un facteur de r' = m S.T. q = n O(n + p), vous pouvez pad toutes les fréquences d'un facteur de <=>, donc <=>, qui met à jour et ensembles <=> lorsque <=> <=>.

Dans tous les cas, cet algorithme ne prend le travail <=>, que je dois penser est optimal.

En ruby:

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

Answer 2

Cela ressemble à la sélection de roue de roulette, principalement utilisé pour le processus de sélection dans les algorithmes génétiques / évolutifs.

Regardez sélection Roulette algorithmes génétiques

Answer 3

On peut créer la matrice cible, puis une boucle sur les mots qui déterminent la probabilité qu'il doit être choisi, et remplacer les mots dans le réseau en fonction d'un nombre aléatoire.

Pour le premier mot de la probabilité serait f ₀ / m ₀ (où m _n = f ₀ + .. + f _n ), soit 100%, de sorte que toutes les positions dans le réseau cible sera rempli avec w ₀ .

Pour les mots la probabilité tombe, et lorsque vous atteignez le dernier mot du tableau cible est rempli avec des mots choisis au hasard accoding à la fréquence.

Exemple de code en 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;
        }
    }
}