Sélectionnez k éléments aléatoires dans une liste dont les éléments ont des poids

La sélection sans poids (probabilités égales) est magnifiquement décrite ici .

Je me demandais s’il existe un moyen de convertir cette approche en une approche pondérée.

Je suis également intéressé par d’autres approches.

Mise à jour: échantillonnage sans remplacement

    Je sais que c’est une très vieille question, mais je pense qu’il y a une astuce pour faire ça en O (n) si vous appliquez un peu de maths!

    La dissortingbution exponentielle a deux propriétés très utiles.

    1. Étant donné n échantillons provenant de différentes dissortingbutions exponentielles avec différents parameters de vitesse, la probabilité qu’un échantillon donné soit le minimum est égale à son paramètre de taux divisé par la sum de tous les parameters de débit.

    2. C’est “sans mémoire”. Donc, si vous connaissez déjà le minimum, alors la probabilité que l’un des éléments restants soit le second est la même que la probabilité que si le min réel était supprimé (et jamais généré), cet élément aurait été le nouveau min. Cela semble évident, mais je pense qu’à cause de certains problèmes de probabilité conditionnels, cela pourrait ne pas être vrai pour d’autres dissortingbutions.

    En utilisant le fait 1, nous soaps que choisir un seul élément peut être fait en générant ces échantillons de dissortingbution exponentiels avec un paramètre de taux égal au poids, puis en choisissant celui avec la valeur minimale.

    En utilisant le fait 2, nous soaps que nous n’avons pas besoin de re-générer les échantillons exponentiels. Au lieu de cela, il suffit d’en générer un pour chaque élément et de prendre les k éléments avec les échantillons les plus bas.

    Trouver le k le plus bas peut être fait dans O (n). Utilisez l’algorithme Quickselect pour trouver le k-ème élément, puis passez simplement un autre passage à travers tous les éléments et affichez tous les éléments inférieurs au k-ème.

    Une note utile: si vous n’avez pas immédiatement access à une bibliothèque pour générer des échantillons de dissortingbution exponentielle, cela peut être facilement fait par: -ln(rand())/weight

    Si l’échantillonnage est avec remplacement, vous pouvez utiliser cet algorithme (implémenté ici en Python):

     import random items = [(10, "low"), (100, "mid"), (890, "large")] def weighted_sample(items, n): total = float(sum(w for w, v in items)) i = 0 w, v = items[0] while n: x = total * (1 - random.random() ** (1.0 / n)) total -= x while x > w: x -= w i += 1 w, v = items[i] w -= x yield v n -= 1 

    C’est O ( n + m ) où m est le nombre d’éléments.

    Pourquoi ça marche? Il est basé sur l’algorithme suivant:

     def n_random_numbers_decreasing(v, n): """Like reversed(sorted(v * random() for i in range(n))), but faster because we avoid sorting.""" while n: v *= random.random() ** (1.0 / n) yield v n -= 1 

    La fonction weighted_sample est juste cet algorithme fusionné avec une promenade de la liste d’ items pour sélectionner les éléments sélectionnés par ces nombres aléatoires.

    Cela fonctionne parce que la probabilité que n nombres aléatoires 0 .. v soient tous inférieurs à z est P = ( z / v ) n . Résoudre pour z , et vous obtenez z = vP 1 / n . Remplacer un nombre aléatoire par P sélectionne le plus grand nombre avec la dissortingbution correcte; et nous pouvons simplement répéter le processus pour sélectionner tous les autres numéros.

    Si l’échantillonnage est sans remplacement, vous pouvez placer tous les éléments dans un segment binary, où chaque nœud met en cache le total des poids de tous les éléments de ce sous-segment. Construire le tas est O ( m ). La sélection d’un élément aléatoire dans le tas, en respectant les poids, est O (log m ). Supprimer cet élément et mettre à jour les totaux mis en cache est également O (log m ). Vous pouvez donc choisir n éléments dans O ( m + n log m ) temps.

    (Note: “poids” signifie ici que chaque fois qu’un élément est sélectionné, les possibilités restantes sont choisies avec une probabilité proportionnelle à leur poids. Cela ne signifie pas que des éléments apparaissent dans la sortie avec une probabilité proportionnelle à leur poids.)

    Voici une mise en œuvre de cela, abondamment commenté:

     import random class Node: # Each node in the heap has a weight, value, and total weight. # The total weight, self.tw, is self.w plus the weight of any children. __slots__ = ['w', 'v', 'tw'] def __init__(self, w, v, tw): self.w, self.v, self.tw = w, v, tw def rws_heap(items): # h is the heap. It's like a binary tree that lives in an array. # It has a Node for each pair in `items`. h[1] is the root. Each # other Node h[i] has a parent at h[i>>1]. Each node has up to 2 # children, h[i<<1] and h[(i<<1)+1]. To get this nice simple # arithmetic, we have to leave h[0] vacant. h = [None] # leave h[0] vacant for w, v in items: h.append(Node(w, v, w)) for i in range(len(h) - 1, 1, -1): # total up the tws h[i>>1].tw += h[i].tw # add h[i]'s total to its parent return h def rws_heap_pop(h): gas = h[1].tw * random.random() # start with a random amount of gas i = 1 # start driving at the root while gas >= h[i].w: # while we have enough gas to get past node i: gas -= h[i].w # drive past node i i <<= 1 # move to first child if gas >= h[i].tw: # if we have enough gas: gas -= h[i].tw # drive past first child and descendants i += 1 # move to second child w = h[i].w # out of gas! h[i] is the selected node. v = h[i].v h[i].w = 0 # make sure this node isn't chosen again while i: # fix up total weights h[i].tw -= w i >>= 1 return v def random_weighted_sample_no_replacement(items, n): heap = rws_heap(items) # just make a heap... for i in range(n): yield rws_heap_pop(heap) # and pop n items off it. 

    Si l’échantillonnage est avec remplacement, utilisez la technique de sélection de la roulette (souvent utilisée dans les algorithmes génétiques):

    1. sortinger les poids
    2. calculer les poids cumulés
    3. choisir un nombre aléatoire dans [0,1]*totalWeight
    4. trouver l’intervalle dans lequel ce nombre tombe dans
    5. sélectionner les éléments avec l’intervalle correspondant
    6. répéter k fois

    texte alt

    Si l’échantillonnage est sans remplacement, vous pouvez adapter la technique ci-dessus en supprimant l’élément sélectionné de la liste après chaque itération, puis en re-normalisant les poids de sorte que leur sum soit égale à 1 (fonction de dissortingbution de probabilité valide).

    Je l’ai fait en Ruby

    https://github.com/fl00r/pickup

     require 'pickup' pond = { "selmon" => 1, "carp" => 4, "crucian" => 3, "herring" => 6, "sturgeon" => 8, "gudgeon" => 10, "minnow" => 20 } pickup = Pickup.new(pond, uniq: true) pickup.pick(3) #=> [ "gudgeon", "herring", "minnow" ] pickup.pick #=> "herring" pickup.pick #=> "gudgeon" pickup.pick #=> "sturgeon" 

    Si vous souhaitez générer de grands tableaux d’entiers aléatoires avec remplacement , vous pouvez utiliser l’interpolation linéaire par morceaux. Par exemple, en utilisant NumPy / SciPy:

     import numpy import scipy.interpolate def weighted_randint(weights, size=None): """Given an n-element vector of weights, randomly sample integers up to n with probabilities proportional to weights""" n = weights.size # normalize so that the weights sum to unity weights = weights / numpy.linalg.norm(weights, 1) # cumulative sum of weights cumulative_weights = weights.cumsum() # piecewise-linear interpolating function whose domain is # the unit interval and whose range is the integers up to n f = scipy.interpolate.interp1d( numpy.hstack((0.0, weights)), numpy.arange(n + 1), kind='linear') return f(numpy.random.random(size=size)).astype(int) 

    Ce n’est pas efficace si vous souhaitez échantillonner sans remplacement.

    Voici une implémentation Go des géodns :

     package foo import ( "log" "math/rand" ) type server struct { Weight int data interface{} } func foo(servers []server) { // servers list is already sorted by the Weight atsortingbute // number of items to pick max := 4 result := make([]server, max) sum := 0 for _, r := range servers { sum += r.Weight } for si := 0; si < max; si++ { n := rand.Intn(sum + 1) s := 0 for i := range servers { s += int(servers[i].Weight) if s >= n { log.Println("Picked record", i, servers[i]) sum -= servers[i].Weight result[si] = servers[i] // remove the server from the list servers = append(servers[:i], servers[i+1:]...) break } } } return result } 

    Si vous voulez sélectionner x éléments d’un ensemble pondéré sans les remplacer, les éléments sont choisis avec une probabilité proportionnelle à leur poids:

     import random def weighted_choose_subset(weighted_set, count): """Return a random sample of count elements from a weighted set. weighted_set should be a sequence of tuples of the form (item, weight), for example: [('a', 1), ('b', 2), ('c', 3)] Each element from weighted_set shows up at most once in the result, and the relative likelihood of two particular elements showing up is equal to the ratio of their weights. This works as follows: 1.) Line up the items along the number line from [0, the sum of all weights) such that each item occupies a segment of length equal to its weight. 2.) Randomly pick a number "start" in the range [0, total weight / count). 3.) Find all the points "start + n/count" (for all integers n such that the point is within our segments) and yield the set containing the items marked by those points. Note that this implementation may not return each possible subset. For example, with the input ([('a': 1), ('b': 1), ('c': 1), ('d': 1)], 2), it may only produce the sets ['a', 'c'] and ['b', 'd'], but it will do so such that the weights are respected. This implementation only works for nonnegative integral weights. The highest weight in the input set must be less than the total weight divided by the count; otherwise it would be impossible to respect the weights while never returning that element more than once per invocation. """ if count == 0: return [] total_weight = 0 max_weight = 0 borders = [] for item, weight in weighted_set: if weight < 0: raise RuntimeError("All weights must be positive integers") # Scale up weights so dividing total_weight / count doesn't truncate: weight *= count total_weight += weight borders.append(total_weight) max_weight = max(max_weight, weight) step = int(total_weight / count) if max_weight > step: raise RuntimeError( "Each weight must be less than total weight / count") next_stop = random.randint(0, step - 1) results = [] current = 0 for i in range(count): while borders[current] <= next_stop: current += 1 results.append(weighted_set[current][0]) next_stop += step return results 

    Dans la question que vous avez liée, la solution de Kyle fonctionnerait avec une généralisation sortingviale. Scannez la liste et additionnez le poids total. Alors la probabilité de choisir un élément devrait être:

    1 – (1 – (# nécessaire / (poids restant))) / (poids en n). Après avoir visité un nœud, soustrayez son poids du total. De plus, si vous avez besoin de n et que vous n’avez plus à gauche, vous devez vous arrêter explicitement.

    Vous pouvez vérifier que avec tout ce qui a un poids 1, cela simplifie la solution de kyle.

    Édité: (repenser ce que deux fois plus probable signifiait)

    Celui-ci fait exactement cela avec O (n) et pas d’utilisation excessive de mémoire. Je pense que c’est une solution intelligente et efficace, facile à transférer dans n’importe quelle langue. Les deux premières lignes servent uniquement à renseigner des données d’exemple dans Drupal.

     function getNrandomGuysWithWeight($numitems){ $q = db_query('SELECT id, weight FROM theTableWithTheData'); $q = $q->fetchAll(); $accum = 0; foreach($q as $r){ $accum += $r->weight; $r->weight = $accum; } $out = array(); while(count($out) < $numitems && count($q)){ $n = rand(0,$accum); $lessaccum = NULL; $prevaccum = 0; $idxrm = 0; foreach($q as $i=>$r){ if(($lessaccum == NULL) && ($n <= $r->weight)){ $out[] = $r->id; $lessaccum = $r->weight- $prevaccum; $accum -= $lessaccum; $idxrm = $i; }else if($lessaccum){ $r->weight -= $lessaccum; } $prevaccum = $r->weight; } unset($q[$idxrm]); } return $out; } 

    Je mets ici une solution simple pour choisir 1 article, vous pouvez facilement l’agrandir pour k éléments (style Java):

     double random = Math.random(); double sum = 0; for (int i = 0; i < items.length; i++) { val = items[i]; sum += val.getValue(); if (sum > random) { selected = val; break; } } 

    J’ai implémenté un algorithme similaire à l’idée de Jason Orendorff dans Rust ici . Ma version supporte en outre les opérations en bloc: insérer et supprimer (lorsque vous souhaitez supprimer un groupe d’éléments fournis par leurs identifiants, et non par le chemin de sélection pondéré) de la structure de données dans O(m + log n) des éléments à supprimer et n le nombre d’éléments stockés.

    Echantillonnage sans remplacement avec récursivité – solution élégante et très courte en c #

    // combien de façons nous pouvons choisir 4 étudiants sur 60, de sorte que chaque fois que nous choisissons différents 4

     class Program { static void Main(ssortingng[] args) { int group = 60; int studentsToChoose = 4; Console.WriteLine(FindNumberOfStudents(studentsToChoose, group)); } private static int FindNumberOfStudents(int studentsToChoose, int group) { if (studentsToChoose == group || studentsToChoose == 0) return 1; return FindNumberOfStudents(studentsToChoose, group - 1) + FindNumberOfStudents(studentsToChoose - 1, group - 1); } } 

    J’ai utilisé une carte associative (poids, object). par exemple:

     { (10,"low"), (100,"mid"), (10000,"large") } total=10110 

    Jetez un coup d’oeil à un nombre aléatoire compris entre 0 et «total» et parcourez les touches jusqu’à ce que ce nombre corresponde à une plage donnée.