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

Question

Récemment, j'ai eu besoin de faire une sélection aléatoire pondérée d'éléments d'une liste, avec et sans remplacement. Alors qu'il existe de bons algorithmes bien connus pour la sélection non pondérée, et certains pour la sélection pondérée sans remplacement (comme des modifications de l'algorithme resevoir), je n'ai pas trouvé de bons algorithmes pour la sélection pondérée avec remplacement. Je voulais également éviter la méthode du resevoir, car je sélectionnais une fraction significative de la liste, qui est assez petite pour être conservée en mémoire.

Quelqu'un a-t-il des suggestions sur la meilleure approche à adopter dans cette situation ? J'ai mes propres solutions, mais j'espère trouver quelque chose de plus efficace, de plus simple, ou les deux.

Answer 1

L'un des moyens les plus rapides de créer de nombreux échantillons avec remplacement à partir d'une liste immuable est la méthode des alias. L'intuition de base est que nous pouvons créer un ensemble de cases de taille égale pour la liste pondérée qui peut être indexée très efficacement par des opérations sur les bits, afin d'éviter une recherche binaire. Il s'avérera que, si l'on procède correctement, nous n'aurons besoin de stocker que deux éléments de la liste originale par bac, et nous pourrons donc représenter la division avec un seul pourcentage.

Prenons l'exemple de cinq choix à pondération égale, (a:1, b:1, c:1, d:1, e:1)

Pour créer la recherche d'alias :

1. Normaliser les poids de sorte que leur somme soit égale à 1.0 . (a:0.2 b:0.2 c:0.2 d:0.2 e:0.2) C'est la probabilité de choisir chaque poids.

2. Trouvez la plus petite puissance de 2 supérieure ou égale au nombre de variables, et créez ce nombre de partitions, |p| . Chaque partition représente une masse de probabilité de 1/|p| . Dans ce cas, nous créons 8 partitions, chacune pouvant contenir 0.125 .

3. Prenez la variable ayant le moins de poids restant, et placez autant de sa masse que possible dans une partition vide. Dans cet exemple, nous voyons que a remplit la première partition. (p1{a|null,1.0},p2,p3,p4,p5,p6,p7,p8) con (a:0.075, b:0.2 c:0.2 d:0.2 e:0.2)

4. Si la partition n'est pas remplie, prenez la variable ayant le plus de poids, et remplissez la partition avec cette variable.

Répétez les étapes 3 et 4, jusqu'à ce qu'aucun des poids de la partition d'origine n'ait besoin d'être affecté à la liste.

Par exemple, si nous exécutons une autre itération de 3 et 4, nous voyons

(p1{a|null,1.0},p2{a|b,0.6},p3,p4,p5,p6,p7,p8) con (a:0, b:0.15 c:0.2 d:0.2 e:0.2) restant à attribuer

En cours d'exécution :

1. Obtenir un U(0,1) un nombre aléatoire, disons binaire 0.001100000

2. le bithift lg2(p) en trouvant la partition de l'indice. Ainsi, nous le décalons de 3 ce qui donne 001.1 ou la position 1, et donc la partition 2.

3. Si la partition est divisée, utilisez la partie décimale du nombre aléatoire décalé pour décider de la division. Dans ce cas, la valeur est 0.5 y 0.5 < 0.6 donc retour a .

Voici un peu de code et une autre explication mais malheureusement, il n'utilise pas la technique du bithifting, et je ne l'ai pas vérifié.

Answer 2

Une approche simple qui n'a pas été mentionnée ici est celle proposée dans Efraimidis et Spirakis . En python, vous pourriez sélectionner m éléments parmi n >= m éléments pondérés avec des poids strictement positifs stockés dans weights, 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 dans la sélection des éléments (voir les commentaires sur la méthode). Efraimidis et Spirakis ont prouvé que leur approche est équivalente à l'échantillonnage aléatoire sans remplacement dans l'article lié.

Answer 3

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:]

C'est O(m log m) sur le nombre d'éléments de la liste à sélectionner. Je suis presque certain que cela pondère correctement les éléments, bien que je ne l'aie pas vérifié de manière formelle.

Voici ce que j'ai trouvé pour la sélection pondérée avec 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 O(m + n log m), où m est le nombre d'éléments dans la liste d'entrée, et n est le nombre d'éléments à sélectionner.

Answer 4

Je vous recommande de commencer par consulter la section 3.4.2 de l'ouvrage de Donald Knuth intitulé Algorithmes semi-numériques .

Si vos tableaux sont de grande taille, il existe des algorithmes plus efficaces dans le chapitre 3 de l'ouvrage intitulé Principes de la génération de variables aléatoires par John Dagpunar. Si vos tableaux ne sont pas très grands ou si vous ne vous souciez pas d'obtenir le plus d'efficacité possible, les algorithmes plus simples de Knuth sont probablement parfaits.

Answer 5

Ce qui suit est une description de la sélection aléatoire et pondérée d'un élément d'un ensemble (ou d'un multiset si les répétitions sont autorisées), avec et w. ensemble (ou multi-ensemble, si les répétitions sont autorisées), avec et sans remplacement, en espace O(n) et en temps O(log n). et en O(log n) temps.

Elle consiste à mettre en œuvre un arbre de recherche binaire, trié par les éléments à sélectionnés, où chaque nœud de l'arbre contient :

1. l'élément lui-même ( élément )
2. le poids non normalisé de l'élément ( poids des éléments ), et
3. la somme de tous les poids non normalisés du nœud enfant de gauche et de tous ses enfants (" le nœud enfant "). ses enfants ( poids de la branche gauche ).
4. la somme de tous les poids non normalisés du nœud fils droit et de tous les nœuds fils. ses enfants ( poids de la branche droite ).

Ensuite, nous sélectionnons aléatoirement un élément de la BST en descendant dans l'arbre. A description approximative de l'algorithme suit. On donne à l'algorithme un nœud de l'arbre. Ensuite, les valeurs de poids de la branche gauche , poids de la branche droite , et poids des éléments de nœud est additionné, et les poids sont divisés par cette somme. somme, ce qui donne les valeurs probabilité de la branche gauche , probabilité de la branche droite y élémentprobabilité respectivement. Puis un nombre aléatoire compris entre 0 et 1 ( nombre aléatoire ) est obtenu.

• si le nombre est inférieur à élémentprobabilité ,
  • retirer l'élément de la BST comme d'habitude, en mettant à jour les données de la BST. poids de la branche gauche et poids de la branche droite de tous les noeuds nécessaires, et retourne l'élément élément.
• sinon, si le nombre est inférieur à ( élémentprobabilité + poids de la branche gauche )
  • Récupérer sur enfant de gauche (exécuter l'algorithme en utilisant enfant de gauche como nœud )
• sinon
  • Récupérer sur enfant de droite

Lorsque nous trouvons finalement, à l'aide de ces poids, quel élément doit être renvoyé, soit nous le renvoyons simplement (avec remplacement), soit nous le supprimons et mettons à jour les poids pertinents dans l'arbre (sans remplacement).

AVIS DE NON-RESPONSABILITÉ : L'algorithme est approximatif, et un traité sur l'implémentation appropriée d'une BST n'est pas tenté ici ; nous espérons plutôt que cette réponse aidera ceux qui realmente ont besoin d'une sélection rapide pondérée sans remplacement (comme moi).