Sélection aléatoire pondérée avec et sans remplacement

voici ce que j'ai trouvé pour la sélection pondérée sans remplacement:

def WeightedSelectionWithoutReplacement(l, n):
  """Selects without replacement n random elements from a list of (weight, item) tuples."""
  l = sorted((random.random() * x[0], x[1]) for x in l)
  return l[-n:]

Ceci est O (log m) sur le nombre d'éléments dans la liste à sélectionner. Je suis assez certain que cela va pondérer les articles correctement, bien que je ne l'ai pas vérifié dans un sens formel.

Voici ce que j'ai trouvé pour pondérée sélection de remplacement:

def WeightedSelectionWithReplacement(l, n):
  """Selects with replacement n random elements from a list of (weight, item) tuples."""
  cuml = []
  total_weight = 0.0
  for weight, item in l:
    total_weight += weight
    cuml.append((total_weight, item))
  return [cuml[bisect.bisect(cuml, random.random()*total_weight)] for x in range(n)]

C'est de O(m + n log m), où m est le nombre d'éléments dans la liste d'entrée, et n est le nombre de les éléments sélectionnés.

je vous recommande tout d'abord de consulter la section 3.4.2 de L'ouvrage de Donald Knuth Algorithmes Seminumériques.

si vos tableaux sont grands, il y a des algorithmes plus efficaces dans le chapitre 3 de Principes de l'Aléatoire de la variable aléatoire de la Génération par John Dagpunar. Si vos tableaux ne sont pas très grands ou si vous ne vous souciez pas de tirer le plus d'efficacité possible, les algorithmes plus simples à Knuth sont probablement très bien.

une approche simple qui n'a pas été mentionnée ici est celle proposée dans Efraimidis et Spirakis. En python, vous pouvez sélectionner m éléments à partir de N >= m éléments pondérés avec des poids strictement positifs stockés dans les poids, en retournant les indices sélectionnés, avec:

import heapq
import math
import random

def WeightedSelectionWithoutReplacement(weights, m):
    elt = [(math.log(random.random()) / weights[i], i) for i in range(len(weights))]
    return [x[1] for x in heapq.nlargest(m, elt)]

cette structure est très similaire à la première approche proposée par Nick Johnson. Malheureusement, cette approche est biaisée en sélectionnant les éléments (voir les commentaires sur la méthode). Efraimidis et Spirakis a prouvé que leur approche est équivalente à l'échantillonnage aléatoire sans remplacement dans le document lié.

ce qui suit est une description de la sélection aléatoire pondérée d'un élément d'un set (ou multiset, si les répétitions sont autorisées), à la fois avec et sans remplacement dans L'espace O(n) et O (log n) Temps.

il consiste à implémenter un arbre de recherche binaire, trié par les éléments à être sélectionné, où chaque noeud de l'arbre contient:

1. l'élément lui-même (l'élément)
2. le poids non normalisé de l'élément (elementweight) et
3. la somme de l'onu, les poids normalisés de la gauche-nœud enfant et tous ses enfants ( leftbranchweight).
4. la somme de l'onu, les poids normalisés de la droite du nœud enfant et tous son chilren (rightbranchweight).

puis nous sélectionnons au hasard un élément du BST en descendant dans l'arbre. Un une description sommaire de l'algorithme suit. L'algorithme est donné un noeud de arbre. Ensuite, les valeurs de leftbranchweight,rightbranchweight, et elementweightnoeud est additionnée, et les pondérations sont divisées par somme, résultant dans les valeurs leftbranchprobability, droitprobabilité et elementprobability, respectivement. Puis un nombre aléatoire entre 0 et 1 ( randomnumber) obtenu.

• si le nombre est inférieur à elementprobability,
  • supprimer l'élément de la BST comme normal, updating leftbranchweight et rightbranchweight de tous les noeuds nécessaires, et élément.
• sinon si le nombre est inférieur à (elementprobability+ leftbranchweight)
  • boucle leftchild(lancer le algorithme utilisant leftchildnoeud)
• else
  • boucle rightchild

lorsque nous trouvons finalement, en utilisant ces poids, quel élément doit être retourné, nous le retournons simplement (avec remplacement) ou nous le supprimons et mettons à jour les poids pertinents dans l'arbre (sans remplacement).

DISCLAIMER: l'algorithme est rugueux, et un traité sur le bon application D'un TSB n'est pas tenté ici; on espère plutôt que cette réponse aidera ceux qui vraiment besoin d'une sélection pondérée rapide sans remplacement (comme je le fais).

il est possible de faire une sélection aléatoire pondérée avec remplacement dans le temps O(1), après avoir d'abord créé une structure de données de taille O(N) supplémentaire dans le temps O(N). L'algorithme est basé sur l' Méthode Alias développé par Walker et Vose, qui est bien décrit ici.

l'idée essentielle est que chaque bin dans un histogramme serait choisi avec une probabilité 1 / N par un RNG uniforme. Donc, nous allons marcher à travers elle, et pour toute poubelle sous-peuplée qui serait recevrait des résultats excédentaires, assignerait l'excédent à une cellule surpeuplée. Pour chaque cellule, nous stockons le pourcentage de visites qui lui appartiennent, et le partenaire bin pour l'excédent. Cette version suit les petits et grands bacs en place, éliminant le besoin d'une pile supplémentaire. Il utilise l'index du partenaire (stocké dans bucket[1]) comme un indicateur qu'ils ont déjà été traitées.

Voici une implémentation minimale de python, basée sur la mise en oeuvre de C ici

def prep(weights):
    data_sz = len(weights)
    factor = data_sz/float(sum(weights))
    data = [[w*factor, i] for i,w in enumerate(weights)]
    big=0
    while big<data_sz and data[big][0]<=1.0: big+=1
    for small,bucket in enumerate(data):
        if bucket[1] is not small: continue
        excess = 1.0 - bucket[0]
        while excess > 0:
            if big==data_sz: break
            bucket[1] = big
            bucket = data[big]
            bucket[0] -= excess
            excess = 1.0 - bucket[0]
            if (excess >= 0):
                big+=1
                while big<data_sz and data[big][0]<=1: big+=1
    return data

def sample(data):
    r=random.random()*len(data)
    idx = int(r)
    return data[idx][1] if r-idx > data[idx][0] else idx

Exemple d'utilisation:

TRIALS=1000
weights = [20,1.5,9.8,10,15,10,15.5,10,8,.2];
samples = [0]*len(weights)
data = prep(weights)

for _ in range(int(sum(weights)*TRIALS)):
    samples[sample(data)]+=1

result = [float(s)/TRIALS for s in samples]
err = [a-b for a,b in zip(result,weights)]
print(result)
print([round(e,5) for e in err])
print(sum([e*e for e in err]))

supposons que vous voulez échantillonner 3 éléments sans les remplacer de la liste ['blanc','bleu','noir','jaune',' vert'] par un prob. la distribution [0.1, 0.2, 0.4, 0.1, 0.2]. Utilisation de numpy.module random c'est aussi simple que cela:

    import numpy.random as rnd

    sampling_size = 3
    domain = ['white','blue','black','yellow','green']
    probs = [.1, .2, .4, .1, .2]
    sample = rnd.choice(domain, size=sampling_size, replace=False, p=probs)
    # in short: rnd.choice(domain, sampling_size, False, probs)
    print(sample)
    # Possible output: ['white' 'black' 'blue']

replace drapeau True, vous avez un échantillonnage avec remplacement.

Plus d'info ici: http://docs.scipy.org/doc/numpy/reference/generated/numpy.random.choice.html#numpy.random.choice