Pondérée sélection aléatoire à partir de la matrice de

Je voudrais choisir au hasard un élément d'un tableau, mais chaque élément a une probabilité connue de sélection.

Toutes les chances de concert (dans la matrice) des sommes à 1.

Quel algorithme de proposeriez-vous comme le plus rapide et le plus approprié pour de grands calculs?

Exemple:

id => chance
array[
    0 => 0.8
    1 => 0.2
]

pour cette pseudo-code, l'algorithme de la question sur les appels multiples statistiquement retour quatre éléments sur l'id 0 pour un élément id 1.

OriginalL'auteur Mikulas Dite | 2010-12-16

67

Calculer la nature distincte de la fonction de densité cumulative (CDF) de votre liste (ou, en termes simples, le tableau des sommes cumulées du poids. Ensuite, générer un nombre aléatoire dans la plage comprise entre 0 et la somme de tous les poids (peut-être 1 dans votre cas), faire une recherche binaire pour trouver ce nombre aléatoire dans votre discrets CDF tableau et obtenir la valeur correspondant à cette entrée -- c'est votre pondérée du nombre aléatoire.

Le tableau original a environ 500 éléments, et les chances peuvent différer très légèrement, faisant de la nouvelle pesé tableau vraiment énorme (je suppose qu'il pourrait atteindre rapidement plus de 10e5 éléments). Serait-ce l'effet de la performance? De nouveau, je dois utiliser cette fonction vraiment souvent.
Dite: Ce binaire de recherche log2(500) = 9 étapes par recherche.
J'ai d'abord pensé que vous parlez de la création de la nouvelle matrice @thejh suggéré. Cependant, je comprends maintenant. Merci pour la meilleure solution! : )
Vous êtes à la recherche pour l'intervalle contenant le nombre aléatoire généré -- dans ce cas, l'intervalle de 0,3 à 0,7. Bien sûr, vous ne pouvez pas attendre de la valeur exacte de son apparition, mais une recherche binaire pour trouver l'intervalle de travail de toute façon.
Binaire de recherche peut facilement être utilisé pour trouver l'intervalle de la valeur que vous recherchez se trouve, et c'est tout ce dont vous avez besoin. La plupart des binaires de recherche mises en œuvre dans les bibliothèques standard des langages de programmation ne nécessitent pas la valeur exacte pour être trouvé, par exemple, lower_bound() en C++ ou bisect_left() en Python.

OriginalL'auteur Sven Marnach
13

L'algorithme est simple
```
rand_no = rand(0,1)
for each element in array 
     if(rand_num < element.probablity)
          select and break
     rand_num = rand_num - element.probability
```
Ce ne serait pas de travail, parce que j'ai des chances, non pas la zone. | Même si quelqu'un downvoted cette réponse, il m'a donné une idée viable. Les limites sont tout simplement calculée et ne devrait pas l'effet de performance.
Pourquoi en Bas de vote s'il vous plaît ?
en supposant que vous avez discrète chances et de nombres aléatoires distribués également entre 0 et 1, il va donner une probabilité égale à leur poids. Pour votre cas il y a 80% de chances de nombre aléatoire serait moins .8 donc le premier élément sera sélectionné et 20% de chance de son supérieur à 8. dans ce cas, le deuxième élément est sélectionné.
Non, il n'y a pas de tri, et fonctionne plus rapidement le binaire de recherche si vous souhaitez supprimer l'élément une fois qu'il est sélectionné.
Désolé pour la question, et si j'ai eu à deux éléments avec le même poids? Dans ce cas, je voudrais obtenir seul le premier des deux éléments dans le tableau ou je me trompe?

OriginalL'auteur
8

J'ai trouvé cet article être le plus utile à la compréhension de cette problématique.
Cette question stackoverflow peut aussi être ce que vous cherchez.

Je crois que la meilleure solution est d'utiliser le Alias Méthode (wikipedia).
Il nécessite O(n) temps pour initialiser, O(1) le temps de faire une sélection, et O(n) mémoire.

Voici l'algorithme pour générer le résultat de rouler une pondéré n-verso mourir (à partir d'ici, il est trivial pour sélectionner un élément à partir d'une longueur-n tableau) que de prendre de cet article.
L'auteur suppose que vous disposez des fonctions pour rouler juste mourir (floor(random() * n)) et retournement de la partialité de la monnaie (random() < p).
Algorithme: Vose Alias de la Méthode

Initialisation:
1. Créer des tableaux Alias et Prob, chacun de la taille n.
2. La création de deux réserves de travail, Petit et Grand.
3. Multiplier chaque probabilité par n.
4. Pour chaque échelle de probabilité p_i:
  
  Si p_i < 1, ajouter je à Petit.
  
  Autrement (p_i ≥ 1), ajouter je à Grand.
5. Tout Petit et Grand ne sont pas vides: (Grand peut être vidé en premier)
  
  Supprimer le premier élément de Petit; appeler l.
  
  Supprimer le premier élément de Grand; appeler g.
  
  Ensemble Prob[l]=p_l.
  
  Ensemble Alias[l]=g.
  
  Ensemble p_g := (p_g+p_l)-1. (Ce qui est un numériquement plus stable).
  
  Si p_g<1, ajouter g à Petit.
  
  Autrement (p_g ≥ 1), ajouter g à Grand.
6. Tout Grand n'est pas vide:
  
  Supprimer le premier élément de Grand; appeler g.
  
  Ensemble Prob[g] = 1.
7. Tout Petit n'est pas vide: Il est seulement possible en raison de l'instabilité numérique.
  
  Supprimer le premier élément de Petit; appeler l.
  
  Ensemble Prob[l] = 1.
Génération:
1. Générer une juste lancer de dé à partir d'un n-verso mourir; appelez le côté je.
2. Flip un biaisée pièce, qui est pile avec une probabilité Prob[i].
3. Si la pièce est "les chefs," retour je.
4. Sinon, retour Alias[i].
OriginalL'auteur Simon Baumgardt-Wellander

Un exemple en ruby

#each element is associated with its probability
a = {1 => 0.25 ,2 => 0.5 ,3 => 0.2, 4 => 0.05}

#at some point, convert to ccumulative probability
acc = 0
a.each { |e,w| a[e] = acc+=w }

#to select an element, pick a random between 0 and 1 and find the first   
#cummulative probability that's greater than the random number
r = rand
selected = a.find{ |e,w| w>r }

p selected[0]

Dans cet algorithme, le dernier élément ne sera jamais sélectionné comme c'est la probabilité est 1.0, et rand sera toujours entre 0 et 1.

OriginalL'auteur krusty.ar

6

Cela peut être fait en O(1) le délai prévu par exemple comme suit.

Calculer la CDF F(i) pour chaque élément i est la somme des probabilités est inférieure ou égale à i.

Définir la gamme r(i) d'un élément i de l'intervalle [F(i - 1), F(i)].

Pour chaque intervalle [(i - 1)/n, i/n], créez un compartiment constitué de la liste des éléments dont l'aire de répartition chevauche l'intervalle. Cela prend un temps O(n) fois au total pour le tableau complet aussi longtemps que vous êtes assez prudent.

Lorsque vous au hasard de l'échantillon le tableau, il vous suffit de calculer quel contenant le nombre aléatoire, et de les comparer avec chaque élément de la liste jusqu'à trouver l'intervalle qui le contient.

Le coût d'un échantillon est O(la durée prévue d'une choisie au hasard de la liste) <= 2.

