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:
-
Créer un tableau de taille
m
, et le remplir de sorte que les premières entrées sontf0
w0
, les entrées suivantes sontf1
w1
, et ainsi de suite, de sorte que le dernier <= > entrées sontfp-1
.[ w0, ..., w0, w1,..., w1, ..., wp-1, ..., wp-1 ]
Utilisez ensuite le PRNG pour sélectionner les indices dans lawp-1
gamme0...m-1
, et signaler les mots stockés à ces indices.
Cela prend travailO(n + m + p)
, ce qui est grand, car peut être beaucoupmi
beaucoup plus grande que n. -
Etape par l'intermédiaire du réseau d'entrée une fois, calcul
mi = ∑h≤ifh = mi-1 + fi
et après le calculxk
, utiliser le PRNG pour générer un nombre dans la gamme0...mi-1
k
pour chaque0...p-1
danswjk
et sélectionnerxk < fi
pourO(n + np)
(éventuellement le remplacement de la valeur actuelle dei
) simi-fi ≤ xk < mi
.
Cela nécessite le travailO(n + p log n)
. - 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
La solution 3
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
Autres conseils
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
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 0 / m 0 (où m n = f 0 + .. + f n ), soit 100%, de sorte que toutes les positions dans le réseau cible sera rempli avec w 0 .
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;
}
}
}