Cet algorithme a un pire des cas, la complexité de O(n) si les poids sont très différentes grandeurs. Il peut arriver que tous les intervalles appartiennent à la même seau. Sans autres restrictions sur le poids, ce n'est certainement pas O(1) et même pas de O(log n).
Le pire des cas ne se produit que rarement. Si tous les n intervalles se chevauchent l'un seau, puis près de toutes les requêtes nécessiterait une comparaison à un seul intervalle. Dans la pratique, ce sera nettement plus rapide que la recherche binaire. Si vous insistez sur l'optimisation pour le pire des cas, vous pourriez faire une recherche binaire à l'intérieur de chaque compartiment, rendant le coût de chaque requête coût O(lg(la longueur de la plus grande seau)) dans le pire des cas, et O(l'attente de lg(la longueur d'un choisis au hasard de la liste)) dans l'attente, ce qui est encore O(1).
Merci, il a l'air vraiment bien. Je vais lancer quelques essais afin de déterminer si elle est vraiment la méthode la plus rapide que CDF-chemin dans ma solution.
Dite, Il est important de souligner que c'est un CDF-solution de matrice, et la différence avec de la pure binaire de recherche est un peu comme la différence entre faire de la recherche binaire et le hachage pour rechercher un élément dans un tableau. Une autre façon de voir les choses, c'est que vous calculez le CDF tableau, et plutôt que de faire une recherche binaire sur elle, vous le hachage, le nombre aléatoire à l'index du tableau correspondant au début du seau. Ensuite, vous pouvez utiliser quelle que soit la stratégie de recherche que vous souhaitez (par exemple, la force brute de recherche linéaire, ou binaire de recherche) afin d'affiner davantage à la bonne échantillonnés élément.
Notez que vous avez de meilleures garanties que dans votre habitude de "pire cas" de l'évaluation, parce que votre accès sont connu au hasard, par la construction...

OriginalL'auteur jonderry

Un autre Rubis exemple:

def weighted_rand(weights = {})
  raise 'Probabilities must sum up to 1' unless weights.values.inject(&:+) == 1.0
  raise 'Probabilities must not be negative' unless weights.values.all? { |p| p >= 0 }
  # Do more sanity checks depending on the amount of trust in the software component using this method
  # E.g. don't allow duplicates, don't allow non-numeric values, etc.

  # Ignore elements with probability 0
  weights = weights.reject { |k, v| v == 0.0 }   # e.g. => {"a"=>0.4, "b"=>0.4, "c"=>0.2}

  # Accumulate probabilities and map them to a value
  u = 0.0
  ranges = weights.map { |v, p| [u += p, v] }   # e.g. => [[0.4, "a"], [0.8, "b"], [1.0, "c"]]

  # Generate a (pseudo-)random floating point number between 0.0(included) and 1.0(excluded)
  u = rand   # e.g. => 0.4651073966724186

  # Find the first value that has an accumulated probability greater than the random number u
  ranges.find { |p, v| p > u }.last   # e.g. => "b"
end

Comment utiliser:

weights = {'a' => 0.4, 'b' => 0.4, 'c' => 0.2, 'd' => 0.0}

weighted_rand weights

À quoi s'attendre:

d = 1000.times.map{ weighted_rand weights }
d.count('a') # 396
d.count('b') # 406
d.count('c') # 198

Juste utilisé ce et a réalisé un reconnu le nom! Merci @wolfgang-teuber!
L'inconvénient avec cette méthode, c'est que si vous avez une pondération de 1,0 et le reste 0,0 cette méthode ne fonctionnera pas comme prévu. Nous avons eu la pondération comme des variables d'environnement et lorsque nous sommes passés de l'un des pondérations à 1.0 (j'.e pour le rendre toujours vrai), il avait l'effet inverse. Juste un FYI pour d'autres là-bas qui utilisent cette méthode!
J'ai mis à jour le weighted_rand méthode pour résoudre le problème que vous avez décrit.
Excellent travail! Merci pour la mise à jour.

OriginalL'auteur knugie

Ruby solution à l'aide de la ramassage gem:

require 'pickup'

chances = {0=>80, 1=>20}
picker = Pickup.new(chances)

Exemple:

5.times.collect {
  picker.pick(5)
}

a donné de sortie:

[[0, 0, 0, 0, 0], 
 [0, 0, 0, 0, 0], 
 [0, 0, 0, 1, 1], 
 [0, 0, 0, 0, 0], 
 [0, 0, 0, 0, 1]]

OriginalL'auteur devstopfix

2

Si le tableau est petit, je voulais donner la matrice de longueur, dans ce cas, cinq et attribuer les valeurs appropriées:
```
array[
    0 => 0
    1 => 0
    2 => 0
    3 => 0
    4 => 1
]
```
C'est la solution la plus évidente, mais je ne peux pas vraiment l'utiliser pour la quantité de données que j'aimerais processus.

OriginalL'auteur thejh

C'est un bout de code PHP que j'ai utilisé dans la production:

/**
 * @return \App\Models\CdnServer
*/
protected function selectWeightedServer(Collection $servers)
{
    if ($servers->count() == 1) {
        return $servers->first();
    }

    $totalWeight = 0;

    foreach ($servers as $server) {
        $totalWeight += $server->getWeight();
    }

    //Select a random server using weighted choice
    $randWeight = mt_rand(1, $totalWeight);
    $accWeight = 0;

    foreach ($servers as $server) {
        $accWeight += $server->getWeight();

        if ($accWeight >= $randWeight) {
            return $server;
        }
    }
}

OriginalL'auteur Gustav.Calder

le truc pourrait être à l'échantillon un auxiliaire de tableau avec des éléments des répétitions qui tiennent compte de la probabilité

Donné les éléments associés à leur probabilité, en pourcentage:

h = {1 => 0.5, 2 => 0.3, 3 => 0.05, 4 => 0.05 }

auxiliary_array = h.inject([]){|memo,(k,v)| memo += Array.new((100*v).to_i,k) }   

ruby-1.9.3-p194 > auxiliary_array 
 => [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,                                 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 3, 3, 3, 3, 3, 4, 4, 4, 4, 4] 

auxiliary_array.sample

si vous voulez être aussi générique que possible, vous devez calculer le multiplicateur basé sur le nombre maximum de chiffres fractionnaires, et l'utiliser à la place de 100:

m = 10**h.values.collect{|e| e.to_s.split(".").last.size }.max

OriginalL'auteur masciugo

0

J'imagine que le nombre supérieure ou égale à 0,8, mais de moins de 1,0 sélectionne le troisième élément.

En d'autres termes:

x est un nombre aléatoire entre 0 et 1

si 0.0 >= x < 0.2 : Article 1

si 0,2 >= x < 0.8 : Article 2

si 0.8 >= x < 1.0 : Point 3

OriginalL'auteur user3339458
0

Je vais améliorer https://stackoverflow.com/users/626341/masciugo réponse.

Fondamentalement, vous faire un grand tableau où le nombre de fois qu'un élément s'affiche est proportionnelle au poids.

Il a aussi quelques inconvénients.
1. Le poids peut ne pas être entier. Imaginez élément 1 a une probabilité de pi et de l'élément 2 a une probabilité de 1-pi. Comment répartissez-vous que? Ou imaginez si il y a des centaines de ces éléments.
2. Le tableau créé peut être très grande. Imaginez si moins commun multiplicateur est de 1 million de dollars, alors nous avons besoin d'un tableau de 1 million d'élément dans le tableau, nous voulons choisir.
Pour contrer cela, c'est ce que vous faites.

Créer un tel tableau, mais seulement insérer un élément au hasard. La probabilité qu'un élément est inséré est proportionnelle à la le poids.

Puis sélectionnez l'élément aléatoire de d'habitude.

Donc si il y a 3 éléments avec différents poids, il vous suffit de choisir un élément d'un tableau de 1 à 3 éléments.

Des problèmes peuvent survenir si l'élément construit est vide. Qu'est-il arrive juste qu'aucun présentent des éléments de la matrice car leur jet de dés différemment.

Dans ce cas, je propose que la probabilité qu'un élément est inséré est p(inséré)=wi/wmax.

De cette façon, un seul élément, à savoir celui qui a la plus grande probabilité, va être inséré. Les autres éléments seront insérés par la probabilité relative.

Dire que nous avons 2 objets.

élément 1 montre .20% du temps.
élément 2 montre .40% du temps et a la plus grande probabilité.

Dans thearray, l'élément 2 va se montrer tout le temps. Élément 1 montrera la moitié du temps.

Donc l'élément 2 sera appelé 2 fois plus nombreux que l'élément 1. Pour la généralité de tous les autres éléments seront appelés proportionnelle à leur poids. Aussi la somme de leur probabilité de 1, parce que le tableau aura toujours au moins 1 élément.

Mon calcul est éteint. Ressemble à des éléments avec un nombre plus élevé ont plus de probabilité réelle avec cette technique. Je dirais le plus de vote réponse maintenant.

OriginalL'auteur user4951

Vous devez vous connecter pour publier un commentaire.

Algorithme: Vose Alias de la Méthode

Initialisation:

Génération: